比赛链接:https://atcoder.jp/contests/abc291/tasks
D题:大意是给出n张卡片的正面和反面的数值,卡片正反面为不同数字,求翻某些卡片的一面使得向正的一面的数值全都不一样的集合的数量。
解决方法:考虑使用01动态规划解决。f[i][0/1],表示前i张卡片能够翻出的不同集合的数量。只需要对比最后一步对前i-1种情况进行累加,考虑当前面是否对于前一张卡片的正反两面是否可行,总共四种情况进行对比。
code:
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
// 不翻面 / 翻面
f[1][0] = 1;f[1][1] =1;
for(int i=2;i<=n;i++){
if(a[i]!=a[i-1]) f[i][0]+=f[i-1][0];
if(a[i]!=b[i-1]) f[i][0]+=f[i-1][1];
if(b[i]!=a[i-1]) f[i][1]+=f[i-1][0];
if(b[i]!=b[i-1]) f[i][1]+=f[i-1][1];
f[i][0]%=mod9;f[i][1]%=mod9;
}
ll ans = f[n][0]+f[n][1];
ans%=mod9;
cout<<ans<<endl;
E题:大意是给出n个数字的一个排列。你需要求出这个排列。给出m条信息包含xi和yi,求是否存在唯一确定的A。
解决方法:拓扑排序模板题,当每个层次存在一一对应的情况下(即队列内的元素数量始终<2),可以使得序列唯一。对于求出的拓扑序,排一遍1-n的代入排列即可。
code:
const int nn = 2e5+10; vector<int> ve[nn]; int ru[nn]; int ts[nn]; int cnt; int n,m; bool flag = true; int ans[nn]; void topsort(){ queue<int> q; for(int i=1;i<=n;i++){ if(ru[i]==0){ q.push(i); ts[++cnt]=i; } } if(q.size()>1){ flag = false; return; } while(!q.empty()){ if(q.size()>1){ flag = false; return; } int u = q.front();q.pop(); for(int i=0;i<ve[u].size();i++){ int v = ve[u][i]; ru[v]--; if(ru[v]==0) q.push(v),ts[++cnt]=v; } } } int main() { //cin.ignore(numeric_limits<streamsize>::max(),'\n'); ios_base::sync_with_stdio(0); cin.tie(0); //cout.tie(0); cin>>n>>m; int x,y; for(int i=1;i<=m;i++){ cin>>x>>y; ve[x].push_back(y); ru[y]++; } topsort(); if(!flag){ cout<<"No"<<endl; return 0; } cout<<"Yes"<<endl; for(int i=1;i<=cnt;i++){ ans[ts[i]] = i; } for(int i=1;i<=cnt;i++){ cout<<ans[i]<<" "; } }