比赛链接:https://codeforc.es/contest/1709

A了两个A和B,C题比D题难,很无语。C题是个规律题,但是我没有找到。很多人都卡在了C题上。

A题:大意是有是三个门,每个门里面可能有一把其他们的钥匙,也可能没有。你最开始拥有一把钥匙,试着开启所有门。

比较水,但是读题读了很长时间,可以直接用标记数组的做法来写。

code:

#include<bits/stdc++.h>
using namespace std;
bool sign[4];
int a[4];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		memset(a,0,sizeof a);
		memset(sign,false,sizeof sign);
		int x;
		cin>>x;
		cin>>a[1]>>a[2]>>a[3];
		while(x!=0)
		{
			sign[x] = true;
			x = a[x];
		}
		if(sign[1]==true&&sign[2]==true&&sign[3]==true)
			printf("YES\n");
		else
			printf("NO\n");
	}	
} 

B题:大意有n个塔,从s飞向t,如果飞向的那个塔比当前塔低,那么有当前塔的高度-飞向塔的高度的损伤。地图是一个线性。

很明显的前后缀和问题,最开始的时候我读错题了以为是一个环形,也没有去好好看样例,后来因为输入格式wa了一次,因为数据类型wa了两次,不应该哎。这个题做题的速度上也有很大的问题,如果一开始就读懂题,弄好数据类型,可以做的很快的。

code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int nn = 1e5+10;
int a[nn];
ll sq[nn];
ll sh[nn];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=n;i++)
		if(a[i]>a[i+1])
			sq[i]=sq[i-1]+(a[i]-a[i+1]);
		else
			sq[i]=sq[i-1];
	for(int i=n;i>=1;i--)
		if(a[i]>a[i-1])
			sh[i]=sh[i+1]+(a[i]-a[i-1]);
		else
			sh[i]=sh[i+1];
	sq[n] = sq[n-1];
	sh[1] = sh[2];
/*	for(int i=1;i<=n;i++)
		cout<<sq[i]<<' ';
	cout<<endl; 
	for(int i=1;i<=n;i++)
		cout<<sh[i]<<' ';
	cout<<endl; */

	int s,t;
	int tt;
	while(m--)
	{
		ll sum1 = 0,sum2 = 0,sum=0;
		scanf("%lld%lld",&s,&t);
		if(s<t)
			sum = sq[t-1] - sq[s-1];
		else if(s>t)
			sum = sh[t+1] - sh[s+1];
		else
			sum = 0;
		printf("%lld\n",sum);
	}
} 

C题:给出一段字符串,只有(,),?,这三种字符。?可以用任意()代替。如果组成的合法表达式法则不唯一输出NO,否则YES。

考虑一种贪心的策略,我们可以知道左括号和右括号的数量是相同的,所以我们可以去掉左括号和右括号的数量。如果在消除过程中有一个左括号和0个问号,则左括号的数量可以等于1,问号的数量可以等于0。如果有0个左括号和一个问号,则问号必须是左括号,否则不满足条件。最后一个问号的数量必须大于或等于不匹配括号的数量。如果左括号的数量与右括号的数量相同,或者左括号的数量与右括号的数量相同,则只剩下一个问号状态。否则,问号的数量大于左括号或右括号的数量,并且存在多个状态。

考虑一种模型的策略(但是我们还是需要用到贪心的思想)。首先题意中一定有解,至少为一种方法,所以我们贪心的去构造一组合法的表达式法则,也就是除了消除的部分外,令左边的一直是左,右边的一直是右,这样一定能构造一组合法策略。然后我们交换最里面的一组问号,它们的影响因子是最小的,因为只需要一组就可以影响到使其状态合法。如果交换后状态合法,那么NO,不合法那么YES,交界处不合法,那么其余组数更不合法。

贪心策略code:

#include<bits/stdc++.h>
using namespace std;
vector<int> ve;
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		string a;
		int k = 0,wen=0;
		cin>>a;
		for(int i=0;i<a.size();i++)
		{
			if(a[i]=='(') k++;
			if(a[i]==')') k--;
			if(a[i]=='?') wen++;
			//如果存在一个左括号没有消除,那么?只能为右括号,且在没出现左括号时不能出现右括号 
			//如果出现右括号,那么?只能为左括号,与之匹配,那么左括号数量一定为1 
			if(k+wen==1)
				k = 1, wen = 0;
		}
		//最后剩余的左括号的数量如果等于右括号,那么状态一定是唯一的 
		if((abs(k))==wen)	cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}	
} 

 

贪心+模型策略code:

#include<bits/stdc++.h>
using namespace std;
bool check(string &s)
{
	int k = 0;
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='(') k++;
		if(s[i]==')') k--;
		if(k<0) return false;
	}
	return k==0;
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		string s;
		cin>>s;
		vector<int>ve;
		int zk = s.size()/2,yk = s.size()/2;
		for(int i=0;i<s.size();i++)
		{
			if(s[i]=='?') ve.push_back(i);
			if(s[i]=='(') zk--;
			if(s[i]==')') yk--;	
		} 
		for(int i=0;i<ve.size();i++)
		{
			if(i<zk) s[ve[i]] = '(';
			else s[ve[i]] = ')';
		}
		bool ok = true;
		if(zk>0&&yk>0)
		{
			swap(s[ve[zk-1]],s[ve[yk-1]]);
			if(check(s)) ok = false;
		}
		cout<<(ok?"YES":"NO")<<endl;
	}
}

D题: