A.ZOJ 3666 Alice and Bob

组合博弈，SG函数应用

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int maxn = 10000 + 100;int SG[maxn];vector
         
           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
         
        
       
      
     

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

D.ZOJ 3669 Japanese Mahjong I

简单粗暴 

F.ZOJ 3671 Japanese Mahjong III

简单模拟

#include
     
      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
     

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
     
      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) printf("NO\n");        else printf("YES\n");    }    return 0;}
        
       
      
     

H.ZOJ 3673  1729

I.ZOJ 3674 Search in the Wiki

STL应用set、map

#include
     
      using namespace std;const int maxn = 100 + 10;set
      
        S[maxn];map
       
         M;char buf[1001], str[1001];vector
        
          vc;int n, m;int main() {    while(~scanf("%d", &n)) {        M.clear();        string ss;        for(int i=0; i
         
          >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
          
            ans; for(set
           
            ::iterator it = S[vc[0]].begin(); it!=S[vc[0]].end(); ++it) { string tmp = *it; bool found = true; for(int i=1; i
           
          
         
        
       
      
     

J.ZOJ 3675 Trim the Nails

bfs：每次用没实用过的方式去剪指甲，直到结果为0，即指甲剪光了就结束

状态压缩DP:  状态:dp[1<<M-1]，结果是dp[0]。状态转移即 枚举指甲剪剪的位置和顺序。然后产生新状态。

#include
     
      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
      
       =0; --i)            if(dp[i]!=INF) {                for(int j=0; j
       
        >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;}