首页 > 代码库 > ZOJ Monthly, November 2012
ZOJ Monthly, November 2012
A.ZOJ 3666 Alice and Bob
组合博弈,SG函数应用#include<vector> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 10000 + 100; int SG[maxn]; vector<int> g[maxn]; int mex(int u) { //minimal excludant if(SG[u]!=-1) return SG[u]; int i; bool vis[maxn]; memset(vis, 0, sizeof vis ); for(i=0; i<g[u].size(); ++i) { vis[mex(g[u][i])] = true; } for(i=0; vis[i]; ++i); return SG[u] = i; } int main() { int n, c, x, q, m; int cas= 1; while(~scanf("%d", &n)) { for(int i=0; i<=n; ++i) g[i].clear(); for(int i=1; i<n; ++i) { scanf("%d", &c); while(c--) { scanf("%d", &x); g[i].push_back(x); } } memset(SG, -1, sizeof SG ); printf("Case %d:\n", cas++); scanf("%d", &q); while(q--) { scanf("%d", &m); int ans = 0; while(m--) { scanf("%d", &x); ans ^= mex(x); } if(ans) puts("Alice"); else puts("Bob"); } } return 0; }
C.ZOJ3668 Launching the Spacecraft
约束条件 :f[i] 表示前i块石头的能量总和。
f[R]-f[L-1]>=A
f[R]-f[L-1]<=B
f[i]-f[i-1]<=10000
f[i]-f[i-1]>=-10000
关于为什么是字典序。
。。
在网上看到例如以下:
总结了一下。差分约束系统有两个解决方式:
1, 最短路模型。 全部的约束条件都是形如f(X)<=f(Y)+B。B正负不分。这样在有向图中addEdge(Y, X, B)这条边。这样依据最短路求解的性质我们能够得到X的最短路值满足了全部的f(X)<=f(Yi)+Bi,而且使得某个(某些)f(X)=f(Yk)+Bk。本来是f(X)<=f(Yk)+Bk的,如今都f(X)=f(Yk)+Bk了。因此利用最短路模型求出来的f值是最大值。
2。最长路模型。全部的约束条件都是形如f(X)>=f(Y)+B,B正负不分。这样在有向图中addEdge(Y, X, B)这条边,这样依据最长路求解的性质我们能够得到X的最长路值满足了全部的f(X)>=f(Yi)+Bi。而且使得某个(某些)f(X)=f(Yk)+Bk。本来是f(X)>=f(Yk)+Bk的,如今仅仅是f(X)=f(Yk)+Bk了,因此利用最长路模型求出来的f值是最小值。
回归到本题,全部值求是最大值。sum[0]和sum[n]确定的,于是能够得到是字典序最大。
#include<bits/stdc++.h> using namespace std; const int maxn = 1010; const int maxm = 40000 + 100; const int INF = 1e9; struct Edge{ int to, next; int w; }edge[maxm]; int head[maxn], tot; void init() { tot = 0; memset(head, -1, sizeof head ); } void addedge(int u, int v, int w){ edge[tot].to = v; edge[tot].next = head[u]; edge[tot].w = w; head[u] = tot++; } bool vis[maxn]; int cnt[maxn]; int dist[maxn]; bool spfa(int n) { memset(vis, false, sizeof vis ); for(int i=0; i<=n; ++i) dist[i] = INF; memset(cnt, 0, sizeof cnt ); queue<int> q; q.push(0); vis[0] = true; cnt[0] = 1; dist[0] = 0; while(!q.empty()){ int u = q.front(); q.pop(); vis[u] = false; for(int i=head[u]; i!=-1; i=edge[i].next){ int v = edge[i].to; int w = edge[i].w; if(dist[v] > dist[u] + w){ dist[v] = dist[u] + w; if(!vis[v]){ vis[v] = true; q.push(v); if(++cnt[v] > n+1) return false; } } } } return true; } int main() { int n, m; while(~scanf("%d%d", &n, &m)){ init(); for(int i=1; i<=n; ++i){ addedge(i-1, i, 10000); addedge(i, i-1, 10000); } int l, r, a, b; while(m--){ scanf("%d%d%d%d", &l, &r, &a, &b); addedge(l-1, r, b); addedge(r, l-1, -a); } if(!spfa(n)){ printf("The spacecraft is broken!\n"); continue; } for(int i=1; i<=n; ++i){ printf("%d", dist[i]-dist[i-1]); if(i<n) printf(" "); else printf("\n"); } } return 0; }
D.ZOJ 3669 Japanese Mahjong I
简单粗暴 点击打开链接
简单模拟
#include<bits/stdc++.h> using namespace std; const int maxn = 9; int z[maxn+10], s[maxn+10], p[maxn+10], m[maxn+10]; char str[100]; bool seven() { int cnt = 0; for(int i=1; i<=9; ++i) { if(z[i]==2) cnt++; if(s[i]==2) cnt++; if(p[i]==2) cnt++; if(m[i]==2) cnt++; } return cnt==7; } bool thirteen() { int cnt = m[1] + m[9] + p[1] + p[9] + s[1] + s[9] + z[1] + z[2] + z[3] + z[4] + z[5] + z[6] + z[7]; if(m[1]>=1&&m[9]>=1&&p[1]>=1&&p[9]>=1&&s[1]>=1&&s[9]>=1&&z[1]>=1&&z[2]>=1&&z[3]>=1&&z[4]>=1 &&z[5]>=1&&z[6]>=1&&z[7]>=1){ return cnt == 14; } return 0; } int main() { while(~scanf("%s", str)) { int n = strlen(str); memset(z, 0, sizeof z ); memset(s, 0, sizeof s ); memset(p, 0, sizeof p ); memset(m, 0, sizeof m ); for(int i=0; i<n; i+=2) { int num = str[i] - ‘0‘; if(str[i+1]==‘z‘) z[num]++; else if(str[i+1]==‘s‘) s[num]++; else if(str[i+1]==‘m‘) m[num]++; else if(str[i+1]==‘p‘) p[num]++; } if(seven()) { printf("Seven Pairs\n"); } else if(thirteen()) { printf("Thirteen Orphans\n"); } else printf("Neither!\n"); } return 0; }
G.ZOJ 3672 Gao The Sequence
1、每一次操作,总共减去2个delta,是个偶数。所以最后的增量和一定是偶数。
2、假设存在2*(a[i]-b[i])>sum,也是不行的。由于这样的情况下。a数组要减去2*(a[i]-b[i]),当中a[i]要减去(a[i]-b[i]),其它数也要减去和为(a[i]-b[i])的量。但明显增量不足,所以不行
#include<bits/stdc++.h> using namespace std; typedef long long LL; int main () { int n; while (~scanf("%d",&n)) { LL maxx = 0, sum = 0; for (int i=1; i<=n; i++) { LL a,b; scanf("%I64d%I64d",&a, &b); maxx=max(maxx,a-b); sum+=a-b; } cout<<sum<<" "<<maxx<<endl; if ((sum%2==1) ||maxx*2>sum) printf("NO\n"); else printf("YES\n"); } return 0; }
H.ZOJ 3673 1729
STL应用set、map
#include<bits/stdc++.h> using namespace std; const int maxn = 100 + 10; set<string> S[maxn]; map<string,int> M; char buf[1001], str[1001]; vector<int> vc; int n, m; int main() { while(~scanf("%d", &n)) { M.clear(); string ss; for(int i=0; i<n; ++i) { S[i].clear(); cin>>ss; M[ss] = i; getchar(); gets(buf); char *p = strtok(buf," "); while(p) { sscanf(p, "%s", str ); S[i].insert(string(str)); p = strtok(NULL, " "); } } scanf("%d", &m); getchar(); while(m--) { vc.clear(); gets(buf); char *p = strtok(buf, " "); while(p) { sscanf(p, "%s", str ); vc.push_back( M[string(str)] ); p = strtok(NULL, " "); } vector<string> ans; for(set<string>::iterator it = S[vc[0]].begin(); it!=S[vc[0]].end(); ++it) { string tmp = *it; bool found = true; for(int i=1; i<vc.size(); ++i) { if(S[vc[i]].find(tmp) == S[vc[i]].end()) { found = false; break; } } if(found) ans.push_back(tmp); } sort(ans.begin(), ans.end()); if(ans.size()==0) puts("NO"); else { for(int i=0; i<ans.size(); ++i) { cout<<ans[i]; if(i<ans.size()-1) cout<<" "; else cout<<endl; } } } } return 0; }
J.ZOJ 3675 Trim the Nails
bfs:每次用没实用过的方式去剪指甲,直到结果为0,即指甲剪光了就结束
状态压缩DP: 状态:dp[1<<M-1],结果是dp[0]。状态转移即 枚举指甲剪剪的位置和顺序。然后产生新状态。
#include<bits/stdc++.h> using namespace std; const int INF = 1e9; int dp[1<<21]; int main() { int n, m; char s[20]; while(~scanf("%d", &n)) { scanf("%s", s); scanf("%d", &m); int clr = 0, rclr = 0; for(int i=0; i<n; ++i) { clr = (clr<<1) + (s[i]==‘*‘); rclr = (rclr<<1) + (s[n-i-1]==‘*‘); } for(int i=0; i<=(1<<m); ++i) dp[i] = INF; dp[(1<<m)-1] = 0; for(int i=(1<<m)-1; i>=0; --i) if(dp[i]!=INF) { for(int j=0; j<m; ++j) { dp[i& (~(clr<<j))] = min(dp[i&(~(clr<<j))], dp[i] + 1); dp[i& (~(rclr<<j))] = min(dp[i&(~(rclr<<j))], dp[i]+1); dp[i& (~(clr>>j))] = min(dp[i&(~(clr>>j))], dp[i] + 1); dp[i& (~(rclr>>j))] = min(dp[i&(~(rclr>>j))], dp[i]+1); } } if(dp[0]!=INF) { printf("%d\n", dp[0]); } else printf("-1\n"); } return 0; }
ZOJ Monthly, November 2012
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。