[ARC103F] Distance Sums (构造，重心)
首先显然 \(D_i\) 的最小值被重心取到，不妨以重心为根。
对于一条边连接的两个点 \(x,y\) ，不妨设这条边 \(x\) 侧的点数为 \(siz_x\) ，\(y\) 侧为 \(siz_y\) 。
那么 \(D_y=D_x+siz_x-siz_y=D_x+siz_x-(n-siz_x)=D_x+2\times siz_x -n\) 。
那么我们就可以知道以重心为根的时候，从 \(fa_x\) 转移到 \(x\) 的时候，\(2\times siz_x \leq n\)，因此沿着叶向，\(D_i\) 递减。
那我们可以直接剥叶子，把 \(D_i\) 从大到小排序，然后依次确定父亲。
最后检查跟合不合法就好了。
using namespace std;
typedef long long LL;
map<LL,int> node;
int n;
const int N = 1e5+7;
LL D[N];
int siz[N],fa[N],dep[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%lld",&D[i]);
node[D[i]]=i;
}
sort(D+1,D+n+1);
for(int i=n;i>=2;i--)
{
int x=node[D[i]];
siz[x]++;
fa[x]=node[D[i]+2ll*siz[x]-n];
if(!fa[x]||fa[fa[x]])
{
cout<<-1;
return 0;
}
siz[fa[x]]+=siz[x];
}
LL S=0;
for(int i=2;i<=n;i++)
{
int x=node[D[i]];
dep[x]=dep[fa[x]]+1;
S+=dep[x];
}
if(S!=D[1])
{
cout<<-1;
return 0;
}
for(int i=2;i<=n;i++)
{
int x=node[D[i]];
printf("%d %d\n",x,fa[x]);
}
return 0;
}
[ARC102F] Revenge of BBuBBBlesort!
如果在 \(i\) 位置做过交换，则称 \(i\) 为一个中心点。
性质1：若 \(i\) 为中心点，则在原始排列 \(p\) 中 \(p_i = i\)
\(\texttt{proof:}\)
对 \(i\) 进行过操作后 , 有 \(p_{i-1}<p_i<p_{i+1}\)，不妨设现在\(p_{i}<i\)，那么一定会在 \(p_{i-1}\) 进行一次交换。
也就是说，我们需要使得 \(p_{i-2}>p_{i-1}>p_i\)，这需要在 \(p_{i-2}\) 进行一次交换，也就是说交换完变成 \(p_{i-3}<p_i<p_{i-2}<p_{i-1}\)，那就无法操作了。
另一侧同理。
设 \(a_i=[p_i=i]\)，那么我们只会对 \(a_i=1\) 的位置进行操作。
我们可以发现，如果 \(a_i=1,a_{i+1}=1\)，那么在 \(i,i+1\) 都不会进行操作。
那么 我们可以把 \(a\) 换分成若干段，使得每个段内没有连续相同的\(a\)。
那么各个段是独立的。
合法的条件：
-
[l,r] 内的数恰好覆盖 [l,r]
-
把\(a_i=0\)的单独拿出来，如果这个序列中有长度大于2的下降子序列则不合法。
\(\texttt{proof:}\)
不妨设 \(p_i>p_j>p_k,i<j<k\)。
如果我们现在先交换 \(p_i,p_j\)，那么一定存在 \(a_x=1,i<x<j,p_j<p_x<p_i\)
然后再交换 \(p_i,p_k\)，那么一定存在 \(a_y=1,j<y<k,p_k<p_y<p_i\)。
现在我们要交换\(p_j,p_k\)，但是因为 现在 \(p_j<p_x\)，因此比不可能交换。
其他方案同理。
复杂度 \(O(n)\)
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+7;
int n,p[N],a[N];
void badending()
{
printf("No\n");
exit(0);
}
int mx[N];
void check(int l,int r)
{
int Max=0,SMax=0;
for(int i=l;i<=r;i++)
{
if(p[i]<l||p[i]>r)badending();
if(a[i]==0)
{
mx[i]=Max;
Max=max(Max,p[i]);
}
}
int Min=1e9;
for(int i=r;i>=l;i--)
{
if(a[i]==0)
{
if(mx[i]>p[i]&&p[i]>Min)badending();
Min=min(Min,p[i]);
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",&p[i]);
a[i]=(p[i]==i);
}
for(int i=1;i+2<=n;i++)
if(a[i]==0&&a[i+1]==0&&a[i+2]==0)badending();
for(int i=1;i<=n;i++)
{
int j=i;
while(j+1<=n&&a[j]!=a[j+1])j++;
check(i,j);
i=j;
}
printf("Yes\n");
return 0;
}
[ARC111F] Do you like query problems?
首先为了方便，转成期望。
根据期望的线性性，答案等于每个位置的贡献之和。
记 \(a_{t,i}\) 为 \(t\) 次操作后 \(i\) 位置的数，总的操作种类数 \(S=\frac{n(n+1)}{2}\times (m+m+1)\)，\(Q(i)=\frac{i(n-i+1)}{S}\)为一个当前操作是一个询问操作且包含了位置 \(i\)的概率，那么答案为：
根据整数概率公式，\(E(a_{t,i})=\sum_{w=1}P(a_{t,i}\ge w)\) 。
对于每个 \(w\) 独立计算，把大于等于 \(v\) 的数看成1，小于的看成0，那么最终就是 \(a_{t,i}=1\) 的概率。
设可能会导致 \(a_i\) 改变的操作为关键操作，那么就有两种，一种是 \(v\geq w\) 的取 \(\max\) 操作，一种是\(v<w\) 的取 $\min $ 操作，概率记为\(p1(i)=\frac{i(n-i+1)(m-w)}{S},p2(i)=\frac{i(n-i+1)w}{S}\)。
那么 \(t\) 次操作后 \(a_i=1\) 就是要求至少有一个关键操作且最后一次操作是 \(p1(i)\)，这个概率 \(p_{t,i,w}=\frac{p1(i)}{p1(i)+p2(i)}(1-(1-p1(i)-p2(i))^t)\) 。
记 \(s_{t,i}=\sum\limits_{w=1}^{m-1}p_{t,i,w}=\sum\limits_{w=1}^{m-1}\frac{m-w}{m}(1-(1-\frac{i(n-i+1)m}{S})^t)=\frac{m-1}{2}(1-(1-\frac{i(n-i+1)m}{S})^t)\)
枚举 \(i\)，后面就是一个等比数列求和，复杂度\(O(n\log n)\)
#include<bits/stdc++.h>
using namespace std;
const int N = 1000;
const int mod = 998244353;
const int inv2=(mod+1)/2;
int Pow(int a,int b)
{
int res=1;
while(b)
{
if(b&1)res=1ll*res*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return res;
}
int n,m,q;
inline int mul(int a,int b){return 1ll*a*b%mod;}
inline int inv(int a){return Pow(a,mod-2);}
int Sum(int a,int b)
{
if(a==1) return b;
return mul((Pow(a,b)-1+mod)%mod,inv(a-1));
}
int main()
{
cin>>n>>m>>q;
int S=mul(n,mul(n+1,mul(inv2,m+m+1)));
int ans=0;
for(int i=1;i<=n;i++)
{
int Q=mul(mul(i,n-i+1),inv(S));
int P=mul(m-1,inv2);
int A=mul(mul(i,n-i+1),mul(m,inv(S)));
int W=Sum((1-A+mod)%mod,q);
ans=(ans+mul(P,mul(Q,(q-W+mod)%mod)))%mod;
}
cout<<mul(ans,Pow(S,q));
return 0;
}
[ARC131F] ARC Stamp
考虑倒序操作，将被操作过的位置设为 \(?\) ，那么可以被操作的有如下几种：\(\texttt{ARC,AR?,?RC,A?C,A??,?R?,??C}\) 。
考虑将序列划分成若干段，每段是上述的一种，那么每段是独立的，把所有被操作过的段的方案数。
因为每一段是否被选择和他前后两端都有关系，因此不妨每三个计算一次贡献。
考虑 \(dp\) ，\(f_{i,x,y}\) 表示前 \(i\) 段，第 \(i-1\) 段的状态是 \(x\)，第 \(i\) 段的状态是 \(y\) 的方案数，转移时枚举下一段的状态。
复杂度 \(O(n^2)\)
#include<bits/stdc++.h>
using namespace std;
int n,k;
const int N = 5040;
char S[N];
int a[N],b[N];
#define PII pair<int,int>
#define mk(x,y) make_pair(x,y)
PII range[N];
int m=0;
int dp[N][N][2][2];
int bef[N][N];
const int mod = 998244353;
int w[N];
int calc(int i,int x,int y,int z)
{
if(!i)return 1;
int A=range[i-1].second,B=range[i].first;
int C=range[i].second,D=range[i+1].first;
bool must1=0;
bool must0=0;
if(x==1&&bef[A][B]==2)must1=1;
if(z==1&&bef[C][D]==1)must1=1;
if(x==0&&bef[A][B]==1)must0=1;
if(z==0&&bef[C][D]==2)must0=1;
if(must0&&must1)return 0;
if(must0) return y==0;
if(must1) return (y==1)*w[i];
if(y==0) return 1;
return w[i]-1;
}
int main()
{
scanf("%s",S+1);
n=strlen(S+1);
cin>>k;k=min(k,n);
for(int i=1;i<=n;i++)
if(S[i]=='A')a[i]=1;
else if(S[i]=='R')a[i]=2;
else a[i]=3;
for(int i=1;i<=n;i++)b[i]=a[i];
while(1)
{
bool flag=0;
for(int i=1;i+2<=n;i++)
{
if(b[i]==1&&b[i+1]==2&&b[i+2]==3)
{
range[++m]=mk(i,i+2);
b[i]=b[i+1]=b[i+2]=0;
flag=1;
continue;
}
if(b[i]==0&&b[i+1]==2&&b[i+2]==3)
{
range[++m]=mk(i+1,i+2);
bef[i][i+1]=1;
b[i]=b[i+1]=b[i+2]=0;
flag=1;
continue;
}
if(b[i]==1&&b[i+1]==2&&b[i+2]==0)
{
range[++m]=mk(i,i+1);
bef[i+1][i+2]=2;
b[i]=b[i+1]=b[i+2]=0;
flag=1;
continue;
}
if(b[i]==1&&b[i+1]==0&&b[i+2]==0)
{
range[++m]=mk(i,i);
bef[i][i+1]=2;
b[i]=b[i+1]=b[i+2]=0;
flag=1;
continue;
}
if(b[i]==0&&b[i+1]==2&&b[i+2]==0)
{
bef[i][i+1]=1;
bef[i+1][i+2]=2;
range[++m]=mk(i+1,i+1);
b[i]=b[i+1]=b[i+2]=0;
flag=1;
continue;
}
if(b[i]==0&&b[i+1]==0&&b[i+2]==3)
{
bef[i+1][i+2]=1;
range[++m]=mk(i+2,i+2);
b[i]=b[i+1]=b[i+2]=0;
flag=1;
continue;
}
}
if(!flag)break;
}
sort(range+1,range+m+1);
for(int i=1;i<=m;i++)
{
w[i]=1;
for(int u=range[i].first;u<=range[i].second;u++)w[i]=w[i]*3;
}
dp[0][0][0][0]=1;
for(int i=1;i<=m;i++)
for(int j=0;j<=min(i-1,k);j++)
for(int x=0;x<=1;x++)
for(int y=0;y<=1;y++)
if(dp[i-1][j][x][y])
{
for(int z=0;z<=1;z++)
{
dp[i][j+z][y][z]=(dp[i][j+z][y][z]+1ll*dp[i-1][j][x][y]*calc(i-1,x,y,z)%mod)%mod;
}
}
int res=0;
for(int i=0;i<=k;i++)
for(int c=0;c<=1;c++)
for(int d=0;d<=1;d++)
res=(res+1ll*dp[m][i][c][d]*calc(m,c,d,0)%mod)%mod;
cout<<res;
return 0;
}
[ARC085F] NRE
简单题，设 \(dp_{i,j}\) 表示前 \(i\) 个位置，覆盖最远的区间覆盖到 \(j\) 的最小代价，转移是简单的。
那么只需要线段树优化 \(dp\) 即可。
// LUOGU_RID: 111038731
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
typedef long long LL;
void ckmax(int &x,int v){x=max(x,v);}
int tag[N*4],mn[N*4],upd[N*4];
const int INF = 1e8;
void pushtag(int k,int v)
{
mn[k]+=v;
tag[k]+=v;
upd[k]+=v;
}
void pushmin(int k,int v)
{
mn[k]=min(mn[k],v);
upd[k]=min(upd[k],v);
}
void pushdown(int k)
{
if(tag[k])
{
pushtag(k<<1,tag[k]);
pushtag(k<<1|1,tag[k]);
tag[k]=0;
}
if(upd[k]<=INF)
{
pushmin(k<<1,upd[k]);
pushmin(k<<1|1,upd[k]);
upd[k]=INF;
}
}
void pushup(int k)
{
mn[k]=min(mn[k<<1],mn[k<<1|1]);
}
void Add(int k,int l,int r,int L,int R,int v)
{
if(L<=l&&r<=R)
{
pushtag(k,v);
return;
}
pushdown(k);
int mid=(l+r)>>1;
if(L<=mid)Add(k<<1,l,mid,L,R,v);
if(R>mid)Add(k<<1|1,mid+1,r,L,R,v);
pushup(k);
}
void Min(int k,int l,int r,int L,int R,int v)
{
if(L<=l&&r<=R)
{
pushmin(k,v);
return;
}
pushdown(k);
int mid=(l+r)>>1;
if(L<=mid)Min(k<<1,l,mid,L,R,v);
if(R>mid)Min(k<<1|1,mid+1,r,L,R,v);
pushup(k);
}
int Qry(int k,int l,int r,int L,int R)
{
if(L<=l&&r<=R)return mn[k];
pushdown(k);
int res=INF;
int mid=(l+r)>>1;
if(L<=mid)res=min(res,Qry(k<<1,l,mid,L,R));
if(R>mid)res=min(res,Qry(k<<1|1,mid+1,r,L,R));
return res;
}
void Build(int k,int l,int r)
{
mn[k]=INF;
upd[k]=INF;
tag[k]=0;
if(l==r)return;
int mid=(l+r)>>1;
Build(k<<1,l,mid);
Build(k<<1|1,mid+1,r);
}
int n,w[N],m,dp[N];
void ADD(int l,int r,int v)
{
Add(1,0,n,l,r,v);
}
void MIN(int l,int r,int v)
{
Min(1,0,n,l,r,v);
}
int QRY(int l,int r)
{
return Qry(1,0,n,l,r);
}
vector<int> G[N];
int main()
{
// freopen("a.in","r",stdin);
// freopen("a.ans","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
cin>>m;
for(int i=1;i<=m;i++)
{
int l,r;
scanf("%d %d",&l,&r);
G[l].push_back(r);
}
Build(1,0,n);
MIN(0,0,0);
for(int i=1;i<=n;i++)
{
for(auto x:G[i])MIN(x,x,QRY(0,x-1));
//a[i]=0
if(w[i]==1)ADD(0,i-1,1);
//a[i]=1
if(w[i]==0)ADD(i,n,1);
}
cout<<QRY(0,n);
return 0;
}
[ARC094F] Normalization
可以发现如果把 \(a,b,c\) 设为 \(0,1,2\)，那么操作不会改变字符串中数字总和 \(\%3\) 意义下的数。
首先特判掉 \(S\) 都是一个字符以及 \(|S|<=3\) 的情况。
那么一个串 \(T\) 可以被得到的必要条件是： \(T\) 中存在一对相邻且相等的位置，且两个序列 \(\%3\) 相等。
猜一下这个也是充分的，事实也确实如此。
因此直接 \(dp\) 就好了。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
const int mod = 998244353;
char s[N];
int n;
int dp[N][3][2][3];
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
bool flag=1,flag2=0;
for(int i=1;i<n;i++)
{
flag&=(s[i]==s[i+1]);
flag2|=(s[i]==s[i+1]);
}
if(flag)
{
printf("1\n");
return 0;
}
if(n==2)
{
cout<<2;
return 0;
}
if(n==3)
{
if(s[1]!=s[2]&&s[2]!=s[3]&&s[1]!=s[3])cout<<3;
else if(s[1]==s[2])cout<<6;
else if(s[2]==s[3])cout<<6;
else cout<<7;
return 0;
}
for(int c=0;c<=2;c++)dp[1][c][0][c]=1;
int w=0;
for(int i=1;i<=n;i++)w=(w+s[i]-'a')%3;
for(int i=2;i<=n;i++)
{
for(int v=0;v<=2;v++)
for(int c=0;c<=1;c++)
for(int a=0;a<=2;a++)
if(dp[i-1][v][c][a])
{
for(int b=0;b<=2;b++)
dp[i][(v+b)%3][c|(a==b)][b]=(dp[i][(v+b)%3][c|(a==b)][b]+dp[i-1][v][c][a])%mod;
}
}
int ans=0;
for(int c=0;c<=2;c++)ans=(ans+dp[n][w][1][c])%mod;
cout<<(ans+1-flag2)%mod;
return 0;
}
[ARC082F] Sandglass
设 \(f_{a}(t)\) 为初始值为 \(a\) 的情况下，时间 \(t\) 时的值。
那么整个图像就是一条折线，碰到 \(y=0\) 和 \(y=X\) 就会顶着，而遇到 \(x=r_i\) 就会改变斜率。
容易发现对于 \(0\leq a\leq b\leq X,t\in Z,f_a(t)\leq f_b(t)\) 。
同时，如果在某一时刻 \(t\)，\(f_a(t)=f_0(t)\) 或者 \(f_a(t)=f_X(t)\)，那么之后，\(f_a(t)\) 就会一直和 \(f_0(t)\) 或 \(f_X(t)\) 相等，而如果从来没有，那么说明\(f_a(t)\)一直没有触碰上下界，因此当前位置可以直接求出，设为 \(x\)。
那么如果 \(x<f_0(t)\)，最终就是 \(f_0(t)\)，如果 \(>f_X(t)\)，最终就是 \(f_X(t)\)，否则就是 \(x\) 。
复杂度 \(O(n+m)\)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
typedef long long LL;
LL X,O,n,q,fo,fx,f,p[N];
int main()
{
scanf("%lld",&X);
cin>>n;
for(int i=1;i<=n;i++)scanf("%lld",&p[i]);
fo=O;fx=X;f=0;
int now=0;
cin>>q;
while(q--)
{
LL t,a;
scanf("%lld %lld",&t,&a);
while(now+1<=n&&p[now+1]<=t)
{
if(now&1)
{
fx=min(X,fx+p[now+1]-p[now]);
fo=min(X,fo+p[now+1]-p[now]);
f+=p[now+1]-p[now];
}
else
{
fx=max(O,fx-p[now+1]+p[now]);
fo=max(O,fo-p[now+1]+p[now]);
f-=p[now+1]-p[now];
}
now++;
}
LL Fx=0,Fo=0,Fa=0;
if(now&1)
{
Fx=min(X,fx+t-p[now]);
Fo=min(X,fo+t-p[now]);
Fa=f+t-p[now];
}
else
{
Fx=max(O,fx-t+p[now]);
Fo=max(O,fo-t+p[now]);
Fa=f-t+p[now];
}
Fa+=a;
Fa=min(Fa,Fx);
Fa=max(Fa,Fo);
printf("%lld\n",Fa);
}
return 0;
}