# CF1132.Educational Codeforces Round 61（简单题解）

2019/03/06 20:02

## A .Regular Bracket Sequence

``````#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=200010;
ll A,B,C,D,ans;
int main()
{
scanf("%lld%lld%lld%lld",&A,&B,&C,&D);
ans=B;
if(A||D) ans+=C; ans+=2LL*min(A,D);
if(ans==A+B+C+D) puts("1");
else puts("0");
return 0;
}``````

## B .Discounts

``````#include<bits/stdc++.h>
#define ll long long
#define rep(i,w,v) for(int i=w;i<=v;i++)
using namespace std;
const int maxn=2000010;
ll a[maxn],sum,ans;
int main()
{
int N,M,x; scanf("%d",&N);
rep(i,1,N) scanf("%lld",&a[i]),sum+=a[i];
sort(a+1,a+N+1);
scanf("%d",&M);
rep(i,1,M) {
scanf("%d",&x);
printf("%lld ",sum-a[N+1-x]);
}
return 0;
}``````

## C .Painting the Fence

``````#include<bits/stdc++.h>
#define ll long long
#define rep(i,w,v) for(int i=w;i<=v;i++)
using namespace std;
const int maxn=5100;
int sum[maxn],num[3][maxn],ans,tot; pair<int,int>s[maxn];
int main()
{
int N,M;
scanf("%d%d",&N,&M);
rep(i,1,M){
scanf("%d%d",&s[i].first,&s[i].second);
sum[s[i].first]++; sum[s[i].second+1]--;
}
rep(i,1,N) sum[i]+=sum[i-1];
rep(i,1,N){
if(sum[i]) tot++;
num[1][i]+=num[1][i-1];
num[2][i]+=num[2][i-1];
if(sum[i]==1) num[1][i]++;
if(sum[i]==2) num[2][i]++;
}
sort(s+1,s+M+1);
rep(i,1,M)
rep(j,i+1,M){
if(s[j].first>s[i].second) ans=max(ans,tot-(num[1][s[i].second]-num[1][s[i].first-1])-(num[1][s[j].second]-num[1][s[j].            first-1]));
else if(s[j].second<=s[i].second)
ans=max(ans,tot-(num[1][s[j].first-1]-num[1][s[i].first-1])-(num[1][s[i].second]-num[1][s[j].second])-(num[2][s            [j].second]-num[2][s[j].first-1]));
else
ans=max(ans,tot-(num[1][s[j].first-1]-num[1][s[i].first-1])-(num[1][s[j].second]-num[1][s[i].second])-(num             [2][s[i].second]-num[2][s[j].first-1]));
}
printf("%d\n",ans);
return 0;
}``````

## D .Stressful Training

``````#include<bits/stdc++.h>
#define ll long long
#define rep(i,w,v) for(int i=w;i<=v;i++)
using namespace std;
const int maxn=200010;
ll a[maxn],b[maxn],ans=-1;int N,K,vis[maxn];
bool check(ll x)
{
int cnt=0; rep(i,1,K) vis[i]=0;
rep(i,1,N){
ll L=a[i];
while(L-b[i]*(K-1)<0){
int t=L/b[i]+1;
if(L/b[i]+1<=K) vis[L/b[i]+1]++;
cnt++; if(cnt==K) return false;
L+=x;
}
}
for(int i=K;i>1;i--) {
if(vis[i]) vis[i-1]+=vis[i]-1;
}
if(vis[1]>1) return false;
return true;
}
int main()
{
ll L=0,R=1e18,Mid;
scanf("%d%d",&N,&K);
rep(i,1,N) scanf("%lld",&a[i]);
rep(i,1,N) scanf("%lld",&b[i]);
while(L<=R){
Mid=(L+R)/2;
if(check(Mid)) R=Mid-1,ans=Mid;
else L=Mid+1;
}
printf("%lld\n",ans);
return 0;
}``````

## E .Knapsack

（这是比较暴力的做法了，有更优美的解法

``````#include<bits/stdc++.h>
#define ll long long
using namespace std;
map<ll,bool>mp,tmp;
map<ll,bool>::iterator it;
const int maxn=20000;
ll ans,W,a[maxn],v[maxn],sum[maxn]; int tot,cnt;
int main()
{
scanf("%lld",&W);
for(int i=1;i<=8;i++){
scanf("%lld",&a[i]);
if(!a[i]) continue; cnt++; ll t=1;
ans=max(ans,min(W/i,a[i])*i);
while(1){
tot++; v[tot]=min(t,a[i])*i;
a[i]-=min(t,a[i]); t=t*2;
if(!a[i]) break;
}
}
if(cnt==1){
printf("%lld\n",ans); return 0;
}
sort(v+1,v+tot+1); reverse(v+1,v+tot+1);
for(int i=tot;i>=1;i--) sum[i]=sum[i+1]+v[i];
mp[0]=true;
for(int i=1;i<=tot;i++){
tmp.clear();
for(it=mp.begin();it!=mp.end();it++){
ll x=it->first;
tmp[x]=true;
if(x+v[i]<=W) tmp[x+v[i]]=true;
}
mp.clear();
for(it=tmp.begin();it!=tmp.end();it++){
if(it->first+sum[i+1]<ans) continue;
mp[it->first]=true;
ans=max(it->first,ans);
}
}
printf("%lld\n",ans);
return 0;
}``````

## F .Clear the String

``````#include<bits/stdc++.h>
#define ll long long
#define rep(i,w,v) for(int i=w;i<=v;i++)
using namespace std;
const int maxn=510;
int dp[maxn][maxn]; char a[maxn];
int main()
{
int N,tot=1; scanf("%d%s",&N,a+1);
rep(i,2,N){
if(a[i]!=a[i-1]) a[++tot]=a[i];
}
N=tot;
memset(dp,0x3f,sizeof(dp));
rep(len,1,N){
rep(L,1,N-len+1){
int R=L+len-1;
if(len==1) dp[L][R]=1;
else if(len==2) dp[L][R]=(a[L]==a[R]?1:2);
else {
dp[L][R]=len;
if(a[L]==a[R]) dp[L][R]=min(dp[L+1][R],dp[L][R-1]);
else{ dp[L][R]=min(dp[L+1][R],dp[L][R-1])+1;
rep(k,L,R) dp[L][R]=min(dp[L][R],dp[L][k]+dp[k][R]-1);
}
}
}
}
printf("%d\n",dp[1][N]);
return 0;
}``````

0
0 收藏

0 评论
0 收藏
0