1.11-1.15做题笔记

说句闲话

主要记录了一模考完之后做的一些题，有难的也有比较简单的，都是一些不属于任何比赛的题，所以放在这里统一记录了。

P3551 [POI2013] USU-Take-out

题目大意

有 \(n\) 块砖，其中白色是黑色的 \(k\) 倍，求一个消除序列，满足以下条件：

每次消除 \(k+1\) 个砖，其中 \(k\) 块白色，\(1\) 块黑色，并且这 \(k+1\) 块砖从开始到结束，中间不能路过已经消除过的砖。

解题思路

这个问题看似很棘手：怎样保证中间不能路过已经消除过的砖块？

可以手模一下样例，就会发现，一个比较优的策略是先将取两边的砖块，最后取中间的砖块，但是这样很难实现。

这时候可以考虑反向思考，如果是按照这样的策略，那么最后一组序列就会是在中间的一段连续区间，根据这个突破口，我们不难得到以下做法：

维护一个栈，当栈顶有连续的一段区间中恰好满足白色 \(1\) 个，黑色 \(k\) 个的条件，就将这 \(k+1\) 个元素弹出，依此类推，只要栈顶有连续 \(k+1\) 个元素满足要求就弹出，最终将弹出的元素倒序输出就是正确方案。

判断满足要求可以将白色砖块赋值为 \(1\)，黑色砖块赋值为 \(0\)，再用前缀和维护。

for(int i=1;i<=n;i++){
    stk.push(i);

    int top=stk.size();
    sum[top]=sum[top-1]+(s[i-1]=='c'); 

    if(stk.size()<k+1)continue;
    if(sum[top]-sum[top-k-1]==1){
        int j=0;
        while(j<=k){
            output.push_back(stk.top());
            j++,stk.pop();
        }
        //stk.pop_k(k+1);
    }
}

for(int i=output.size()-1;i>=0;i--){
    cout<<output[i]<<" ";
    if(i%(k+1)==0)cout<<"\n";
}

P11148 [THUWC 2018] 零食

题目大意

有两种物品价值为 \(a_i\) 与 \(b_i\) 分别 \(n\) 个和 \(m\) 个，现在将两种物品放到同一个序列中，如果当前物品类型与上一个物品相同，则总价值会加上当前物品价值 \(a_i\) 或 \(b_i\)，若类型不同，则总价值不变。

求解最大的总价值。

\(a_i\) 和 \(b_i\) 都有可能是负数。

题目思路

贪心地思考问题，最优的情况肯定是正的价值全部算入总价值，负的价值全部不算。

考虑如何尽量让负的价值全都不算呢？将负的物品 \(a\) 与物品 \(b\) 交替放置是显然的。

那么就可以直接确定策略：

先将 \(a\) 与 \(b\) 分别由小到大排序，计算前缀和 \(suma\) 以及 \(sumb\)，然后就可以线性枚举求出最大值。

注意开 long long。

sort(a+1,a+1+n);
sort(b+1,b+1+m);

ll ans=-1ll<<62;
for(int i=n;i>=1;i--){
    sum_a[i-1]=sum_a[i]+a[i];
}
for(int i=m;i>=1;i--){
    sum_b[i-1]=sum_b[i]+b[i];
}
for(int i=1;i<=min(n,m);i++){
    ans=max(ans,sum_a[i]+sum_b[i]);
    if(i<n)ans=max(ans,sum_a[i+1]+sum_b[i]);
    if(i<m)ans=max(ans,sum_a[i]+sum_b[i+1]);
}

P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并

线段树合并的模板题。

首先学习了动态开点线段树，在线段树的 build 函数中维护两个数组 ls 和 rs。

线段树合并的主要过程：

假设两颗线段树为 A 和 B，从 \(1\) 号节点开始递归合并。

递归到某个节点时，如果 A 树或者 B 树上的对应节点为空，直接返回另一个树上对应节点，运用了动态开点线段树的特性。

如果递归到叶子节点，我们合并两棵树上的对应节点。

最后，根据子节点更新当前节点并且返回。

对于本题，用差分把树上修改转化为单点修改，然后向上 dfs 线段树合并统计答案即可。

这里是线段树合并的模板。

struct Seg_Tree{
    int cnt=0;
    int sum[N*50],res[N*50];
    int ls[N*50],rs[N*50];
    
    void push_up(int rt) {
        if(sum[ls[rt]]<sum[rs[rt]]){
            res[rt]=res[rs[rt]],sum[rt]=sum[rs[rt]];
        } 
        else{
            res[rt]=res[ls[rt]],sum[rt]=sum[ls[rt]];
        }
    }

    void merge(int &a,int b,int l,int r){
        if(!a){
            a=b;
            return;
        }
        if(!b){
            return;
        }

        if(l==r){
            sum[a]+=sum[b];
            return;
        }

        int md=(l+r)>>1;
        merge(ls[a],ls[b],l,md);
        merge(rs[a],rs[b],md+1,r);
        push_up(a);

        return;
    }

    void add(int &rt,int l,int r,int p,int x){
        if(!rt){
            rt=++cnt;
        }
        if(l==r){
            sum[rt]+=x,res[rt]=p;
            return;
        }
        int md=(l+r)>>1;
        if(p<=md){
            add(ls[rt],l,md,p,x);
        }
        else{
            add(rs[rt],md+1,r,p,x);
        }
        push_up(rt);
        
        return;
    }
}Tr;

P10242 [THUSC 2021] Emiya 家明天的饭

首先可以钦定每个菜满足哪些人的需求，问题就被转化为了求解：

$\sum S \sum {i \in S} \sum f \(，\)f$ 表示每一行的超集和。

求解超集和可以使用状压dp，时间复杂度 \(O(n^2\times 2^n)\)。

for(int j=1;j<=m;j++){
    int tmp=0;
    for(int i=1;i<=n;i++)
        if(a[i][j]!=-1){
            tmp|=1<<i-1;
        }
    for(int i=1;i<=n;i++)
        if(a[i][j]!=-1){
            f[i][tmp]+=a[i][j];
        }
}

for(int i=1;i<=n;i++)
    for(int j=0;j<n;j++)
        for(int k=0;k<(1<<n);k++){
            if(!(k&(1<<j))){
                f[i][k]+=f[i][k|(1<<j)];
            }
        }

ll maxn=0;
for(int i=0;i<(1<<n);i++){
    ll sum=0;
    for(int j=1;j<=n;j++){
        if(i&(1<<j-1)){
            sum+=f[j][i];
        }
    }
    maxn=max(maxn,sum);
}

cout<<maxn<<"\n";