9/10
简单地写个题解，毕竟总个结很重要。但是由于题目水 + 不会写题解，路过的大牛莫喷。。。
题A
题意：给你两个序列a和b，有一种操作，对于一个数（非头尾）v，左边加上v，右边加上v，自己变成-v，然后问a操作无数次可不可以变成b？
题解：这题我学会了一个分析题目的方法：从目标逆着推。对于两个一样的序列，如下
操作前：……(i - 1) (i) (i + 1) ……
操作后：……(i - 1) + (i) (i) - (i) - (i) (i + 1) + (i)……
定义si为前i项的和，假设原序列为si - 1， si， si + 1，那么变化之后对应序列为si， si - 1，si + 1，所以这个操作的实质就是将前缀和变一下位置，所以对于两个序列我们只要求出前缀和s，然后sort一下看对应区域是否相等即可。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 #define lson l, m, rt*2 6 #define rson m + 1, r, rt*2+1 7 #define xx first 8 #define yy second 9 10 11 typedef long long ll; 12 typedef unsigned long long ull; 13 14 const int maxn = 1e5 + 10; 15 int a[maxn], b[maxn]; 16 ll s1[maxn], s2[maxn]; 17 18 int main() { 19 // freopen("case.in", "r", stdin); 20 int T; 21 scanf("%d", &T); 22 while (T--) { 23 int n; 24 scanf("%d", &n); 25 s1[0] = s2[0] = 0; 26 for (int i = 1; i <= n; i++) { 27 scanf("%d", a + i); 28 s1[i] = s1[i - 1] + a[i]; 29 } 30 for (int i = 1; i <= n; i++) { 31 scanf("%d", b + i); 32 s2[i] = s2[i - 1] + b[i]; 33 } 34 35 sort(s1 + 1, s1 + n + 1); 36 sort(s2 + 1, s2 + n + 1); 37 // for (int i = 1; i <= n; i++) cout << s1[i] << ' '; puts(""); 38 39 bool ok = 1; 40 for (int i = 0; i < n; i++) { 41 if (s1[i] != s2[i]) { 42 ok = 0; break; 43 } 44 } 45 if (ok) puts("Yes"); else puts("No"); 46 } 47 return 0; 48 } 代码君
题B
题意：给你B，告诉你A ^ B的每个位都为1，且A > B，最后输出A - B
题解：模拟题，水。
1 /*zhen hao*/ 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <queue> 6 #include <vector> 7 #include <stack> 8 #include <string> 9 #include <set> 10 #include <map> 11 #include <iostream> 12 #include <algorithm> 13 using namespace std; 14 15 #define lson l, m, rt*2 16 #define rson m + 1, r, rt*2+1 17 #define xx first 18 #define yy second 19 20 typedef pair<int,int> pii; 21 typedef long long ll; 22 23 const int maxn = 1e6 + 10; 24 int a[maxn], b[maxn], c[maxn]; 25 26 int main() { 27 // freopen("case.in", "r", stdin); 28 int T; 29 scanf("%d", &T); 30 while (T--) { 31 int m, n; 32 scanf("%d%d", &m, &n); 33 memset(b, 0, sizeof b); 34 for (int i = 1; i <= n; i++) { 35 int p; 36 scanf("%d", &p); 37 b[p] = 1; 38 } 39 for (int i = 1; i <= m; i++) { 40 a[i] = b[i] ^ 1; 41 } 42 int now = 0; 43 for (int i = 1; i <= m; i++) { 44 int temp = a[i] - now - b[i]; 45 if (temp < 0) now = 1; 46 else now = 0; 47 c[i] = (temp + 2) % 2; 48 } 49 while (!c[m]) --m; 50 for (int i = m; i >= 1; i--) printf("%d", c[i]); 51 puts(""); 52 } 53 return 0; 54 } 代码君
题C
题意：给你n个串，构造一个串使得这n个串都是这个串的子串，问你这个串的最短长度。
题解：容易想到dp[i][j]表示状态为i，然后以j为结尾的串的最短长度，但是有个问题，对于AB CD ABCDE，假如构造了ABCDE 显然CD不可能接在后面而是在中间已经被匹配了，所以对于这种情况只需要做个预处理，如果一个串是另一个串的子串，那么就可以无视掉这个串，最后定义一个cat[i][j]表示i串接在j串后面的多出来的长度，最后转移就是枚举作为末尾的是什么就好了。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 #define lson l, m, rt*2 6 #define rson m + 1, r, rt*2+1 7 #define xx first 8 #define yy second 9 10 typedef pair<int,int> pii; 11 typedef long long ll; 12 typedef unsigned long long ull; 13 14 const int maxn = 13; 15 char s[maxn][60], ns[maxn][60]; 16 int dp[1 << maxn][maxn], len[maxn], cat[maxn][maxn], n, ok[maxn]; 17 18 void split() { 19 for (int i = 0; i < n; i++) { 20 ok[i] = 1; 21 for (int j = 0; j < n; j++) 22 if (strstr(s[j], s[i]) != NULL && strcmp(s[i], s[j])) { 23 ok[i] = 0; break; 24 } 25 } 26 for (int i = 0; i < n; i++) if (ok[i]) 27 for (int j = 0; j < i; j++) if (ok[j]) 28 if (!strcmp(s[i], s[j])) ok[i] = 0; 29 int cnt = 0; 30 for (int i = 0; i < n; i++) if (ok[i]) 31 strcpy(s[cnt++], s[i]); 32 n = cnt; 33 } 34 35 void init() { 36 for (int i = 0; i < n; i++) len[i] = strlen(s[i]); 37 for (int i = 0; i < n; i++) 38 for (int j = 0; j < n; j++) { 39 if (i == j) { cat[i][j] = len[j]; continue; } 40 int p; 41 for (p = 0; p < len[i]; p++) { 42 int ok = 1; 43 for (int k = 0; p + k < len[i]; k++) 44 if (s[i][p + k] != s[j][k]) ok = 0; 45 if (ok) break; 46 } 47 cat[i][j] = len[j] - len[i] + p; 48 // cout << s[i] << ' ' << s[j] << ' ' << cat[i][j] << endl; 49 } 50 } 51 52 int main() { 53 // freopen("case.in", "r", stdin); 54 int T; 55 scanf("%d", &T); 56 while (T--) { 57 scanf("%d", &n); 58 memset(dp, 0x3f, sizeof dp); 59 for (int i = 0; i < n; i++) { 60 scanf("%s", s[i]); 61 } 62 split(); 63 init(); 64 int inf = dp[0][0]; 65 dp[0][0] = 0; 66 for (int i = 0; i < 1 << n; i++) 67 for (int j = 0; j < n; j++) if (dp[i][j] != inf) { 68 // cout << i << ' ' << j << ' ' << dp[i][j] << endl; 69 for (int k = 0; k < n; k++) if (!(i & (1 << k))) { 70 int v; 71 if (i == 0) v = len[k]; else v = cat[j][k]; 72 dp[i ^ (1 << k)][k] = min(dp[i ^ (1 << k)][k], dp[i][j] + v); 73 } 74 } 75 int ans = inf; 76 for (int i = 0; i < n; i++) ans = min(ans, dp[(1 << n) - 1][i]); 77 cout << ans << endl; 78 } 79 return 0; 80 } 代码君
题D
题意：给你一个矩阵v，vij > 0表示i可以到达j，然后可以走若干步，i可到达j那么就破坏这条边，问你最后有没有边剩下。
题解：本来是个传递闭包的，但是数据规模有点大，所以直接求个强连通，看最后强连通的数量是否为1即可。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 #define lson l, m, rt*2 6 #define rson m + 1, r, rt*2+1 7 #define xx first 8 #define yy second 9 10 typedef pair<int,int> pii; 11 typedef long long ll; 12 typedef unsigned long long ull; 13 14 const int maxn = 1e3 + 10; 15 int pre[maxn], lowlink[maxn], sccno[maxn], dfs_clock, scc_cnt, n; 16 vector<int> G[maxn]; 17 stack<int> S; 18 19 void dfs(int u) { 20 pre[u] = lowlink[u] = ++dfs_clock; 21 S.push(u); 22 for (int i = 0; i < (int)G[u].size(); i++) { 23 int v = G[u][i]; 24 if (!pre[v]) { 25 dfs(v); 26 lowlink[u] = min(lowlink[u], lowlink[v]); 27 } else if (!sccno[v]) { 28 lowlink[u] = min(lowlink[u], pre[v]); 29 } 30 } 31 if (lowlink[u] == pre[u]) { 32 ++scc_cnt; 33 for (;;) { 34 int x = S.top(); S.pop(); 35 sccno[x] = scc_cnt; 36 if (x == u) break; 37 } 38 } 39 } 40 41 void find_scc() { 42 dfs_clock = scc_cnt = 0; 43 memset(pre, 0, sizeof pre); 44 memset(sccno, 0, sizeof sccno); 45 for (int i = 0; i < n; i++) if (!pre[i]) 46 dfs(i); 47 } 48 49 int main() { 50 // freopen("case.in", "r", stdin); 51 int T; 52 cin >> T; 53 while (T--) { 54 scanf("%d", &n); 55 for (int i = 0; i < n; i++) G[i].clear(); 56 for (int i = 0; i < n; i++) 57 for (int j = 0; j < n; j++) { 58 int x; 59 scanf("%d", &x); 60 if (x > 0) G[i].push_back(j); 61 } 62 find_scc(); 63 if (scc_cnt != 1) puts("exists"); else puts("not exists"); 64 } 65 return 0; 66 } 代码君
题E
题意：给你n组物品，共有m元，每组物品有多个，但是只能买其中一个，问你最大能够买到物品的价值。
题解：很裸的分组背包问题，然而我并没有专门做过分组背包的问题，所以只能根据普通背包来水了，dp[i][j]表示前i组物品的有j元获得的最大价值，然后就有一个预处理，dp2[i][j]表示i组物品j元能得到的最大价值，如果dp2[1][3] = 6; dp2[1][4] = 5;显然这个4是多余的，所以就要把dp2[1][4]置为-1，代表不存在，这样就优化很多，然后就能够很快地跑出这道题。
1 /*zhen hao*/ 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <queue> 6 #include <vector> 7 #include <stack> 8 #include <string> 9 #include <set> 10 #include <map> 11 #include <iostream> 12 #include <algorithm> 13 using namespace std; 14 15 #define lson l, m, rt*2 16 #define rson m + 1, r, rt*2+1 17 #define xx first 18 #define yy second 19 20 typedef pair<int,int> pii; 21 typedef long long ll; 22 23 int dp[21][1010], dp2[21][1010]; 24 25 int main() { 26 // freopen("case.in", "r", stdin); 27 int T; 28 scanf("%d", &T); 29 while (T--) { 30 int n, m; 31 scanf("%d%d", &n, &m); 32 memset(dp2, -1, sizeof dp2); 33 memset(dp, 0, sizeof dp); 34 for (int i = 1; i <= n; i++) { 35 int c, w, v; 36 scanf("%d", &c); 37 for (int j = 0; j < c; j++) { 38 scanf("%d%d", &w, &v); 39 dp2[i][w] = max(dp2[i][w], v); 40 } 41 int pre = dp2[i][0]; 42 for (int j = 1; j <= m; j++) { 43 if (pre > dp2[i][j]) dp2[i][j] = -1; 44 pre = max(pre, dp2[i][j]); 45 } 46 } 47 for (int i = 1; i <= n; i++) { 48 for (int j = 1; j <= m; j++) if (dp2[i][j] != -1) { 49 for (int k = m; k >= j; k--) { 50 dp[i][k] = max(dp[i][k], dp[i - 1][k - j] + dp2[i][j]); 51 } 52 } 53 for (int j = 0; j <= m; j++) dp[i][j] = max(dp[i][j], dp[i - 1][j]); 54 } 55 printf("%d\n", dp[n][m]); 56 } 57 return 0; 58 } 代码君
题F
题意：略
题解：略
1 /*zhen hao*/ 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <queue> 6 #include <vector> 7 #include <stack> 8 #include <string> 9 #include <set> 10 #include <map> 11 #include <iostream> 12 #include <algorithm> 13 using namespace std; 14 15 #define lson l, m, rt*2 16 #define rson m + 1, r, rt*2+1 17 #define xx first 18 #define yy second 19 20 typedef pair<int,int> pii; 21 typedef long long ll; 22 23 const int maxn = 110; 24 25 struct Circle { 26 double x, y, r; 27 void input() { 28 scanf("%lf%lf%lf", &x, &y, &r); 29 } 30 bool check(Circle c) { 31 double dist = sqrt((x - c.x) * (x - c.x) + (y - c.y) * (y - c.y)); 32 return dist > r + c.r; 33 } 34 } c[110]; 35 36 int main() { 37 // freopen("case.in", "r", stdin); 38 int T; 39 scanf("%d", &T); 40 while (T--) { 41 int n; 42 scanf("%d", &n); 43 for (int i = 0; i < n; i++) c[i].input(); 44 int ans = 0; 45 for (int i = 0; i < n; i++) { 46 int ok = 1; 47 for (int j = 0; j < n; j++) if (i != j) { 48 if (!c[i].check(c[j])) { ok = 0; break; } 49 } 50 if (ok) ans++; 51 } 52 printf("%d\n", ans); 53 } 54 return 0; 55 } 代码君
题G
题意：告诉你a和b干活要x天，b和c干活要y天，a和c干活要z天，问你a b c独立干活要多少天？
题解：推公式，比较水。。。
1 代码君： 2 /*zhen hao*/ 3 #include <cstdio> 4 #include <cstring> 5 #include <cmath> 6 #include <queue> 7 #include <vector> 8 #include <stack> 9 #include <string> 10 #include <set> 11 #include <map> 12 #include <iostream> 13 #include <algorithm> 14 using namespace std; 15 16 #define lson l, m, rt*2 17 #define rson m + 1, r, rt*2+1 18 #define xx first 19 #define yy second 20 21 typedef pair<int,int> pii; 22 typedef long long ll; 23 24 int main() { 25 // freopen("case.in", "r", stdin); 26 int T; 27 cin >> T; 28 while (T--) { 29 double a, b, c; 30 cin >> a >> b >> c; 31 double y = (2 * a * b * c) / (b * c + a * c - a * b); 32 double x = a * y / (y - a); 33 double z = b * y / (y - b); 34 printf("%.0lf %.0lf %.0lf\n", x, y, z); 35 } 36 return 0; 37 } 代码君
题H
题意：给你n堆石头，每个有自己的数量s，然后合并两堆石头s1和s2的时候，花费是p（s1 + s2），每次只能合并相邻的两堆石头，问你最小花费。
题解：第一眼是经典的石头合并问题，但是数据规模好像有点不对，1e3这么大，要做优化，然而太渣了不会，参考一下题解：设pos[i][j]表示这堆石头获得最优值所移动的地方，然后这个怎么来呢，答案是从[pos[i][j - 1], pos[i + 1][j]]来，为什么一定是这个区间内呢？可以简易地想一下，前面都是考虑过的，所以只能从没考虑过的这个区间内去一个最优值。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 #define lson l, m, rt*2 6 #define rson m + 1, r, rt*2+1 7 #define xx first 8 #define yy second 9 10 typedef pair<int,int> pii; 11 typedef long long ll; 12 typedef unsigned long long ull; 13 14 const int maxn = 1e3 + 10; 15 ll dp[maxn][maxn], s[40 * maxn]; 16 int a[10], sum[maxn], size[maxn], pos[maxn][maxn]; 17 int n, m; 18 19 int main() { 20 // freopen("case.in", "r", stdin); 21 int T; 22 cin >> T; 23 while (T--) { 24 scanf("%d", &n); 25 for (int i = 1; i <= n; i++) scanf("%d", size + i); 26 scanf("%d", &m); 27 for (int i = 0; i <= m; i++) scanf("%d", a + i); 28 29 sum[0] = 0; 30 for (int i = 1; i <= n; i++) { 31 sum[i] = sum[i - 1] + size[i]; 32 } 33 34 for (int i = 1; i <= sum[n]; i++) { 35 ll base = 1, t = 0; 36 for (int j = 0; j <= m; j++) { 37 t += base * a[j]; 38 base *= i; 39 } 40 s[i] = t; 41 } 42 43 memset(dp, 0x3f, sizeof dp); 44 for (int i = 1; i <= n; i++) dp[i][i] = 0, pos[i][i] = i; 45 for (int l = 2; l <= n; l++) 46 for (int i = 1; i + l - 1 <= n; i++) { 47 int j = i + l - 1, p1 = pos[i][j - 1], p2 = pos[i + 1][j]; 48 for (int k = p1; k <= p2; k++) { 49 if (dp[i][j] > dp[i][k] + dp[k + 1][j] + s[sum[j] - sum[i - 1]]) { 50 pos[i][j] = k; 51 dp[i][j] = dp[i][k] + dp[k + 1][j] + s[sum[j] - sum[i - 1]]; 52 } 53 } 54 // cout << i << ' ' << j << ' ' << dp[i][j] << endl; 55 } 56 printf("%lld\n", dp[1][n]); 57 } 58 return 0; 59 } 代码君
题I
题意：给你一个多项式，然后问你对于集合{0，……，n-1}的子集用这个多项式得到的结果还是子集的有多少种情况？
题解：注意到这个多项式有一个modn的存在，也就是每个数的结果是0……n-1，假设0得到的是2,2得到的是3，3得到的0，那么这个集合{0,2,3}不就符合题意吗？想到这里我们已经可以知道用并查集来维护了，最后答案就是2的连通块的个数次幂。最后这道题卡常，所以尽量写少点函数，我*****。
1 /*zhen hao*/ 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <queue> 6 #include <vector> 7 #include <stack> 8 #include <string> 9 #include <set> 10 #include <map> 11 #include <iostream> 12 #include <algorithm> 13 using namespace std; 14 15 #define lson l, m, rt*2 16 #define rson m + 1, r, rt*2+1 17 #define xx first 18 #define yy second 19 20 typedef pair<int,int> pii; 21 typedef long long ll; 22 23 const int maxn = 1e4 + 10, mod = 1e9 + 7; 24 int fa[maxn], a[maxn], p[maxn]; 25 26 void init_set(int n) { 27 for (int i = 0; i < n; i++) fa[i] = i; 28 } 29 30 int find_set(int rt) { 31 if (rt == fa[rt]) return rt; 32 return fa[rt] = find_set(fa[rt]); 33 } 34 35 void union_set(int u, int v) { 36 int fu = find_set(u), fv = find_set(v); 37 if (fu == fv) return; 38 fa[fu] = fv; 39 } 40 41 int main() { 42 // freopen("case.in", "r", stdin); 43 int T; 44 scanf("%d", &T); 45 while (T--) { 46 int n, m; 47 scanf("%d%d", &n, &m); 48 for (int i = 0; i <= m; i++) scanf("%d", a + i); 49 init_set(n); 50 for (int i = 0; i < n; i++) { 51 int ret = 0, base = 1; 52 for (int j = 0; j <= m; j++) { 53 ret = (ret + 1ll * base * a[j]) % n; 54 base = 1ll * base * i % n; 55 } 56 p[i] = ret; 57 } 58 for (int i = 0; i < n; i++) { 59 union_set(i, p[i]); 60 } 61 int ans = 1; 62 for (int i = 0; i < n; i++) { 63 if (i == find_set(i)) ans = ans * 2 % mod; 64 } 65 printf("%d\n", ans); 66 } 67 return 0; 68 } 代码君
最后一题，并不会，哈哈~~
转载于:https://www.cnblogs.com/zhenhao1/p/5483983.html
