程序设计实习实验班2017作业(算法 作业19, 20, 21)
一些以前做过的就不再贴了
A Funny Stone Game
发现每一堆的每个石子之间都是相互独立的
|
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 |
#include <cmath> #include <ctime> #include <queue> #include <string> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #define inf 100000 using namespace std; int n; int s[1005]; int sg[25]; int pre(int x) { if(sg[x] != -1)return sg[x]; if(x == n) sg[x] = 0; else { bool vis[505] = {0}; for(int i = x + 1; i <= n; i++) for(int j = i; j <= n; j++) vis[pre(i) ^ pre(j)] = 1; for(int i = 0; ; i++) if(!vis[i]) { sg[x] = i; break; } } return sg[x]; } int main() { int T = 0; while(scanf("%d", &n)) { if(n == 0)break; T++; printf("Game %d: ", T); memset(sg, -1, sizeof(sg)); pre(1); int ans = 0; for(int i = 1; i <= n; i++) { scanf("%d", &s[i]); if(s[i] & 1) ans ^= sg[i]; } for(int i = 1; i <= n; i++) if(s[i]) for(int j = i + 1; j <= n; j++) for(int k = j; k <= n; k++) if(ans == (sg[i] ^ sg[j] ^ sg[k])) { printf("%d %d %d\n", i - 1, j - 1, k - 1); ans = -1; } if(ans == 0)puts("-1 -1 -1"); } return 0; } |
nnim
n 阶 nim 和，在二进制下，每一位求和后对 (n+1) 取模
|
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 |
#include <cmath> #include <ctime> #include <queue> #include <string> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #define inf 100000 using namespace std; int T, n, m; int a[100005]; int cnt[30]; void add(int x) { for(int i = 0; i < 30; i++) if(x & (1 << i)) cnt[i]++; } int main() { scanf("%d", &T); while(T--) { scanf("%d%d", &m, &n); memset(cnt, 0, sizeof(cnt)); for(int i = 1; i <= m; i++) scanf("%d", &a[i]); for(int i = 1; i <= m; i++) add(a[i]); bool flag = 0; for(int i = 0; i < 30; i++) if(cnt[i] % (n + 1) != 0) flag = 1; if(flag)puts("Yes"); else puts("No"); } return 0; } |
一个水水的序列
在建操作树的过程中就能顺便维护信息
每次新加入节点的时候维护一下这个点的倍增数组，询问的时候直接向上倍增
|
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 |
#include <cmath> #include <ctime> #include <queue> #include <string> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; int lastans; int T, n, cnt; int anc[100005][17]; int rt[100005], val[100005], dep[100005]; int main() { scanf("%d", &T); while(T--) { lastans = 0, cnt = 0; scanf("%d", &n); int a, b, id = 0; while(n--) { scanf("%d%d", &a, &b); a ^= lastans, b ^= lastans; if(a == 1) { id++; rt[id] = ++cnt; val[cnt] = b; anc[cnt][0] = rt[id - 1]; dep[cnt] = dep[rt[id - 1]] + 1; for(int j = 1; j <= 16; j++) anc[cnt][j] = anc[anc[cnt][j - 1]][j - 1]; } if(a == 2) { id++; rt[id] = rt[id - b - 1]; } if(a == 3) { int x = rt[id]; for(int j = 0; j <= 16; j++) if((1 << j) & (dep[x] - b)) x = anc[x][j]; lastans = val[x]; printf("%d\n", lastans); } } } return 0; } |
「poj1523」SPF
求割点，并且求删去割点后的连通分量个数
|
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 |
#include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 0x7fffffff #define ll long long using namespace std; int n, ind, tes; int low[1005], dfn[1005], blo[1005]; vector<int> e[1005]; int tarjan(int x) { low[x] = dfn[x] = ++ind; for(int i = 0; i < e[x].size(); i++) if(!dfn[e[x][i]]) { tarjan(e[x][i]); low[x] = min(low[x], low[e[x][i]]); if(dfn[x] <= low[e[x][i]]) blo[x]++; } else low[x] = min(low[x], dfn[e[x][i]]); } int main() { int x, y; while(scanf("%d", &x) != EOF) { if(x == 0)break; n = 0; memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); scanf("%d", &y); n = max(n, max(x, y)); e[x].push_back(y); e[y].push_back(x); while(scanf("%d", &x) && x) { scanf("%d", &y); e[x].push_back(y); e[y].push_back(x); n = max(n, max(x, y)); } for(int i = 1; i <= n; i++)blo[i] = 1; blo[1] = 0; tarjan(1); printf("Network #%d\n", ++tes); bool flag = 0; for(int i = 1; i <= n; i++) if(blo[i] > 1) { printf(" SPF node %d leaves %d subnets\n",i , blo[i]); flag = 1; } if(!flag)printf(" No SPF nodes\n"); puts(""); for(int i = 1; i <= n; i++) e[i].clear(); } return 0; } |
BZOJ 4006: [JLOI2015]管道连接 Channel
求斯坦纳树森林，先预处理出任意子集的斯坦纳树，其实就是一般的斯坦纳树做法
然后状压 dp，具体见注释
|
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 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long #define pa pair<int,int> using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n, m, p, cnt; bool vis[1005]; int last[1005]; int c[15], d[15]; int f[1005][1024], cs[1024], g[1024]; struct data{ int to, next, v; }e[1000005]; void insert(int u, int v, int w) { e[++cnt].to = v; e[cnt].next = last[u]; last[u] = cnt; e[cnt].v = w; e[++cnt].to = u; e[cnt].next = last[v]; last[v] = cnt; e[cnt].v = w; } priority_queue<pa, vector<pa>, greater<pa> >q; void dijkstra(int st) { memset(vis, 0, sizeof(vis)); for(int i = 1; i <= n; i++) if(f[i][st] < inf)q.push(make_pair(f[i][st], i)); while(!q.empty()) { int now = q.top().second; q.pop(); if(vis[now])continue; vis[now] = 1; for(int i = last[now]; i; i = e[i].next) if(f[now][st] + e[i].v < f[e[i].to][st]) { f[e[i].to][st] = f[now][st] + e[i].v; q.push(make_pair(f[e[i].to][st], e[i].to)); } } } void solve() { memset(f, 127 / 2, sizeof(f)); memset(g, 127 / 2, sizeof(g)); memset(cs, 0, sizeof(cs)); for(int i = 1; i <= n; i++) f[i][0] = 0; for(int i = 1; i <= p; i++) f[d[i]][1 << (i - 1)] = 0; for(int S = 1; S < (1 << p); S++) //S 为情报站状态 { for(int i = 1; i <= n; i++) for(int st = (S - 1) & S; st; st = (st - 1) & S) f[i][S] = min(f[i][S], f[i][st] + f[i][S - st]); dijkstra(S); } for(int S = 1; S < 1024; S++) //S 为频道状态 { for(int i = 1; i <= p; i++) if((1 << (c[i] - 1)) & S) cs[S] += (1 << (i - 1)); for(int i = 1; i <= n; i++) g[S] = min(g[S], f[i][cs[S]]); } //将 S 中的频道建成一棵斯坦纳树，至少要包含情报站 cs[S] for(int S = 1; S < 1024; S++) //S 为频道状态 for(int st = (S - 1) & S; st; st = (st - 1) & S) g[S] = min(g[S], g[st] + g[S - st]); } int main() { while(1) { n = read(), m = read(), p = read(); if(n == 0)break; cnt = 0; memset(last, 0, sizeof(last)); for(int i = 1; i <= m; i++) { int u = read(), v = read(), w = read(); insert(u, v, w); } for(int i = 1; i <= p; i++) c[i] = read(), d[i] = read(); solve(); printf("%d\n", g[1023]); } return 0; } |
更大的轮状病毒
得到递推式后矩阵乘法
|
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<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long #define pa pair<int,int> #define mod 10007 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll n; struct M{ int a[3][3]; M(){ memset(a, 0, sizeof(a)); } M operator*(M b){ M c; for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) { for(int k = 0; k < 3; k++) c.a[i][j] += a[i][k] * b.a[k][j]; c.a[i][j] = (c.a[i][j] % mod + mod) % mod; } return c; } }; int main() { while(scanf("%lld", &n) != EOF) { if(n == 1) { puts("1"); continue; } if(n == 2) { puts("5"); continue; } n -= 2; M a, tr, ans; a.a[0][0] = 3; a.a[0][1] = -1; a.a[0][2] = 2; a.a[1][0] = 1; a.a[2][2] = 1; for(int i = 0; i < 3; i++) tr.a[i][i] = 1; for(ll i = n; i; i >>= 1, a = a * a) if(i & 1)tr = tr * a; ans.a[0][0] = 5; ans.a[1][0] = 1; ans.a[2][0] = 1; ans = tr * ans; printf("%d\n", ans.a[0][0]); } return 0; } |
Mobile phones
二维树状数组模板
|
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 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long #define pa pair<int,int> #define mod 10007 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; int t[2005][2005]; void add(int x, int y, int v) { for(int i = x; i <= n; i += i & -i) for(int j = y; j <= n; j += j & -j) t[i][j] += v; } int query(int x, int y) { int ans = 0; for(int i = x; i; i -= i & -i) for(int j = y; j; j -= j & -j) ans += t[i][j]; return ans; } int main() { int opt, x, y, l, r, v; opt = read(); n = read(); memset(t, 0, sizeof(t)); while(1) { opt = read(); if(opt == 3)break; if(opt == 1) { x = read(), y = read(), v = read(); add(x + 1, y + 1, v); } else { x = read(), y = read(), l = read(), r = read(); printf("%d\n", query(l + 1, r + 1) - query(l + 1, y) - query(x, r + 1) + query(x, y)); } } return 0; } |
Subscribe
计数器 9321489
OI 课件=>
OI 课件=>