首页 > 其他分享 >Codeforces Round 923 (Div. 3)(A~F)

Codeforces Round 923 (Div. 3)(A~F)

时间:2024-02-07 13:12:25浏览次数:33  
标签:int rep Codeforces long cin pair Div 923 define

目录

A

image

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back

using namespace std;

void solve()
{
	int n;cin>>n;
	string s;cin>>s;
	int x=0,y=0;
	rep(i,0,s.size()-1){
		if(s[i]=='B')	y=i;
	}
	fep(i,s.size()-1,0){
		if(s[i]=='B')	x=i;
	}
	cout<<y-x+1<<endl;
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//   	freopen("1.in", "r", stdin);
  	int _;
	cin>>_;
	while(_--)
	solve();
	return 0;
}

B

image

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back

using namespace std;

void solve()
{
	int n;
	cin>>n;
	vector<int>a(n+1);
	rep(i,1,n)	cin>>a[i];
	map<int,set<char>>kk;
	for(char i='a';i<='z';++i){
		kk[0].insert(i);
	}
	string ans;
	rep(i,1,n){
		int cnt=a[i];
		char c=*kk[cnt].begin();
		kk[cnt].erase(c);
		kk[cnt+1].insert(c);
		ans+=c;
	}
	cout<<ans<<endl;
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//   	freopen("1.in", "r", stdin);
  	int _;
	cin>>_;
	while(_--)
	solve();
	return 0;
}

C

image

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back

using namespace std;

void solve()
{
	int n,m,k;
	cin>>n>>m>>k;
	vector<int>a(n+1),b(m+1);
	set<int>s1,s2;
	rep(i,1,n){
		cin>>a[i];
		s1.insert(a[i]);
	}
	rep(i,1,m){
		cin>>b[i];
		s2.insert(b[i]);
	}
	
	if(s1.size()<k/2||s2.size()<k/2){
		cout<<"No"<<endl;
		return;
	}
	int cnta=0,cntb=0,cntss=0;
	rep(i,1,k){
		if(s1.count(i)&&s2.count(i)){
			cntss++;
		}else if(s1.count(i)&&!s2.count(i)){
			cnta++;
		}else if(!s1.count(i)&&s2.count(i)){
			cntb++;
		}else{
			cout<<"No"<<endl;
			return;
		}
	}
	if(cnta<k/2){
		cntss-=(k/2-cnta);
	}
	if(cntb<k/2){
		cntss-=(k/2-cntb);
	}
	if(cntss<0){
		cout<<"No"<<endl;
	}else{
		cout<<"Yes"<<endl;
	}
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//   	freopen("1.in", "r", stdin);
  	int _;
	cin>>_;
	while(_--)
	solve();
	return 0;
}

D

image

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
//#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back

using namespace std;
const int N=1e6+10;

#include <iostream>
using namespace std;


void solve()
{
	int n;cin>>n;
	vector<int>a(n+1),lmin(n+1),lmax(n+1);
	rep(i,1,n){
		cin>>a[i];
		lmin[i]=lmax[i]=0;
	}
	stack<int>stk;
	rep(i,1,n){
		while(stk.size()&&a[i]<=a[stk.top()])	stk.pop();
		if(stk.size()){
			lmin[i]=stk.top();
		}	
		stk.push(i);
	}
	while(stk.size())	stk.pop();
	rep(i,1,n){
		while(stk.size()&&a[i]>=a[stk.top()])	stk.pop();
		if(stk.size()){
			lmax[i]=stk.top();
		}	
		stk.push(i);
	}
//	rep(i,1,n)	cout<<lmin[i]<<' ';
//	cout<<endl;
//	rep(i,1,n)	cout<<lmax[i]<<' ';
//	cout<<endl;
	int q;cin>>q;
	while(q--){
		int l,r;cin>>l>>r;
		int minn=lmin[r],maxx=lmax[r];
		if(minn>=l){
			cout<<minn<<' '<<r<<endl;
		}else if(maxx>=l){
			cout<<maxx<<' '<<r<<endl;
		}else{
			cout<<"-1 -1"<<endl;
		}
	}
	cout<<endl;
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//   	freopen("1.in", "r", stdin);
  	int _;
	cin>>_;
	while(_--)
	solve();
	return 0;
}

E

image

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back

using namespace std;
const int N=1e6+10;

#include <iostream>
using namespace std;


void solve()
{
	int n,k;cin>>n>>k;
	vector<int>ans(n+1);
	int bb=1,dd=n;
	rep(i,1,k){
		if(i&1){
			//从大到小去放
			for(int j=i;j<=n;j+=k){
				ans[j]=dd--;
			}
		}else{
			//从小到大去放
			for(int j=i;j<=n;j+=k){
				ans[j]=bb++;
			}
		}
	}
	rep(i,1,ans.size()-1)	cout<<ans[i]<<' ';
	cout<<endl;
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//   	freopen("1.in", "r", stdin);
  	int _;
	cin>>_;
	while(_--)
	solve();
	return 0;
}

F

image

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back

using namespace std;

const int N=2e5+10;
int fa[N];
struct edge{
	int x,y,w;
}e[N];
vector<int>g[N];

int find(int x){
	if(x==fa[x])	return x;
	return fa[x]=find(fa[x]);
}
int n,m;

vector<int>path;
int vis[N];
void dfs(int u,int tag){
	vis[u]=1;
	path.pb(u);
	if(u==tag){
		cout<<path.size()<<endl;
		for(auto i:path)	cout<<i<<' ';
		cout<<endl;
	}else{
		for(auto y:g[u]){
			if(vis[y])	continue;
			dfs(y,tag);
		}
	}
	path.pop_back();
}

void solve()
{
	cin>>n>>m;
	rep(i,1,n)	fa[i]=i;
	rep(i,1,n)	vis[i]=0;
	path.clear();
	rep(i,1,n)	if(g[i].size())	g[i].clear();
	rep(i,1,m){
		int u,v,w;cin>>u>>v>>w;
		e[i]={u,v,w};
	}
	sort(e+1,e+1+m,[&](edge t1,edge t2){return t1.w>t2.w;});
	
	int id=0,ans=1e9;
	rep(i,1,m){
		int u=find(e[i].x),v=find(e[i].y);
		if(u==v){
			id=i;
			ans=min(ans,e[i].w);
		}else{
			fa[u]=v;
		}		
	}
	cout<<ans<<' ';
	rep(i,1,m){
		if(id==i)	continue;
		int x=e[i].x,y=e[i].y;
		g[x].pb(y);g[y].pb(x);
	}
	dfs(e[id].x,e[id].y);
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//   	freopen("1.in", "r", stdin);
  	int _;
	cin>>_;
	while(_--)
	solve();
	return 0;
}

标签:int,rep,Codeforces,long,cin,pair,Div,923,define
From: https://www.cnblogs.com/cxy8/p/18010833

相关文章

  • Codeforces-Hello-2024-Round
    比赛链接A.WalletExchange签到,某个人操作的时候只要一方有金币就行,所以最终赢的应该是拿到最后一个硬币的人,当\(a+b\equiv1\pmod2\)的时候Alice获胜,否则Bob获胜。时间复杂度\(\mathcal{O}(1)\)。codeforA#include<bits/stdc++.h>usingnamespacestd;inli......
  • CF1401E Divide Square 题解
    解题思路其实多看几组也能发现块数等于交点的数量加上两个端点都在边上的线段数量再加一。证明如下(图见样例):对于两条只有一个端点位于边上的线段,因为保证有一个端点位于边上,那么这两条线段的交点一定会和已存在的点、边构成一个新的矩形;对于其中有一条为两个端点均位于边上的......
  • Codeforces Round 920 (Div. 3)(A~F)
    目录ABCDEFA按题意模拟即可#include<bits/stdc++.h>#defineintlonglong#definerep(i,a,b)for(inti=(a);i<=(b);++i)#definefep(i,a,b)for(inti=(a);i>=(b);--i)#definepiipair<int,int>#definepllpair<longlong,longlong......
  • Codeforces div2 C题补题
    Codeforcesdiv2C题补题1922C.ClosestCitiesC.ClosestCities很容易看出,端点的两个城市的最近城市就是他的直接后继和直接前驱,而中间的城市的最近城市就是他前驱和后继中距离绝对值最小的那个,因此我们可以先预处理出每个城市对应的最近城市,用map存储。然后因为区间可以从......
  • 从BigDecimal的divide的异常说起
    在过去做项目的某一天中,突然有小伙伴说两个BigDecimal的数据相除(divide)报错了,觉得不可能,然后问他是怎么编写的,他说很简单呀,就是new了2个BigDecimal,然后相除的结果赋值给另外一个BigDecimal对象。听起来觉得没有问题,正常来说,2个Integer(int),2个Double(double)都不会报错,然后问是什么......
  • Codeforces Round 913 (Div. 3) G.
    题目链接G.把灯看成节点,灯之间的关系看成有向边得到基环树森林若节点的入度为0,那么它一定要用一次开关,这是可以确定的所以用拓扑,把这些确定贡献的节点删去然后就剩下了若干个环若环上有奇数个权值为1的节点,那么不可能全部关上对于环上一个打开的灯,它要么直接用自己的开关......
  • Codeforces Round 921 (Div. 1) 题解
    HelloAd-HocForces!A字符集为前\(k\)个小写字母,给定长度为\(m\)的字符串,求所有的长度为\(n\)的字符串是否是这个字符串的子串。(此处字串不连续)如果不是需要给出反例。\(1\len,k\le26\),\(1\lem\le1000\)。\(\sumn,\summ\le10^6\)sol.D1A就是神秘贪心,汗流浃背......
  • Codeforces Round 917 (Div. 2)
    https://codeforces.com/contest/1917A.LeastProduct*800给定整数数组,可以把数组中的数\(a_i\)改为\(0\sima_i\)中的任意整数,最小化所有数的乘积,在此基础上使操作次数最少讨论一下负数的个数和\(0\)的个数#include<bits/stdc++.h>usingnamespacestd;usingll......
  • left 3 Codeforces Round 913 (Div. 3)
    题目链接A.把同行同列除了起点都输出即可#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=2e5+10;voidsolve(){charc;inta;cin>>c>>a;for(inti=1;i<=8;i++){if(i==a)continue;cout<<c<......
  • CodeCraft-22 and Codeforces Round 795 (Div. 2)C. Sum of Substrings(分类讨论、贪
    感觉分类讨论的能有点弱。遇到复杂一点的分类讨论的题目,代码就写的巨长。首先观察到处在中间位置的1对答案的贡献是11,具体在中间哪个位置是没有关系的。只有两端的两个位置是比较特殊的\(1位置处的1对答案的贡献是10\)\(2位置处的1对答案的贡献是1\)所有我们考虑将最左端第一......