首页 > 其他分享 >Codeforces Round 898 (Div. 4)(A~H)

Codeforces Round 898 (Div. 4)(A~H)

时间：2024-07-17 10:59:57浏览次数：16  
标签：const 898 Codeforces long cin int Div include define

目录

A. Short Sort

B. Good Kid

C. Target Practice

D. 1D Eraser

E. Building an Aquarium

F. Money Trees

G. ABBC or BACB

H. Mad City

A. Short Sort

Problem - A - Codeforces

暴力枚举每个位置的交换即可。

#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#include<cstring>
#include<set>
#include<map>
#define int long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 1000010;
const int M = 1e9 + 7;
const int bit=63;
inline void solve() {
	string s;
	cin>>s;
	if(s=="abc")
	{
		cout<<"YES\n";
		return ;
	}
	for(int i=0;i<3;i++)
	{
		for(int j=i+1;j<3;j++)
		{
			string t=s;
			swap(t[i],t[j]);
			if(t=="abc")
			{
				cout<<"YES\n";
				return;
			}
		}
	}
	cout<<"NO\n";
}
signed main() {
	TEST
	solve();
	return 0;
}

B. Good Kid

Problem - B - Codeforces

将最小的数加上1，再全部相乘就是答案。

#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#include<cstring>
#include<set>
#include<map>
#define int long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 1000010;
const int M = 1e9 + 7;
const int bit=63;
inline void solve() {
	int n;
	cin>>n;
	int a[n+1];
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+1+n);
	int ans=1;
	a[1]++;
	for(int i=1;i<=n;i++)
	{
		ans*=a[i];
	}
	cout<<ans<<"\n";
}
signed main() {
	TEST
	solve();
	return 0;
}

C. Target Practice

Problem - C - Codeforces

经典的if语句判断。

#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#include<cstring>
#include<set>
#include<map>
#define int long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 1000010;
const int M = 1e9 + 7;
const int bit=63;
inline void solve() {
	char x;
	int ans=0;
	for(int i=1;i<=10;i++)
	{
		for(int j=1;j<=10;j++)
		{
			cin>>x;
			if(x=='X')
			{
				if(i>=5&&i<=6&&j>=5&&j<=6) 
				{
					ans+=5;
				}
				else if(i>=4&&i<=7&&j>=4&&j<=7)
				{
					ans+=4;
				}
				else if(i>=3&&i<=8&&j>=3&&j<=8)
				{
					ans+=3;
				}
				else if(i>=2&&i<=9&&j>=2&&j<=9)
				{
					ans+=2;
				}
				else ans++;
				
				
			}
		}
	}
	cout<<ans<<"\n";
}
signed main() {
	TEST
	solve();
	return 0;
}

D. 1D Eraser

Problem - D - Codeforces

从头枚举，找到B的位置，答案加一，从这开始的前k-1个位置的B不用给答案+1。

#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#include<cstring>
#include<set>
#include<map>
#define int long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 1000010;
const int M = 1e9 + 7;
const int bit=63;
inline void solve() {
	int n,k;
	cin>>n>>k;
	string s;
	cin>>s;
	int ans=0,cnt=0;
	for(int i=0;i<n;i++){
		cnt--;
		if(s[i]=='B'&&cnt<=0)
		{
			ans++;
			cnt=k;
		}
	}
	cout<<ans<<"\n";
}
signed main() {
	TEST
	solve();
	return 0;
}

E. Building an Aquarium

Problem - E - Codeforces

经典的二分答案，都是有一个坑，就是r要开你比你想的大一些。

#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#include<cstring>
#include<set>
#include<map>
#define int long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 1000010;
const int M = 1e9 + 7;
const int bit=63;
int a[N];
int n,x;
bool check(int xx)
{
	int sum=0;
	for(int i=1;i<=n;i++) sum+=max(0ll,xx-a[i]);
	
	return sum<=x;
}
inline void solve() {

	cin>>n>>x;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	int L=1,R=1e12,ans;
	
	while(L<=R)
	{
		int mid=L+R>>1;
		if(check(mid)) 
		{
			ans=mid;
			L=mid+1;
		}
		else R=mid-1; 
 	}
	
	cout<<ans<<"\n";
}
signed main() {
	TEST
	solve();
	return 0;
}

F. Money Trees

Problem - F - Codeforces

也是一道二分答案的题，不过也可以贪心加双指针解决，这里给出两份代码。

二分答案：

#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#include<cstring>
#include<set>
#include<map>
#define int long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 200010;
const int M = 1e9 + 7;
const int bit = 63;
int sum[N], h[N], a[N];
int n, k;
vector<pair<int, int>>f;

bool check(int x)
{
	for(int i=0;i<f.size();i++)
	{
		if(f[i].second-f[i].first+1<x) continue;
		for(int j=f[i].first;j<=f[i].second-x+1;j++)
		{
			if(sum[j+x-1]-sum[j-1]<=k) return true;
		}
	}
	return false;
}
inline void solve() {
	f.clear();
	
	cin >> n >> k;

	for (int i = 1; i <= n; i++) cin >> a[i], sum[i] = sum[i - 1] + a[i];

	for (int i = 1; i <= n; i++) cin >> h[i];

	if(n==1)
	{
		if(a[1]>k)
		{
			cout<<0<<"\n";
		}
		else
		{
			cout<<1<<"\n";
			
		}
		return;
	}
	int l, r;
	l = r = 1;
	for (int i = 2; i <= n; i++) {
		if (h[i - 1] % h[i] == 0) {
			r++;
		} else {
			f.push_back({l,r});
			l = r = i;
		}
	}
	
	f.push_back({l,r});
	
	l=1,r=N;
	while(l<=r)
	{
		int mid=l+r>>1;
		if(check(mid)) 
		{
			l=mid+1;
		}
		else r=mid-1;
	}
	cout<<r<<"\n";
	
}
signed main() {
	TEST
	solve();
	return 0;
}

贪心+双指针：

#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#include<cstring>
#include<set>
#include<map>
#define int long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 1000010;
const int M = 1e9 + 7;
const int bit = 63;
int sum[N], a[N], h[N];
inline void solve() {
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> a[i], sum[i] = sum[i - 1] + a[i];
	for (int i = 1; i <= n; i++) cin >> h[i];
	int mx = 0;
	int l = 1, r = 1;
	while(r<=n)
	{
		if(h[r-1]%h[r]) l=r;
		while(sum[r]-sum[l-1]>k) l++;
		mx=max(mx,r-l+1);
		r++;
	}
	cout<<mx<<"\n";
}
signed main() {
	TEST
	solve();
	return 0;
}

G. ABBC or BACB

Problem - G - Codeforces

先是模拟了一个，发现用贪心就可以解决。

找到所有的连续A段，再找到字符串元素B的个数。将每个A段按照长度从大到小排序，每个A短对应一个元素B，答案加上A段的长度，最后得到答案。

#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#include<cstring>
#include<set>
#include<map>
#define int long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 1000010;
const int M = 1e9 + 7;
const int bit = 63;
struct node {
	int l, r;
} e[N];
bool cmp(node a,node b)
{
	return a.r-a.l>b.r-b.l;
}
inline void solve() {
	string s;
	cin >> s;
	int n = s.size();
	s = '#' + s;

	int l = -1, r, c = 0,B=0;
	for (int i = 1; i <= n; i++) {
		if(s[i]=='B') B++;
		
		if (s[i] == 'A' && l == -1) {
			l = i;
			r = i;
		} else if (s[i] == 'A' && l != -1) {
			r++;
		} else {
			if (l != -1) {
				e[++c].l = l;
				e[c].r = r;
				l = -1;
			}
		}
	}
	if (l != -1) {
		e[++c].l = l;
		e[c].r = r;
		l = -1;
	}
	
	sort(e+1,e+1+c,cmp);
	
	int ans=0;
	
	for(int i=1;i<=c;i++)
	{
		if(B==0) break;
		ans+=(e[i].r-e[i].l+1);
		B--;
	}
	
	cout<<ans<<"\n";
}
signed main() {
	TEST
	solve();
	return 0;
}

H. Mad City

Problem - H - Codeforces

题目给出限制，每两个顶点最多有一条边相连，有n条边n个顶点，那么就必成一个环，我们要找到的是b到环中最近的一个顶点叫做入环点。我们需要判断b到入环点的距离严格小于a到入环点的距离。

第一步：

找入环点，如果b已经在一个环中，那么它本身就是入环点，反之从b开始搜索，遍历过的点标记，当遍历到一个已经遍历过的点，并且这个点不是它的父节点，那么这个点就是入环点。

第二步：找a和b到入环点的最短路径。

b的最短路径小于a的最短路径，则输出"YES"反之输出"NO"。

#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#include<cstring>
#include<set>
#include<map>
#define int long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 200010;
const int M = 1e9 + 7;
const int bit = 63;
int n, a, b, huan = -1, vis[N];
vector<int>f[N];
bool dfs(int u, int p) {
	vis[u] = true;
	for (auto v : f[u]) {
		if (v != p && vis[v]) {
			huan = v;
			return true;
		} else if (v != p && !vis[v]) {
			if (dfs(v, u)) {
				return true;
			}
		}
	}
	return false;
}
void bk() {
	for (int i = 1; i <= n; i++) {
		f[i].clear();
	}
}
int ans1 = 1e9, ans2 = 1e9;
int dfs2(int u)
{
    vis[u] = 1;
    int ans = 1e9;
    for(auto v : f[u])
    {
        if(v == huan)
        {
            return 1;
        }
        if(!vis[v])
        {
            int dist = dfs2(v)+1;
            ans = min(dist, ans);
        }
    }
    return ans;
}
inline void solve() {
	bk();
	ans1 = 1e9, ans2 = 1e9;
	cin >> n >> a >> b;
	huan = -1;
	for (int i = 1; i <= n; i++) {
		int u, v;
		cin >> u >> v;
		f[u].push_back(v);
		f[v].push_back(u);
	}
	if (n == 3 && a != b) {
		cout << "YES\n";
		bk();
		return;
	}
	if (a == b) {
		cout << "NO\n";
		bk();
		return;
	}
	//标记成环点
	memset(vis, 0, sizeof(vis));
	dfs(b, -1);
	memset(vis, 0, sizeof(vis));
	if (b == huan) {
		ans1 = 0;
	} else
		ans1 = dfs2(b);
	memset(vis, 0, sizeof(vis));
	if (a == huan) {
		ans2 = 0;
	} else
		ans2 = dfs2(a);
	if (ans1 < ans2) {
		cout << "YES\n";
		return;
	} else {
		cout << "NO\n";
		return ;
	}
	bk();
}
signed main() {
	TEST
	solve();
	return 0;
}

标签：const,898,Codeforces,long,cin,int,Div,include,define
From： https://blog.csdn.net/2301_80314483/article/details/140487977

相关文章

  • CF1898D Absolute Beauty 题解
    思路容易发现，如果\(a_i>b_i\)则将\(a_i\)和\(b_i\)交换。在数轴上标出要交换的四个数的位置若线段\(a_ib_i\)和线段\(a_jb_j\)互不相交，此时交换比两条线段处于其他位置时更优。具体证明这里就不再赘述，其他题解讲的已经很清楚了。所以只需交换最大的\(a_i\)和最小......
  • Codeforces Round 957 (Div. 3)
    题目链接：CodeforcesRound957(Div.3)总结：E不懂，F差一个set去重A.OnlyPlusesfag：枚举B.AngryMonkfag：模拟Solution：分裂的花费为\(a_i-1\)，添加的花费为\(a_i\)。C.GorillaandPermutationfag：思维Solution：大于等于\(k\)的数，逆序放在最前面，小于等于\(m\)的数，从最后面......
  • Codeforces Round 958 (Div. 2)补题
    文章目录A题(拆分多集)B题(获得多数票)C题（固定OR的递增序列）A题(拆分多集) 本题在赛时卡的时间比较久，把这题想复杂了，导致WA了两次。后来看明白之后就是将n每次转换成k-1个1，到最后分不出来k-1个1直接一次就能分完，即结果加一；#include<bits/stdc++.h>#definein......
  • CodeForces 1983A Array Divisibility
    题目链接：CodeForces1983A【ArrayDivisibility】思路    按规律可得，当a[i]=i时满足题目要求。代码#include<functional>#include<iostream>#include<algorithm>#include<queue>#include<stdio.h>#include<string>#include<cstring......
  • CodeForces 1983B Corner Twist
    题目链接：CodeForces1983B【CornerTwist】思路    可以发现操作一次，被操作位置的对应每一横行和每一纵行的加减数都是3，所以可以根据网格a和b的横纵状态确定是否通过操作使得网格a到达网格b。代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglo......
  • CodeForces 1992A Only Pluses
    题目链接：CodeForces1992A【OnlyPluses】思路    代码#include<functional>#include<iostream>#include<algorithm>#include<queue>usingnamespacestd;#definelllonglongconstintN=500+10;inta[N];voidsolve(){intn......
  • CodeForces 1992D Test of Love
    题目链接：CodeForces1992D【TestofLove】思路    从起点开始起跳，找出下一个木头的位置，若与当前位置的距离小于等于m，则可以直接跳过去，否则判断当前位置与下一个木头之间有没有鳄鱼，有鳄鱼则不能到达对岸，否则继续查找下一个木头，直到对岸。代码#include<functional>......
  • CodeForces 1992E Novice's Mistake
    题目链接：CodeForces1992E【Novice'sMistake】思路    直接对a,b枚举肯定会超时，因为a,b数数字过大，但是通过结果a*n-b可以发现结果最多为6位数，所以对结果的位数进行枚举，然后枚举a，来计算出b并判断是否符合题意，同时需要去掉b不符合题目的范围的情况。代码#includ......
  • CodeForces - 1485F
    题目大意给定数组\(b\)，求有多少\(a\)数组满足\(a_i=b_i\or\\sum\limits_{k=1}^ia_k=b_i\)。分析既然有前缀和，不妨将前缀和计入状态中，设\(dp_{i,j}\)为前\(i\)个前缀和为\(j\)的方案数。考虑两种条件的转移方程。若选第一种，有\(dp_{i,j}=dp_{i-1,j-b_i}\)若......
  • Codeforces Round #956 (Div. 2) and ByteRace 2024
    目录写在前面ABCDEF写在最后写在前面比赛地址：https://codeforces.com/contest/1983孩子们我回来了。这场实在是太对胃口，vp不到1h就4题了之后EF也口出来了，然而赛时睡大觉去了没打真是亏死。感觉自己的文字能力已经很牛逼了，不需要再多练了，以后的题解都会写得简略些。A......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99