20160728 训练记录
1. 字符串复原
【题目大意】
给出n个长度为3的字符串,它们都是一个字串S的长度为3的连续字串,而且字串不包含除了这n个字符串以外的,长度为3的连续子串。求出字串S。
【题解】
hash+离散+欧拉路
# include <stdio.h> using namespace std; int n, T, rn; char st[3]; int head[666666], next[666666], to[666666], tot=0, in[666666], out[666666], hd1[666666]; int s[666666], sn=0, ls[666666]; bool used[666666]; int fc[666666], top, ans[666666], gg[666666], gn=0; int fa[666666]; // ============UNIONSET============== // inline int getf(int x) { return fa[x] == x ? x : fa[x] = getf(fa[x]); } // ============UNIONSET============== // // ============HASH============= // inline int hash(char a, char b) { return a * 256 + b; } char UNHASHa, UNHASHb; inline void unhash(int s) { UNHASHb = s % 256; UNHASHa = (s - UNHASHb)/256; } // ============HASH============= // inline void add(int a, int b) { ++tot; next[tot] = head[a]; head[a] = tot; to[tot] = b; out[a] ++; in[b] ++; used[tot] = 0; } // ===========FLEURY============= // inline void dfs(int x) { ans[++top] = x; for (int i=hd1[x]; i; i=next[i]) { if(!used[i]) { used[i] = 1; out[x] --; in[to[i]] --; hd1[x] = i; dfs(to[i]); break; } } } inline void fleury(int s) { top = 1; ans[top] = s; while(top > 0) { int can = 0; if(out[ans[top]] >= 1) can = 1; if(can == 0) { gg[++gn] = ans[top]; --top; } else { --top; dfs(ans[top+1]); } } } // ===========FLEURY============= // int main() { freopen("recover.in", "r", stdin); freopen("recover.out", "w", stdout); scanf("%d", &T); for (int I=1; I<=T; ++I) { tot=0; sn=0; gn=0; scanf("%d", &n); for (int i=1; i<=n+66; ++i) head[i] = in[i] = out[i] = 0, fa[i] = i; for (int i=1; i<=n; ++i) { scanf("%s", st); int front = hash(st[0], st[1]), back = hash(st[1], st[2]); // printf("%d %d\n", front, back); if(fc[front] != I) { fc[front] = I; s[++sn] = front; ls[front] = sn; // printf("***new front\n"); } if(fc[back] != I) { fc[back] = I; s[++sn] = back; ls[back] = sn; // printf("***new back\n"); } front = ls[front]; back = ls[back]; add(front, back); int fu = getf(front), fv = getf(back); fa[fu] = fv; // printf("edge: %d %d bh=%d\n", front, back, tot); } // for (int i=1; i<=sn; ++i) // printf("number = %d, in = %d, out = %d\n", i, in[i], out[i]); int start=-1, end=-1; bool no=0; for (int i=1; i<=sn; ++i) { hd1[i] = head[i]; if(in[i] - out[i] == 1) { if(end==-1) end=i; else { no=1; break; } } else if(in[i] - out[i] == -1) { if(start==-1) start=i; else { no=1; break; } } else if(in[i] != out[i]) { no = 1; break; } } for (int i=1; i<n; ++i) { if(getf(i) != getf(i+1)) { no = 1; break; } } if(no) { puts("NO"); continue; } // printf("start = %d, end = %d\n", start, end); if(start == -1 && end == -1) start = 1, end = 1; puts("YES"); gg[++gn] = start; fleury(start); for (int i=gn; i>=3; --i) { gg[i] = s[gg[i]]; unhash(gg[i]); printf("%c", UNHASHa); } gg[2] = s[gg[2]]; unhash(gg[2]); printf("%c%c", UNHASHa, UNHASHb); printf("\n"); } return 0; }
2. 好排列
【题目大意】
给出一个排列的大小关系(大于,小于),求排列方案数量
【题解】
f[i, j] 1...i的排列最后一个是j的满足要求的方案数量
随便转移一下前缀和搞搞
# include <stdio.h> # include <algorithm> # include <string.h> using namespace std; int T, n, m; long long f[2020][2020]; int s[2020]; bool t[2020]; const int MOD = 1e9+7; int main() { freopen("good.in", "r", stdin); freopen("good.out", "w", stdout); scanf("%d", &T); while(T--) { memset(f, 0, sizeof(f)); memset(t, 0, sizeof(t)); scanf("%d %d", &n, &m); for (int i=1; i<=m; ++i) { scanf("%d", &s[i]); t[s[i]+1] = 1; } f[1][1] = 1; for (int i=2; i<=n; ++i) { if(t[i] == 1) { long long sum = 0; for (int j=1; j<=i; ++j) { f[i][j] = sum; sum = (sum + f[i-1][j]) % MOD; } } else { long long sum = 0; for (int j=i; j>=1; --j) { sum = (sum + f[i-1][j]) % MOD; f[i][j] = sum; } } } long long ans = 0; for (int i=1; i<=n; ++i) ans = (ans + f[n][i]) % MOD; printf("%lld\n", ans); } return 0; }
3. 黑帮
【题目大意】同codeforces 690A1,A2
【题解】
随便考虑一下就行啦,见codeforces 690A 题解
# include <stdio.h> using namespace std; int T; int n, S; int main() { freopen("distribute.in", "r", stdin); freopen("distribute.out", "w", stdout); scanf("%d", &T); while(T--) { scanf("%d%d", &n, &S); if(S==1) { printf("%d\n", (n+1)/2); continue; } else { if(n&1) printf("%d\n", (n-1)/2); else { int s = 1; if(n <= 2) printf("%d\n", (n-1)/2); else { for (int i=1; i<=30; ++i) { s = s * 2; if((long long)s*2 > n) { printf("%d\n", (n-s)/2); break; } } } } } } return 0; }