AtCoder Beginner Contest 291 DEF
AtCoder Beginner Contest 291
D - Flip Cards
Problem Statement
题意：\(N\)张卡片，编号\(1\)到\(N\),每张卡片有正反两面，写有数字，初始状态都是正面朝上。
考虑每张卡片的翻转情况，选择翻或者不翻，求是的相邻两张卡片的数字不同，求方案数，答案模\(998244353\)
Solution
题解：求方案数，想到\(DP\)。对于每张卡片，无非两种情况，翻或者不翻，且该张卡片的翻转情况只和上一张卡片有关，那我们定义\(dp[idx][0/1]\)为上一张卡片编号为\(idx\),翻转情况用\(flag = 0/1\)表示，\(0\)表示不翻\(1\)表示翻。注意要记忆化搜索一下，不然会\(TLE\).
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
ll dp[N][3];
struct modular_arithmetic {
const int mod = 998244353;
int add(ll a, ll b) {
return (a % mod + b % mod) % mod;
}
int mul(ll a, ll b) {
return ((a % mod) * (b % mod)) % mod;
}
int pow(ll x, ll n) {
if (n == 0) return 1;
int res = pow(x, n / 2);
res = mul(res, res);
if (n % 2) res = mul(x, res);
return res;
}
int inv(ll x) {
return pow(x, mod - 2);
}
int div(ll a, ll b) {
return mul(a, inv(b));
}
};
modular_arithmetic mod;
int n;
int a[N][3];
ll dfs(int idx,int flag)
{
if(idx>n)
return 1;
ll &ret = dp[idx][flag];
if(~dp[idx][flag])return ret;
ret = 0;
if(a[idx][0]!=a[idx-1][flag])
ret = mod.add(ret,dfs(idx+1,0));
if(a[idx][1]!=a[idx-1][flag])
ret = mod.add(ret,dfs(idx+1,1));
return ret;
}
int main()
{
cin>>n;
for(int i = 1;i<=n;i++)
{
cin>>a[i][0]>>a[i][1];
}
memset(dp,-1,sizeof(dp));
cout<<mod.add(dfs(2,0),dfs(2,1))<<endl;
return 0;
}
E - Find Permutation
Problem Statement
题意：\(A\)是一个排列，告诉你\(M\)组排列中不同位置数的大小关系，问能否找出唯一一个符合题意的\(A\)
Solution
题解：\(Topo\)排序,根据题目给的位置大小关系连边建图。
对于\(Topo\)排序：
规则：
-
图中每个顶点只出现
一次。 -
A在B前面，则不存在B在A前面的路径。(
不能成环！！！！) -
顶点的顺序是保证所有指向它的下个节点在被指节点前面！(例如A—>B—>C那么A一定在B前面，B一定在C前面)。所以，这个核心规则下只要满足即可，所以拓扑排序序列不一定唯一！
题目要找唯一的，我们注意判一下。
不行的情况：
-
入度为0的点有多个或无
-
有环。但因为我们用了\(Topo\)就不用再特意判了。
#include<bits/stdc++.h> using namespace std; const int N = 2e5+10; vector<int>edge[N]; int n,m,d[N],a[N]; map<pair<int,int>,int>mp; queue<int>q; int now; inline void TopoSort() { now = n; for(int i = 1;i<=n;i++) { if(!d[i]) { q.push(i); } } if(q.size()>1)//入度为0点不止1个 { cout<<"No\n"; return; } while(!q.empty()) { int x = q.front(); q.pop(); a[x] = now--; for(auto y:edge[x]) { if(--d[y]==0) { q.push(y); } } if(q.size()>1) { cout<<"No\n"; return; } } for(int i = 1; i <= n; i++) { if(a[i] == 0) //有点没连上 { cout << "No" << endl; return; } } cout<<"Yes\n"; for(int i = 1;i<=n;i++) cout<<a[i]<<" "; cout<<endl; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i =1 ;i<=m;i++) { int x,y; cin>>x>>y; if(mp[{y,x}])continue;//注意可能有重边，continue掉 mp[{y,x}]++; edge[y].push_back(x); ++d[x]; } TopoSort(); return 0; }
-
F - Teleporter and Closed off
Problem Statement
题意：给你\(N\)个城市，编号从\(1\)到\(N\)。给你\(N\)个字符串代表是否能从一个城市传送到另一个城市。
问：你可以从\(1\)到\(N\)不经过第\(k\)个城市吗？如果可以输出最小的使用传送机次数，否则输出\(-1\)。
Solution
题解：显然是最短路问题,题目中说求从\(1\)到\(N\)要不能经过第\(k\)号城市的最短路，我们考虑用bfs求\(1\)到所有点的最短路d1，再建反向边求\(n\)到所有点的距离d2。
对于\(x\)到\(y\),如果\(d1x\)和\(d2y\)都存在，且\(d1x+d2y+1\)的距离就是\(1\)到\(N\)的最短路，且该路径必然不经过\([x+1,y-1]\)的。
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int>bfs(vector<vector<int>>&edge,int s)
{
vector<int>dist(n+10,-1);
dist[s] = 0;
queue<int>q;
q.push(s);
while(!q.empty())
{
int x = q.front();
q.pop();
for(auto y:edge[x])
{
if(dist[y]==-1)
{
dist[y] = dist[x]+1;
q.push(y);
}
}
}
return dist;
}
int main()
{
cin>>n>>m;
vector<vector<int>>edge(n+10),edge2(n+10);
for(int i = 1;i<=n;i++)
{
string s;
cin>>s;
s = "?"+s;
for(int j = 1;j<=m;j++)
{
if(s[j]=='1')
{
edge[i].push_back(i+j);
edge2[i+j].push_back(i);
}
}
}
vector<int> d1,d2,ans(n,-1);
d1=bfs(edge,1);
d2=bfs(edge2,n);
for(int i = 1;i<=n;i++)
{
for(auto &x:edge[i])
{
if(d1[i]==-1||d2[x]==-1)continue;
int t = d1[i]+d2[x]+1;
for(int j = i+1;j<x;j++)
{
if(ans[j]==-1||t<ans[j])
ans[j] = t;
}
}
}
for(int i = 2;i<n;i++)
cout<<ans[i]<<" ";
cout<<endl;
return 0;
}