Educational Codeforces Round 61 (Rated for Div. 2)

A. Regular Bracket Sequence

题意：给出四种括号的数量 (( )) () )( 问是否可以组成合法的序列（只能排序不能插在另外一个的中间）

思路：条件一：一个或 n个)( 都可以组成 )()()( 这种结构这只需要一个((和一个))就可以合成合法的序列

　　　条件二： (( 和))需要相等

()本身就合法不用管

 1 ude<bits/stdc++.h>
 2 #define FOR(i,f_start,f_end) for(int i=f_startl;i<=f_end;i++)
 3 #define MS(arr,arr_value) memset(arr,arr_value,sizeof(arr)) 
 4 using namespace std;
 5 const int maxn=500;
 6 const int maxm=2e4+5;
 7 int main(){
 8 int cnt1,cnt2,cnt3,cnt4;
 9 cin>>cnt1>>cnt2>>cnt3>>cnt4;
10 if(cnt1==cnt4&&(cnt3&&cnt1||!cnt3)){
11     printf("1");
12     
13 }
14 else printf("0");
15 return 0;
16 }

B. Discounts

题意：给出n个数a 和m个数 q 求选择q个数a 求他们的和-q个数中最小的那个 +剩余的数的最小值

思路：直接sort a 求出总和a 然后暴力每次减去可以删除的那个数即可

 1 #include<bits/stdc++.h>
 2 #define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++)
 3 #define MS(arr,arr_value) memset(arr,arr_value,sizeof(arr)) 
 4 using namespace std;
 5 const int maxn=3e5+5;
 6 typedef long long ll;
 7 ll a[maxn],q[maxn],sum[maxn];
 8 int main(){
 9     int n;
10     scanf("%d",&n);
11     FOR(i,1,n)scanf("%I64d",&a[i]);
12     sort(a+1,a+1+n);
13     FOR(i,1,n)sum[i]=sum[i-1]+a[i];
14     int m;
15     scanf("%d",&m);
16     int ans=0x3f3f3f3f;
17     FOR(i,0,m-1)scanf("%I64d",&q[i]);
18     FOR(i,0,m-1){
19         cout<<sum[n]-sum[n-q[i]+1]+sum[n-q[i]]<<endl;;
20     }
21 
22 return 0;
23 }

View Code

C. Painting the Fence

题意：给出q个区间问q-2个区间的最大覆盖 n,q<5000

思路：给每个区间计数例如给出区间 l--r 则FOR(i,l,r)cnt[i]++;

然后先枚举第一个删的区间把这个要删的区间cnt[i]-- 然后统计现在还有多少个区间可以用这个还有一个重点统计cnt为1的点的前缀和这样枚举第二个删的区间时只要多少个区间能用 - 第二个区间删去能使多少个点为0就可以计算了，很巧妙

 1 #include<bits/stdc++.h>
 2 #define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++)
 3 #define MS(arr,arr_value) memset(arr,arr_value,sizeof(arr)) 
 4 #define F first 
 5 #define S second
 6 #define pii pair<int ,int >
 7 #define mkp make_pair
 8 using namespace std;
 9 const int maxn=5000+5;
10 typedef long long ll;
11 pii a[maxn];
12 int sum[maxn],cnt[maxn];
13 int main(){
14     int n,q;
15     scanf("%d%d",&n,&q);
16     FOR(i,0,q-1){
17         scanf("%d%d",&a[i].F,&a[i].S);
18         FOR(j,a[i].F,a[i].S)cnt[j]++;
19     }
20 //    for(int i=1;i<=n;i++)cout<<cnt[i];
21     int ans=0;
22     FOR(i,0,q-1){
23         
24         FOR(j,a[i].F,a[i].S)cnt[j]--;
25         int tot=0;
26         FOR(k,1,n){
27             tot+=(cnt[k]>0);
28             if(cnt[k]==1)sum[k]=1;
29             else sum[k]=0;
30             sum[k]+=sum[k-1];
31         }
32     //    FOR(k,1,n)cout<<sum[k];
33     //    cout<<endl;
34         int tmp=0;
35         FOR(j,0,q-1){
36             
37             if(i==j)continue;
38             tmp= max(tmp,tot-(sum[a[j].S]-sum[a[j].F-1]));
39     //if(tmp==3)cout<<i<<" "<<j<<" "<<tot<<" "<<sum[a[i].S]<<" "<<sum[a[i].F-1]<<endl;    
40         }
41         FOR(j,a[i].F,a[i].S)cnt[j]++;
42         ans=max(tmp,ans);
43     }
44     cout<<ans<<endl;
45     return 0;
46 }

View Code

F. Clear the String

题意：祖玛游戏问最小多少次能全部消掉

思路 :区间dp[i][j] 表示 i 到j全部消掉要多少次初始化当s[i]==s[j]时dp[l][j]=dp[l+1][r-1]+1 不能时dp[l][r]=min(dp[l+1][r],dp[l][r-1])+1;然后在l r区间dp[l][r]=min(dp[l][r],dp[l][k]+dp[k][r]-1); 这里k取了两次所以要减1

 1 #include<bits/stdc++.h>
 2 #define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++)
 3 #define MS(arr,arr_value) memset(arr,arr_value,sizeof(arr)) 
 4 #define F first 
 5 #define S second
 6 #define pii pair<int ,int >
 7 #define mkp make_pair
 8 using namespace std;
 9 const int maxn=500+5;
10 char s[maxn];
11 int dp[maxn][maxn];
12 
13 int main(){
14     int n;
15 scanf("%d",&n);
16 scanf("%s",s+1);
17 FOR(i,1,n)dp[i][i]=1;
18 FOR(len,2,n){
19     for(int l=1,r=len;r<=n;r++,l++)
20     {
21         if(s[l]==s[r])dp[l][r]=dp[l+1][r-1]+1;
22         else dp[l][r]=min(dp[l+1][r],dp[l][r-1])+1;
23         FOR(k,l,r){
24             dp[l][r]=min(dp[l][r],dp[l][k]+dp[k][r]-1);
25         }
26     }
27 }
28 cout<<dp[1][n]<<endl;
29 
30 return 0;
31 }