A 狭窄的通道
题意: 51nod 1331
题解: 贪心
一种显然的想法是分成左中右三部分, 左边退到左边再进去, 右边同理, 中间直接移, 枚举左边和中间分界点
于是你获得了 1/25 的好成绩
- 1
- 5 11
- 5 3
- 3 4
- 1 10
- 7 9
- 9 1
这组数据答案是 48, 做法是先把前三个移到 0, 后两个移到 L, 再把 1 移到 L,5 移到 0, 最后左右分别移
所以还要一种贪心, 枚举断点, 左边全移 0, 右边全移 L, 分别按终点排序
然后设 \(l,r\) 为断点左边, 右边的第一个
枚举直到发生冲突 (左边的某一个的终点大于右边的)
然后有两种方法
左边的剩余的全部移到 L
右边的从上次移到这次移的全部移到 0
第一种一次性把所有冲突解决了, 直接更新
第二种不一定解决了所有冲突, 需要等最后再更新
复杂度:\(O(n^2\log n)\)(应该吧)
- #include<bits/stdc++.h>
- using namespace std;
- inline void read(int& x)
- {
- x = 0; char c = getchar();
- while (!isdigit(c)) c = getchar();
- while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
- }
- #define maxn 105
- #define ll long long
- ll ans, sum;
- int n, L;
- struct Wolf
- {
- int s, t;
- }w[maxn];
- inline bool cmp(Wolf& x, Wolf& y) { return x.s <y.s; }
- inline bool cmp2(Wolf& x, Wolf& y) { return x.t < y.t; }
- inline bool check(int l1, int r1, int l2, int r2)
- {
- int mx = 0, mn = 1e9;
- for (int i = l1; i <= r1; ++i) mx = max(mx, w[i].t);
- for (int i = l2; i <= r2; ++i) mn = min(mn, w[i].t);
- return mx < mn;
- }
- void solve1()
- {
- for (int i = 0; i <= n; ++i)
- {
- if (!check(0, i, i + 1, n)) continue;
- int cut = n + 1; sum = 0;
- for (int j = 0; j <= i; ++j) sum += w[j].s + w[j].t;
- for (int j = i + 1; j <= n; ++j)
- {
- if (!check(i + 1, j, j + 1, n))
- {
- cut = j;
- break;
- }
- sum += abs(w[j].s - w[j].t);
- }
- for (int j = cut; j <= n; ++j) sum += 2 * L - w[j].s - w[j].t;
- ans = min(ans, sum);
- }
- }
- void calc(int cut)
- {
- sort(w + 1, w + cut + 1, cmp2);
- sort(w + cut + 1, w + n + 1, cmp2);
- int l = 1, r = cut + 1, rlast = cut + 1;
- ll sum1 = 0, sum2 = 0;
- while (l <= cut && r <= n)
- {
- sum2 = 0;
- while (l <= cut && w[l].t < w[r].t) ++l;
- if (l == cut + 1) break;
- while (r <= n && w[r].t < w[l].t) ++r;
- for (int i = l; i <= cut; ++i) sum2 += 2 * (L - w[i].t);// 左边移 L
- ans = min(ans, sum + sum1 + sum2);
- for (int i = rlast; i < r; ++i) sum1 += 2 * w[i].t;// 右边移 0
- if (w[r].t> w[cut].t) break;
- rlast = r, ++l;
- }
- ans = min(ans, sum + sum1);
- }
- void solve2()
- {
- for (int i = 1; i <n; ++i)
- {
- sort(w + 1, w + n + 1, cmp);
- sum = 0;
- for (int j = 1; j <= i; ++j) sum += w[j].s + w[j].t;
- for (int j = i + 1; j <= n; ++j) sum += 2 * L - w[j].s - w[j].t;
- if (sum>= ans || check(1, i, i + 1, n)) continue;
- calc(i);
- }
- }
- int main()
- {
- int T; read(T);
- while (T--)
- {
- read(n), read(L), ans = 1e18, sum = 0;
- for (int i = 1; i <= n; ++i) read(w[i].s), read(w[i].t);
- w[n + 1].s = w[n + 1].t = L;
- sort(w + 1, w + n + 1, cmp);
- solve1(); solve2();
- printf("%lld\n", ans);
- }
- return 0;
- }
B 破坏道路
题意: 51nod 1444
题解: 最短路
预处理任意两点间的最短路
题意可以转化为至少需要多少条路才能达到要求
于是可以合并道路, 具体看代码
注意这道题由于边数很少, dijskra 会 T 掉
复杂度:\(O(n^2+n*spfa)\)
- #include<bits/stdc++.h>
- using namespace std;
- inline void read(int& x)
- {
- x = 0; char c = getchar();
- while (!isdigit(c)) c = getchar();
- while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
- }
- #define maxn 3005
- #define mp make_pair
- #define pa pair<int,int>
- struct Edge
- {
- int fr, to, val;
- }eg[maxn <<1];
- int head[maxn], edgenum, n, m, dis[maxn][maxn], vis[maxn];
- int s1, t1, l1, s2, t2, l2;
- inline void add(int fr, int to)
- {
- eg[++edgenum] = { head[fr],to,1 };
- head[fr] = edgenum;
- }
- queue<int> q;
- inline void spfa(int S)
- {
- q.push(S);
- dis[S][S] = 0;
- while (!q.empty())
- {
- int tp = q.front();
- q.pop();
- vis[tp] = 0;
- for (int i = head[tp]; i; i = eg[i].fr)
- if (dis[S][eg[i].to]> dis[S][tp] + eg[i].val)
- {
- dis[S][eg[i].to] = dis[S][tp] + eg[i].val;
- if (!vis[eg[i].to]) vis[eg[i].to] = 1, q.push(eg[i].to);
- }
- }
- }
- inline void cmin(int& a, int b)
- {
- a = min(a, b);
- }
- int main()
- {
- read(n), read(m);
- for (int i = 1, u, v; i <= m; ++i)
- read(u), read(v), add(u, v), add(v, u);
- read(s1), read(t1), read(l1), read(s2), read(t2), read(l2);
- memset(dis, 0x3f, sizeof(dis));
- for (int i = 1; i <= n; ++i) spfa(i);
- if (dis[s1][t1]> l1 || dis[s2][t2]> l2)
- {
- puts("-1");
- return 0;
- }
- int ans = dis[s1][t1] + dis[s2][t2];
- for (int i = 1; i <= n; ++i)
- for (int j = 1; j <= n; ++j)
- {
- if (dis[s1][i] + dis[i][j] + dis[j][t1] <= l1 && dis[s2][i] + dis[i][j] + dis[j][t2] <= l2)
- cmin(ans, dis[s1][i] + dis[s2][i] + dis[i][j] + dis[j][t1] + dis[j][t2]);
- if (dis[s1][j] + dis[j][i] + dis[i][t1] <= l1 && dis[s2][i] + dis[i][j] + dis[j][t2] <= l2)// 不写这个就只有 85
- cmin(ans, dis[s1][j] + dis[j][i] + dis[i][t1] + dis[s2][i] + dis[j][t2]);
- }
- printf("%d\n", m - ans);
- return 0;
- }
C 矩形面积交
题意: 51nod 1302
题解: 贪心
一组里的面积一定是最短长乘最短宽, 一定是短边对短边, 长边对长边
钦定最短短边放在 A 组里
按长边把剩下的排序
从长边从大往小扔到 B 组里, 满了就把短边最短的扔到 A 组里
注意 A 组的最短长度要特判一下
复杂度:\(O(n\log n)\)
- #include<bits/stdc++.h>
- using namespace std;
- inline void read(int& x)
- {
- x = 0; char c = getchar();
- while (!isdigit(c)) c = getchar();
- while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
- }
- #define ll long long
- #define mp make_pair
- #define pa pair<int,int>
- priority_queue<pa, vector<pa>, greater<pa>>q;
- struct Rectangle
- {
- int x, y;
- bool operator <(const Rectangle& p) const
- {
- if (y != p.y) return y < p.y;
- return x < p.x;
- }
- }a[200005];
- int n;
- int main()
- {
- read(n);
- for (int i = 1; i <= n * 2; ++i)
- {
- read(a[i].x), read(a[i].y);
- if (a[i].x> a[i].y) swap(a[i].x, a[i].y);
- if (a[i].x <a[1].x || (a[i].x == a[1].x && a[i].y < a[1].y)) swap(a[i], a[1]);
- }
- sort(a + 2, a + 2 * n + 1);
- ll ans = 0;
- for (int i = 2 * n; i>= 2; --i)
- {
- q.push(mp(a[i].x, a[i].y));
- if (q.size()> n)
- {
- a[1].y = min(a[1].y, q.top().second);
- q.pop();
- }
- if (q.size() == n)
- {
- int tmp = a[1].y;
- if (i != 2) tmp = min(tmp, a[2].y);//i=2 时已经被分好组了, 否则默认 A 组
- ans = max(ans, 1ll * a[1].x * tmp + 1ll * a[i].y * q.top().first);//A+B
- }
- }
- printf("%lld\n", ans);
- return 0;
- }
D 两棵树的问题
题意: 51nod 1325
题解: 最大权闭合子图
可惜我考场上没想到啊
注意是无根树, 所以要枚举根
或者也可以用点分治求出必选的重心这里 https://www.cnblogs.com/cjfdf/p/9397769.html
复杂度:\(O(n^4)/O(n^3\log n)\)(设最大流复杂度为 \(n^3\))
- #include<bits/stdc++.h>
- using namespace std;
- inline void read(int& x)
- {
- x = 0; char c = getchar(); int f = 1;
- while (!isdigit(c)) { if (c == '-') f = -1; c = getchar(); }
- while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
- x *= f;
- }
- #define maxn 100005
- #define inf 0x3f3f3f3f
- struct Edge
- {
- int fr, to, val;
- }eg[maxn <<1];
- int head[maxn], edgenum = 1;
- inline void add(int fr, int to, int val)
- {
- eg[++edgenum] = { head[fr],to,val };
- head[fr] = edgenum;
- }
- #define Add(a,b,c) add(a,b,c),add(b,a,0)
- #define to eg[i].to
- int dep[maxn], vis[maxn], cur[maxn], S, T, maxflow;
- queue<int> q;
- bool bfs()
- {
- for (int i = 0; i <= T; ++i) dep[i] = inf, cur[i] = head[i];
- while (!q.empty()) q.pop();
- dep[S] = 0; q.push(S);
- while (!q.empty())
- {
- int tp = q.front();
- q.pop(); vis[tp] = 0;
- for (int i = head[tp]; i; i = eg[i].fr)
- if (dep[to]> dep[tp] + 1 && eg[i].val)
- {
- dep[to] = dep[tp] + 1;
- if (!vis[to]) vis[to] = 1, q.push(to);
- }
- }
- return dep[T] != inf;
- }
- int dfs(int rt, int flow)
- {
- if (rt == T)
- {
- maxflow += flow;
- return flow;
- }
- int tmpflow = 0, used = 0;
- for (int& i = cur[rt]; i; i = eg[i].fr)
- if (dep[to] == dep[rt] + 1 && eg[i].val)
- if (tmpflow = dfs(to, min(flow - used, eg[i].val)))
- {
- used += tmpflow;
- eg[i].val -= tmpflow;
- eg[i ^ 1].val += tmpflow;
- if (used == flow) break;
- }
- return used;
- }
- inline void dinic()
- {
- while (bfs()) dfs(S, inf);
- }
- #undef to
- int val[maxn];
- struct Graph
- {
- struct Edge
- {
- int fr, to;
- }eg[maxn <<1];
- int head[maxn], edgenum, fa[maxn];
- inline void add(int fr, int to)
- {
- eg[++edgenum] = { head[fr],to };
- head[fr] = edgenum;
- }
- inline void ADD(int fr, int to)
- {
- add(fr, to), add(to, fr);
- }
- void dfs(int rt)
- {
- for (int i = head[rt]; i; i = eg[i].fr)
- if (eg[i].to != fa[rt]) fa[eg[i].to] = rt, dfs(eg[i].to);
- }
- }G[2];
- int main()
- {
- int n, ans = 0, sum = 0; read(n);
- S = n + 1, T = n + 2;
- for (int i = 1; i <= n; ++i) read(val[i]), sum += val[i]> 0 ? val[i] : 0;
- for (int i = 1, FR, TO; i <n; ++i) read(FR), read(TO), ++FR, ++TO, G[0].ADD(FR, TO);
- for (int i = 1, FR, TO; i < n; ++i) read(FR), read(TO), ++FR, ++TO, G[1].ADD(FR, TO);
- for (int rt = 1; rt <= n; ++rt)
- {
- memset(head, 0, sizeof(head)); edgenum = 1; maxflow = 0;
- for (int i = 1; i <= n; ++i)
- {
- if (val[i]> 0) Add(S, i, val[i]);
- if (val[i] < 0) Add(i, T, -val[i]);
- }
- G[0].fa[rt] = G[1].fa[rt] = 0;
- G[0].dfs(rt), G[1].dfs(rt);
- for (int i = 1; i <= n; ++i)
- {
- Add(i, G[0].fa[i], inf);
- Add(i, G[1].fa[i], inf);
- }
- dinic();
- ans = max(ans, sum - maxflow);
- }
- printf("%d\n", ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3451322.html