0426 C组模拟赛 题解
T1 题解
部分分暴力 \(DFS\)，后面两个特殊点可以用最大的一半和最小的一半匹配，不展开讲。
首先题意等价为选 \(\dfrac{n}{2}\) 个 \(i\) 的 \(r\) 加起来，减去其他数的 \(l\)，求最大值。考虑贪心。
首先全选 \(r\)，把第 \(i\) 个换成选 \(l\) 就会使总和减小 \(-l_i-r_i\)，换句话说，把第 \(i\) 个选成 \(l\) 的代价是 \(l_i+r_i\)。
贪心选最小的 \(\dfrac{n}{2}\) 个代价即可。
code
code
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(register int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(register int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e6+5,inf=0x3f3f3f3f;
int n,l[N],r[N];
long long lrlr[N],ans;
signed main(){
n=read();
forup(i,1,n){
l[i]=read();r[i]=read();
ans+=r[i];
lrlr[i]=l[i]+r[i];
}
sort(lrlr+1,lrlr+n+1);
forup(i,1,n/2){
ans-=lrlr[i];
}
printf("%lld",ans);
}
T2 题解
这道题我没钻研过就不讲部分分了。
树上背包合并。
考虑枚举种族 \(i\) 可能会造反，一个连通块中每有一个种族 \(i\) 就产生 \(1\) 贡献，反之产生 \(-1\) 贡献，转化为求贡献大于 \(0\) 的连通块个数。
考虑 \(dp_{i,j}\) 表示 \(i\) 的子树中包括 \(i\) 的连通块有多少个值为 \(j\)（注意处理负数下标），依次将当前节点与每个子节点合并。
关于如何合并，枚举当前连通块 \(u\) 的值 \(j\) 与子节点 \(v\) 的值 \(k\)，使得 \(dp_{u,j+k}\) 增加 \(dp_{u,j}\cdot dp_{v,k}\)，需要注意开一个临时数组存不然可能出现错误。
每次枚举只需要枚举有意义的部分，其他负无穷的值略过，即对于每个节点存一个上界和下界来转移，并且只需要保留 \(-cnt\) 至 \(cnt\) 的部分（\(cnt\) 为整棵树中当前颜色的数量），就能卡过去了。
关于复杂度，树上背包复杂度是 \(O(nk)\) 的，这里 \(k\) 即为 \(cnt\)，而 \(\sum cnt=n\)，故复杂度为 \(O(n^2)\)，由于转移时是 \(O(n)\) 带小常数，所以总的复杂度是 \(O(n^3)\) 带小常数。
code
code
#include<bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(register ll i=(s);i<=(e);i++)
#define fordown(i,s,e) for(register ll i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline ll read(){
ll x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const ll N=3005,inf=0x3f3f3f3f,add=3005,mod=998244353;
ll n,c[N],cnt[N],ans;
vector<ll> e[N];
ll dp[N][N<<1],sv[N<<1],mn[N],mx[N];
ll nwco;
void dfs(ll x,ll fa){
forup(i,-cnt[nwco],cnt[nwco]){
dp[x][i+add]=0;
}
if(c[x]==nwco){
dp[x][1+add]=1;
mx[x]=mn[x]=1;//存储上下界
}else{
dp[x][-1+add]=1;
mx[x]=mn[x]=-1;
}
for(auto i:e[x]){
if(i==fa) continue;
dfs(i,x);
forup(j,mn[x],mx[x]){
sv[j+add]=dp[x][j+add];
}
forup(j,mn[x],mx[x]){
forup(k,mn[i],mx[i]){
if(dp[x][j+add]==0||dp[i][k+add]==0||j+k>cnt[nwco]||j+k<-cnt[nwco]) continue;
sv[j+k+add]=(sv[j+k+add]+dp[x][j+add]*dp[i][k+add]%mod)%mod;
mn[x]=min(mn[x],j+k);
mx[x]=max(mx[x],j+k);
}
}
forup(j,mn[x],mx[x]){
dp[x][j+add]=sv[j+add];sv[j+add]=0;
}
}
forup(i,1,mx[x]){
ans=(ans+dp[x][i+add])%mod;
}
}
signed main(){
n=read();
forup(i,1,n){
c[i]=read();
cnt[c[i]]++;
}
forup(i,1,n-1){
ll u=read(),v=read();
e[u].push_back(v);e[v].push_back(u);
}
forup(i,1,n){
if(!cnt[i]) continue;
nwco=i;
dfs(1,0);
}
printf("%lld",ans);
}
T3 题解
子任务 #1 20pts
设 \(dp_i\) 表示从 \(i\) 到 \(n\) 的最大心情值，有一个显然的 dp 式子。
边界条件是 \(dp_n=H_n\)，特判即可，可以 \(O(n)\) 转移，复杂度 \(O(n^2)\)。
子任务 #3 子任务 #4
子任务 #3 中，\(K=1\)，此时下取整不会影响，#4 中，\(K=n\)，此时疲劳度始终为 \(0\)，这两个点可以直接用线段树维护，复杂度 \(O(n\log n)\)。
90pts
其实棺方题解说这个方法可以 AC，但是我不太信 \(O(n\log^2n)\) 可以过 \(10^6\)。
我们发现下取整非常麻烦，因为难以把 \(i\) 和 \(j\) 分别拆出来，但思考一下发现其实可以拆出来。
先不看后面的系数 \(D\)，那个式子可以这样转化：
令 \(I=i \bmod K,J=j\bmod K\)
由于前面两项都是整数所以可以直接提出来，则上式可化为：
由于 \(J < K,I<K\)，所以 \(\left\lfloor\frac{J-I}{K}\right\rfloor\) 必定等于 \(0\) 或 \(-1\)，当且仅当 \(J <I,\left\lfloor\frac{J-I}{K}\right\rfloor=-1\)。
故 20pts 的 dp 式子可化为：
其中中括号表示满足该条件时该表达式的值为 \(1\)（注意 \(-1\) 与前面的减号负负得正就变成加号了）。
然后我们把带 \(i\) 的式子拆出来：
令 \(f_j=dp_j-\left\lfloor\frac{j}{K}\right\rfloor\cdot D\)：
接下来我们只需要考虑那个让人头疼的中括号了。
注意到，假如我们把所有 \(\left\lfloor\frac{j}{K}\right\rfloor\) 相等的 \(j\) 分为一块，满足那个式子的一定在一个连续的区间内，且一定是这一块的前缀。
画个图理解一下，我们把所有 \(\left\lfloor\frac{j}{K}\right\rfloor\) 相等的 \(j\) 放在同一列，模数相同的放在同一行。
这启发我们用一个二维树状数组维护（或者笼统地说，树状数组套树状数组）。
对于每个模数（即上图中每一行），维护一个求前缀最大值树状数组，然后把这些树状数组压到一棵纵向的树状数组里，用来求二维区间最大值。
这样我们就能在 \(O(\log^2n)\) 的时间内查询某个矩形内的最大值。
接下来我们考虑要查询哪些区间，带哪个式子。
分两种情况讨论：
这种情况下，\(i+T_i\) 的模数大于 \(i\) 的模数，我们需要查询以下几个区间。
上图几个彩色圆点即我们查询的点，前面多查的部分都赋为 \(-\infty\) 所以不用管。
有人可能有问题：为什么红色部分和黄色部分带两个不同的式子，但红色部分包含了黄色部分。
欸这你就问对人了，我昨晚做梦都在想这个问题。
思考一个问题，黄色部分带的式子等于红色部分加 \(1\)，也就是说假如红色部分的最大值在黄色部分里，那么它并不会对答案产生贡献，可以忽略。
另一种情况：
同理，不解释了。
复杂度 \(O(n \log \frac{n}{K}\cdot\log K)\) 题解说能过 \(2 \times 10^6\)，但我不信。
100 pts
注意到每一列只有求前缀操作，且处理完当前列后就不会修改，想到纵向维度上并不需要树状数组，我们对当前列单独开一个树状数组，每次清空，处理完当列后顺着跑一边前缀最大值上传到对应的横向树状数组中。
复杂度 \(O(n \log \frac{n}{K})\)。
需要注意，100pts 做法和 90pts 做法都需要用 vector 动态开空间来防止 MLE。
code
code
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(register ll i=(s);i<=(e);i++)
#define fordown(i,s,e) for(register ll i=(s);i>=(e);i--)
using namespace std;
typedef long long ll;
#define T (1<<15)
char buf[T],*p1=buf,*p2=buf;
#define nc() (p1==p2&&(p2=buf+fread(p1=buf,1,T,stdin),p1==p2)?-1:*p1++)
ll read(){//题目给的快读，赞美好题！
ll x=0;char c;bool s=0;
do c=nc();while(c!=45&&(c<48||c>57));
if(c==45)c=nc(),s=1;
do x=10*x+(c&15),c=nc();while(c>=48&&c<=57);
return s?-x:x;
}
#undef T
const ll N=2e6+5,inf=1e18;
ll n,K,D,h[N],t[N],dp[N],blg[N],L[N],R[N];
void mymax(ll& a,ll b){
if(a<b) a=b;
}
struct Tree1{
vector<ll> c;
ll sz;
void resz(ll x){c.resize(x+1);sz=x;forup(i,1,sz)c[i]=-inf;}
void Upd(ll x,ll k){
for(;x<=sz;x+=x&-x){
if(c[x]>k)break;
c[x]=k;
}
}
ll Ask(ll x){ll res=-inf;for(;x>0;x-=x&-x)res=max(res,c[x]);return res;}
}nt;
vector<Tree1> mt;
signed main(){
n=read();K=read();D=read();
mt.resize(K+1);
forup(i,0,K){
mt[i].resz((n+K-1)/K+1);
}
forup(i,1,n){
h[i]=read();
}
forup(i,1,n-1){
t[i]=read();
}
ll cnt;//块数
for(int i=1;R[i-1]!=n;++i){
cnt=i;
L[i]=max((i-1)*K,1ll);R[i]=min(i*K-1,n);
forup(j,L[i],R[i]){blg[j]=i;}
}
fordown(bl,cnt,1){
nt.resz(K+1);//清空当前树状数组
fordown(i,R[bl],L[bl]){
ll pipi=i%K;//在哪一行
if(i==n){//n 要特判
dp[i]=h[i];
nt.Upd(pipi+1,dp[i]-i/K*D);
continue;
}
ll rted=min(t[i]+pipi+1,K);//在当前块最右能取到哪里
ll res=-inf;
mymax(res,nt.Ask(rted)+i/K*D);
if(t[i]+pipi+1<=K){//如果 i+T 就在当前行可以直接跳过
dp[i]=res+h[i];
nt.Upd(pipi+1,dp[i]-i/K*D);
continue;
}
ll post=blg[i+t[i]],ppt=(pipi+t[i])%K;//Ti+i 的行数和列数
if(ppt>=pipi-1){
if(pipi!=0) mymax(res,mt[pipi-1].Ask(post)+i/K*D+D);
//注意不取等，所以要减一
mymax(res,mt[K-1].Ask(post-1)+i/K*D);
mymax(res,mt[ppt].Ask(post)+i/K*D);
}else{
mymax(res,mt[pipi-1].Ask(post-1)+i/K*D+D);
mymax(res,mt[K-1].Ask(post-1)+i/K*D);
mymax(res,mt[ppt].Ask(post)+i/K*D+D);
}
dp[i]=res+h[i];//统计答案
nt.Upd(pipi+1,dp[i]-i/K*D);//上传到当前树状数组
}
ll mx=-inf;//前缀最大值
forup(i,L[bl],max(R[bl],L[bl]+K-1)){
//处理完后順向上传前缀最大值
if(i<=R[bl]) mymax(mx,dp[i]-i/K*D);
mt[i%K].Upd(bl,mx);
}
}
ll ans=0;
forup(i,1,n){
// printf("%lld ",dp[i]);
ans^=(dp[i]+i);
}
printf("%lld",ans);
}