2024 提高组杂题
T1 [CF1763C] Another Array Problem
弱智题。容易发现无论怎么操作 \(\sum a_i\) 不会超过 \(\max a_i\times n\)，且在 \(n\ge4\) 时一定能够取到。所以我们只需考虑 \(n=2\) 或 \(n=3\) 的情况。
\(n=2\) 时，只需取 \(\max(a_1+a_2,2\times|a_1-a_2|)\) 即可。
\(n=3\) 时，数组最后的取值只可能有 \(a_1+a_2+a_3,3\times a_1,3\times a_3,3\times|a_1-a_2|,3\times|a_2-a_3|\) 五种情况。取 \(\max\) 即可。
constexpr int MAXN=2e5+5;
int T,n;
long long a[MAXN];
int main(){
T=read();
while(T--){
n=read();
for(int i=1;i<=n;++i) a[i]=read();
if(n==2) write(max(abs(a[2]-a[1])<<1,a[1]+a[2]));
else if(n==3) write(max(a[1]+a[2]+a[3],max({a[1],a[3],abs(a[1]-a[2]),abs(a[2]-a[3])})*n));
else write(*max_element(a+1,a+n+1)*n);
}
return fw,0;
}
T2 [CF1775E] The Human Equation
精妙构造题。题目所给的操作看似复杂，但观察到一个加一、一个减一这种操作很像差分，于是把 \(a\) 数组当成差分数组，还原出原数组 \(b\)。则在 \(a\) 数组上的每一次操作都可以转化为将 \(b\) 数组的任意值加或减一个数。
显然最少操作次数为 \(b\) 数组的极差。
constexpr int MAXN=2e5+5;
int T,n;
long long a[MAXN];
int main(){
T=read();
while(T--){
n=read();
for(int i=1;i<=n;++i) a[i]=a[i-1]+read();
long long mx=0,mn=0;
for(int i=1;i<=n;++i) mx=max(mx,a[i]),mn=min(mn,a[i]);
write(mx-mn);
}
return fw,0;
}
T3 [CF1290C] Prefix Enlightenment
前置知识：种类并查集。代表例题：[NOI2001] 食物链。
首先需要理解 ”任意三个子集的交集为空集“ 是什么意思。翻译成人话就是：任意一点顶多出现在两个集合中。于是我们设 \(L_i,R_i\) 分别为包含 \(i\) 点的两个集合（若没有则为 \(0\)）。
题目要求求出对于所有 \(m_i\)，于是我们考虑一个个加入。对于每个点都有如下情况讨论：
- \(S_i=0\)，则 \(L_i,R_i\) 能且仅能操作一个；
- \(S_i=1\)，则 \(L_i,R_i\) 要么都操作，要么都不操作。
这种维护条件的连通性的题目，想到种类并查集。对于每个集合 \(k\)，设立两个点分别表示操作/不操作，记为 \(p(k,0/1)\)。则对于如上条件，我们只需连边：
- \(S_i=0\)，则连边 \(p(L_i,0)\leftrightarrow p(R_i,0)\) 和 \(p(L_i,1)\leftrightarrow p(R_i,1)\)；
- \(S_i=1\)，则连边 \(p(L_i,0)\leftrightarrow p(R_i,1)\) 和 \(p(L_i,1)\leftrightarrow p(R_i,0)\)。
显然，每一条边都代表一种合法的方案。连完边之后，对于每一个连通块，要么选 ”操作“，要么选 ”不操作“，于是我们在合并的时候统计第一层和第二层的最小值即可。
需要注意：
- 注意不能按秩合并，那样会导致关系混乱；只能用路径压缩。
- 还要注意：要处理一个点仅被一个集合包含的情况。在上文我们已经说了，如果不存在就是 \(0\)。所以 \(0\) 点需要用来处理这种情况。并查集的空间应该是 \(O(2n)\) 的。
- 对于这个 \(0\) 点不能操作。所以对于 \(0\) 点的两层情况需要特判，只能取不包含的那一部分。
#include<bits/stdc++.h>
using namespace std;
constexpr int MAXN=3e5+5;
int n,k,ans;
char s[MAXN];
int L[MAXN],R[MAXN];
int f[MAXN<<1],siz[MAXN<<1][2];
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
void combine(int u,int v){
int fu=find(u),fv=find(v);
if(fu==fv) return;
ans-=min(siz[fu][0],siz[fu][1])+min(siz[fv][0],siz[fv][1]);
siz[fu][0]+=siz[fv][0];
siz[fu][1]+=siz[fv][1];
f[fv]=fu;
ans+=min(siz[fu][0],siz[fu][1]);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>k>>(s+1);
for(int i=1,c,x;i<=k;++i){
cin>>c;
for(int j=1;j<=c;++j){
cin>>x;
L[x]?R[x]=i:L[x]=i;
}
}
for(int i=0;i<=k;++i) f[i]=i,siz[i][0]=1;
for(int i=k+1;i<=(k<<1|1);++i) f[i]=i,siz[i][1]=1;
for(int i=1,rt;i<=n;++i){
if(s[i]=='1') combine(L[i],R[i]),combine(L[i]+k+1,R[i]+k+1);
else combine(L[i]+k+1,R[i]),combine(L[i],R[i]+k+1);
rt=find(0);
if(siz[rt][0]<siz[rt][1]) cout<<(ans>>1)+siz[rt][1]-siz[rt][0]<<'\n';
else cout<<(ans>>1)<<'\n';
}
return 0;
}
T4 [CF1458D] Flip and Reverse
想象力/人类智慧/脑电波的构造题。对原串记 \(0\) 为 \(-1\)，\(1\) 为 \(+1\)，得到新的序列；对这个序列做前缀和，记前缀和序列为 \(s\)，并连一条 \(s_i\to s_{i+1}\) 的有向边，可以得到一张图，一个欧拉回路就对应一个字符串。
然后转化题目中的奇怪操作。
- 要求 \([l,r]\) 的 01 个数相等，则 \(s_{l-1}=s_r\)；
- 翻转 + 反转，实际上等于将 \([l,r]\) 的这些边反向。
所以该操作就等价于选择一个环然后将环上所有边反向。
然后需要观察出一个性质：操作前后，原图包含的边集不变。因为操作的是一个环，在操作前 \(x\to y\) 和 \(y\to x\) 的数量是相同的，所以操作后也是相同的。
还需要观察出另外一个性质。。原图任意一条欧拉回路代表的字符串都可以由原串经过操作得到。具体可以看 @tzc_wk 的证明。
于是此题就变为：求字典序最小的欧拉序！
直接贪心即可。
#include<bits/stdc++.h>
using namespace std;
constexpr int MAXN=5e5+5,N=5e5;
int T,n,cnt[MAXN<<1][2];
string s;
int main(){
ios::sync_with_stdio(0);
cin.tie(nullptr),cout.tie(nullptr);
cin>>T;
while(T--){
cin>>s;
n=s.size();
s=' '+s;
for(int i=1,cur=0;i<=n;++i){
++cnt[cur+N][s[i]-'0'];
cur+=s[i]=='0'?-1:1;
}
for(int i=1,x=0;i<=n;++i)
if(cnt[x+N][0]&&cnt[x-1+N][1])
--cnt[x+N][0],--x,cout<<0;
else if(cnt[x+N][1])
--cnt[x+N][1],++x,cout<<1;
else --cnt[x+N][0],--x,cout<<0;
cout<<'\n';
}
return 0;
}
T5 [CF1389F] Bicolored Segments
线段树优化 DP，当然也可以用神秘的 multiset 做。
首先像我就想到二分答案 + 离散化上去了，不过想一想就知道会假。
不过离散化肯定是正确的，先把所有区间离散化。
正解设 \(f_{i,j,0/1}\) 表示考虑到前 \(i\) 个区间、最后一个放入的区间的右端点是 \(j\)、最后放入的区间的颜色是 \(0/1\)。其中第一维可以滚掉，第二维离散化之后空间不成问题。考虑优化时间。
不妨设当前线段是黑色的，也就是 \(1\)。
如果不选当前线段，显然有：\(f_{i,r_i,1}=f_{i-1,r_{i-1},1}\)。
如果选当前线段，设上一条被选择的白色线段的右端点是 \(r_j\)，则所有左右端点都在 \((r_j,r_i]\) 的黑色线段都可以选择。则：\(f_{i,r_i,1}=\max\{f_{j,r_j,0}+w\}\)，其中 \(w\) 为这些黑色线段数量。
这里想要优化就需要状态提前计算。事先将所有 \(r_j<l_i\) 的 \(f_{j,r_j,0}\) 都加上一个 \(1\)，则方程变为 \(f_{i,r_i,1}=\max\{f_{j,r_j,0}\}\)。用一棵支持区间加、单点修、区间最大值的线段树搞它。
#include<bits/stdc++.h>
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
using namespace std;
char buf[1<<20],*p1=buf,*p2=buf;
int read(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch))ch=='-'&&(f=-1),ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
constexpr int MAXN=2e5+5;
int n,mx,b[MAXN<<1],tot;
struct SEG{
int l,r,t;
bool operator<(const SEG&x)const{
return r<x.r;
}
}a[MAXN];
int max(int a,int b){
return a>b?a:b;
}
struct{
#define lp p<<1
#define rp p<<1|1
#define mid ((s+t)>>1)
struct SegTree{
int c,lazy;
}st[MAXN<<3];
void pushdown(int p){
if(!st[p].lazy) return;
st[lp].c+=st[p].lazy,st[lp].lazy+=st[p].lazy;
st[rp].c+=st[p].lazy,st[rp].lazy+=st[p].lazy;
st[p].lazy=0;
}
void pushup(int p){
st[p].c=max(st[lp].c,st[rp].c);
}
void mdf(int l,int r,int k,int s=0,int t=mx,int p=1){
if(l<=s&&t<=r) return st[p].c+=k,st[p].lazy+=k,void();
pushdown(p);
if(l<=mid) mdf(l,r,k,s,mid,lp);
if(mid<r) mdf(l,r,k,mid+1,t,rp);
pushup(p);
}
void chg(int x,int k,int s=0,int t=mx,int p=1){
if(s==t) return st[p].c=k,void();
pushdown(p);
if(x<=mid) chg(x,k,s,mid,lp);
else chg(x,k,mid+1,t,rp);
pushup(p);
}
int sum(int l,int r,int s=0,int t=mx,int p=1){
if(l<=s&&t<=r) return st[p].c;
pushdown(p);
int res=0;
if(l<=mid) res=max(res,sum(l,r,s,mid,lp));
if(mid<r) res=max(res,sum(l,r,mid+1,t,rp));
return res;
}
}s[2];
int main(){
n=read();
for(int i=1;i<=n;++i){
a[i]={read(),read(),read()-1};
b[++tot]=a[i].l,b[++tot]=a[i].r;
}
sort(b+1,b+tot+1);
tot=unique(b+1,b+tot+1)-b-1;
for(int i=1;i<=n;++i){
a[i].l=lower_bound(b+1,b+tot+1,a[i].l)-b;
a[i].r=lower_bound(b+1,b+tot+1,a[i].r)-b;
mx=max(mx,a[i].r);
}
sort(a+1,a+n+1);
for(int i=1,p;i<=n;++i){
p=a[i].t;
s[p].mdf(0,a[i].l-1,1);
s[!p].chg(a[i].r,max(s[p].sum(0,a[i].l-1),s[!p].sum(0,a[i].r)));
}
printf("%d\n",max(s[0].st[1].c,s[1].st[1].c));
return 0;
}
T6 [CF1580D] Subsequence
笛卡尔树的构造。将原式化为：
\[(m-1)\sum_{i=1}^ma_{b_i}-2\sum_{i=1}^m\sum_{j=i+1}^m\min\{a_{b_i},\dots,a_{b_j}\}~. \]把所有的 \(a_i\) 放到笛卡尔树上，利用笛卡尔树的一个美妙的性质：连续区间最大值就是 LCA，将原式化为：
\[(m-1)\sum_{i=1}^ma_{b_i}-2\sum_{i=1}^m\sum_{j=i+1}^ma_{\operatorname{LCA}(i,j)}~. \]设 \(f_{u,j}\) 表示节点 \(u\) 选择 \(j\) 个节点的最大价值，初始 \(f_{u,1}=(m-1)a_i\)，然后类似树形背包地转移：
\[f_{u,i+j}=\max\{f_{u,i}+f_{v,j}-2\times i\times j\times a_u\}~. \]constexpr int MAXN=4005;
int n,m,a[MAXN];
int ls[MAXN],rs[MAXN],stk[MAXN],top;
int f[MAXN][MAXN],tmp[MAXN],siz[MAXN];
void insert(int k,int w){
while(top&&w<a[stk[top]]) ls[k]=stk[top--];
if(top) rs[stk[top]]=k;
stk[++top]=k;
}
bool vis[MAXN];
void dfs(int u);
void work(int u,int v){
dfs(v);
for(int i=0;i<=siz[u];++i) tmp[i]=f[u][i],f[u][i]=0;
for(int i=0;i<=siz[u];++i)
for(int j=0;j<=siz[v];++j)
f[u][i+j]=max(f[u][i+j],tmp[i]+f[v][j]-2*a[u]*i*j);
siz[u]+=siz[v];
}
void dfs(int u){
f[u][1]=(m-1)*a[u];
siz[u]=1;
if(ls[u]) work(u,ls[u]);
if(rs[u]) work(u,rs[u]);
}
signed main(){
n=read(),m=read();
for(int i=1;i<=n;++i) insert(i,a[i]=read());
for(int i=1;i<=n;++i) vis[ls[i]]=vis[rs[i]]=1;
for(int i=1;i<=n;++i)
if(!vis[i]){
dfs(i);
printf("%lld\n",f[i][m]);
return 0;
}
}