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 excludantif(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

簡單粗暴?點擊打開鏈接

F.ZOJ 3671 Japanese Mahjong III
簡單模擬

#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

I.ZOJ 3674 Search in the Wiki
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;
}