20160813下午训练记录

*下午听说讲课很简单，被拉去隔壁做只可口胡 不可写的题了

T1

江苏省选的时候有道题面差不多的题目，邵战狂当时跟我口胡过这题

我们还是先不考虑1

那么我们选取一个元素，当加入第二个的时候，两个的奇偶性不同，加入第三个数时，肯定不满足。

那么我们特判一下1的数目，然后乱搞一下

int n,a[1234];
bool np[33333333];
int tot,pr[8001234];
const int N=30000000;
void sieve(){
    for(int i=2;i<=N;i++){
        if(!np[i])pr[++tot]=i;
        for(int j=1;j<=tot&&i*pr[j]<=N;j++){
            np[i*pr[j]]=1;
            if(i%pr[j]==0)break;
        }
    }
    return;
}
int f(int cnt1){
    int ans=0;
    if(cnt1)
        for(int i=1;i<=n;i++)if(a[i]!=1)if(!np[a[i]+1])return 1;
    else 
        return 0;
}
int main(){
    freopen("prime.in","r",stdin);
    freopen("prime.out","w",stdout);
    sieve();
    cin>>n;
    
    int L=0,cnt1=0,is2=0;
    for(int i=1;i<=n;i++)cin>>a[i],cnt1+=(a[i]==1);
    sort(a+1,a+n+1);
    if(n==2){
        cout<<n<<endl<<a[1]<<' '<<a[2];
        return 0; 
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i^j)if(!np[a[i]+a[j]])L=2;
    if(!L)for(int i=1;i<=n;i++)if(!np[a[i]])L=1;
    if(L==1){
        printf("1
");for(int i=n;i>=1;i--)if(!np[a[i]]){
            printf("%d",a[i]);return 0;
        }
    }int t;
    if(cnt1+f(cnt1)<=2){
        puts("2");
        for(int i=n;i>=1;i--)for(int j=i-1;j>=1;j--){
        if(i^j)if(!np[a[i]+a[j]])printf("%d %d
",a[j],a[i]);return 0;}
    }else{
        L=cnt1+f(cnt1);
        cout<<L<<endl; 
        for(int i=1;i<=cnt1;i++)printf("%d ",1);
        for(int i=n;i>=1;i--)if(!np[a[i]+1]){
            printf("%d",a[i]);return 0;
        }
    }
}

然后我走远了。。

T2

只会n^2dp

f[i][j][0] 前i个放j朵花的最优值，i不放

f[i][j][1]前i个放j朵花的最优值，i放

转移

int f[3010][3010][2],a[3010];
int n,m;
int main(){
    freopen("flower.in","r",stdin);
    freopen("flower.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)f[i][j][0]=f[i][j][1]=-2000000000;
    f[1][1][1]=a[1]; 
    for(int i=2;i<=n;i++){
        f[i][0][0]=0;
        for(int j=1;j<=m;j++){
            f[i][j][1]=f[i-1][j-1][0]+a[i];
            f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]);
        }
    }
    int ans=f[n][m][0];
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)f[i][j][0]=f[i][j][1]=-2000000000;
    f[1][0][0]=0;
    for(int i=2;i<=n;i++){
        f[i][0][0]=0;
        for(int j=1;j<=m;j++){
            f[i][j][1]=f[i-1][j-1][0]+a[i];
            f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]);
        }
    }
    ans=max(ans,max(f[n][m][0],f[n][m][1]));
    if(m>n/2)cout<<"Error!";
    else cout<<ans;
//    cout<<(m>n/2?"Error!":ans);
    return 0;
}

T3

给定一棵树，可以把他删除一条边，分成两个联通块，最小化两个的直径之和

不会做