Atcoder ABC 291
D
题意
n张牌，每张牌两面都有数字，可以翻面，问有多少种情况使得这n张牌中每相邻两张牌表面上的数互不相同
思路
线性dp，每次比较当前位和上一位是否相同即可。
唉，看漏条件了，没看到相邻，想得太复杂了。
但又可以想一想，如果去掉相邻这个条件，这个题要怎么做。
代码
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
}
f[1][0]=f[1][1]=1;//初始化不是从0开始
for(int i=2;i<=n;i++)
{
if(a[i]!=a[i-1]) f[i][0]=(f[i][0]+f[i-1][0])%mod;
if(a[i]!=b[i-1]) f[i][0]=(f[i][0]+f[i-1][1])%mod;
if(b[i]!=a[i-1]) f[i][1]=(f[i][1]+f[i-1][0])%mod;
if(b[i]!=b[i-1]) f[i][1]=(f[i][1]+f[i-1][1])%mod;
}
cout<<(f[n][0]+f[n][1])%mod<<endl;
}
E
题意
一个长度为n的数组，每个数都是（1~n）且互不相同，给出m个关系，\(x<y\)表示\(a_x<a_y\) ,为是否可以通过这些关系确定该数组。
思路
一开始以为差分约束，打了一发，超时了，后来一想情况没那么复杂，拓扑排序一下就好了。
不行的情况：
1.入度为0的点有多个或者没有
2.有环。但因为用了拓扑排序就不用特意判环了，有环就会出现数组中某些位置的值会重复。
代码
int h[N],e[N],ne[N],idx;
int dis[N],in[N];
bool vis[N];
map<pii,int> mp;//去重边
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
bool toph_()
{
int cnt=0,rt=0;
for(int i=1;i<=n;i++)
{
if(!in[i]) rt=i,cnt++;
}
if(cnt>1||rt==0) return false;
queue<int> que;
que.push(rt);
dis[rt]=1;
while(que.size())
{
int u=que.front();
que.pop();
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(--in[j]==0)
{
que.push(j);
dis[j]=dis[u]+1;
}
}
}
return true;
}
void solve()
{
memset(h,-1,sizeof(h));
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
if(mp.count({x,y})) continue;
mp[{x,y}]=1;
add(x,y);
in[y]++;
}
if(!toph_()) cout<<"No\n";
else
{
for(int i=1;i<=n;i++)
{
if(vis[dis[i]]) {cout<<"No\n";return;}
vis[dis[i]]=1;
}
cout<<"Yes\n";
for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
cout<<endl;
}
}
F 补
题意
给出n个字符串，如果\(s_{ij}=1\) 则表示第i个点可以到第i+j个点
问不经过点k是否有一条从1到n的路径，如果有就求最短的，没有就-1，k=2,3,4...n-1
思路
真的是个弱鸡啊，脑子不够用了，溜去看大佬代码了。
bfs求 1到各个点的最短路\(d1\)，建反图求 n到其它点的最短路\(d2\)
对于x到y，如果\(d1_x\)存在且\(d2_y\) 存在，那么它们连在一起+1就等于从1到n了，可以确定的是，这条路径没有经过\([x+1,y-1]\)
代码
int n,m;
vector<int> bfs(vector<vector<int>> &a,int s)
{
vector<int> dis(n,-1);
dis[s]=0;
queue<int> que;
que.push(s);
while(que.size())
{
int u=que.front();
que.pop();
for(auto &x:a[u])
{
if(dis[x]==-1)
{
dis[x]=dis[u]+1;
que.push(x);
}
}
}
return dis;
}
void solve()
{
cin>>n>>m;
vector<vector<int>> a1(n),a2(n);
for(int i=0;i<n;i++)
{
string s;
cin>>s;
for(int j=0;j<m;j++)
{
if(s[j]=='1')
{
a1[i].push_back(i+j+1);
a2[i+j+1].push_back(i);
}
}
}
vector<int> d1,d2,ans(n,-1);
d1=bfs(a1,0);
d2=bfs(a2,n-1);
for(int i=0;i<n;i++)
{
for(auto &x : a1[i])
{
if(d1[i]==-1||d2[x]==-1) continue;
int res=d1[i]+d2[x]+1;
for(int j=i+1;j<x;j++)
{
if(ans[j]==-1||ans[j]>res)
{
ans[j]=res;
}
}
}
}
for(int i=1;i<n-1;i++) cout<<ans[i]<<" ";
cout<<endl;
}