南外Day8

A&B&C 100

真的很水

D 100

搜索/状压

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,g[5],a[15],lg[258],f[258][258],ans=INT_MAX;
int cnt(int lbt){
    int op=0;
    while(lbt){
        int p=lbt&-lbt;
        lbt^=p;op+=a[lg[p]];
    }
    return op;
}
int mge(int lbt){
    int op=0;
    while(lbt){
        int p=lbt&-lbt;
        lbt^=p;op++;
    }
    return op;
}
signed main(){
    cin.tie(0);cout.tie(0);
    cin>>n>>g[1]>>g[2]>>g[3];
    for(int i=0;i<=8;i++) lg[1<<i]=i+1;
    for(int i=1;i<=n;i++) cin>>a[i];
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(int i=1;i<=3;i++){
    for(int j=0;j<(1<<n);j++){
    for(int k=0;k<(1<<n);k++){
        if((j^k)!=j-k) continue;
        if(j==k) continue;
        f[i][j]=min(f[i][j],f[i-1][k]+abs(cnt(j^k)-g[i])+mge(j^k)*10-10);
        if(i==3) ans=min(ans,f[i][j]);
    }}}
    cout<<ans;
    return 0;
} 

E 100

前缀和，以下是计算代码

for(int i=1;i<n;i++){
for(int j=1;j<n;j++){
    gx[0]=0;
    for(int k=i+1;k<=n;k++){
    for(int l=j+1;l<=n;l++){
        mp[lp[i+1][j+1][k][l]+5000000]++;
        gx[++gx[0]]=lp[i+1][j+1][k][l]+5000000;
    }}
    for(int k=1;k<=i;k++)
    for(int l=1;l<=j;l++)
        ans+=mp[lp[k][l][i][j]+5000000];
    for(int i=1;i<=gx[0];i++) mp[gx[i]]=0;
}}

F 20→100

贪心，枚举最后得到的票数
其实有n log n做法但是就不放了
以下n²核心代码

for(int i=1;i<n;i++) cin>>a[i];
for(int i=1;i<n;i++){
    cin>>b[i];
    p[a[i]-1][++p[a[i]-1][0]]=b[i];
}
xa=p[0][0];
for(int i=1;i<n;i++){
    sort(p[i]+1,p[i]+p[i][0]+1);
    for(int j=2;j<=p[i][0];j++)
        p[i][j]+=p[i][j-1];
    for(int j=p[i][0]+1;j<=n;j++)
        p[i][j]=INF;
}
for(int i=xa;i<=n;i++){ans=min(ans,ck(i));}

G&H

sro CJX,CYC,CYE orz