最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

全球短讯！Codeforces 1785 E Infinite Game 题解 (图论，自动机，dp)

来源：博客园


(相关资料图)

题目链接

假设现在字符串s中已经没有问号，我们来确定这时的答案。我们建立一个4个点的有向图(可以看成一个自动机)，4个点分别代表每个set内部的比分：0:0, 1:0, 0:1, 1:1。在其中连一些边，比如从1:0往1:1连一条权值为0的边，代表放一个字符b时会走这条边，且对Alice赢的set数贡献为0；从1:0往0:0连一条权值为1的边，代表放一个字符a时会走这条边，且对Alice赢的set数的贡献为1。一共连8条这样的边，每个点的出度为2。然后令初始位置为0:0，我们从左到右遍历s，当加入一个字符时就在图中走对应的边，把边权加入答案，并把当前位置沿着这条边移动一次。令\(to_i\)表示以状态i为初始位置，遍历完整个s后得到的状态；\(val_i\)表示以状态i为初始位置，遍历完s的过程中给答案加上的值的和，其中\(i\in \{0:0,1:0,0:1,1:1 \}\)。我们把\(i\to to_i\)连边，建出一个新图。新图的形态是一个内向基环树，由于这题要求我们不断重复s，也就相当于在新图上从0:0开始不断地走，并把经过的每个点的\(val_i\)加入答案。在这个新图中，从0:0出发一定会到达基环，并在基环上不断绕圈。令sum表示基环上所有点的\(val_i\)之和，如果\(sum>0\)，显然当走的步数趋于无穷时Alice赢的set数更多；如果\(sum<0\)，显然Bob赢的set数更多；否则\(sum=0\)，此时无论你在到达基环之前经过的点的\(val_i\)之和是正是负，当走的步数趋于无穷时，Alice与Bob赢的set数之差都是趋于0的，所以此时是平局。

然后来看原问题，考虑dp。你可以在dp状态中记录有向图中的4个点每个分别可以走到哪个位置，以及它们的\(val_i\)，但是这样复杂度非常高，可能是\(n^5\)左右(但是tourist说实现得好是可以过的)。注意到我们只对新图中基环里所有点的\(val_i\)之和感兴趣，而不是对每个状态的\(val_i\)都感兴趣。所以可以先枚举基环中含有的点的mask，对于每次枚举用一次dp算出答案。\(dp_{i,u1,u2,u3,u4,sum}\)表示确定了s中的前i个位置填什么，此时0:0,1:0,0:1,1:1分别能走到\(u1,u2,u3,u4\)，在mask中的状态的\(val\)之和为\(sum\)的方案数。转移就枚举s中接下来一个位置填什么，然后根据那个4个点8条边的有向图的信息更新dp状态就可以了，转移是\(O(1)\)的。最后计算答案的时候，枚举所有\(u1,u2,u3,u4\)的组合，检查它们确定的基环树的基环中的点是否就是mask中那些，如果是就更新答案。

时间复杂度\(O(2^4\cdot 4^4\cdot n^2)\)。看上去计算量挺大，其实如果只访问可能有效的状态，是跑得很快的。dp数组要滚动，不然空间可能会爆掉。

点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define pb push_back#define mpr make_pairvoid fileio(){  #ifdef LGS  freopen("in.txt","r",stdin);  freopen("out.txt","w",stdout);  #endif}void termin(){  #ifdef LGS  std::cout<<"\n\nEXECUTION TERMINATED";  #endif  exit(0);}using namespace std;const LL MOD=998244353,bas=404;void add(LL &x,LL y){x+=y;if(x>=MOD) x-=MOD;}string s;LL dp[2][810][4][4][4][4],ans1=0,ans2=0,ans3=0,curto[4];pii to[4][2];int getCyc(){  bool vis[4];rep(i,4) vis[i]=false;  vector  pth;int cur=0;  while(true)  {    if(vis[cur])    {      rep(i,pth.size()) if(pth[i]==cur)      {        int ret=0;        for(int j=i;j>s;  rep(incyc,1<<4) if(incyc>0)  {    LL cnt=__builtin_popcount(incyc);    rep(i,2) rep(j,809) rep(k1,4) rep(k2,4) rep(k3,4) rep(k4,4) dp[i][j][k1][k2][k3][k4]=0;    dp[0][bas][0][1][2][3]=1;    rep(ii,s.size())    {      int i=ii&1,lb=bas-(ii+4)/2*cnt,ub=bas+(ii+4)/2*cnt;      lb=max(lb,0);ub=min(ub,809);      for(int j=lb;j<=ub;++j) rep(k1,4) rep(k2,4) rep(k3,4) rep(k4,4)      {        LL &val=dp[i][j][k1][k2][k3][k4];        if(val==0) continue;        int nk1,nk2,nk3,nk4;        rep(nxt,2) if(s[ii]=="?"||s[ii]==nxt+"a")        {          LL nj=j;          if(incyc&1) nj+=to[k1][nxt].se;nk1=to[k1][nxt].fi;          if(incyc&2) nj+=to[k2][nxt].se;nk2=to[k2][nxt].fi;          if(incyc&4) nj+=to[k3][nxt].se;nk3=to[k3][nxt].fi;          if(incyc&8) nj+=to[k4][nxt].se;nk4=to[k4][nxt].fi;          add(dp[i^1][nj][nk1][nk2][nk3][nk4],val);        }        val=0;      }    }    rep(k1,4) rep(k2,4) rep(k3,4) rep(k4,4)    {      curto[0]=k1;curto[1]=k2;curto[2]=k3;curto[3]=k4;      if(getCyc()==incyc)      {        rep(j,809)        {          if(j

关键词： 初始位置 已经没有 就可以了