首页 > 其他分享 >AtCoder Beginner Contest 291 DEF

AtCoder Beginner Contest 291 DEF

时间:2023-06-17 09:00:35浏览次数:47  
标签:AtCoder return idx int ll ret mod DEF 291

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前面)。所以,这个核心规则下只要满足即可,所以拓扑排序序列不一定唯一

    题目要找唯一的,我们注意判一下。

    不行的情况

    1. 入度为0的点有多个或无

    2. 有环。但因为我们用了\(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;
}

标签:AtCoder,return,idx,int,ll,ret,mod,DEF,291
From: https://www.cnblogs.com/nannandbk/p/17487008.html

相关文章

  • AtCoder Beginner Contest 302 ABCDEF
    AtCoderBeginnerContest302A-AttackProblemStatement题意:敌人有\(A\)的耐力值,每次攻击敌人可以减少\(B\)的耐力值,问多少次敌人耐力值\(<=0\)?Solution题解:\(\dfrac{a}{b}\)上取整。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;intmain(){......
  • AtCoder Beginner Contest 305 ABCDE
    AtCoderBeginnerContest305A-WaterStationProblemStatement题意:水站每\(5km\)设一个,给你一个\(N\)\(km\)的位置,问你离它最近的水站位置。Solution题解:模5在乘5,比较给出的点的左边和右边的点,取min#include<bits/stdc++.h>usingnamespacestd;intmain(){ int......
  • Educational Codeforces Round 150 (Rated for Div. 2) B. Keep it Beautiful
    #include<iostream>#include<cstring>usingnamespacestd;constintN=2e5+10;inta[N],res[N];intt;intmain(){ cin>>t; while(t--){ intn; cin>>n; for(inti=0;i<n;i++){ cin>>a[i]; } intk=a[0]; res[0]=......
  • CodeForces 1841C Ranom Numbers
    洛谷传送门CF传送门先反转\(s\)串,然后考虑dp,设\(f_{i,j,0/1}\)为考虑了\([1,i]\),前缀最大值为\(j\),是否修改过字符的最大得分。转移讨论是否在这个位置修改即可。时间复杂度\(O(n)\)。code//Problem:C.RanomNumbers//Contest:Codeforces-Educational......
  • Vue进阶(幺贰陆):表格复用 TypeError: _self.$scopedSlots.default is not a function解
    (文章目录)一、前言在使用elementUI的el-table组件时,表头应用v-if判断来动态显示,正常来说这样的操作是没有问题的,但是如果在这基础上使用<templateslot-scope="scope">操作的话,表头一旦切换就会报错,错误信息如下:_self.$scopedSlots.defaultisnotafunction二、解决方......
  • AtCoder Beginner Contest 253 Ex We Love Forest
    洛谷传送门AtCoder传送门没做出来。考虑求出方案数后除以\(m^i\)求出概率。设\(U=\{1,2,...,n\}\)。因为题目限制了加几条边,不妨设\(f_{i,S}\)为,加了\(i\)条边,\(S\)形成森林且\(U\setminusS\)没有边的方案数。转移枚举子集\(T\),钦定\(T\)为树,设\(T\)......
  • AtCoder Beginner Contest 298 Ex Sum of Min of Length
    洛谷传送门AtCoder传送门挺无脑的。是不是因为unr所以评分虚高啊/qd考虑把\(L_i\toR_i\)的路径拎出来,那么路径中点(或中边)左边的点挂的子树到\(L_i\)更优,右边的点挂的子树到\(R_i\)更优。差分一下,可以转化成\(O(q)\)次询问,每次询问形如\((u,v)\)表示求\(v\)......
  • AtCoder Beginner Contest 251 G Intersection of Polygons
    洛谷传送门AtCoder传送门经典结论,一个点\(P(x,y)\)在一个凸多边形内部\(S=\{(x_i,y_i)\}\)的充要条件是\(\foralli\in[1,n],(x_{i+1}-x_i,y_{i+1}-y_i)\times(x-x_i,y-y_i)\ge0\),其中\(S\)的点按照逆时针排列。然后我们运用叉积的一个性质......
  • AtCoder Beginner Contest 220 G Isosceles Trapezium
    洛谷传送门AtCoder传送门简单题。首先肯定是要枚举梯形其中一条底边的两个端点的。那么另一条底边除了斜率与这条边相等,两个端点的距离要分别与这条底边两个端点的距离相等。发现这个十分不好做,考虑一个梯形是等腰梯形的一个充要条件。不难想到,连接两底中点,这条线段垂直于两......
  • AtCoder Beginner Contest 249 G Xor Cards
    洛谷传送门AtCoder传送门好题。套路地,考虑枚举最优解的\(a\)异或和二进制下与\(k\)的\(\text{LCP}\),设在第\(i\)位不同。这样的好处是\(i\)之后的位可以随便选。之后按位贪心确定最优解\(b\)的异或和。考虑之前的答案是\(res\),当前在确定第\(j\)位,如何判断\(r......