AtCoder Beginner Contest 291（Sponsored by TOYOTA SYSTEMS）（D，E，F）
D
又一次误解题意
这个题的要求是相邻的两个数不同，而我的翻译上是整个数列的数都是不同的 (ಥ﹏ಥ)
大意是给你\(2n\)个数，每一个数都有一个选择，但是我们必须要从这两个数中选择一个，然后我们要求知道有多少种选择满足相邻两个数之间是不同的数量
如果没有误解题意，那么这道题就是很明显的\(dp\)
我们可以这样构造
\(dp[i] [0]\)是长度为\(i\)，其中最后一个（也就是第\(i\)个数是第一个数）的数量
\(dp[i] [1]\)是长度为\(i\)，其中最后一个（也就是第\(i\)个数是第二个数）的数量
然后我们可得状态转移方程如下
if (a[i][0]!=a[i-1][0])
{
dp[i][0]=(dp[i][0]+dp[i-1][0])%mod;
}
if (a[i][0]!=a[i-1][1])
{
dp[i][0]=(dp[i][0]+dp[i-1][1])%mod;
}
if (a[i][1]!=a[i-1][0])
{
dp[i][1]=(dp[i][1]+dp[i-1][0])%mod;
}
if (a[i][1]!=a[i-1][1])
{
dp[i][1]=(dp[i][1]+dp[i-1][1])%mod;
}
还蛮好理解的
然后就可以写代码了
#include <iostream>
#include <string>
using namespace std;
const int maxn=2e5+10;
const int mod=998244353;
#define int long long
int n;
int a[maxn][2],dp[maxn][2];
signed main ()
{
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>a[i][0]>>a[i][1];
}
dp[1][0]=dp[1][1]=1;
for (int i=2;i<=n;i++)
{
if (a[i][0]!=a[i-1][0])
{
dp[i][0]=(dp[i][0]+dp[i-1][0])%mod;
}
if (a[i][0]!=a[i-1][1])
{
dp[i][0]=(dp[i][0]+dp[i-1][1])%mod;
}
if (a[i][1]!=a[i-1][0])
{
dp[i][1]=(dp[i][1]+dp[i-1][0])%mod;
}
if (a[i][1]!=a[i-1][1])
{
dp[i][1]=(dp[i][1]+dp[i-1][1])%mod;
}
//cout<<dp[i][0]<<" "<<dp[i][1]<<'\n';
}
int ans=(dp[n][1]+dp[n][0])%mod;
cout<<ans<<'\n';
system ("pause");
return 0;
}
E
题目大意就是会给我们\(1\)到\(n\)(不是顺序的)\(n\)个数，并且给出\(m\)种关系，如给出\(x\)和\(y\),意思就是\(a_x < a_y\),我们最终的要求是判断是否可以得到唯一的满足条件的数组
对于每两个数之间的关系，我们可以把这个关系看成是两个点之间的边，然后还需要的值每一个点的值，这个我们可以使用拓扑排序（但是要满足这个序列是唯一的，所以在进行拓扑排序时的队列里面的\(size\)要为\(1\)，因为此时的值只能赋给一个点）
然后就没什么了
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
int n,m;
int main ()
{
cin>>n>>m;
vector<vector<int>>g(n+1);
vector<int>in(n+1);
for (int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
g[x].push_back(y);
in[y]++;
}
vector<int>ans(n+1);
queue<int>q;
int cnt=0;
for (int i=1;i<=n;i++)
{
if (!in[i])q.push(i);
}
while (!q.empty())
{
if (q.size()!=1)//可以赋给多个点，不唯一
{
cout<<"No\n";
system ("pause");
return 0;
}
int u=q.front();
q.pop();
ans[u]=++cnt;
for (auto v:g[u])
{
in[v]--;
if (in[v]==0) q.push(v);
}
}
cout<<"Yes\n";
for (int i=1;i<=n;i++)
{
cout<<ans[i]<<" ";
}
cout<<'\n';
system ("pause");
return 0;
}
F
这个题大意是给你\(n\)个点，然后对于哪两个点之间可连通的判断条件如下
对于\(i\)点和\(j\)点，如果第\(i\)个字符串的第\(j-i\)个字符是\(1\)的，并且\(1<(j-i)<=m\)的情况下，这两点才表明是连通的
然后我们还有\(n-2\)个问题，每次询问对于\(2,3,...n-1\)这些点中的一个点不可以到达的情况下从\(1\)到\(n\)的最小步数
然后看到这一道题，我就觉得和寒假训练营的某一道题相似
这次训练营因为一些原因没有写题解，这两个题都用到了这一个思路
然后其他的就是一些细节的处理，具体的看代码吧
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
#define int long long
#define inf (int)1e9+10
const int maxn=2e5+10;
int n,m;
signed main ()
{
cin>>n>>m;
vector<string>s(n+1);
for (int i=1;i<=n;i++)
{
cin>>s[i];
s[i]=" "+s[i];
}
vector<int>dp0(n+1,inf),dp1(n+1,inf);//dp0[i]代表顺方向的，从1到i的步数，dp1[i]代表从n到i，逆着走
dp0[1]=0;
for (int i=1;i<=n;i++)//i作为开始的点
{
for (int j=i+1;j<=min(n,i+m);j++)//j作为到达的点
{
if (s[i][j-i]=='1')
{
dp0[j]=min(dp0[j],dp0[i]+1);
}
}
}
dp1[n]=0;
for (int j=n;j>=1;j--)//逆着走时，j是初始点
{
for (int i=max(1ll,j-m);i<j;i++)//到达点
{
if (s[i][j-i]=='1') dp1[i]=min(dp1[i],dp1[j]+1);
}
}
for (int k=2;k<n;k++)
{
int ans=inf;
for (int i=max(k-m+1,1ll);i<k;i++)
{
for (int j=k+1;j<=min(n,i+m);j++)//注意这里的j取min(n,i+m)意思是在不大于n的情况下，我们最远到达的是和i距离为m的点，而不是k-1+m，看到有一些题解时这么写的，一直没找到这个bug
{
if (s[i][j-i]=='1')
{
ans=min(ans,dp0[i]+dp1[j]+1);
}
}
}
if (ans==inf) ans=-1;
cout<<ans<<' ';
}
cout<<'\n';
system ("pause");
return 0;
}