牛客NOIP暑期七天营-提高组4 Solution

T1 麻将

T2 卖羊驼

$V$为最大权值,$K$为总段数,$n$为羊驼总数,$p[i]$表示第 i 只羊驼的权值,$dp[i][k]$表示在 i 及 i 之前将序列分解为k组的最优解,$lp[j]$表示在 i 往前第一个二进制第 j 位为1的羊驼 , $or\_val[j]$ 为从 $i$ 到 $lp[j]$ 的或和

根据如上定义,我们可以得到一个动态转移方程

$$dp[i][k]=max(dp[i][k],dp[lp[j]][k-1]+or\_val[j])$$

其中 j 从 0 到 $\lceil log_2(V)\rceil$,时间复杂度为$O(nKlog_2(V))$

实际上,我们最初的想法或许是这样的(其中i,j,k与上无关)

$dp[i][j] = max(dp[i][j],dp[k-1][j-1]+or\_sum(k,i))$

其中 k 为枚举 i 往前的任意一个节点

可是再望时间复杂度$O(n^2K)$,受不起

我们再想(这是一个绝妙的点),或和的本质是对于每一个二进制位上来说,若其中一个值在这一位上为1,则或和在这一位上也为1。而对于一个节点 i 来说,若有两个节点 a , b $(a<b)$,它们的值均在某一位上为1,那么选择 b 作为 新阶段的开始,会比 a 更优。

而对于 第二个转移方程中的 k 的枚举,本质上是对二进制位的枚举,以求出最优答案。

因而,我们会有如下代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int const MAXN=5010,MAXK=1010;
int n,K;
int p[MAXN],dp[MAXN][MAXK],lp[MAXN],or_val[MAXN];
signed main(){
    scanf("%lld%lld",&n,&K);
    for(int i=1;i<=n;i++)scanf("%lld",&p[i]);
    for(int i=1;i<=n;i++){
        for(int j=0;j<=24;j++){//24
            if((p[i]>>j)&1){
                or_val[j]=p[i];
                lp[j]=i;
            }
            or_val[j]|=p[i];
        }
        for(int k=1;k<=K && k<=i;k++){
            for(int j=0;j<=24;j++){
                if(lp[j]>=k)dp[i][k]=max(dp[i][k],dp[lp[j]-1][k-1]+or_val[j]);
            }
        }
    }
    printf("%lld\n",dp[n][K]);
    return 0;
}

本代码对$or\_val,lp$采取的是在 dp 中更新

而还有另外一种玩法,就是在 dp 前就预处理好,这时对于 $or\_val[i][j]$ 的处理便可以用ST表我绝不是因为我不会才没有写

(by fpjo)

T3 清新题

线性基模板。

直接求子树线性基,暴力合并

关于线性基

#include <bits/stdc++.h>
using namespace std;
int n;
int a[100005];
int k[100005][31];
int tot,head[100005],to[100005],nex[100005];
void add(int x,int y){
    to[++tot]=y;nex[tot]=head[x];head[x]=tot;
}
void insert(int s,int x){
    for (int i=20;i>=0;i--){
        if (x&(1<<i)) {
            if (k[s][i]) x=x^k[s][i];
            else {
                k[s][i]=x;
                return ;
            }
        }
    }
}
int maxji(int s){
    int ans=0;
    for (int i=20;i>=0;i--) {
        if ((ans^k[s][i]) > ans) ans=ans^k[s][i];
    }
    return ans;
}
void build_up(int s,int fa){
    insert(s,a[s]);
    for (int i=head[s];i;i=nex[i]){
        if (to[i]==fa) continue;
        build_up(to[i],s);
        for (int j=20;j>=0;j--){
            if (k[to[i]][j])
            insert(s,k[to[i]][j]);
        }
    }
}
int main(){
     cin>>n;
    for (int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    for (int i=1;i<=n;i++)
        cin>>a[i];
    build_up(1,0);
    int m;
    cin>>m;
    for (int i=1;i<=m;i++){
        int x;
        cin>>x;
        cout<<maxji(x)<<endl;
    }
    return 0;
}
Last modification:August 24th, 2019 at 01:59 pm

Leave a Comment