「百度之星2017」程序设计大赛 初赛(B)
好气啊突然发现复赛的时候要军训
1001.Chess
f(i,j)表示最后一个棋放在(i,j)的方案
|
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 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define mod 1000000007 #define ll long long 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 T; int n, m; int f[1005][1005], g[1005][1005]; int main() { T = read(); while(T--) { memset(f, 0, sizeof(f)); memset(g, 0, sizeof(g)); n = read(); m = read(); if(n > m)swap(n, m); for(int i = 1; i <= m; i++) { f[1][i] = 1; g[1][i] = i; } for(int i = 2; i <= n; i++) for(int j = 1; j <= m; j++) { f[i][j] = g[i - 1][j - 1]; g[i][j] = (g[i][j - 1] + f[i][j]) % mod; } cout << g[n][m] << endl; } return 0; } |
1002.Factory
把集合分为元素个数大于\(m = \sqrt{n}\)，和小等于 m 的
对于元素个数很多的集合，每个集合 bfs 一次，预处理出到其它集合的距离
如果询问的两个集合的元素个数都比较少，建一下虚树 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 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define mod 1000000007 #define inf 1000000000 #define ll long long 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; } bool vis[100005]; int T; int n, m, Q, id, cnt; int last[100005]; int mp[100005], q[100005], dis[100005]; int dep[100005], D[100005]; vector<int>G[100005], B[100005]; int ans[205][100005]; int fa[100005][17]; map<int, int>ANS[100005]; struct data{ int to, next, v; }e[200005]; int lca(int x, int y) { if(dep[x] < dep[y])swap(x, y); int d = dep[x] - dep[y]; for(int i = 0; i <= 16; i++) if((1 << i) & d)x = fa[x][i]; for(int i = 16; i >= 0; i--) if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i]; if(x == y)return x; return fa[x][0]; } void insert(int u, int v, int w) { e[++cnt].to = v; e[cnt].next = last[u]; e[cnt].v = w; last[u] = cnt; e[++cnt].to = u; e[cnt].next = last[v]; e[cnt].v = w; last[v] = cnt; } void bfs(int x) { memset(vis, 0, sizeof(vis)); memset(dis, 0, sizeof(dis)); if(!mp[x])mp[x] = ++id; int now = mp[x], l = 0, r = 0; for(int i = 0; i < G[x].size(); i++) { q[r] = G[x][i]; vis[G[x][i]] = 1; r++; } while(l <= r) { int u = q[l]; l++; for(int i = 0; i < B[u].size(); i++) ans[now][B[u][i]] = min(ans[now][B[u][i]], dis[u]); for(int i = last[u]; i; i = e[i].next) if(!vis[e[i].to]) { vis[e[i].to] = 1; dis[e[i].to] = dis[u] + e[i].v; q[r] = e[i].to; r++; } } } void dfs(int x) { for(int i = 1; i <= 16; i++) fa[x][i] = fa[fa[x][i - 1]][i - 1]; for(int i = last[x]; i; i = e[i].next) if(e[i].to != fa[x][0]) { fa[e[i].to][0] = x; D[e[i].to] = D[x] + e[i].v; dep[e[i].to] = dep[x] + 1; dfs(e[i].to); } } int getdis(int x, int y) { int f = lca(x, y); return D[x] + D[y] - 2 * D[f]; } int main() { T = read(); while(T--) { cnt = id = 0; memset(last, 0, sizeof(last)); memset(mp, 0, sizeof(mp)); memset(ans, 127, sizeof(ans)); for(int i = 1; i <= 100000; i++) { G[i].clear(); B[i].clear(); ANS[i].clear(); } n = read(); m = read(); for(int i = 1; i < n; i++) { int u = read(), v = read(), w = read(); insert(u, v, w); } for(int i = 1; i <= m; i++) { int x, y; x = read(); for(int j = 1; j <= x; j++) { y = read(); G[i].push_back(y); B[y].push_back(i); } } for(int i = 1; i <= m; i++) if(G[i].size() >= 500) bfs(i); dfs(1); Q = read(); for(int i = 1; i <= Q; i++) { int x = read(), y = read(); if(G[y].size() > G[x].size())swap(x, y); if(G[x].size() >= 500) { int now = mp[x]; printf("%d\n", ans[now][y]); } else { if(ANS[x][y]) printf("%d\n", ANS[x][y] - 1); else { int ans = inf; for(int p = 0; p < G[x].size(); p++) for(int q = 0; q < G[y].size(); q++) ans = min(ans, getdis(G[x][p], G[y][q])); ANS[x][y] = ans + 1; printf("%d\n", ans); } } } } return 0; } |
1005.度度熊的交易计划
预处理最短路，枚举n^2点对建图费用流
|
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 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define mod 1000000007 #define ll long long 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 T; int n, m, cnt, ans; int last[1005], q[1005], dis[1005]; int a[505], b[505], c[505], d[505]; int D[505][505]; struct edge{ int to,next,v,c; }e[200005]; bool mark[1005],inq[1005]; void insert(int u,int v,int w,int c) { e[++cnt]=(edge){v,last[u],w,c};last[u]=cnt; e[++cnt]=(edge){u,last[v],0,-c};last[v]=cnt; } bool spfa() { for(int i=0;i<=T;i++)dis[i]=-inf; int head=0,tail=1; q[0]=T;dis[T]=0; while(head!=tail) { int now=q[head];head++;if(head==1005)head=0; inq[now]=0; for(int i=last[now];i;i=e[i].next) if(e[i^1].v&&dis[now]-e[i].c>dis[e[i].to]) { dis[e[i].to]=dis[now]-e[i].c; if(!inq[e[i].to]) { q[tail++]=e[i].to; if(tail==1005)tail=0; inq[e[i].to]=1; } } } return dis[0]>0; } int dfs(int x,int f) { mark[x]=1; if(x==T)return f; int w,used=0; for(int i=last[x];i;i=e[i].next) if(e[i].v&&dis[x]-e[i].c==dis[e[i].to]&&!mark[e[i].to]) { w=dfs(e[i].to,min(e[i].v,f-used)); e[i].v-=w;e[i^1].v+=w; ans+=e[i].c*w;used+=w;if(used==f)return f; } return used; } void zkw() { while(spfa()) { for(int i=0;i<=T;i++)mark[i]=0; mark[T]=1; while(mark[T]) mark[T]=0,dfs(0,inf); } } int main() { while(scanf("%d%d", &n, &m) != EOF) { T = 2 * n + 1; cnt = 1; memset(last, 0, sizeof(last)); for(int i = 1; i <= n; i++) a[i] = read(), b[i] = read(), c[i] = read(), d[i] = read(); memset(D, 127 / 2, sizeof(D)); for(int i = 1; i <= n; i++) D[i][i] = 0; for(int i = 1; i <= m; i++) { int u = read(), v = read(), w = read(); D[u][v] = D[v][u] = min(D[u][v], w); } for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) D[i][j] = min(D[i][j], D[i][k] + D[k][j]); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(D[i][j] + a[i] < c[j]) { insert(i, j + n, inf, c[j] - D[i][j] - a[i]); } for(int i = 1; i <= n; i++) { insert(0, i, b[i], 0); insert(i + n, T, d[i], 0); } ans = 0; zkw(); cout << ans << endl; } return 0; } |
1006.小小粉丝度度熊
先处理出互不相交的区间
枚举答案的左边第一个区间，最后一个区间是单调往右的
|
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 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define mod 1000000007 #define ll long long 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, top; int l[100005], r[100005], sum[100005]; struct data{ int l, r, sum; }a[100005], b[100005]; bool cmp(data a, data b) { return a.l < b.l; } int main() { while(scanf("%d%d", &n, &m) != EOF) { top = 0; for(int i = 1; i <= n; i++) a[i].l = read(), a[i].r = read(); sort(a + 1, a + n + 1, cmp); int l = 0, r = 0; for(int i = 1; i <= n; i++) { if(a[i].l <= r)r = max(r, a[i].r + 1); else { if(r)b[++top] = (data){l, r - 1, r - l}; l = a[i].l, r = a[i].r + 1; } } b[++top] = (data){l, r - 1, r - l}; for(int i = 1; i <= top; i++) sum[i] = sum[i - 1] + b[i].sum; r = 1; int ans = 0; for(int i = 1; i <= top; i++) { while(sum[r + 1] - sum[i - 1] + m >= b[r + 1].r - b[i].l + 1 && r + 1 <= top) r++; int t = (b[r].r - b[i].l + 1) - (sum[r] - sum[i - 1]); ans = max(ans, (b[r].r - b[i].l + 1) + m - t); } cout << ans << endl; } return 0; } |
计数器 9322845
OI 课件=>
OI 课件=>
上课偶遇大神，小人我口出狂言，谢罪，谢罪。
搞不懂你们学校这时候军训。
所以复赛就没有参加嘛