gym102220 Mini-game Before Contest
https://codeforces.com/gym/102220/problem/F
在vj跟着现场榜打的，没人开这题，水题啊卧槽，一直在想A题，A题难得一比卧槽，省赛还是要多开题，cf上gym牛逼网友F过了一车。虽然我当时看了这题但是因为没人过所以没有花很多时间想，晚上仔细想想一写就过了
用-1表示平局，0表示A获胜，1表示B获胜，b[i]=0/1表示他实际是希望谁赢的,dp[i][j]表示到了第i个点现在是第j个人移动时的状态
从没有出度的点开始，此时dp[i][1-6]是谁获胜了都知道了，就是当前移动的输了，接着吧他们放到队列里，队列里存新增的被确定为0或者1的dp[u][i]，从队列里拿出一个u,i，然后枚举所有连向u的点v，及存在v->u的一条正向边，v可以走到u，如果dp[u][i]正如pre(i)所愿，dp[u][i]=b[pre(i)]，那么直接把dp[v][pre(i)]确定，加进队列，否则如果与pre(i)期望相反，那么我们知道如果v能走到的所有点都与pre(i)期望相反，那么dp[v][pre(i)]才是必输的，否则他可以选择走某一个点得到平局，用一个du[v][pre(i)]来记录一下是不是全都必输了就行。
我们发现每一个dp[u][i]不等于-1也就是有确定的胜负之后，只会被加入队列一次，而且更新也只会更新一次，所以虽然是类似spfa的写法，但实际上只有O((n+m)*6)的复杂度
我好菜啊.jpg，以后一定要每道题都认真想想，不能比赛后期看没人过就摸鱼啊
#include
using namespace std;const int maxl=2e5+10;int n,m;
int a[10],b[10];
int dp[maxl][7],du[maxl][7];
char ord[10],s[10];
typedef pair p;
vector e[maxl],fe[maxl];
queue q;
bool in[maxl][7];inline void prework()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=6;j++)dp[i][j]=-1,du[i][j]=0,in[i][j]=false;e[i].clear();fe[i].clear();}int u,v;for(int i=1;i<=m;i++){scanf("%d%d",&u,&v);e[u].push_back(v);fe[v].push_back(u);for(int j=1;j<=6;j++)du[u][j]++;}scanf("%s",ord+1);scanf("%s",s+1);for(int i=1;i<=6;i++)a[i]=s[i]-'0',b[i]=(ord[i]-'A')^a[i];
}inline int pre(int i)
{if(i==1)return 6;return i-1;
}
inline int nxt(int i)
{if(i==6)return 1;return i+1;
}inline void mainwork()
{while(!q.empty()) q.pop();for(int i=1;i<=n;i++)if(du[i][1]==0){for(int j=1;j<=6;j++)if(ord[j]=='A'){ dp[i][j]=1; //A can't move B winq.push({i,j});in[i][j]=true;}else {dp[i][j]=0;//0 -> A winq.push({i,j});in[i][j]=true;}}int u,i;p d;while(!q.empty()){d=q.front();q.pop();u=d.first;i=d.second;for(int v:fe[u])if(dp[v][pre(i)]==-1){if(dp[u][i]==b[pre(i)]){dp[v][pre(i)]=b[pre(i)];q.push({v,pre(i)});in[v][pre(i)]=true;}else{du[v][pre(i)]--;if(du[v][pre(i)]==0){dp[v][pre(i)]=b[pre(i)]^1;q.push({v,pre(i)});in[v][pre(i)]=true;}}}}
}inline void print()
{for(int i=1;i<=n;i++)if(dp[i][1]<0)putchar('D');else putchar('A'+dp[i][1]);puts("");
}int main()
{int t;scanf("%d",&t);for(int i=1;i<=t;i++){prework();mainwork();print();}return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！