Codeforces Round #556

A Stock Arbitraging

暴力

B Tiling Challenge

暴力

1A&C Prefix Sum Primes

先放2，再放一个1，之后把所有的2放完，再放1，除了2，其他的质数都是奇数

1B&D - Three Religions

序列自动机+dp
分析：给定三个空串和一个母串
操作1：选一个串在其后面增加一个字符
操作2：删除一个串最后的一个字符
总结，关于序列匹配首先想到序列自动机肯定没错，关键是这个m^3的dp不好想，div2 最后也没过几个

分析:
$dp\left[i\right]\left[j\right]\left[k\right]$dp[i][j][k] 表示匹配 $i,j,k$i,j,k 最少需要到母串的哪个位置

$dp\left[i\right]\left[j\right]\left[k\right]=min\left(nxt\right[dp[i-1]\left[j\right]\left[k\right]\left]\right[s\left[i\right]\left[0\right]{-}^{\prime }{a}^{\prime }\left]\right),nxt\left[dp\right[i\left]\right[j-1\left]\right[k\left]\right]\left[s\right[j\left]\right[1\left]{-}^{\prime }{a}^{\prime }\right],nxt\left[dp\right[i\left]\right[j\left]\right[k-1\left]\right]\left[s\right[k\left]\right[2\left]{-}^{\prime }{a}^{\prime }\right]);$dp[i][j][k]=min(nxt[dp[i−1][j][k]][s[i][0]−′a′]),nxt[dp[i][j−1][k]][s[j][1]−′a′],nxt[dp[i][j][k−1]][s[k][2]−′a′]);

const int maxn = 3e5+10,maxm = 250+10;
char ar[maxn],s[maxm][4];
int len[3];
int nxt[maxn][30];
int dp[maxm][maxm][maxm];

char op[3],ch[maxn];
int main(void)
{
    int n,m;cin>>n>>m;
    cin>>(ar+1);
    for(int i = 0;i < 26; ++i) nxt[n][i]  = nxt[n+1][i] = n+1;
    for(int i = n-1;i >= 0; --i){
      for(int j = 0;j < 26; ++j)
        nxt[i][j] = nxt[i+1][j];
      nxt[i][(int)(ar[i+1]-'a')] = i+1;
    }
    for(int i = 1;i <= m; ++i){
      int t;
      scanf("%s %d",op,&t);
      t--;
      // cout<<t<<endl;
      if(op[0] == '-'){
        len[t]--;
      }
      else{
        scanf("%s",ch);
        // cout<<len[t]<<endl;
        ++len[t];
        // cout<<len[t]<<endl;

        // cout<<len[0]<<" "<<len[1]<<" "<<len[2]<<endl;
        s[len[t]][t] = ch[0];
        // 初始化
        // DEBUG
        for(int i = t == 0?len[0]:0;i <= len[0]; ++i){
          for(int j = t == 1?len[1]:0;j <= len[1]; ++j){
            for(int k = t == 2?len[2]:0;k <= len[2]; ++k){
              // cout<<i<<" "<<j<<" "<<k<<endl;
              dp[i][j][k] = n+1;
            }
          }
        }
        // DEBUG;
        for(int i = t == 0?len[0]:0;i <= len[0]; ++i){
          for(int j = t == 1?len[1]:0;j <= len[1]; ++j){
            for(int k = t == 2?len[2]:0;k <= len[2]; ++k){
              if(i > 0)
                dp[i][j][k] = min(dp[i][j][k],nxt[dp[i-1][j][k]][s[i][0]-'a']);
              if(j > 0)
                dp[i][j][k] = min(dp[i][j][k],nxt[dp[i][j-1][k]][s[j][1]-'a']);
              if(k > 0)
                dp[i][j][k] = min(dp[i][j][k],nxt[dp[i][j][k-1]][s[k][2]-'a']);
            }
          }
        }
        
      }
      // cout<<dp[len[0]][len[1]][len[2]]<<endl;
      puts(dp[len[0]][len[1]][len[2]] <= n ?"YES":"NO");
    }


   return 0;
}

div1 E Election Promises

题意：
给定一棵有向树，每个点有一个权值，两个人进行操作，可以选择任意一个节点，将其权值减小为一个非负数，并且可以将其子节点修改为任意的权值，判定是否先手必赢，如果先手必赢，给定一个先手的方案

分析:

1 我们看到有向树，就可以联想到拓扑排序有关的问题，或者直接dfs进行图的遍历，

2 博弈问题，我们应该关注其是不是一个ICG（组合博弈问题），能否使用sg函数找出其规律并求解，当你找出了sg函数的时候，你就已经可以解决这个问题了

3 大部分博弈问题的模型都或多或少与石子博弈问题有关，本题同样，输出方案的过程就是石子博弈问题输出方案的翻版

本题的SG函数模型，我们可以这样来构造，即

一个节点的Sg函数值，就是mex(sg[son])

那么判断先手必胜的条件是什么呢？，

1 我们首先想到博弈问题有关的树博弈问题，根节点的sg值就是整个游戏的sg值，这样想，样例就不对

2 将所有节点的值Sg函数值都异或起来，看起来挺有效的,但是也不太对

3 我们思考如果只有两个点的情况，如果没有边，那么就是石子博弈问题，直接取sumxor(h(x)) 就ok了，对于这一题，我们同样需要异或，就是将所有相同sg值的点的h值异或，如果有一个异或值部位0，那么肯定必赢

怎么输出方案呢？

首先我们参考有关问题的方案输出，那就是我们找到最大的sg函数相同的异或不为0的位置，如果 xorsum[sg[u]] ^ h[i] < h[i] ，说明这个时候就是可行的，它的子节点包含所有的sg值，可以同时将它的子节点的xor[sg[son]]都修改，这样最后肯定所有 的xor[sg[i]] 都为0，就是必败态

const int maxn = 2e5+10;
vector<int> G[maxn];
int topo[maxn];
int  sg[maxn],deg[maxn],mem[maxn];
int  Xor[maxn];
LL  h[maxn];
int main(void)
{
    // IOS;
    int n,m;cin>>n>>m;
    for(int i = 1;i <= n; ++i) scanf("%lld",&h[i]);
        // cin>>h[i];
    for(int i = 1;i <= m; ++i){
        int u,v;
        //cin>>u>>v;
        scanf("%d%d",&u,&v);
        G[u].Pb(v);
        deg[v]++;
    }
    queue<int> q;
    int cnt = 1;
    for(int i = 1;i <= n; ++i)
        if(deg[i] == 0)
            q.push(i);//,vis[i] = true;
    while(!q.empty()){
        int p = q.front(); q.pop();
        topo[cnt++] = p;
        for(auto c: G[p]){
            deg[c]--;
            if(deg[c] == 0)
                q.push(c);
        }
    }

    for(int i = n;i >= 1; --i){
        int  u = topo[i];
        for(auto c: G[u])
            mem[sg[c]] = i;
        while(mem[sg[u]] == i)
            sg[u]++;
        Xor[sg[u]] ^= h[u];
    }
    // for(int i = 1;i <= n; ++i)
    // cout<<sg[i]<<" ";
    // cout<<endl;
    int index = -1;
    for(int i = 0;i < maxn; ++i)
        if(Xor[i] != 0)
            index = i;
    if(index == -1)
        return 0*puts("LOSE");
    for(int i = 1;i <= n; ++i){

        if(sg[i] == index && ((h[i] ^ Xor[index]) < h[i])){
            h[i] ^= Xor[index];
            for(auto c: G[i]){
                h[c] ^= Xor[sg[c]];
                Xor[sg[c]] = 0;
            }
            break;
        }
    }
    // for
    puts("WIN");
    for(int i = 1;i <= n; ++i)
        printf("%lld ",h[i]);
    

   return 0;
}