https://odzkskevi.qnssl.com/727b6827e404fd453ff4858e2619c49c?v=1504751451
A - GREAT+SWERC=PORTO
全排列枚举。先将字母按照出现的顺序,重新编码为以$0$为开始值的数字,方便后续使用。然后构造一个排列数组$p$,长度为$10$,初始值$p[i] = i$。然后枚举$p$的全排列,$p[i]$的意义就是将数字(实质上是被重新编码后的字母)$i$以值$p[i]$来代替。假设有$cnt$个不同的字母,全排列我们枚举的却是$10$个数,每次只取前$cnt$个进行代替,那么最终的答案会重复计算$(10-cnt)!$次。进行暴力枚举并统计答案后,除以$(10-cnt)!$即可。
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
|
#include<bits/stdc++.h> using namespace std; char str[12][12]; int length[12]; int main() { int n; while(~scanf("%d", &n)) { for(int i = 1; i <= n; i++) scanf("%s", str[i]); int mp[127]; memset(mp, -1, sizeof(mp)); int cnt = 0; for(int i = 1; i <= n; i++) { length[i] = strlen(str[i]); for(int j = 0; j < length[i]; j++) { if(mp[str[i][j]] != -1) continue; mp[str[i][j]] = cnt++; } } for(int i = 1; i <= n; i++) { for(int j = 0; j < length[i]; j++) str[i][j] = mp[str[i][j]]; }//对字母进行重新编码 int p[12]; for(int i = 0; i < 10; i++) p[i] = i;//排列数组 int ans = 0; do { bool ok = 1; for(int i = 1; i <= n; i++) { if(p[str[i][0]] == 0)//不能将第一位替换为0 { ok = 0; break; } } if(!ok) continue; int val[12]; memset(val, 0, sizeof(val)); for(int i = 1; i <= n; i++) { for(int j = 0; j < length[i]; j++) val[i] = val[i] * 10 + p[str[i][j]];//计算替换后,每个单词的值 } int sum = 0; for(int i = 1; i < n; i++) sum += val[i]; if(sum == val[n]) ans++; } while(next_permutation(p, p + 10));//枚举下一个排列 int t = 1; for(int i = 10 - cnt; i >= 2; i--) t *= i;//(10-cnt)的阶乘 printf("%d\n", ans / t); } return 0; } |
B - Flowery Trails
从起点和终点进行两次最短路。开一个$dis[2][i]$数组,分别表示从$0$点到$i$点的最短路、从$n-1$点到$i$点的最短路。要判断一条边是否在最短路上,可以枚举每一条$单向边$,假设这条边的两个端点分别为$u$和$v$,如果满足$dis[0][u] + len + dis[1][v] = dis[0][n-1]$,那么从$u->v$方向的这条边就在最短路上,应该纳入统计。这个题可能会卡SPFA,所以使用了堆优化的DIJ
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
|
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int maxn = 10005; const int maxm = 250000 * 2; struct EDGE { int to, next, len; EDGE() {} EDGE(int to, int next, int len) : to(to), next(next), len(len) {} } edge[maxm]; int head[maxn], edgecnt; int dis[2][maxn]; int n; struct node { int u, dis; node(int u, int dis): u(u), dis(dis) {} bool operator < (const node &b) const { return dis > b.dis; } }; void init() { memset(head, -1, sizeof(head)); edgecnt = 0; } void add(int s, int t, int l) { edge[edgecnt] = EDGE(t, head[s], l); head[s] = edgecnt++; } void spfa(int st, int dis[]) { memset(dis, 0x7F, sizeof(int) *n); dis[st] = 0; priority_queue<node> q; static bool f[maxn]; memset(f, 0, n); q.emplace(st, 0); while(!q.empty()) { int u = q.top().u; q.pop(); if(f[u]) continue; f[u] = 1; for(int i = head[u]; ~i; i = edge[i].next) { int v = edge[i].to; if(dis[v] > dis[u] + edge[i].len) { dis[v] = dis[u] + edge[i].len; q.emplace(v, dis[v]); } } } } int main() { int m; while(~scanf("%d %d", &n, &m)) { init(); for(int i = 1; i <= m; i++) { int s, t, l; scanf("%d %d %d", &s, &t, &l); add(s, t, l); add(t, s, l); } spfa(0, dis[0]); spfa(n - 1, dis[1]); int len = dis[0][n - 1]; int ans = 0; for(int u = 0; u < n; u++) { for(int i = head[u]; ~i; i = edge[i].next) { int v = edge[i].to; if(v == u) continue; if(dis[0][u] + edge[i].len + dis[1][v] == len) ans += edge[i].len; } } printf("%d\n", 2 * ans); } return 0; } |
C - Golf Bot
使用FFT进行计数。使用$cnt$数组记录每个值是否出现。将$cnt$数组和自己进行卷积后(假设为$A$数组),$A[i]$的意义就是任意选两个存在的数进行求和后,和值为$i$的方案数。再将$A$数组加回到$cnt$数组。$cnt[i]$是否为$0$,就代表是否有方案至多选两个数,至少选一个数的和为i。
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 117
|
#include<bits/stdc++.h> using namespace std; const int FFT_MAXN = 1 << 19; const double pi = acos(-1.0); struct Complex { double R, I; inline Complex(double real = 0.0, double image = 0.0) { R = real, I = image; } inline Complex operator + (Complex const &b) const { return Complex(R + b.R, I + b.I); } inline Complex operator - (Complex const &b) const { return Complex(R - b.R, I - b.I); } inline Complex operator * (Complex const &b) const { return Complex(R * b.R - I * b.I, I * b.R + R * b.I); } } Wn[FFT_MAXN + 1]; int bitrev[FFT_MAXN]; inline int getLength(int n, int m) { n = n + m - 1; int i = 1; for(; i < n; i <<= 1); return i; } void Change(Complex a[], int n) { int d = 0; while((1 << d)*n != FFT_MAXN) d++; for(int i = 0; i < n; i++) if(i < (bitrev[i] >> d)) swap(a[i], a[bitrev[i] >> d]); } void FFT(Complex P[], int n, int op) { Change(P, n); for(int len = 2; len <= n; len <<= 1) { int m = len >> 1; int del = FFT_MAXN / len * op; for(int i = 0; i < n; i += len) { Complex *p = P + i, *q = P + i + m, *w = op == 1 ? Wn : Wn + FFT_MAXN; for(int j = 0; j < m; j++, p++, q++, w += del) { Complex ne = *q * *w; *q = *p - ne; *p = *p + ne; } } } if(op == -1) for(int i = 0; i < n; i++) { P[i].R /= n; P[i].I /= n; } } void FFTInit() { int L = 0; while((1 << L) != FFT_MAXN) L++; bitrev[0] = 0; for(int i = 1; i < FFT_MAXN; i++) bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << (L - 1)); for(int i = 0; i <= FFT_MAXN; i++) Wn[i] = Complex(cos(2 * pi / FFT_MAXN * i), sin(2 * pi / FFT_MAXN * i)); } Complex A[FFT_MAXN], B[FFT_MAXN]; long long cnt[FFT_MAXN]; int main() { FFTInit(); int n; while(~scanf("%d", &n)) { memset(cnt, 0, sizeof(cnt)); for(int i = 1; i <= n; i++) { int x; scanf("%d", &x); cnt[x]++; } for(int i = 0; i < FFT_MAXN; i++) A[i] = Complex(cnt[i], 0); FFT(A, FFT_MAXN, 1); for(int i = 0; i < FFT_MAXN; i++) A[i] = A[i] * A[i]; FFT(A, FFT_MAXN, -1); for(int i = 0; i < FFT_MAXN; i++) { int t = A[i].R + 0.5; cnt[i] += t; } int m; scanf("%d", &m); int ans = 0; while(m--) { int x; scanf("%d", &x); if(cnt[x]) ans++; } printf("%d\n", ans); } return 0; } |
D - Book Club
最大流求是否有合法方案
给出一些给书的关系,问是否有方案,使得每个人可以交出一本书,并且获得一本书,不能自己和自己玩。
将一个人$i$看作两个点,编号$A_i$和$B_i$。从源点引边到每一个$A_i$点,容量为1,表示$i$这个人要交出一本书。从每一个$B_i$引一条边到汇点,容量为1,表示$i$这个人要获得一本书。如果有一个关系,$i$的书可以给$j$,那么连一条边从$A_i$到$B_j$。最后跑最大流,如果流量为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 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
|
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5; const int maxm = 2e5; struct EDGE { int to, next, flow; EDGE(int to = 0, int next = 0, int flow = 0): to(to), next(next), flow(flow) {} } edge[maxm]; int head[maxn], edgecnt; void init() { memset(head, -1, sizeof(head)); edgecnt = 0; } void AddEdge(int s, int t, int c) { edge[edgecnt] = EDGE(t, head[s], c); head[s] = edgecnt++; edge[edgecnt] = EDGE(s, head[t], 0); head[t] = edgecnt++; } int layer[maxn]; int p[maxn]; bool GetLayer(int st, int en) { memset(layer, 0, sizeof(int) * (en + 1)); layer[st] = 1; queue<int>q; q.push(st); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = head[u]; ~i; i = edge[i].next) { if (edge[i].flow == 0) continue; int v = edge[i].to; if (layer[v]) continue; layer[v] = layer[u] + 1; q.push(v); } } return layer[en]; } int dfsFlow(int u, int en, int f) { int ret = 0; if (u == en) return f; if (layer[u] >= layer[en]) return 0; for (; ~p[u]; p[u] = edge[p[u]].next) { if (edge[p[u]].flow == 0) continue; int v = edge[p[u]].to; if (layer[v] != layer[u] + 1) continue; int temp = dfsFlow(v, en, min(f, edge[p[u]].flow)); ret += temp; f -= temp; edge[p[u]].flow -= temp; edge[p[u] ^ 1].flow += temp; if (f == 0) break; } return ret; } int dinic(int st, int en) { int ans = 0; while (GetLayer(st, en)) { memcpy(p, head, sizeof(int) * (en + 1)); ans += dfsFlow(st, en, INT_MAX); } return ans; } int main() { init(); int n, m; scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { AddEdge(0, i, 1); AddEdge(n + i, n + n + 1, 1); } while (m--) { int u, v; scanf("%d %d", &u, &v); u++; v++; AddEdge(u, n + v, 1); } int flow = dinic(0, n + n + 1); if (flow != n) puts("NO"); else puts("YES"); return 0; } |
G - Playing With Geometry
离散化,坐标旋转。
给定两个图,以转角坐标的方式逆时针给出,问两个图的轮廓是否相似。允许进行压缩或者旋转。
直接将两个图的横纵坐标进行离散化(压缩)。枚举将第一图进行旋转,和第二个图进行匹配,匹配的时候,需要找到两张图最左下角的点,让后从这个点开始,逆时针匹配。如果每个坐标都是相同的,那么就是OK的。
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<bits/stdc++.h> using namespace std; const int maxn = 505; int n; void Compress(pair<int, int> p[maxn]) { int x[maxn], y[maxn]; for (int i = 0; i < n; i++) { x[i] = p[i].first; y[i] = p[i].second; } sort(x, x + n); sort(y, y + n); int cntx = unique(x, x + n) - x - 1; int cnty = unique(y, y + n) - y - 1; for (int i = 0; i < n; i++) { p[i].first = lower_bound(x, x + cntx, p[i].first) - x; p[i].second = lower_bound(y, y + cnty, p[i].second) - y; } } void Rotate(pair<int, int> p[maxn]) { int ym = 0; for (int i = 0; i < n; i++) ym = max(ym, p[i].second); for (int i = 0; i < n; i++) p[i] = make_pair(ym - p[i].second, p[i].first); } bool Compare(pair<int, int> p[2][maxn]) { int p1 = min_element(p[0], p[0] + n) - p[0]; int p2 = min_element(p[1], p[1] + n) - p[1]; for (int i = 0; i < n; i++) if (p[0][(p1 + i) % n] != p[1][(p2 + i) % n]) return false; return true; } bool check(pair<int, int> p[2][maxn]) { for (int i = 0; i < 4; i++) { if (Compare(p)) return true; Rotate(p[0]); } return false; } int main() { pair<int, int> p[2][maxn]; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d %d", &p[0][i].first, &p[0][i].second); int m; scanf("%d", &m); if (n != m) { puts("no"); return 0; } for (int i = 0; i < n; i++) scanf("%d %d", &p[1][i].first, &p[1][i].second); Compress(p[0]); Compress(p[1]); if (check(p)) puts("yes"); else puts("no"); return 0; } |
I - The Safe Secret
循环枚举,区间DP
给一个由数字和运算符号组成的序列,长度为$2*n$运算符号只包含+-*和?,?可以任意替换为+-*。枚举将序列向左进行循环位移,每次位移$2$个单位,可以得到$n$个表达式序列,问这$n$个表达式的值的最小值和最大值的绝对值。
先将原始序列的数字和符号进行分离。再分别复制一份后接到后面。这样就可以进行区间dp了。注意,第i个数字就是$num[i]$了,它后面的符号就是$symbol[i]$。用$mx[i][j]$来表示从第$i$个数字到第$j$个数字组成的子区间的表达式的最大值,$mi[i][j]$表示最小值。初始化$mx[i][i] = mi[i][i] = num[i]$。枚举区间长度,枚举区间起点,再枚举区间内的断点,进行转移即可。要注意断点处为乘号的时候,并不是最小值*最小值就是最小值(考虑两个都是负数的情况),为了偷懒,直接暴力枚举了4种情况进行转移。
最后mx[i][n+i-1]和mi[i][n+i-1]就是第i个序列的表达式的最大值和最小值
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
|
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 405; LL mx[maxn][maxn]; LL mi[maxn][maxn]; void getMaxMin(const vector<int> &num, const vector<char> &symbol) { memset(mx, 0x80, sizeof(mx)); memset(mi, 0x7F, sizeof(mi)); int n = num.size(); for (int i = 0; i < n; i++) mi[i][i] = mx[i][i] = num[i]; for (int len = 2; len <= n / 2; len++) { for (int st = 0; st + len <= n; st++) { int en = st + len - 1; for (int mid = st; mid < en; mid++) { if (symbol[mid] == '+' || symbol[mid] == '?') { mi[st][en] = min(mi[st][en], mi[st][mid] + mi[mid + 1][en]); mx[st][en] = max(mx[st][en], mx[st][mid] + mx[mid + 1][en]); } if (symbol[mid] == '-' || symbol[mid] == '?') { mi[st][en] = min(mi[st][en], mi[st][mid] - mx[mid + 1][en]); mx[st][en] = max(mx[st][en], mx[st][mid] - mi[mid + 1][en]); } if (symbol[mid] == '*' || symbol[mid] == '?') { mi[st][en] = min(mi[st][en], mi[st][mid] * mi[mid + 1][en]); mi[st][en] = min(mi[st][en], mi[st][mid] * mx[mid + 1][en]); mi[st][en] = min(mi[st][en], mx[st][mid] * mi[mid + 1][en]); mi[st][en] = min(mi[st][en], mx[st][mid] * mx[mid + 1][en]); mx[st][en] = max(mx[st][en], mx[st][mid] * mx[mid + 1][en]); mx[st][en] = max(mx[st][en], mx[st][mid] * mi[mid + 1][en]); mx[st][en] = max(mx[st][en], mi[st][mid] * mx[mid + 1][en]); mx[st][en] = max(mx[st][en], mi[st][mid] * mi[mid + 1][en]); } } } } } int main() { int n; while (~scanf("%d", &n)) { vector<int> num; vector<char> symbol; for (int i = 0; i < n; i++) { int x; scanf("%d", &x); num.push_back(x); char s[10]; scanf("%s", s); symbol.push_back(s[0]); } for (int i = 0; i < n; i++) { num.push_back(num[i]); symbol.push_back(symbol[i]); } getMaxMin(num, symbol); for (int i = 0; i < n; i++) printf("%lld%lld", abs(mi[i][i + n - 1]), abs(mx[i][i + n - 1])); printf("\n"); } return 0; } |