模拟赛

数据范围：$n \le 100,1\le a_i,b_i,c_i \le 10^9$

值域很大，无法加到状态里。那么考虑每个操作对答案产生的贡献。

我们把攻击力拆开来算。

直接攻击，那么贡献就是 $a_i$。

设这回合后一共攻击 $j$ 次。

加攻击力，那么在这以后每次攻击伤害都会加 $c_i$，贡献就是 $j\times c_i$

加增量，那么设后续攻击的回合是 $p_1,p_2,\cdots,p_j$，那么贡献为 $\sum_{k=1}^j (p_k-i)\times b_i$。

把这个东西稍微拆一下，得到 $b_i(\sum_{k=1}^j p_k-j\times i)$。

那么我们只需要记录攻击次数和攻击回合的编号和即可。

但有个问题，我们现在的贡献和未来回合的行动有关。

所以要倒过来做。那么转移也要相应的变一下。

设 $f_{i,j,k}$ 表示第 $i$ 个回合到最后一个回合，一共攻击了 $j$ 次，攻击回合的编号和为 $k$ 的最大值。

转移为

$$f_{i,j+1,k+i}=f_{i+1,j,k}+a_i \\ f_{i,j,k}=f_{i+1,j,k}+(i\times j-k)\times b_i \\ f_{i,j,k}=f_{i+1,j,k}+j\times c_i$$

转移时可以把第一维压掉，但第二维要倒序枚举。

复杂度 $O(n^4)$。

Code：

#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=110,inf=1e18;
int n;
int a[maxn],b[maxn],c[maxn],f[maxn][maxn*maxn];
inline void solve(){
    cin>>n;
    for(re int i=1;i<=n;++i) cin>>a[i]>>b[i]>>c[i];
    reverse(a+1,a+n+1);reverse(b+1,b+n+1);reverse(c+1,c+n+1);
    memset(f,-0x3f,sizeof f);
    f[0][0]=0;
    for(re int i=1;i<=n;++i){
        for(re int j=i-1;j>=0;--j){
            for(re int k=0;k<=(i-1)*i/2;++k){
                f[j+1][k+i]=max(f[j+1][k+i],f[j][k]+a[i]);
                f[j][k]=max(f[j][k],f[j][k]+max((i*j-k)*b[i],j*c[i]));
            }
        }
    }
    int ans=-inf;
    for(re int i=0;i<=n;++i) for(re int j=0;j<=n*(n+1)/2;++j) ans=max(ans,f[i][j]);
    cout<<ans<<'\n';
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T;cin>>T;while(T--) solve();
    return 0;
}

Removing Leaves *2300

又读错题被硬控了。

一开始没看见 $k$，以为随便删。

考虑贪心。

我们用 set 存每个节点，然后每次找到叶子最多的那个点，然后删 $k$ 个。找不到就结束。

这为什么是对的？

感性理解一下，我们这么做只会让能删的点越来越多，而且不会有本来能删的点因为操作而不能删除，所以这么做操作数就是最大的。

复杂度 $O(n\log n)$

Voting (Hard Version) *2400

看完题就想到了一个假贪心：先按 $m$ 降序再按 $p$ 升序，每次买 $m$ 最大 $p$ 最小的。

显然不对。我们不一定只从 $m$ 最大的里面买。

那改成每次买 $p$ 最小的呢？

还是不对。因为不一定买最小的就优。例如这组样例

2
1 1
2 2

显然只需要 $2$ 即可。

那应该怎么做？

我们依旧按 $m$ 降序排序。

对于当前的 $m_i$，设 $m$ 值小于 $m_i$ 的人数为 $pre$，大于 $m_i$ 且被买的人数为 $cnt$。

假设我们已经把 $< m_i$ 的人全搞定了，那么只需要让 $pre+cnt\ge m_i$，就能搞定 $m_i$了。

但如果不满足，我们就要从 $\ge m_i$ 的人里买人（因为 $pre$ 是固定的），直到 $pre+cnt\ge m_i$。

满足该条件后，$m_i$ 就被我们搞定了。

那么我们只需要保证 $< m_i$ 的人都被搞定就行了。

然后再处理 $< m_i$ 的那些人。这是一个子问题，和上述步骤完全一致。

买人贪心买最便宜的，用个堆维护一下即可。

复杂度 $O(n\log n)$

Happy Life in University *2300

怎么现在啥数据结构都不会了/kk。

对于这种 lca 的问题，常见套路是枚举 lca，把贡献都在 lca 处统计（枚举 lca 的意思是考虑每个点作为 lca 时的情况）。

而这种 lca 的路径问题又能跟子树弄上关系。

设当前考虑到以 $u$ 为根的子树。

那么我们只需要维护 $u$ 到子树内节点的路径即可，答案就是拿两条路径拼起来。

假设已经搜完了子树，回溯到了 $u$。

那么 $u$ 会对所有路径产生自己颜色的贡献。

但显然会算重，那么考虑去重。

因为每个点只需要在离他最近的且颜色和他相同的祖先处减去重复，所以只会操作 $O(n)$ 次。

那么直接去重就是对的。

所以我们的操作就只有子树加和子树查，线段树维护。

答案用最大值和次大值拼一下即可。

复杂度 $O(n\log n)$

Wine Factory (Easy Version) *2300

讲一个很有意思的做法。

我们考虑有多少水被浪费了。

设 $f_i$ 表示从 $i$ 流向 $i+1$ 的水的量。

转移为

$$f_i=\max(f_{i-1}+a_i-b_i,0)$$

这东西可以用 $(max,+)$ 矩乘表示。

$$\begin{bmatrix} f_i \\ 0 \end{bmatrix} = \begin{bmatrix} a_i-b_i & 0 \\ -inf & 0 \end{bmatrix} \times \begin{bmatrix} f_{i-1} \\ 0 \end{bmatrix}$$

然后线段树维护矩阵即可。单点修改也是简单的。

复杂度 $O(k^3n\log n)$

Mark and Professor Koro *2300

感觉和 [HBCPC2024] Enchanted 非常的像啊，套路也是一样。

对于这种两个相同的数合并成+1的数的操作，我们可以把它看成二进制意义下的加法，然后进行维护。

但这个题不能直接把数的二进制用整数表示，值域太大了。

我们用线段树维护值域上每个数出现次数，不难发现每个数出现次数只会为 0/1。

那么修改可以看成删一个数再加上一个数。

删和加是类似的，先考虑加。设加的那个数是 $x$。

如果 $x$ 那一位是 0，那么不用进位，直接给这一位 +1 即可。

否则会进位。但不难发现，这东西是一次区间覆盖和一次单点修改。

删数同理。

如果 $x$ 那一位是 1，那么不用退位，直接给这一位 -1 即可。

否则会退位。依旧是一次区间覆盖和一次单点修改。

那么答案就是最右边的 1 的位置，这个可以线段树上二分找到。

具体的，线段树上维护区间里 1 的个数。

加法进位：找到 $x$ 后第一个为 0 的位置 $pos$，然后把 $[x,pos-1]$ 区间赋值为 0，把 $pos$ 赋值为 1.

减法进位：找到 $x$ 后第一个为 1 的位置 $pos$，然后把 $[x,pos-1]$ 区间赋值为 1，把 $pos$ 赋值为 0.

找位置都可以线段树上二分。

复杂度 $O(n\log n)$