题解 P8908 [USACO22DEC] Palindromes P
vectorwyx
·
·
题解
先考虑对于整个数组怎么求出最小代价。
首先如果 0,1 均出现了奇数次那么它不可能重排为回文串，直接贡献 -1。否则令 m 表示 1 的个数，考虑每个 1 最终去到了哪。假设最初 1 所在位置构成的序列 a，最终 1 所在位置构成的序列为 b，那么这是一个类似匹配的问题，贪心，把 a,b 从小到大排序后 \sum |a_i-b_i| 即为答案。
接下来优化这个 dp，有个显然的想法是对每个 $a_i(i\le \frac{m}{2})$ 取匹配点 $i$ 使得 $|i-a_i|+|n-i+1-a_{m-i+1}|$ 最小，问题在于这样取出来的 $b_i$ 可能不单调。注意到 $|i-a_i|+|n-i+1-a_{m-i+1}|=|i-a_i|+|i-(n+1-a_{m-i+1})|$，那么当 $i$ 落在 $[a_i,n+1-a_{m-i+1}]$ 时式子取得最小值。考虑 $a$ 的前半边是否落在 $\frac{n}{2}$ 左边，如果是，令 $b_i=a_i$ 即满足条件。否则，令 $b_i=n+1-a_{m-i+1}$ 则满足条件。那么答案即为 $\sum_i |a_i+a_{m-i+1}-(n+1)|$，不需要 dp。复杂度变为 $O(n^3)$，可以通过前五个点。
然后转为枚举 $a_i,a_{m-i+1}$ 计算它们配对产生的贡献。还是记 $a$ 为整个数组中 $1$ 的位置序列，如果两个位置 $a_i,a_j$ 想要配对的话首先有 $l\le a_i,r\ge a_j$，同时如果 $j-i+1$ 为奇数那么 $r-l+1$ 应当也为奇数。对于每个合法的 $l,r$，$a_i,a_j$ 的贡献为 $|a_i+a_j-(l+r)|$。如果事先知道所有 $[l,r]$ 的信息是不是就好办了，不难发现 $i,j$ 对应的信息可以由 $i-1,j+1$ 递推而来。那么考虑从 $a$ 的每段前缀以及每段后缀出发，每次砍掉首尾的两个元素，把新产生的 $[l,r]$ 加进一个数据结构里。而这里新产生的 $[l,r]$ 其实就是 $l\in(a_{i-1},a_i],r\in[a_j,a_{j+1})$ 对应的所有区间，于是可以枚举 $l+r$ 简单地算出 $l+r$ 的出现次数，然后一并插入数据结构。
现在看看这个数据结构需要支持什么：维护一个可重集，支持：插入 $c$ 个 $x$，查询所有 $\le x$ 的元素之和以及元素个数。由于 $x\le 2n$，只需要用一个树状数组。复杂度 $O(n^2\log n)$。有一个细节是让出现次数较少的值作为 $1$，这样可以省去一半的常数。
代码如下：（码字不易，能不能点个赞再走QAQ）
```cpp
#include<bits/stdc++.h>
namespace vectorwyx{
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define sml(x,y) (x=min(x,y))
#define big(x,y) (x=max(x,y))
#define ll long long
#define uint unsigned
#define ull unsigned long long
#define umap unordered_map
#define db double
#define fo(i,x,y) for(int i=(x);i<=(y);++i)
#define go(i,x,y) for(int i=(x);i>=(y);--i)
#define ptc putchar
#define emp emplace
#define re return
#define co continue
#define brk break
#define HH (ptc('\n'))
#define bctz __builtin_ctz
#define bclz __builtin_clz
#define bppc __builtin_popcount
using namespace std;
ll seed=chrono::system_clock::now().time_since_epoch().count();
mt19937 rnd(seed);
inline int rm(int x,int y){return (int)(rnd()%(y-x+1ll)+x);}
inline int read(){signed ch=getchar();int x=0,f=1;while(!isdigit(ch)){if(ch==(int)('-'))f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void out(int *a,int l,int r){fo(i,l,r) cout<<*(a+i)<<' ';puts("");}
const int N=7505,inf=1e9;
int cnt;ll sum;
namespace BIT{
int n;
pair<int,ll> tr[N<<1];
#define lbit(x) (x&(-x))
void upd(int c,int k){//插入 c 个 k
// printf("upd(%d,%d)\n",c,k);
sum+=(ll)c*k;cnt+=c;
int x=k;
while(x<=n){
tr[x].fi+=c,tr[x].se+=(ll)c*k;
x+=lbit(x);
}
}
int ask_cnt(int x){
int ret=0;
while(x){
ret+=tr[x].fi;
x-=lbit(x);
}
re ret;
}
ll ask_sum(int x){
ll ret=0;
while(x){
ret+=tr[x].se;
x-=lbit(x);
}
re ret;
}
void clear(){fo(i,1,n) tr[i]=mk(0,0);}
}
using BIT::upd;
using BIT::ask_cnt;
using BIT::ask_sum;
using BIT::clear;
int a[N],n,c0[N],c1[N],b[N],m,pos[N],ct;
ll ans;
inline void play(int l,int r,int L,int R,bool fl){
r-=l,R-=L;
fo(x,0,r+R) if(!fl||(x+l+L)%2==0){
int lx=max(0,x-R),rx=min(x,r);
// int c=fl?(rx/2-(lx-1)/2):(rx-lx+1);
int c=(rx-lx+1);
upd(c,x+l+L);
}
}
void shrink(int l,int r){
int fl=(r-l+1)&1;
sum=0;cnt=0;
clear();
while(l<=r){
// printf("[%d,%d]\n",l,r);
// fo(j,pos[l-1]+1,pos[l]) fo(k,pos[r],pos[r+1]-1)
// if(!fl||((k-j+1)&1)) upd(1,j+k),sum+=j+k,cnt++;
play(pos[l-1]+1,pos[l],pos[r],pos[r+1]-1,fl);
int x=pos[l]+pos[r];
ll val=sum-2*ask_sum(x)+(ll)x*(2*ask_cnt(x)-cnt);
// printf("cnt=%d sum=%lld x=%d val=%lld\n",cnt,sum,x,val);
if(l==r){
assert(val%2==0);
ans+=val/2;
}else ans+=val;
// printf("now ans=%lld\n",ans);
l++,r--;
}
}
signed main(){
int ch=getchar();while(ch!='G'&&ch!='H') ch=getchar();
while(ch=='G'||ch=='H') a[++n]=ch=='G',ch=getchar();
{
int c=0;fo(i,1,n) c+=a[i];
if(c>n/2) fo(i,1,n) a[i]^=1;
}
BIT::n=2*n;
// cout<<n<<'\n';out(a,1,n);
fo(i,1,n){
c0[i]=c0[i-1]+(a[i]==0);
c1[i]=c1[i-1]+(a[i]==1);
}
fo(i,1,n) if(a[i]) pos[++ct]=i;
pos[ct+1]=n+1;
// cout<<"pos:";out(pos,0,ct+1);
fo(i,1,ct) shrink(1,i);
fo(i,2,ct) shrink(i,ct);
fo(l,1,n) fo(r,l+1,n){
int x=c0[r]-c0[l-1],y=c1[r]-c1[l-1];
if((x&1)&&(y&1)) ans--;
}
cout<<ans;
return 0;
}
}
/*
GHHGGHHGH
-------------------------------------------------
12
*/
signed main(){re vectorwyx::main();}
```