首页 > 其他分享 >AtCoder Beginner Contest 302 ABCDEF

AtCoder Beginner Contest 302 ABCDEF

时间：2023-06-17 09:00:25浏览次数：45  
标签：AtCoder cout int 302 long edge && ABCDEF ll

AtCoder Beginner Contest 302

A - Attack

Problem Statement

题意：敌人有\(A\)的耐力值，每次攻击敌人可以减少\(B\)的耐力值，问多少次敌人耐力值\(<=0\)?

Solution

题解:\(\dfrac{a}{b}\)上取整。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ll a,b;
	cin>>a>>b;
	if(a%b==0)
		cout<<a/b<<endl;
	else cout<<a/b+1<<endl;
	return 0;
}

B - Find snuke

Problem Statement

题意：给你一个\(n\)行\(m\)列矩阵，里面都是小写英文字母，输出在同一直线上出现的\(snuke\)。输出坐标。

Solution

题解:遍历一遍，找到\(s\)的位置进行\(check\)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 110;
char a[N][N];
int n,m;
bool check(int i,int j)
{
	bool ok = false;
	if(i-4>=1)
		if(a[i-1][j]=='n'&&a[i-2][j]=='u'&&a[i-3][j]=='k'&&a[i-4][j]=='e')
		{
			ok = true;
			cout<<i<<" "<<j<<endl;
			cout<<i-1<<" "<<j<<endl;
			cout<<i-2<<" "<<j<<endl;
			cout<<i-3<<" "<<j<<endl;
			cout<<i-4<<" "<<j<<endl;
			return ok;
		}
	if(i+4<=n)
		if(a[i+1][j]=='n'&&a[i+2][j]=='u'&&a[i+3][j]=='k'&&a[i+4][j]=='e')
		{
			ok = true;
			cout<<i<<" "<<j<<endl;
			cout<<i+1<<" "<<j<<endl;
			cout<<i+2<<" "<<j<<endl;
			cout<<i+3<<" "<<j<<endl;
			cout<<i+4<<" "<<j<<endl;
			return ok;
		}
	if(j-4>=1)
		if(a[i][j-1]=='n'&&a[i][j-2]=='u'&&a[i][j-3]=='k'&&a[i][j-4]=='e')
		{
			ok = true;
			cout<<i<<" "<<j<<endl;
			cout<<i<<" "<<j-1<<endl;
			cout<<i<<" "<<j-2<<endl;
			cout<<i<<" "<<j-3<<endl;
			cout<<i<<" "<<j-4<<endl;
			return ok;
		}
	if(j+4<=m)
		if(a[i][j+1]=='n'&&a[i][j+2]=='u'&&a[i][j+3]=='k'&&a[i][j+4]=='e')
		{
			ok = true;
			cout<<i<<" "<<j<<endl;
			cout<<i<<" "<<j+1<<endl;
			cout<<i<<" "<<j+2<<endl;
			cout<<i<<" "<<j+3<<endl;
			cout<<i<<" "<<j+4<<endl;
			return ok;
		}
	if(i-4>=1&&j-4>=1)
		if(a[i-1][j-1]=='n'&&a[i-2][j-2]=='u'&&a[i-3][j-3]=='k'&&a[i-4][j-4]=='e')
		{
			ok = true;
			cout<<i<<" "<<j<<endl;
			cout<<i-1<<" "<<j-1<<endl;
			cout<<i-2<<" "<<j-2<<endl;
			cout<<i-3<<" "<<j-3<<endl;
			cout<<i-4<<" "<<j-4<<endl;
			return ok;
		}
	if(i+4<=n&&j+4<=m)
		if(a[i+1][j+1]=='n'&&a[i+2][j+2]=='u'&&a[i+3][j+3]=='k'&&a[i+4][j+4]=='e')
		{
			ok = true;
			cout<<i<<" "<<j<<endl;
			cout<<i+1<<" "<<j+1<<endl;
			cout<<i+2<<" "<<j+2<<endl;
			cout<<i+3<<" "<<j+3<<endl;
			cout<<i+4<<" "<<j+4<<endl;
			return ok;
		}
	if(i-4>=1&&j+4<=m)
		if(a[i-1][j+1]=='n'&&a[i-2][j+2]=='u'&&a[i-3][j+3]=='k'&&a[i-4][j+4]=='e')
		{
			ok = true;
			cout<<i<<" "<<j<<endl;
			cout<<i-1<<" "<<j+1<<endl;
			cout<<i-2<<" "<<j+2<<endl;
			cout<<i-3<<" "<<j+3<<endl;
			cout<<i-4<<" "<<j+4<<endl;
			return ok;
		}
	if(i+4<=n&&j-4>=1)
		if(a[i+1][j-1]=='n'&&a[i+2][j-2]=='u'&&a[i+3][j-3]=='k'&&a[i+4][j-4]=='e')
		{
			ok = true;
			cout<<i<<" "<<j<<endl;
			cout<<i+1<<" "<<j-1<<endl;
			cout<<i+2<<" "<<j-2<<endl;
			cout<<i+3<<" "<<j-3<<endl;
			cout<<i+4<<" "<<j-4<<endl;
			return ok;
		}

	return ok;

}
int main()
{
	cin>>n>>m;
	for(int i = 1;i<=n;i++)
		for(int j = 1;j<=m;j++)
			cin>>a[i][j];
	for(int i = 1;i<=n;i++)
	{
		for(int j = 1;j<=m;j++)
		{
			if(a[i][j]=='s')
			{
				if(check(i,j))return 0;
			}
		}
	}
	return 0;
}

C - Almost Equal

Problem Statement

题意：给你\(N\)个长度为\(M\)的字符串，问你能否对这些字符串重新排列，使得第\(i\)个和第\(i+1\)个字符串只有一个字母不一样，可以输出\(Yes\),否则\(No\).

Solution

题解:因为注意到\(N\)范围很小，可以直接暴力\(dfs\)，先进性一个全排列，每次\(check\)是否满足。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,cnt;
const int N = 10;
string s[N];
int a[N];
bool vis[N];
map<int,string>mp;
bool yes;
void dfs(int step)
{
	if(yes)return;
	if(step>n)
	{
		bool ok = true;
		for(int i = 1;i<n;i++)
		{
			int c = 0;
			string t = mp[a[i]];
			string t2 = mp[a[i+1]];
			for(int j = 0;j<m;j++)
			{
				if(t[j]!=t2[j])c++;
			}
			if(c!=1)
			{
				ok = false;
				break;
			}
		}
		if(ok)yes = true;
		return;
	}	
	for(int i = 1;i<=n;i++)
	{
		if(!vis[i])
		{
			a[step] = i;
			vis[i] = true;
			dfs(step+1);
			vis[i] = false;
			a[step] = 0;
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i = 1;i<=n;i++)
		cin>>s[i],mp[++cnt] = s[i];
	dfs(1);
	if(yes)cout<<"Yes\n";
	else cout<<"No\n";
	return 0;
}

D - Impartial Gift

Problem Statement

题意：要为两个人选礼物，从\(N\)个候选中选一个给\(A\)，从\(M\)个候选中选一个给\(B\),问两个的价值相差不超过\(D\)，问你两个礼物总和最大为多少？

Solution

题解:排序+双指针。因为我们优先选价值高的，如果不满足价值差小于\(D\)就移动价值大的那个指针，因为这个时候移动小的只会更厘普。

注意\(A,B\)的范围，小心爆\(long long\)

#include<bits/stdc++.h>
using namespace std;
__int128 read()
{
	__int128 f = 1, w = 0;
	char ch = getchar();
	while (ch < '0' || ch>'9')
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch <= '9' && ch >= '0')
	{
		w = w * 10 + ch - '0';
		ch = getchar();
	}
	return f * w;
}

void print(__int128 x)
{
	if (x < 0)
	{
		putchar('-');
		x = -x;
	}
	if (x > 9)print(x / 10);
	putchar(x % 10 + '0');
}

typedef __int128 ll;
const int N = 2e5+10;
ll n,m,D;
ll a[N],b[N];
bool cmp(ll a,ll b)
{
	return a>b;
}
int main()
{
	n = read(),m = read(),D = read();
	for(int i = 1;i<=n;i++)
		a[i] = read();
	for(int i = 1;i<=m;i++)
		b[i] = read();
	sort(a+1,a+1+n,cmp);
	sort(b+1,b+1+m,cmp);
	ll c = 1,d = 1;
	bool ok = false;
	ll ans = 0;
	while(c<=n&&d<=m)
	{

		if((a[c]-b[d]>=0&&a[c]-b[d]<=D)||(b[d]-a[c]>=0&&b[d]-a[c]<=D))
		{
			ok = true;
			ans = a[c]+b[d];
			break;
		}
		else
		{
			if(a[c]>b[d])c++;
			else d++;
		}
	}
	if(ok)
		print(ans);
	else cout<<-1<<endl;
	return 0;
}

E - Isolation

Problem Statement

题意:给你一个无向图，\(N\)个点，编号\(1\)到\(N\),并且初始状态没有边。

给你\(Q\)个询问，每次询问输出当前孤立的点的数目。

\(1\) $ u$ $ v$ :连接\(uv\)

$2 $ $ v$ ：删除和\(v\)相连的所有边

Solution

题解：用\(set\)存边，先说操作一：对于点x,y,连接他们两个，如果set[x].size()==0的话，那现在连上了，那答案-1，同样对于\(y\)也是。对于操作二：删边操作。我们遍历该点连的所有边，用lower_bound直接erase掉对应点和\(x\)的边，如果删完之后edge[y].size()变为0了，那答案+1，最后如果对于操作的点\(x\)，如果edge[x].size是大于0的，那答案-1，edge[x].clear。解决。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5+10;
int cnt;
map<pair<int,int>,int>mp;
set<int>edge[N];
int main()
{
	int n,q;
	cin>>n>>q;
	cnt = n;
	for(int i = 1;i<=q;i++)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int x,y;
			cin>>x>>y;	
			cnt -= edge[x].empty(),cnt-=edge[y].empty();
			edge[x].insert(y);
			edge[y].insert(x);
			cout<<cnt<<endl;
		}
		else
		{
			int x;
			cin>>x;
			for(auto y:edge[x])
			{
				edge[y].erase(edge[y].lower_bound(x));
				cnt += edge[y].empty();
			}
			if(edge[x].size())
				cnt++,edge[x].clear();
			cout<<cnt<<endl;
		}
	}
	return 0;
}

F - Merge Set

Problem Statement

题意:给你\(N\)个集合，我们每次选2个集合进行合并，这两个集合要至少有一个一样的元素才能合并，问至少合并多少次能使得集合中包含\(1\)到\(M\)所有元素。

Solution

思路：是01bfs。我们考虑把\(N\)个集合看成\(N\)个点，\(M\)个元素看成\(M\)个点，建图跑最短路。当前集合到集合内元素的距离设为0，集合元素到集合的距离设为1，跑bfs或者dijkstra都可以。因为是求合并次数，最后答案-1.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
struct Node
{
	int y,v;
	Node(int _y,int _v){y = _y;v = _v;};
};
set<pair<int,int>>q;
vector<Node>edge[N*2];
int n,m,k, dist[N*2];
inline void dijkstra(int s)
{
	memset(dist,127,sizeof(dist));
	dist[s] = 0;
	q.clear();
	for(int i = 1;i<=n+m;i++)
	{
		q.insert({dist[i],i});
	}
	while(!q.empty())
	{
		int x = q.begin()->second;//离起点最近的点的下标
		q.erase(q.begin());
		for(auto i:edge[x])
		{
			if(dist[x]+i.v<dist[i.y])
			{
				q.erase({dist[i.y],i.y});
				dist[i.y]= dist[x]+i.v;
				q.insert({dist[i.y],i.y});
			}
			
		}
	}
}


int main()
{
	cin>>n>>m;
	for(int i = 1;i<=n;i++)
	{
		int sz;
		cin>>sz;
		for(int j = 1;j<=sz;j++)
		{
			int x;
			cin>>x;
			edge[i].push_back(Node(x+n,0));
			edge[x+n].push_back(Node(i,1));
		}
	}
	dijkstra(1+n);
	ll ans = dist[m+n];
	if(ans>(1<<30))ans= 0;
	cout<<ans-1<<endl;
	return 0;
}

标签：AtCoder,cout,int,302,long,edge,&&,ABCDEF,ll
From： https://www.cnblogs.com/nannandbk/p/17487010.html

相关文章

  • AtCoder Beginner Contest 305 ABCDE
    AtCoderBeginnerContest305A-WaterStationProblemStatement题意：水站每\(5km\)设一个，给你一个\(N\)\(km\)的位置，问你离它最近的水站位置。Solution题解：模5在乘5,比较给出的点的左边和右边的点，取min#include<bits/stdc++.h>usingnamespacestd;intmain(){ int......
  • 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......
  • AtCoder Beginner Contest 305 题解 A - F
    A-WaterStation题目大意找到离给定的数最近的一个\(5\)的倍数输出即可。解题思路我们取这个数对\(5\)的上下界，也就是整数除以\(5\)再乘以\(5\)，以及这个数再加上一个\(5\)，比较这两数和给定数的距离即可。ACCode#include<iostream>#include<algorithm>#includ......
  • AtCoder Beginner Contest 219 H Candles
    洛谷传送门AtCoder传送门套路化了。比较显然的关路灯型区间dp。考虑你\(t\)时刻熄灭一个初始长度为\(a\)的蜡烛，得分是\(\max(a-t,0)\)，所以尝试把时间塞进状态。设\(f_{i,j,k,0/1}\)表示，熄灭完区间\([i,j]\)的蜡烛，当前时间是\(t\)，在左端点还是右端点的最大得......
  • AtCoder Beginner Contest 223 H Xor Query
    洛谷传送门AtCoder传送门考虑一个无脑做法：线段树维护区间线性基。时间复杂度是\(O(m\logn\log^2V)\)，过于优秀以至于无法接受。事实上我们并不需要维护区间线性基，因为不带修。考虑“可持久化线性基”，开\(n\)个线性基，第\(i\)个维护前缀\([1,i]\)的数。并且插入线性......
  • AtCoder Beginner Contest 215 H Cabbage Master
    洛谷传送门AtCoder传送门考虑第一问。发现这个东西长得很像二分图匹配，考虑建图，第\(i\)个盒子建\(b_i\)个左部点，第\(i\)个球建\(a_i\)个右部点，每个盒子的每个点往可以放的球的每个点连边。显然要求能被满足等价于，这个二分图存在一个左部点的完全匹配。因为一个盒子的......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99