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:

#include <cstdio> #include <cstring> #include <algorithm> 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; }
B:

#include <cstdio> #include <cstring>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; }
C:

#include <cstdio> #include <cstring> #include <algorithm> 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; }
D:

#include <cstdio> #include <cstring>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; }
E:

#include <cstdio> #include <cstring> #include <vector> using namespace std;const int N = 300005; int n, m, q, parent[N], len[N], vis[N], Maxu, Maxl; vector<int> 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; }

版權聲明：本文博主原創文章，博客，未經同意不得轉載。

轉載于:https://www.cnblogs.com/zfyouxi/p/4906193.html

總結

以上是生活随笔為你收集整理的Codeforces Round #260 (Div. 2)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。