比赛链接: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题: