B. MADMAX

链接:https://codeforces.com/contest/917/problem/B

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+10,maxm=1e7+10;int n,m;
int sg[110][110][30];
vector<pair<int,int> > e[110];bool dfs(int x,int y,int kw)
{if(sg[x][y][kw]!=-1)return sg[x][y][kw];sg[x][y][kw]=0;for(auto edge : e[x]){int v=edge.first;int w=edge.second;if(w<kw) continue;if(dfs(y,v,w)==0){sg[x][y][kw]=1;break;}}return sg[x][y][kw];
}int main()
{scanf("%d%d",&n,&m);memset(sg,-1,sizeof(sg));for(int i=1;i<=m;++i){int u,v;char w;scanf("%d%d %c",&u,&v,&w);e[u].push_back({v,w-'a'});}for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){bool ok=(dfs(i,j,0)==0);putchar(ok?'B':'A');}cout<<"\n";}return 0;
}

P2575 高手过招

链接：https://www.luogu.com.cn/problem/P2575

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e6+10,maxm=1e7+10;int t,n,m;
int sg[maxn];int dfs(int x)
{if(sg[x]!=-1) return sg[x];int last=-1;int visit[20];memset(visit,0,sizeof(visit));for(int i=19;i>=0;--i){if((x>>i&1)){if(last!=-1){int res=dfs(x^(1<<i)^(1<<last));visit[res]=1;}}else last=i;}for(int i=0;i<=19;++i)if(!visit[i]) return sg[x]=i;
}int main()
{scanf("%d",&t);memset(sg,-1,sizeof(sg));while(t--){scanf("%d",&n);int ans=0;for(int i=1;i<=n;++i){int x=0;scanf("%d",&m);for(int j=1;j<=m;++j){int d;scanf("%d",&d);d--;x|=(1<<d);}ans^=dfs(x);}bool ok=(ans==0);puts(ok?"NO":"YES");}return 0;
}