2022.08.17Educational Codeforces Round div2

burutaofan / 2023-08-27 / 原文

这场状态不行，感觉要寄，于是没交（）；

想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 }