2024-1-21

1787C - Remove the Bracket

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

const int N = 2e5 + 10;
int n,k;
int a[N];
int b[N][2];
int dp[N][2];

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

	b[1][0] = b[1][1] = a[1];
	b[n][0] = b[n][1] = a[n];
	for(int i=2;i<n;i++)
	{
		if(a[i] >= k)
		{
			b[i][0] = k;
			b[i][1] = a[i] - k; 
		}
		else
		{
			b[i][0] = 0;
			b[i][1] = a[i];
		}
	}
	b[1][0] = b[1][1] = a[1];
	b[n][0] = b[n][1] = a[n];
	for(int i=2;i<=n;i++)
	{
		dp[i][0] = min(dp[i-1][0]+b[i-1][1]*b[i][0],dp[i-1][1]+b[i-1][0]*b[i][0]);
		dp[i][1] = min(dp[i-1][0]+b[i-1][1]*b[i][1],dp[i-1][1]+b[i-1][0]*b[i][1]);
		//cout << dp[i][0] << " " << dp[i][1] <<endl;
	}
	cout << min(dp[n][0],dp[n][1]) << endl;
}

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

1393C - Pinkie Pie Eats Patty-cakes

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

const int N = 1e5 + 10;
int cnt[N];
int n;

void solve()
{		
	int n;
	cin >> n;
	int z = -1;
	memset(cnt,0,sizeof cnt);
	for(int i=1;i<=n;i++)
	{
		 int x;
		 cin >> x;
		 cnt[x]++;
		 z = max(z,cnt[x]);
	}
	int x = 0;
	for(int i=1;i<=n;i++)
		if(cnt[i]==z) x++;

	cout << (n - x * z) / (z - 1) + x - 1 << endl;
}

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

1334C - Circle of Monsters

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

const int N = 6e5 + 10;
int a[N],b[N];
int pre1[N],pre2[N];
int n;

void solve()
{		
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i] >> b[i];
		a[i+n] = a[i];
	}
	for(int i=1;i<=n;i++)
	{
		b[i] = min(b[i],a[i+1]);
		b[i+n] = b[i];
	}
	for(int i=1;i<=2*n;i++)
	{
		pre1[i] = pre1[i-1] + a[i];
		pre2[i] = pre2[i-1] + b[i];
	}

	int ans = 1e18;
	/*
		7 2 5 7 2 5
		2 5 3 2 5 3
	*/
	for(int i=1;i<=n;i++)
	{
		int x = pre1[i+n-1] - pre1[i-1];
		int y = pre2[i+n-2] - pre2[i-1];
		//cout << x <<" "<<y<<endl;
		ans = min(ans,x-y);
	}
	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;
}

1411C - Peaceful Rooks

这题有点意思啊

看题解看半天

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

const int N = 1e5 + 10;
int fa[N];
int n,m;

int find(int x){
	return x==fa[x] ? x : fa[x] = find(fa[x]);
}

void solve()
{		
	cin >> n >>m;
	int ans = 0;
	for(int i=1;i<=n;i++) fa[i] = i;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin >> x >> y;
		if(x==y) continue;
		ans++;
		int ta=find(x);
		int tb=find(y);
		if(ta==tb) ans++;
		else fa[ta] = tb;
	}
	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;
}