CSP2019题解

· · 个人记录

咕咕咕……

这是一个从考完到现在都没去听讲评和看题解的屑 (

质量比NOIP2018高多了,成功区分了我这种划水选手。

诶不对,CSP和NOIP没有关系!

D1T1 P5657 格雷码

太难了不会做,莫得。

看来赛后AK是不可能的了。

D1T2 P5658 括号树

一眼看成本质不同括号串,xswl (

先来解决一条链的情况。

我们可以逐个加入括号,对每个右端点考虑有多少个合法的串。

不妨先不考虑限制②,现在就是要计数有多少个和为0的子串。

维护 o[x] 表示目前和为 x 的前缀个数,考虑 push_back 一个括号的影响。

答案就是每次 push_back 操作后 o[0] 的和。

接下来考虑限制②,不难发现相当于 : 每次把和为负数的后缀去掉,令其不能贡献。

相当于这样的一个赋值操作 : o[-\inf,0)=0 ,事实上我们可以直接忽略负下标的 o。

不难发现,只需要注意 o[x-1]\leftarrow o_*[x] 的时候 o[-1] 不能继承 o[0] ,手动清 0 就行了。

对于数组的整体位移,可以使用指针(一个变量)来记录,也就是记录 o[0] 在哪个位置。不移动信息,反而考虑下次信息加入位置的偏移量。

我们现在已经得到了一个针对链的 O(n) 解法。

接下来上树。

仍然可以考虑依次加入括号,麻烦的是同一个状态可能有多个后代。

维护一个可回退化数组就好了,按照dfs序执行,回溯时撤回操作还原状态。

操作中只有赋值,拿个变量记录一下即可。

#include<algorithm>
#include<cstdio>
#include<vector>
#define ll long long
#define MaxN 500500
using namespace std;
int read(){
  int X=0;char ch=0;
  while(ch<48||ch>57)ch=getchar();
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return X;
}
vector<int> g[MaxN];
int n,tp,c[MaxN];
char s[MaxN];
ll ans;
void dfs(int u,ll sum)
{
  int sav;
  if (s[u]=='(')c[tp--]++;
  else {sav=c[tp];c[tp++]=0;sum+=c[tp];}
  ans^=(sum*u);
  for (int i=0;i<g[u].size();i++)
    dfs(g[u][i],sum);
  if (s[u]=='(')c[++tp]--;
  else {
    sum-=c[tp];
    c[--tp]=sav;
  }  
}
int main()
{
  scanf("%d%s",&n,s+1);
  for (int i=2;i<=n;i++)
    g[read()].push_back(i);
  dfs(1,0);
  printf("%lld",ans);
  return 0;
}

写了5min就1A了,不明白考场上为啥白给40min,= =

D1T3 P5659 树上的数

注意,边必须全部删掉。 (考场没看到的屑直接白给2h)

看到字典序,首先想到按位贪心。

接着,我们逐位枚举该填啥,然后就得到了若干关于边顺序的约束。

注意“顺序连续”并不能直接转化成偏序,需要做一番分析。

考虑已经确定了若干条移动路径,如何判定新的一条路径是否可行。

点上旧的限制无非三种情况 : 钦定最先的边,钦定最后的边,某些边连续。

首先,查看 u 点最先的边是否已经被钦定。

然后,对于中间结点,我们会遇见一些“成块”的约束,如果需要的两条边在一个块内,则看看他们是否相邻; 如果不在,则看看是否是一首一尾,把它们拼起来。

最后查看 v 点最后的边是否已经被钦定。

我们一共会枚举 O(n^2) 种可能的移动路径,并确定 O(n) 条。

对于每条路径,需要 O(n) 的复杂度来判断是否合法。合法后,将其加入限制中,容易使用加权并查集大力维护。

具体来讲,就是 P2342 [USACO04OPEN]Cube Stacking G。对于钦定首尾,可以建立两个虚点来维护,细节较少。

复杂度是 O(n^3) ,瓶颈在于判定一条路径是否合法。

观察我们每次需要判定的一组 n 个路径,不难发现终点都在需要填写的点,直接从 v 开始dfs即可 O(n) 判定。

注意到并查集维护的总点数是 O(n) 的,所以最多产生 O(n) 个合并操作。

同时有 O(m=n^2) 个询问,那么路径压缩的加权并查集的复杂度就是 O(m\log_{m/n}n)=O(n^2)。

总的复杂度也就是 O(n^2) 的。

#include<algorithm>
#include<cstdio>
#include<vector>
#define pb push_back
#define MaxN 2050
using namespace std;
int _f[MaxN<<2],_l[MaxN<<2],_c[MaxN<<2],*tf,*tl,*tc;
struct UFS{
  int *f,*l,*c,m;
  void Init(){
    for (int i=0;i<=m;i++)
      {l[f[i]=i]=0;c[i]=1;}
  }
  int findf(int u,int &c){
    if (f[u]==u)return u;
    f[u]=findf(f[u],c);
    c+=l[u];l[u]=c;
    return f[u];
  }
  void merge(int x,int y){
    int len=1;x=findf(x,len);
    c[f[y]=x]+=c[y];l[y]=len;
  }
}T[MaxN];
int n;
vector<int> g[MaxN],b[MaxN];
void adl(int f,int t){
  g[f].pb(t);b[f].pb(g[t].size());
  g[t].pb(f);b[t].pb(g[f].size()-1);
}
int mx,tp,x[MaxN],pl[MaxN],fa[MaxN];
bool vis[MaxN];
void dfs(int u,int fl)
{
  pl[u]=fl;
  int c1=0,f1=T[u].findf(fl,c1);
  for (int i=1,v,tc;i<g[u].size();i++){
    if (i==fl)continue;
    int c2=0,f2=T[u].findf(i,c2);
    v=g[u][i];
    if (c1==T[u].c[f1]-1){
      int c3=0;//拼接两个散块 
      if (f1==f2||c2||
        (f1==0&&T[u].c[f1]+T[u].c[f2]<=g[u].size()&&f2==T[u].findf(g[u].size(),c3))
      )continue;//可能头尾与两个边界相连,黏住了 
    }else {//本就在一块中 
      if (f1!=f2||c1+1!=c2)continue;
    }
    if (!vis[v=g[u][i]]){
      int cv=0,fv=T[v].findf(b[u][i],cv);
      //是否能最后 
      if ((cv==T[v].c[fv]-1&&(fv!=0||T[v].c[fv]>=g[v].size()))&&x[v]<mx)
        {mx=x[v];tp=v;}
    }
    fa[v]=u;
    dfs(v,b[u][i]);
  }
}
int id[MaxN];
void solve()
{
  tf=_f;tl=_l;tc=_c;
  scanf("%d",&n);
  for (int i=1;i<=n;i++){
    scanf("%d",&x[i]);
    id[x[i]]=i;
  }if (n==1){puts("1");return ;}
  for (int i=1;i<=n;i++){
    g[i].clear();g[i].pb(0);
    b[i].clear();b[i].pb(0);
    vis[i]=0;
  }
  for (int i=1,f,t;i<n;i++){
    scanf("%d%d",&f,&t);
    adl(id[f],id[t]);
  }
  for (int i=1;i<=n;i++){
    T[i].m=g[i].size()+1;
    T[i].f=tf;tf+=T[i].m;
    T[i].l=tl;tl+=T[i].m;
    T[i].c=tc;tc+=T[i].m;
    T[i].Init();
  }
  for (int u=1;u<=n;u++){
    mx=n+1;dfs(u,0);
    vis[tp]=1;
    printf("%d ",mx);
    if (mx>n)exit(0);
    T[tp].merge(pl[tp],g[tp].size());
    int v=tp;
    while(v!=u){
      int p=fa[v];
      T[p].merge(pl[p],b[v][pl[v]]);
      v=p;
    }
  }puts("");
}
int main()
{
  int T;scanf("%d",&T);
  while(T--)solve();
  return 0;
}

吐槽这个输入格式,题意看错结果dfs考虑路径的方向是反的,几乎重写了一遍 /kk

D2T1 P5664 Emiya 家今天的饭

先考虑前两条限制,等价于 : 在 a[i][\_] 中最多只能选取一个位置,且不能选出空集。

接着考虑最后一条限制 : 在 a[\_][j] 中选择的位置不能过半。

对于一种方案,权值是对应位置 a 的乘积,求所有合法方案的权值和。

对最后一条限制容斥,设 F(k) 为钦定 k 种食材过半,其余随意的方案数。

然后二项式反……欸等等,怎么可能有两种食材同时过半啊? 我们直接拿所有合法方案减去有任意一个食材过半的方案即可。

先钦定是那个食材过半了,然后使用计数DP。我们称使用钦定的食材做的菜为A菜,反之为B菜。

设 dp[i][j][k] 为考虑了前 i 种烹饪方式,做了 j A菜,做了 k 道B菜的方案数。

设 s[i] 为使用第 i 种烹饪方式做任意一道B菜的方案数, p[i] 为使用第 i 种烹饪方式做A菜的方案数。

对于每种烹饪方式,可以选择做一道A,或者一道B,也可以选择不做,不难写出转移方程:

dp[i][j][k]=dp[i-1][j][k]+p[i]*dp[i-1][j-1][k]+s[i]*dp[i-1][j][k-1]

最终取出 dp[n][j][k] 中 j>k 的部分即为答案。

总状态量是 O(n^2m) ,转移 O(1)。一次DP的复杂度是 O(n2m) 的,共 n 次即为 O(n^3m) 的。

考虑优化,由于我们最后只需要保留 k>j 这一个特征,不妨给A菜赋权 1 ,给B菜赋权 -1。

改设 dp[i][j] 为考虑了前 i 种烹饪方式,菜的权值和为 j 的方案数。(注意, j 可能是负数)

不难发现,最终取出 dp[n][j] 中 j>0 的部分即为答案。

转移方程:

dp[i][j]=dp[i-1][j]+p[i]*dp[i-1][j-1]+s[i]*dp[i-1][j+1]

这样一次DP的复杂度就是 O(nm) ,总复杂度即为 O(n^2m)。

注意最后要减去空集。

#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 105
#define MaxM 2050
using namespace std;
const int mod=998244353;
int read(){
  int X=0;char ch=0;
  while(ch<48||ch>57)ch=getchar();
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return X;
}
int n,m,a[MaxN][MaxM];
ll s[MaxM],f[MaxN][MaxN<<1];
int main()
{
  n=read();m=read();
  for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++){
      a[i][j]=read();
      s[i]+=a[i][j];
    }
  ll ans=1;
  for (int i=1;i<=n;i++){
    s[i]%=mod;
    ans=ans*(s[i]+1)%mod;
  }
  for (int k=1;k<=m;k++){
    f[0][n]=1;
    for (int i=1;i<=n;i++)
      for (int j=1;j<=n+n;j++)
        f[i][j]=(f[i-1][j]+f[i-1][j-1]*a[i][k]+f[i-1][j+1]*(s[i]-a[i][k]))%mod;
    ll sum=0;
    for (int j=n+1;j<=n+n;j++)
      sum+=f[n][j];
    ans=(ans-sum)%mod;
  }printf("%lld",(ans+mod-1)%mod);
  return 0;
}

D2T2 P5665 划分

由于平方是凸函数,肯定要分得尽量“碎”才是最优的。

注意到要求段大小递增,那么最后一段就控制了所有段大小的上界。

猜想最后一段最短的方案总是最优的,尝试归纳证明。

若前 n 个位置内结论成立,新加入一个位置,考虑怎样转移。

不难发现,最后一段最短的方案在向后转移上的约束最少,而其又是最优的,所以最优的转移一定是“最后一段最短”再加一段。

容易理解,随着位置的增多,代价总和是单调不降的。

转移点从左向右移动时,分出的段会逐渐变短,而转移结尾处的最后一段会逐渐变长,在某处超过分出的段,后面的转移都不合法。

所以,合法的转移位置是一个前缀。最靠后的转移位置能够使得最后一段最短,现在我们就是要证明这同时是最优的。

假设有两个转移位置 u,v (u<v) 要向 t 转移,设其最后一段长度分别为 d[u],d[v] , 代价总和分别为 f[u],f[v]。

有 f[u]\leq f[v] ,但不一定有 d[u]\leq d[v]。

对于 f ,一种构造能给出更紧凑的界 : 从 u 结尾的方案直接将最后一段延伸到 v ,可得费用为

f[u]-d[u]^2+(v-u+d[u])^2=f[u]+(v-u)^2+2(v-u)d[u]

那么就能得到

f[v]\leq f[u]+(v-u)^2+2(v-u)d[u]

接着,分别考虑两种转移的代价

u\rightarrow t=f[u]+(t-u)^2 v\rightarrow t=f[v]+(t-v)^2

欲证 f[v]+(t-v)^2\leq f[u]+(t-u)^2

使用前面那个不等式右侧替换 f[v]。

f[u]+(v-u)^2+2(v-u)d[u]+(t-v)^2\leq f[u]+(t-u)^2

拆开并对消整理

2v^2-2vt-2vu+2(v-u)d[u]\leq -2ut

注意到 d[u]\leq t-u ,替换一下。

2v^2-2vt-2vu+2(v-u)(t-u)\leq -2ut

全部拆开

2v^2-2vt-2vu-uv+vt+u^2-ut\leq -2ut 2v^2+u^2+ut\leq 3vu+vt

对消,移项整理

u^2-3vu+2v^2\leq vt-ut

因式分解得

(2v-u)(v-u)\leq (v-u)t 2v-u\leq t

现在已经证明了,若上式成立,则结论成立。

接下来考虑上式不成立的情况, 2v-u>t, 即 2v-t>u。

注意到 d[v]\leq t-v ,所以 v-d[v]\geq 2v-t>u ,即 d[v]\leq u-v

这样能够给出 f[v] 更紧的界 : 直接从 u\rightarrow v 转移

f[v]\leq f[u]+(v-u)^2

带入到前面的式子中。

f[u]+(v-u)^2+(t-v)^2\leq f[u]+(t-u)^2 (t-v)^2+(v-u)^2\leq (t-u)^2

注意到 u\leq v\leq t,(t-v)+(v-u)=(t-u) ,显然成立。

证毕。

前面的证明过程已经指出了求答案的方法 : 每次找到能够转移的最靠后的位置。

( 其实保证大部分答案不超过 4\times10^{18} 也暗示了有一种不直接依赖代价比较的策略存在…… )

前面已经发现了一些单调的性质,拿单调队列维护 d 就可以了。

然后还要压位高精和抄写题面中的Gen,给出题人点赞(选手的肯定)!

P5666 树的重心

之前已经做过了 : 题解 P5666 【树的重心】