[数据结构与算法]补提计划 Codeforces Round #608 (Div. 2)

VP过4题，感觉自己还是挺水的，D还是卡点过的，状态转移没想清楚就开写，结果导致debug麻了。回过头来一看，发现自己过的这几题都是挺简单的题，感觉自己还是需要加训

A

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int a,b,c,d,e,f;
    scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
    ll res=0;
    if(e>f)
    {
        res+=1ll*min(a,d)*e;
        d-=min(a,d);
        res+=1ll*min({b,c,d})*f;
    }
    else 
    {
        res+=1ll*min({b,c,d})*f;
        d-=min({b,c,d});
        res+=1ll*min(a,d)*e;
    }
    cout<<res;
}

B

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e2+10;
char s[maxn];
int n;
vector<int> res;
void turn(int pos)
{
    if(s[pos]=='W')s[pos]='B';else s[pos]='W';
}
void get(char a)
{
    for(int i=1;i<=n;i++)
    {
        if(s[i]==a)
        {
            turn(i);turn(i+1);
            res.push_back(i);
        }
    }
}
int main()
{
    scanf("%d",&n);scanf("%s",s+1);
    int d1=0,d2=0;
    for(int i=1;i<=n;i++)if(s[i]=='W')d1++;else d2++;
    if((d1&1)&&(d2&1)){puts("-1");return 0;};
    if(d2&1)get('W');
    else get('B');
    cout<<res.size()<<endl;
    for(int i=0;i<res.size();i++)cout<<res[i]<<" ";
}

C

#include<bits/stdc++.h>
using namespace std;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int cnt[4];
int main()
{
    int n,sx,sy;scanf("%d%d%d",&n,&sx,&sy);
    while(n--)
    {
        int x,y;scanf("%d%d",&x,&y);
        x-=sx,y-=sy;
        if(x>0)cnt[0]++;
        else if(x<0)cnt[1]++;
        if(y>0)cnt[2]++;
        else if(y<0)cnt[3]++;
    }
    int mx=max({cnt[0],cnt[1],cnt[2],cnt[3]});
    for(int i=0;i<4;i++)
    {
        if(cnt[i]==mx)
        {
            printf("%d\n",cnt[i]);
            printf("%d %d",sx+dx[i],sy+dy[i]);
            return 0;
        }
    }
}

D

dp[i][j]表示到达第i个位置还剩下j个兵

很显然的发现，第i个城堡是否驻守，应该留到最后去选择。毕竟前面缺兵，很可能兵不够。所以我们只需要在最后一个j处建立能抵达i的边就好了

然后就是个简单的01背包

这里可以滚动数组，但显然没有必要

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e3+10;
const int N=5e3;
vector<int> son[maxn];
int dp[maxn][maxn];
typedef pair<int,int> pii;
pii p[maxn];
int a[maxn],b[maxn],c[maxn],e[maxn];
int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++){scanf("%d%d%d",&a[i],&b[i],&c[i]);}
    while(m--)
    {
        int u,v;
        scanf("%d%d",&u,&v);e[v]=max(e[v],u);
    }
    for(int i=1;i<=n;i++)
    {
        if(!e[i])son[i].push_back(i);
        else son[e[i]].push_back(i);
    }
    memset(dp,-1,sizeof(dp));
    dp[0][k]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=a[i];j<=N;j++)
        {
            if(dp[i-1][j]==-1)continue;
            dp[i][j+b[i]]=dp[i-1][j];
        }
        for(auto v:son[i])
        {
            for(int j=1;j<=N;j++)
           { if(dp[i][j]==-1)continue;
             dp[i][j-1]=max(dp[i][j-1],dp[i][j]+c[v]);
               
           }
        }
    }
    // cout<<dp[2][1]<<endl;
    int res=-1;
    for(int i=0;i<=N;i++)res=max(res,dp[n][i]);
    printf("%d\n",res);
}

E 二分终点记得特判L

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k;
ll check(ll x)
{
    ll ans=0,t=1;
    while(x<=n)
    {
        ans+=min(n-x+1,t);
        x<<=1;
        t<<=1;
    }
    return ans;
}
ll solve1()
{
    ll l=1,r=n/2,res=-1;
    while(l<r)
    {
        ll mid=l+r+1>>1;
        if(check(2*mid)+check(2*mid+1)>=k)l=mid,res=mid*2;
        else r=mid-1;
    }
    if(check(2*l)+check(2*l+1)>=k)res=max(res,r*2);
    return res;
}
ll solve2()
{
    ll l=1,r=(n+1)/2,res=-1;
    while(l<r)
    {
        ll mid=l+r+1>>1;
        if(check(2*mid-1)>=k)l=mid,res=mid*2-1;
        else r=mid-1;
    }
    if(check(2*l-1))res=max(2*l-1,res);
    return res;
}
int main()
{
    ll res=-1;
    scanf("%lld%lld",&n,&k);
    res=max(solve1(),res);
    res=max(solve2(),res);
    cout<<res;
}

当然，我注意到有人E题找到了某种性质，性质有空就去猜一下

他用的代码是这样的

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,s;
int solve(int n,int k){
	for (s=1;s<=k;s*=2) ;s/=2;
	return (n-k+s)/s;
}
signed main(){
	scanf("%lld %lld",&n,&k);
	printf("%lld\n",max(solve(n,k),solve(n,k+1)<<1));
	return 0;
} 

F

感觉这题给2700给高了

#include<bits/stdc++.h>
using namespace std;
int a1,a2,b1,b2,c1,c2;
int dabc,dab,dac,dbc,da,db,dc;
bool check()
{
    if(min({a1,b1,c1})+min({a2,b2,c2})<dabc)return false;
    if(a1+a2-da<dabc||b1+b2-db<dabc||c1+c2-dc<dabc)return false;
    return true;
}
void solve()
{
    scanf("%d%d%d",&a1,&b1,&c1);scanf("%d%d%d",&a2,&b2,&c2);
    scanf("%d%d%d%d%d%d%d",&dabc,&dab,&dac,&da,&dbc,&db,&dc);
    for(int tab=0,mx1=min({dab,a1,b1});tab<=mx1;tab++)
    {
        if(dab-tab>min({a2,b2}))continue;
        a1-=tab,b1-=tab;a2-=(dab-tab),b2-=(dab-tab);
        for(int tac=0,mx2=min({dac,a1,c1});tac<=mx2;tac++)
        {
            if(dac-tac>min({a2,c2}))continue;
            a1-=tac,c1-=tac;a2-=(dac-tac),c2-=(dac-tac);
            for(int tbc=0,mx3=min({dbc,b1,c1});tbc<=mx3;tbc++)
            {
                if(dbc-tbc>min({b2,c2}))continue;
                b1-=tbc,c1-=tbc;b2-=(dbc-tbc),c2-=(dbc-tbc);
                if(check())
                {
                    int fabc=min({a1,b1,c1,dabc});
                    a1-=fabc,b1-=fabc,c1-=fabc;
                    printf("%d %d %d %d ",fabc,tab,tac,min(a1,da));
                    printf("%d %d %d\n",tbc,min(b1,db),min(c1,dc));
                    return ;
                }
                b1+=tbc,c1+=tbc;b2+=(dbc-tbc),c2+=(dbc-tbc);
            }
            a1+=tac,c1+=tac;a2+=(dac-tac),c2+=(dac-tac);
        }
        a1+=tab,b1+=tab;a2+=(dab-tab),b2+=(dab-tab);
    }
    printf("-1\n");return ;
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        solve();
    }
}