CF1187D. Subarray Sorting
想要把一个数x换到前面，x一定是小一点的值。由于B串是固定的，A串可调整，我们可以遍历B数组，对于B【i】，找到对于在A数组的位子pos，判断1～pos中，是不是A【pos】最小，如果是最小，说明可以换到最前面，把A【pos】的值变为inf后，继续遍历。
#include <cstdio> #include <vector> #include <cstring> #include <algorithm> #include <iostream> #include <queue> using namespace std; #define pb push_back #define fi first #define se second #define debug(x) cerr<<#x << " := " << x << endl; #define bug cerr<<"-----------------------"<<endl; #define FOR(a, b, c) for(int a = b; a <= c; ++ a) typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int inf = 0x3f3f3f3f; const int MOD = 1e9+7; /**********showtime************/ const int maxn = 3e5+9; int a[maxn], b[maxn]; queue<int>que[maxn]; int mn[maxn<<2]; void update(int pos, int val, int le, int ri, int rt) { if(le == ri) { mn[rt] = val; return ; } int mid = (le + ri) >> 1; if(mid >= pos) update(pos, val, le, mid, rt<<1); else update(pos, val, mid+1, ri, rt<<1|1); mn[rt] = min(mn[rt<<1], mn[rt<<1|1]); } int query(int L, int R, int le, int ri, int rt) { if(le >= L && ri <= R) { return mn[rt]; } int mid = (le + ri) >> 1; int res = inf; if(mid >= L) res = min(res, query(L,R,le, mid, rt<<1)); if(mid < R) res = min(res, query(L,R,mid+1, ri, rt<<1|1)); return res; } void build(int le, int ri, int rt) { if(le == ri) return ; int mid = (le + ri) >> 1; build(le, mid, rt<<1); build(mid+1, ri, rt<<1|1); } int main(){ int T; scanf("%d", &T); while(T--) { int n; scanf("%d", &n); build(1, n, 1); for(int i=1; i<=n; i++) scanf("%d", &a[i]), que[a[i]].push(i), update(i, a[i], 1, n, 1); for(int i=1; i<=n; i++) scanf("%d", &b[i]); int flag = 1; for(int i=1; i<=n; i++) { if(!que[b[i]].empty()) { int p = que[b[i]].front(); que[b[i]].pop(); if(query(1, p, 1, n, 1) < b[i]) flag = 0; else update(p, inf, 1, n, 1); } else flag = 0; } for(int i=1; i<=n; i++) { while(!que[a[i]].empty()) que[a[i]].pop(); } puts(flag?"YES":"NO"); } return 0; }
E Tree Painting
树形DP，换根的转移。
#include <bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define debug(x) cerr<<#x << " := " << x << endl; #define bug cerr<<"-----------------------"<<endl; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int inf = 0x7f7f7f7f; const ll inff = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9+7; const double eps = 1e-6; /**********showtime************/ const int maxn = 2e5+9; vector<int> mp[maxn]; int sz[maxn]; ll ans = 0; int n; void dfs(int u, int fa) { sz[u] = 1; for(int i=0; i<mp[u].size(); i++) { int v = mp[u][i]; if(v == fa) continue; dfs(v, u); sz[u] += sz[v]; } ans += sz[u]; } void dfs2(int u, int fa, ll pre) { for(int i=0; i<mp[u].size(); i++) { int v = mp[u][i]; if(v == fa) continue; ll tmp = pre + n - 2ll * sz[v]; ans = max(ans, tmp); dfs2(v, u, tmp); } } int main(){ scanf("%d", &n); for(int i=1; i<n; i++) { int u,v; scanf("%d%d", &u, &v); mp[u].pb(v); mp[v].pb(u); } dfs(1, -1); dfs2(1, -1, ans); printf("%lld ", ans); return 0; }
G Gang Up
网络流，搞好了。
这道题要把每个点拆成多个点表示不同的时间，每条边要对应多条道路，就是把1,4,9....变成容量为1,费用位1,3,5的边。
每个点要拆成100个点，就是最多会等待100的时间单位。因为第一个人最迟50个时间，那个第50个人就要100个时间到。
#include <cstdio> #include <vector> #include <cstring> #include <algorithm> #include <iostream> #include <queue> using namespace std; #define pb push_back #define fi first #define se second #define debug(x) cerr<<#x << " := " << x << endl; #define bug cerr<<"-----------------------"<<endl; #define FOR(a, b, c) for(int a = b; a <= c; ++ a) typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int inf = 0x3f3f3f3f; const int mod = 1e9+7; /**********showtime************/ const int maxn = 55; int st[maxn]; struct E{ int u,v,w,cost; int nxt; } edge[500009]; int gtot = 0,head[maxn * 100]; void addedge(int u, int v, int w, int cost) { edge[gtot].v = v; edge[gtot].w = w; edge[gtot].cost = cost; edge[gtot].nxt = head[u]; head[u] = gtot++; edge[gtot].v = u; edge[gtot].w = 0; edge[gtot].cost = -cost; edge[gtot].nxt = head[v]; head[v] = gtot++; } int dis[maxn * 100],path[500009],vis[maxn*100],pre[maxn*100]; bool spfa(int s,int t){ memset(pre, -1 ,sizeof(pre)); memset(dis, inf,sizeof(dis)); memset(vis, 0, sizeof(vis)); queue<int>que; que.push(s); vis[s] = 1; dis[s] = 0; while(!que.empty()){ int u = que.front(); que.pop(); vis[u] = 0; for(int i=head[u]; ~i; i = edge[i].nxt){ int v = edge[i].v, val = edge[i].w, cost = edge[i].cost; if(val > 0 && dis[v] > dis[u] + cost){ dis[v] = dis[u] + cost; pre[v] = u; path[v] = i; if(vis[v] == 0){ vis[v] = 1; que.push(v); } } } } return pre[t] != -1; } int mcmf(int s,int t){ int flow = 0,cost = 0; while(spfa(s, t)){ int f = inf; for(int i=t; i!=s; i = pre[i]){ f = min(f, edge[path[i]].w); } flow += f; cost += f * dis[t]; for(int i=t; i!=s; i = pre[i]){ edge[path[i]].w -= f; edge[path[i]^1].w += f; } } return cost; } int main(){ memset(head, -1, sizeof(head)); gtot = 0; int n,m,k,c,d; scanf("%d%d%d%d%d", &n, &m, &k, &c, &d); for(int i=1; i<=k; i++) { int x; scanf("%d", &x); st[x]++; } int s = 0, t = 100 * n + 1; for(int i=1; i<=n; i++) { for(int j=2; j<=100; j++) { addedge((i-1)*100+j-1, (i-1)*100 + j, inf, c); } } for(int i=2; i<=n; i++) { if(st[i]) addedge(s, (i-1)*100 + 1, st[i], 0); } for(int i=1; i<=100; i++) addedge(i, t, inf, 0); for(int i=1; i<=m; i++) { int u,v; scanf("%d%d", &u, &v); for(int j=2; j<=100; j++) { for(int k=1; k<=20; k++){ addedge((u-1)*100 + j - 1, (v-1)*100 + j, 1, (k*k - (k-1)*(k-1)) * d + c); addedge((v-1)*100 + j - 1, (u-1)*100 + j, 1, (k*k - (k-1)*(k-1)) * d + c); } } } printf("%d ", mcmf(s, t)); return 0; }
也可以两个点之间只建立一条道路，那么费用就需要根据流量重新计算。
#include <cstdio> #include <vector> #include <cstring> #include <algorithm> #include <iostream> #include <queue> using namespace std; #define pb push_back #define fi first #define se second #define debug(x) cerr<<#x << " := " << x << endl; #define bug cerr<<"-----------------------"<<endl; #define FOR(a, b, c) for(int a = b; a <= c; ++ a) typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; template<class T> void _R(T &x) { cin >> x; } void _R(int &x) { scanf("%d", &x); } void _R(ll &x) { scanf("%lld", &x); } void _R(double &x) { scanf("%lf", &x); } void _R(char &x) { scanf(" %c", &x); } void _R(char *x) { scanf("%s", x); } void R() {} template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); } const int inf = 0x3f3f3f3f; const int mod = 1e9+7; /**********showtime************/ const int maxn = 55; int st[maxn]; // Min-Cost Flow with positive convex edge weights class MinCostFlow { private: struct Edge { int a, b; // source, target int f, c; // flow, capacity ll m1, m2; // constants for cost Edge(int av, int bv, int cv, ll m1v, ll m2v) : a(av), b(bv), f(0), c(cv), m1(m1v), m2(m2v) {} // Get other end of edge int getOth(int i) { return i == a ? b : a; } // Get change in cost of pushing flow from i to getOth(i) ll getCost(int i) { int tf = f + (i == a ? 1 : -1); if (tf < 0 || tf > c) return inf; return m1*(tf-f) + m2*(tf*tf-f*f); } void pushUnit(int i) { f += (i == a ? 1 : -1); } }; vector<Edge> eds; vector<vector<int> > conns; public: MinCostFlow(int n) : conns(n) {} void addEdge(int a, int b, int c, int m1, int m2) { Edge tmp(a, b, c, m1, m2); eds.push_back(tmp); conns[a].push_back(eds.size() - 1); conns[b].push_back(eds.size() - 1); } ll pushFlow(int source, int sink) { int n = conns.size(); ll res = 0; vector<int> pre(n); vector<ll> cost(n); while(true) { for (int i = 0; i < n; ++i) { pre[i] = -1; cost[i] = inf; } cost[source] = 0; priority_queue<pair<ll, int> > que; que.push(pair<ll, int>(0, source)); while(! que.empty()) { int i = que.top().second; ll v = -que.top().first; que.pop(); if (v > cost[i]) continue; for (auto j : conns[i]) { int t = eds[j].getOth(i); ll off = cost[i] + eds[j].getCost(i); if (off < cost[t]) { cost[t] = off; pre[t] = j; que.push(pair<ll, int>(-off, t)); } } } int i = sink; while(pre[i] != -1) { auto& ed = eds[pre[i]]; i = ed.getOth(i); ed.pushUnit(i); } if (i != source) break; res += cost[sink]; } return res; } }; int main(){ int n,m,k,c,d; // scanf("%d%d%d%d%d", &n, &m, &k, &c, &d); R(n,m,k,c,d); for(int i=1; i<=k; i++) { int x; scanf("%d", &x); st[x]++; } int s = 0, t = 100 * n + 1; MinCostFlow fl(t + 1); for(int i=1; i<=n; i++) { for(int j=2; j<=100; j++) { fl.addEdge((i-1)*100+j-1, (i-1)*100 + j, inf, c, 0); } } for(int i=2; i<=n; i++) { if(st[i]) fl.addEdge(s, (i-1)*100 + 1, st[i], 0, 0); } for(int i=1; i<=100; i++) fl.addEdge(i, t, inf, 0, 0); for(int i=1; i<=m; i++) { int u,v; scanf("%d%d", &u, &v); for(int j=2; j<=100; j++) { fl.addEdge((u-1)*100 + j - 1, (v-1)*100 + j, k, c, d); fl.addEdge((v-1)*100 + j - 1, (u-1)*100 + j, k, c, d); } } // printf("%d ", fl.mcmf(s, t)); cout<<fl.pushFlow(s, t)<<endl; return 0; }