2017ACM萧山训练第2场(NWERC 2008)
A:Equilibrium Mobile
最终天平平衡的状态下， 每个结点x满足w[x]*(2^dep[x])相等
统计所有的w[x]*(2^dep[x])，答案是叶子数减去出现次数最多的个数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
#include<map> #include<set> #include<cmath> #include<stack> #include<deque> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define eps 1e-12 #define mp(a, b) make_pair(a, b) #define ll long long #define inf 1000000000 #define mod 1000000007 #define pa pair<int,int> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T; string s; int n; vector<ll> ve; int l[200005], r[200005]; int solve(string s, int dep) { n++; int res = n; string s1 = "", s2 = ""; if(s[0] == '[') { s = s.substr(1, s.length() - 2); bool flag = 0; int sum = 0; for(int i = 0; i < s.length(); i++) if(s[i] == ',' && sum == 0) flag = 1; else { if(s[i] == '[')sum++; if(s[i] == ']')sum--; if(flag)s2 += s[i]; else s1 += s[i]; } l[res] = solve(s1, dep << 1), r[res] = solve(s2, dep << 1); } else { int tmp = 0; for(int i = 0; i < s.length(); i++) tmp = tmp * 10 + s[i] - '0'; ve.push_back((ll)tmp * dep); } return res; cout << s << ' ' << s1 <<' ' << s2 << endl;; } int main() { T = read(); while(T--) { ve.clear(); n = 0; cin >> s; int root = solve(s, 1); sort(ve.begin(), ve.end()); int ans = inf; for(int i = 0, j = 0; i < ve.size(); i = j) { while(j < ve.size() && ve[i] == ve[j])j++; ans = min(ans, (int)ve.size() - (j - i)); } printf("%d\n", ans); } return 0; } |
B:Proving Equivalences
答案是max{入度为0的连通块个数，出度为0的连通块个数}
特判连通块为1的情况
每个连通块，出度0的点，向其它入度为0的连边，使得形成一个环
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
#include<map> #include<set> #include<cmath> #include<stack> #include<deque> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define eps 1e-12 #define mp(a, b) make_pair(a, b) #define ll long long #define inf 9000000000000000000LL #define mod 1000000007 #define pa pair<int,int> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T, n, m; int ind, scc, top; int in[20005], out[20005]; int low[20005], dfn[20005], q[20005], bl[20005]; bool inq[20005]; vector<int>e[20005]; void tarjan(int x) { low[x] = dfn[x] = ++ind; q[++top]=x; inq[x]=1; for(int i = 0; i < e[x].size(); i++) if(!dfn[e[x][i]]) { tarjan(e[x][i]); low[x] = min(low[x], low[e[x][i]]); } else if(inq[e[x][i]]) low[x] = min(low[x], dfn[e[x][i]]); if(low[x] == dfn[x]) { int now = 0; scc++; while(x != now) { now = q[top]; top--; bl[now] = scc; inq[now] = 0; } } } int main() { T = read(); while(T--) { scc = ind = 0; memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); memset(out, 0, sizeof(out)); memset(in, 0, sizeof(in)); memset(bl, 0, sizeof(bl)); for(int i = 1; i <= 20000; i++) e[i].clear(); n = read(); m = read(); for(int i = 1; i <= m; i++) { int u = read(), v =read(); e[u].push_back(v); } for(int i = 1; i <= n; i++) if(!dfn[i])tarjan(i); for(int i = 1; i <= n; i++) for(int j = 0; j < e[i].size(); j++) if(bl[i] != bl[e[i][j]]) in[bl[e[i][j]]]++, out[bl[i]]++; int t1 = 0, t2 = 0; for(int i = 1; i <= scc; i++) { if(!in[i])t1++; if(!out[i])t2++; } if(scc == 1)puts("0"); else printf("%d\n", max(t1, t2)); } return 0; } |
C:Cat vs. Dog
找出所有相互不兼容的人，将他们连边，求最大独立集的个数
二分图匹配
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 |
#include<map> #include<set> #include<cmath> #include<stack> #include<deque> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define eps 1e-12 #define mp(a, b) make_pair(a, b) #define ll long long #define inf 1000000000 #define mod 1000000007 #define pa pair<int,int> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T; int n,m,cnt,flow; int x[505], y[505]; int last[505],q[505],h[505],type[505]; struct edge{ int to,next,v; }e[200005]; void insert(int u,int v,int w) { e[++cnt]=(edge){v,last[u],w};last[u]=cnt; e[++cnt]=(edge){u,last[v],0};last[v]=cnt; } int bfs() { int head=0,tail=1; memset(h,-1,sizeof(h)); q[0]=0;h[0]=0; while(head!=tail) { int now=q[head];head++; for(int i=last[now];i;i=e[i].next) if(e[i].v&&h[e[i].to]==-1) { h[e[i].to]=h[now]+1; q[tail++]=e[i].to; } } return h[T]!=-1; } int dfs(int x,int f) { if(x==T)return f; int w,used=0; for(int i=last[x];i;i=e[i].next) if(h[e[i].to]==h[x]+1) { w=dfs(e[i].to,min(e[i].v,f-used)); e[i].v-=w;e[i^1].v+=w; used+=w;if(used==f)return f; } if(!used)h[x]=-1; return used; } void dinic() { while(bfs())flow+=dfs(0,inf); } int getnum() { char ch[5]; scanf("%s", ch); int tmp = 0, flag = 1; int l = strlen(ch + 1); for(int i = 1; i <= l; i++) tmp = tmp * 10 + ch[i] - '0'; if(ch[0] == 'D') tmp += 500; return tmp; } int main() { int test = read(); while(test--) { int c = read(), d = read(), v = read(); T = v + 1; flow=0; cnt=1; memset(last, 0, sizeof(last)); memset(type, 0, sizeof(type)); for(int i = 1; i <= v; i++) { x[i] = getnum(), y[i] = getnum(); if(x[i] <= 500)type[i] = 1; } for(int i = 1; i <= v; i++) if(type[i] == 0) insert(0, i, 1); else insert(i, T, 1); for(int i = 1; i <= v; i++) for(int j = 1; j <= v; j++) if(type[i] == 0 && type[j] == 1) { if(x[i] != y[j] && x[j] != y[i])continue; insert(i, j, 1); } dinic(); printf("%d\n",v - flow); } return 0; } |
D:Disgruntled Judge
枚举所有的 a，根据 x1和 x3 可以用扩展欧几里得求出 b，再验证一下
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
#include<map> #include<set> #include<cmath> #include<stack> #include<deque> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define eps 1e-12 #define mp(a, b) make_pair(a, b) #define ll long long #define inf 1000000000 #define mod 1000000007 #define pa pair<int,int> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } void exgcd(ll a,ll b,ll &d,ll &x,ll &y) { if(!b)d=a,x=1,y=0; else exgcd(b,a%b,d,y,x),y-=x*(a/b); } int n; ll x[10005]; int main() { n = read(); if(n == 1) { puts("0"); return 0; } for(int i = 1; i <= 2 * n; i += 2) x[i] = read(); ll x1 = x[1], x3 = x[3]; for(ll a = 0; a <= 10000; a++) { ll tmp = x3 - x1 * a * a, D, X, Y; exgcd(a + 1, 10001, D, X, Y); if(tmp % D)continue; X = X * tmp / D; ll T = x1; bool flag = 1; for(int i = 1; i <= 2 * n; i++) { if(i & 1) { if(T != x[i]) { flag = 0; break; } } else x[i] = T; T = (a * T + X) % 10001; } if(flag) { for(int i = 2; i <= 2 * n; i += 2) printf("%d\n", x[i]); break; } } return 0; } |
E:Easy Climb
发现最后有效的高度只有所有的h_i + k * d (-n <= k <= n)
离散化后只有 n^2 种高度
然后可以设计一个 O(n^3) 状态的 dp，f(i, j) 表示考虑前 i 座山，最后一座的高度是离散后的 j
f(i, j) = max{f(i – 1, k)}(其中 j 和 k 离散前的差不超过d)
用一个单调队列来优化到 O(1)转移
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
#include<map> #include<set> #include<cmath> #include<stack> #include<deque> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define eps 1e-12 #define mp(a, b) make_pair(a, b) #define ll long long #define inf 9000000000000000000LL #define mod 1000000007 #define pa pair<ll,ll> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T; int n, m; ll d, h[105]; ll f[105][25005]; vector<ll> H; int main() { T = read(); while(T--) { H.clear(); n = read(), d = read(); ll mn = inf, mx = 0; for(int i = 1; i <= n; i++) { h[i] = read(); mn = min(mn, h[i]); mx = max(mx, h[i]); } if(abs(h[1] - h[n]) > (ll)(n - 1) * d) { puts("impossible"); continue; } for(int i = 1; i <= n; i++) { for(ll j = 1; j <= n; j++) { if(h[i] + j * d <= mx)H.push_back(h[i] + j * d); if(h[i] - j * d >= mn)H.push_back(h[i] - j * d); } H.push_back(h[i]); } sort(H.begin(), H.end()); H.erase(unique(H.begin(),H.end()),H.end()); m = H.size(); for(int i = 1; i <= n; i++) h[i] = lower_bound(H.begin(), H.end(), h[i]) - H.begin(); for(int i = 0; i <= n; i++) for(int j = 0; j < m; j++) f[i][j] = inf; f[1][h[1]] = 0; deque<pa> dq; for(int i = 2; i <= n; i++) { int l = 0; dq.clear(); for(int j = 0; j < m; j++) { while(abs(H[l] - H[j]) <= d && l < m) { while(dq.size() && dq.front().first >= f[i - 1][l])dq.pop_front(); dq.push_back(make_pair(f[i - 1][l], H[l])); l++; } pa t = dq.front(); while(abs(H[j] - t.second) > d)dq.pop_front(), t = dq.front(); f[i][j] = min(f[i][j], t.first + abs(H[j] - H[h[i]])); } } cout << f[n][h[n]] << endl; } return 0; } |
H:Matchsticks
最小值可以直接 dp 出来，最大值是11…11，或者71…11，根据奇偶性直接输出
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include<map> #include<set> #include<cmath> #include<stack> #include<deque> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define eps 1e-12 #define mp(a, b) make_pair(a, b) #define ll long long #define inf 9000000000000000000LL #define mod 1000000007 #define pa pair<int,int> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T; int cnt[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; ll mn[105]; ll solve(ll x, ll y) { ll tmp = 1; while(tmp <= y)tmp *= 10; return x * tmp + y; } int main() { for(int i = 0; i <= 100; i++)mn[i] = inf; mn[0] = 0; for(int i = 0; i <= 100; i++) if(i != 1) { for(int j = 0; j <= 9; j++) { int t = i + cnt[j]; if(t > 100)continue; ll v1 = mn[i] * 10 + j, v2 = solve(j, mn[i]); if(j == 0)v2 = inf; if(v1 == 0)v1 = inf; mn[t] = min(mn[t], min(v1, v2)); } } int T = read(); while(T--) { int x = read(); cout << mn[x] <<' '; if(x & 1){x -= 3; printf("7");} else {x -= 2; printf("1");} for(int i = 1; i <= x / 2; i++) printf("1"); puts(""); } return 0; } |
J:Shuffle
首先预处理从第 i 个位置向前的 n 个数字中有没有重复的，不重复的打上标记
然后枚举第一个分段点 x，则 x + k * n 都带有标记
注意两侧不完整的分段要验证一下有没有相同的
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include<map> #include<set> #include<cmath> #include<stack> #include<deque> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define eps 1e-12 #define mp(a, b) make_pair(a, b) #define ll long long #define inf 9000000000000000000LL #define mod 1000000007 #define pa pair<int,int> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T; int a[100005]; bool mark[100005], val[100005]; int main() { T = read(); while(T--) { memset(mark, 0, sizeof(mark)); memset(val, 0, sizeof(val)); int n = read(), m = read(); for(int i = 1; i <= m; i++) a[i] = read(); int l = 1; for(int i = 1; i <= m; i++) { while(mark[a[i]]) { mark[a[l]] = 0; l++; } mark[a[i]] = 1; if(l == 1 || l + n - 1 == i)val[i] = 1; } int t = m; memset(mark, 0, sizeof(mark)); while(!mark[a[t]])mark[a[t]] = 1, t--; int ans = 0; for(int i = 1; i <= n; i++) { if(!val[i] && i <= m)break; bool flag = 1; for(int j = i; j <= m; j += n) { if(!val[j])flag = 0; if(j + n > m && j < t)flag = 0; } if(flag)ans++; } cout << ans << endl; } return 0; } |
计数器 9322317
OI 课件=>
OI 课件=>
黄学长最棒啦！