这场状态不行,感觉要寄,于是没交();
想A想了挺久,大概40min吧,后面B想的不算很慢,但是代码实现一直有点问题,于是写出了非常繁琐的代码,赛后补了个比较简洁的,C当时读完题目了,但是已经没空想具体实现,sad;
A.Not a Substring
题意:给定一个长度为N括号序列,问你能否写出一个长度为2*N的合法括号序列,使得该括号序列不能写出的括号序列的一端完全匹配;
首先由样例得出:()肯定不行;
其次可以得出其他排列都可以;先考虑两种最简单的情况:1.类似于()()的类型,只需构造(((())))即可;2.类似于(())的类型,只需构造()()()()即可;
对于两种都有的类型,两种构造都可以;我们不妨将()()类型构造成(((()))),其他所有类型(即存在连续的两个括号相同)全构造成()()()();
1 #include<bits/stdc++.h> 2 using namespace std; 3 int read(){ 4 char ch=getchar();int x=0,f=1; 5 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} 6 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} 7 return x*f; 8 } 9 int T,len; 10 string s; 11 int main(){ 12 T=read(); 13 while(T--){ 14 cin>>s; 15 len=s.length(); 16 if(len==2){ 17 if(s[0]=='('&&s[1]==')'){ 18 cout<<"NO"<<endl;continue; 19 } 20 if(s[0]==')'&&s[1]=='('){ 21 cout<<"YES"<<endl; 22 cout<<"(())"<<endl; 23 continue; 24 } 25 } 26 int flag=0; 27 for(int i=0;i<=len-2;i++){ 28 if(s[i]==s[i+1])flag=1; 29 } 30 cout<<"YES"<<endl; 31 if(flag==1){ 32 for(int i=1;i<=len;i++){ 33 cout<<"()"; 34 } 35 cout<<endl;continue; 36 } 37 if(flag==0){ 38 for(int i=1;i<=len;i++){ 39 cout<<"("; 40 } 41 for(int i=1;i<=len;i++){ 42 cout<<")"; 43 } 44 cout<<endl;continue; 45 } 46 } 47 return 0; 48 }
B.Fancy Coins
题意:给定大小为 1 的硬币 a1 枚和大小为 k 的硬币 ak 枚,以及无数枚fancy coins,可以付出 1 点代价把一个 fancy coin 变成面值为 1 或 k 的硬币,问凑出 M 的最小代价;
赛时代码对于 5 个给定样例总有一个过不了,于是嗯怼判断,写的很繁琐;
其核心问题在于要优先把fancy coin 变成面值为 k 的硬币,而且对于面值为 1 的硬币不应该优先转化为 a1/k 枚面值为 k 的硬币,而是要考虑凑M%k;
赛时代码如下:
1 #include<bits/stdc++.h> 2 using namespace std; 3 int read(){ 4 char ch=getchar();int x=0,f=1; 5 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} 6 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} 7 return x*f; 8 } 9 int T,N,M,K,a1,ak,ans; 10 int main(){ 11 T=read(); 12 while(T--){ 13 M=read();K=read();a1=read();ak=read(); 14 ans=0; 15 if(M/K<=ak){ 16 if(M%K<=a1){ 17 cout<<"0"<<endl;continue; 18 } 19 if(M%K>a1){ 20 cout<<M%K-a1<<endl;continue; 21 } 22 } 23 24 if(M/K>ak){ 25 if(M-K*ak<=a1){ 26 cout<<"0"<<endl;continue; 27 } 28 if(M-K*ak>a1){ 29 M=M-K*ak; 30 int t=(M-a1)/K; 31 ans=M-a1; 32 if((t+1)*K+a1>=M&&(t+1)*K<=M)ans=min(ans,t+1); 33 if((t+1)*K+a1<M)ans=min(ans,t+1+M-(t+1)*K-a1); 34 if(t*K+a1>=M)ans=min(ans,t); 35 if(t*K+a1<M)ans=min(ans,t+M-t*K-a1); 36 cout<<ans<<endl;continue; 37 } 38 } 39 40 } 41 return 0; 42 }
赛后代码如下:
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 ll read(){ 5 char ch=getchar();ll x=0,f=1; 6 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} 7 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} 8 return x*f; 9 } 10 ll T,M,K,a1,ak,ans,x,y; 11 int main(){ 12 T=read(); 13 while(T--){ 14 M=read();K=read();a1=read();ak=read(); 15 ans=0;x=M%K; 16 if(x<=a1){ 17 a1=a1-x;a1=a1/K; 18 } 19 else{ 20 ans+=x-a1;a1=0; 21 } 22 if(M/K-a1-ak>0){ 23 ans+=M/K-a1-ak; 24 } 25 cout<<ans<<endl; 26 } 27 return 0; 28 }
- Educational Codeforces Round 2022 div2educational codeforces round 2022 codeforces round 2023 div2 codeforces round div2 915 codeforces round div2 856 educational codeforces round rated 题解codeforces round div2 codeforces round div2 832 educational codeforces round 151 construction educational codeforces round educational codeforces round 147