Codeforces Round #260 (Div. 2)
A：水题，事实上仅仅要推断有没有一个ai != bi就可以，由于都保证是1 - n的不相等数字
B：找到2 3 4的循环节，发现仅仅有4和2，于是把大数%4，%2，在依据循环节去计算就可以
C：dp，dp[i][0]表示不拿i数字。dp[i][1]表示拿i数字。状态转移为
dp(i,0)=max(dp(i−1,0),dp(i−1,1)),dp(i,1)=dp(i−1,0)+val[i]D：Trie+博弈。依据字符串建Trie，然后两遍dfs找出能控制自己必胜，和能控制自己必败的状态，假设能控制必胜又能控制必败就赢了，假设仅仅能控制必胜，那么假设k为奇数也是赢，剩下都是输
E：并查集+贪心，对于每一个集合，两遍DFS能找出最长链，然后每次合并操作的时候，肯定是拿两遍的最长链中点去合并是最优的，这样带个权值len表示集合最长长度就可以
代码：
A:
#includeB:#include #include using namespace std;const int N = 100005;int n, a[N], b[N];bool judge() { for (int i = 0; i < n; i++) if (a[i] != b[i]) return true; return false;}int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d%d", &a[i], &b[i]); if (judge()) printf("Happy Alex\n"); else printf("Poor Alex\n"); return 0;}
#includeC:#include const int N = 100005;char str[N];int num[5][10];int main() { num[2][0] = 1; num[2][1] = 2; num[2][2] = 4; num[2][3] = 3; num[3][0] = 1; num[3][1] = 3; num[3][2] = 4; num[3][3] = 2; num[4][0] = 1; num[4][1] = 4; scanf("%s", str); if (strcmp(str, "0") == 0) { printf("4\n"); return 0; } int yu = 0; for (int i = 0; i < strlen(str); i++) { yu = (yu * 10 + str[i] - '0') % 4; } int sb = yu % 2; int ans = (1 + num[2][yu] + num[3][yu] + num[4][sb]) % 5; printf("%d\n", ans); return 0;}
#includeD:#include #include using namespace std;const int N = 100005;int n;long long vis[N], dp[N][2];int main() { int a; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a); vis[a]++; } for (long long i = 1; i <= 100000; i++) { dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]); dp[i][1] = max(dp[i][1], dp[i - 1][0] + vis[i] * i); } printf("%lld\n", max(dp[100000][0], dp[100000][1])); return 0;}
#includeE:#include const int MAXNODE = 100005;const int SIGMA_SIZE = 26;struct Trie { int ch[MAXNODE][SIGMA_SIZE]; int win[MAXNODE], lose[MAXNODE]; int sz; void init() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); } int idx(char c) {return c - 'a';} void insert(char *str) { int n = strlen(str); int u = 0; for (int i = 0; i < n; i++) { int c = idx(str[i]); if (!ch[u][c]) { memset(ch[sz], 0, sizeof(ch[sz])); ch[u][c] = sz++; } u = ch[u][c]; } } int dfs1(int u) { win[u] = 0; for (int i = 0; i < SIGMA_SIZE; i++) { int v = ch[u][i]; if (!v) continue; int tmp = dfs1(v); if (!tmp) win[u] = 1; } return win[u]; } int dfs2(int u) { lose[u] = 0; int bo = 1; for (int i = 0; i < SIGMA_SIZE; i++) { int v = ch[u][i]; if (!v) continue; bo = 0; int tmp = dfs2(v); if (!tmp) lose[u] = 1; } if (bo) return lose[u] = 1; return lose[u]; } void getsg() { dfs1(0); dfs2(0); }};const int N = 100005;int n, k;char str[N];Trie gao;bool judge() { gao.init(); scanf("%d%d", &n, &k); for (int i = 0; i < n; i++) { scanf("%s", str); gao.insert(str); } gao.getsg(); if (gao.win[0] && gao.lose[0]) return true; if (gao.win[0]) { if (k&1) return true; return false; } return false;}int main() { if (judge()) printf("First\n"); else printf("Second\n"); return 0;}
#include#include #include using namespace std;const int N = 300005;int n, m, q, parent[N], len[N], vis[N], Maxu, Maxl;vector g[N];void dfs(int u, int h, int p) { vis[u] = 1; int flag = 1; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (v == p) continue; flag = 0; dfs(v, h + 1, u); } if (flag) { if (h > Maxl) { Maxl = h; Maxu = u; } }}int find(int x) { return x == parent[x] ? x : parent[x] = find(parent[x]);}int main() { scanf("%d%d%d", &n, &m, &q); for (int i = 1; i <= n; i++) parent[i] = i; int u, v; while (m--) { scanf("%d%d", &u, &v); int pu = find(u); int pv = find(v); parent[pu] = pv; g[u].push_back(v); g[v].push_back(u); } for (int i = 1; i <= n; i++) { if (vis[i]) continue; Maxl = -1; dfs(i, 0, 0); Maxl = -1; dfs(Maxu, 0, 0); len[find(i)] = Maxl; } int c, a, b; while (q--) { scanf("%d", &c); if (c == 1) { scanf("%d", &a); printf("%d\n", len[find(a)]); } else { scanf("%d%d", &a, &b); int pa = find(a); int pb = find(b); if (pa != pb) { parent[pa] = pb; len[pb] = max(len[pa], max(len[pb], (len[pb] + 1) / 2 + (len[pa] + 1) / 2 + 1)); } } } return 0;}
版权声明：本文博主原创文章，博客，未经同意不得转载。