526互联

Codeforces [Hello 2024]

发布时间 2024-01-10 12:51:13作者: zfxyyy

Codeforces Hello 2024

主打一个昏了头

A. Wallet Exchange

#include <bits/stdc++.h>
#define endl '\n'
//#define int long long
using namespace std;

const int N = 2e5 + 10;
int a,b;

void solve(){
	cin>>a>>b;
	if((a+b)&1) cout<<"Alice"<<endl;
	else		cout<<"Bob"<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T = 1;
	cin >> T;
	while(T--) solve();
    return 0;
}

B. Plus-Minus Split

#include <bits/stdc++.h>
#define endl '\n'
//#define int long long
using namespace std;

const int N = 2e5 + 10;

void solve(){
	string s;
	int n;
	cin>>n>>s;
	long long ans = 0;
	deque<int> path;
	for(int i=0;i<n;i++){
		int x;
		if(s[i]=='+') x=1;
		else		  x=-1;
		if(!path.size()) path.push_back(x);
		else{
			if(x+path.back()==0) path.pop_back();
			else				 path.push_back(x);
		}
	}
	cout << path.size() <<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T = 1;
	cin >> T;
	while(T--) solve();
    return 0;
}

C. Grouping Increases

昨晚贪半天没贪明白也是蠢

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 2e5 + 10;
int n;
int a[N];

void solve(){
	cin >> n;
	for(int i = 1; i <= n;i++) cin>>a[i];

	deque<int> path1,path2;
	path1.push_back(1e10);
	path2.push_back(1e10);
	for(int i=1;i<=n;i++)
	{
		int x=path1.back();
		int y=path2.back();
		if(a[i]<=x&&a[i]<=y)
		{
			if(x<=y) path1.push_back(a[i]);
			else     path2.push_back(a[i]);
		}else 
		if(a[i]>x&&a[i]>y)
		{
			if(x<=y) path1.push_back(a[i]);
			else	 path2.push_back(a[i]);
		}
		else if(a[i]<=x) path1.push_back(a[i]);
		else if(a[i]<=y) path2.push_back(a[i]);
	}

	long long ans = 0;
	for(int i=1;i+1<path1.size();i++)
		if(path1[i]<path1[i+1]) ans++;
	for(int i=1;i+1<path2.size();i++)
		if(path2[i]<path2[i+1]) ans++;
	cout << ans <<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T = 1;
	cin >> T;
	while(T--) solve();
    return 0;
}

D. 01 Tree

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 2e5 + 10;
int a[N];
int l[N];
int r[N];

void del(int x){
	r[l[x]] = r[x];
	l[r[x]] = l[x];
}

void solve(){
	int n;
	cin >> n;
	vector<vector<int>> G(n+1);
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
		G[a[i]].push_back(i);
		l[i] = i-1;
		r[i] = i+1;
	}
	if(G[0].size()!=1)
	{
		cout << " NO " <<endl;
		return;
	}
	for(int i=n-1;i>0;i--)
	{
		int ll,rr;
		for(int j=0;j<G[i].size();j++)
		{
			ll=j;
			while(j+1<G[i].size()&&r[G[i][j]]==G[i][j+1]) j++;
			rr=j;
			//cout<<ll<<" "<<rr<<endl;
			if((r[G[i][rr]]<=n&&a[r[G[i][rr]]]==i-1)||(l[G[i][ll]]>0&&a[l[G[i][ll]]]==i-1))
			{

			}else{
				// cout<<ll<<" "<<rr<<endl;
				// cout<<r[G[i][rr]]<<" "<<a[r[G[i][rr]]]<<endl;
				// cout<<l[G[i][ll]]<<" "<<a[G[i][ll]-1]<<endl;
				// cout<<i<<" "<<j<<" "<<G[i][j]<<endl;
				cout<<"NO"<<endl;
				return;
			}
			for(int k=ll;k<=rr;k++) del(G[i][k]);
			j = rr;	
		}
	}
	cout<<"YES"<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T = 1;
	cin >> T;
	while(T--) solve();
    return 0;
}