Codeforces Round 简单杂题

Problem C. Move Brackets

$$\begin{gathered} 给定n/2个左括号和n/2个右括号,每次可以把某个括号移动到括号序列的最左端或末尾,问最少移动次数 \\ 使得括号正确匹配,题目保证有解 \\ 我们只需要求有多少对括号没有匹配上就好,左右括号读入就像进栈一样 \end{gathered}$$

#include<iostream>
#include<algorithm>
using namespace std;
int t;
int main()
{
    cin>>t;
    while(t--)
    {
        int n;
        int ans=0;
        cin>>n;
        int cnta=0,cntb=0;//左括号数和右括号数
        string a;
        cin>>a;
        for(int i=0;i<n;i++)
        {
            if(a[i]=='(')
            cnta++;//扫描到了左括号，左括号入栈
            else
            {
                cnta--;//扫描到了右括号,左括号数--
                if(cnta<0)//如果栈内没有左括号,发现一个失配的右括号
                {
                    cnta=0;//负数清空
                    ans++;//计数
                }//如果cnta>=0说明正确匹配了
            }
        }
        cout<<ans<<endl;
    }
}

Problem A. Watermelon

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
    int w;
    cin>>w;
    if(w==2)cout<<"NO";
    else if(w&1)
    cout<<"NO";
    else
    cout<<"YES";
    return 0;
}

Problem B. Cows and Poker Game

$$\begin{gathered} 难点：However,soasnottoaffectanybettingdecisions,he/shemayonlydosoif \\ allotherplayershaveastatusofeither"ALLIN"or"FOLDED". \end{gathered}$$

$$\begin{gathered} 然而，为了不影响投注，他只能在其他玩家都是ALLIN或者FOLDED的时候这样做，（哪样做呢？） \\ aplayerwhosecurrentstatusisnot"FOLDED"mayshow \\ his/herhandtothetable.如果一个人的不是F，那么他就展示手牌 \end{gathered}$$

// Problem: B. Cows and Poker Game
// Contest: Codeforces - Codeforces Round #174 (Div. 2)
// URL: https://codeforces.com/contest/284/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms

/*Love coding and thinking!*/ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define pb push_back 
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo2(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
typedef pair<int,int>PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=2e5+10,M=1e9+7;
int n,m,_;
int cnta,cntb,cntc;
int main()
{
	cin>>n;
	string s;cin>>s;
	bool flag=1;
	for(auto c:s)
	{
		if(c=='I')
			cntc++,flag=false;
		if(c=='I')
			cnta++;
		else if(c=='A')
			cntb++;
	}
	if(flag)
		cout<<cnta+cntb;
	else if(cntc==1)
		cout<<1;
	else
		cout<<0<<endl;
	return 0;
}

Problem C. ABBB

$给一个串，把串中的子串"AB","BB"删去，问还剩几个字符$

会T的写法
    // Problem: C. ABBB
// Contest: Codeforces - Codeforces Raif Round 1 (Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/1428/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms

/*Love coding and thinking!*/ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define pb push_back 
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo2(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
typedef pair<int,int>PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=2e5+10,M=1e9+7;
int n,m,_;
//AABB
int main()
{
	cin>>_;
	while(_--)
	{
		string s;cin>>s;
		int t=s.find("AB");
		while(s.size()&&t!=-1)
		{
			s.erase(t,2);
			t=s.find("AB");
		}
		t=s.find("BB");
		while(s.size()&&t!=-1)
		{
			s.erase(t,2);
			t=s.find("BB");
		}
		cout<<s.size()<<endl;
	}		
	return 0;
}

模拟栈即可

// Problem: C. ABBB
// Contest: Codeforces - Codeforces Raif Round 1 (Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/1428/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
/*Love coding and thinking!*/ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define pb push_back 
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo2(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
typedef pair<int,int>PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=2e5+10,M=1e9+7;
int n,m,_;
//AABB
int main()
{
	cin>>_;
	while(_--)
	{
		string s;cin>>s;
		n=0;//模拟栈的大小
		for(int i=0;i<s.size();i++)
		{
			// debug(i);
			if(!n&&s[i]=='B')n++;//首个元素是b
			else if(n&&s[i]=='B')
				n--;
			else
				n++;
			// debug(n);
		}
		cout<<n<<endl;
	}		
	return 0;
}

Problem C. Long Jumps

$$\begin{gathered} 给定n个数,权值为a[i],可以选择n个起跳点,选择i作为起跳点 \\ ans=a[i]+a[i+a[i]]+a[a[i+a[i]]]..(i+a[i]<=n) \\ 求最大得分ans \end{gathered}$$

$$\begin{gathered} 注意到从前向后扫描每个起跳点时,第一次跳到某个点一定比第二次跳到同一个点得分高 \\ 因为,设第一次跳到某个点X,起跳起点为l_1,第二次跳到同一点,来自于l_2,因为l_1!=l_2 \\ 且l_1是率先跳到X的,所以有l_1<l_2,所以有从l_1起跳得分高。 \end{gathered}$$

2021-01-13 11:39:58
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int>PII;
const int N=2e5+10;
typedef long long ll;
int n,a[N];
bool st[N];
int main()
{
	int t;cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
			cin>>a[i],st[i]=0;//使用st数组记录对于每个不同的起跳点,要跳到的那个点是不是
        //第一次跳到了
		ll ans=-1;
		//注意到第一次跳到某个点一定比第二次跳到同一个点得分高 
		for(int i=1;i<=n;i++)
		{
			ll j=i,sum=0;
			while(j<=n)
			{
				if(st[j])break;//不是第一次跳到的break
				st[j]=1;//否则更新下sum,并记录
				sum+=a[j];
				j+=a[j];
			}
			ans=max(sum,ans);
		}
		cout<<ans<<endl;
	}
    return 0;
}

// Problem: C. Long Jumps
// Contest: Codeforces - Codeforces Round #693 (Div. 3)
// URL: https://codeforces.com/problemset/problem/1472/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms

/*Love coding and thinking!*/ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define pb push_back 
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo2(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
typedef pair<int,int>PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=2e5+10,M=1e9+7;
int n,m,_;
ll a[N];
ll dp[N];//表示从i开始跳在满足规则(跳出界就停止)的所有可能方案中,能得到的最大价值,防止爆int 
int main()
{
	cin>>_;
	while(_--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)	
			scanf("%lld",&a[i]);
		ll sum=0;
		//dp[i]表示从1~i-1中某个点跳到该点
		//DAG(有向无环图)上DP(动态规划)
		// dp[i]=dp[i-a[i]]+a[i];  这个和程序写的不一样，
		//动态规划问题，dp数组（或者f数组）定义不同转移方程还有边界就会不同
		// 这里dp[i]表示跳到i（和上边是不一样的）在满足规则(跳出界就停止)的所有可能方案中,能得到的最大价值
		// 但是，i前边可能有很多点可以跳到i，还需要枚举，反而定义成从i开始跳只需要倒序扫一遍就行了
		// dp[i+a[i]]=dp[i]+a[i+a[i]];
		
		// for(int i=1;i<=n;i++)
		// {
			// dp[i]=a[i];
			// if(i-a[i]>=1)
			// {
				// dp[i]+=dp[i-a[i]];
			// }
			// sum=max(sum,dp[i]);
		// }
		
		for(int i=n;i>=1;i--)
		{
			dp[i]=a[i];//从点i起跳,答案就是他自身
			if(i+a[i]<=n)//如果不会出界
				dp[i]+=dp[i+a[i]];//因为需要后边的子问题的答案，所以从后向前算
            /*
           	什么叫需要后边的答案，所以需要从后向前算呢,因为dp[i]需要+=dp[i+a[i]],
           	而i+a[i]>i，但我们现在是在更新dp[i]的值，如果从小到大循环,那么我们现在在求
           	dp[i]的值,但我们需要知道dp[i+a[i]]的值，因为后边的没更新呢，只能是初始值0,
           	无法进行下去了，但是如果从后先前算,因为我们知道了大的就是dp[i+a[i]]的值，dp[i]
           	的值也就能推导了,1维的0/1背包和完全背包在代码上就是循环的方式不同，其余一样。
            */
			sum=max(sum,dp[i]);
		}
		cout<<sum<<endl;

	}			
	return 0;
}

Problem B. Jumps

$$\begin{gathered} 初始时位于坐标轴远点,想要移动到X(X>0),第k步移动要不从pos位置向x正方向移动k步，要么回退一步。 \\ 询问到达目标点X的最小跳跃步数 \end{gathered}$$

贪心+构造，证明待补充 大佬链接

// Problem: B. Jumps
// Contest: Codeforces - Educational Codeforces Round 99 (Rated for Div. 2)
// URL: https://codeforces.com/problemset/problem/1455/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms

/*Love coding and thinking!*/ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define pb push_back 
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo2(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
typedef pair<int,int>PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=3e6+10,M=1e9+7;
int n,m,_;
ll a[N];
int x;
int main()
{
	cin>>_;
	a[1]=1;
	int i;
	for(i=2;;i++)//初始化a数组,
	{
		a[i]=a[i-1]+i;
		if(a[i]>1000000)
			break;
	}
	n=i;//超过1e6的那个i
//	cout<<n<<" "<<a[n]<<endl;
	//1414 1000405
	 while(_--)
	 {
		cin>>x;
		int t=lower_bound(a+1,a+n,x)-a;//1 2 3 4 5 ... step 每次这么跳,二分找一下步数
		
		if(a[t]==x)//刚好有可以通过1 2 3 4 5 这种方式跳到x的一步,输出是那一步就好
			cout<<t<<endl;
		else if(a[t]-1==x)//如果>=x的step步比x多1,需要在过程中返回走一步
			cout<<t+1<<endl;
		else//否则都可以通过在跳跃过程中选择合适的方式凑出x步
			cout<<t<<endl;
	 }				
	return 0;
}

Problem C. Sequence Transformation

$$\begin{gathered} 给你一个有n个数字的序列a,为了使操作后序列中剩余的元素全部相等, \\ 你可以选择在a中至少出现一次的元素x进行以下任意多次的操作 \\ 选择a中[l,r],要求[l,r]中没有元素a[i]==x将[l,r]区间从a中移除,x选定后不能改变.问最少的使a序列元素相等的操作次数是多少 \end{gathered}$$

#include<string>
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=2e5+10;

/*
有了思路之后，怎么最快速的实现
将数组使用unique去重，统计每个元素出现的次数，
*/
int a[N];
map<int,int>mp;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
        int n;cin>>n;
        mp.clear();
        memset(a,0,sizeof a);
        for(int i=0;i<n;i++)
            cin>>a[i];
        int m=unique(a,a+n)-a;
        // cout<<m<<endl;
        if(m==1)//去重后只有一个元素
            cout<<"0"<<endl;
        else
        {
            for(int i=0;i<m;i++)
            {
                if(i==0||i==m-1)//类似隔板法
                    mp[a[i]]--;//不统计最前面和最后边的元素
                mp[a[i]]++;
            }
            int Min=1e7;
            for(auto x:mp)
            {
                Min=min(Min,x.second+1);
            }
            cout<<Min<<endl;
        }
	} 	
	return 0;
}