CSP-S 备战所有题题解(week 1)

sLMxf · 2024-10-08 14:45:13 · 个人记录

或许更慢但更好的阅读体验？

Day1

主要复习：线段树、树状数组（？）、分块、主席树

AT_abc339_e [ABC339E] Smooth Subsequence

一道线段树板子题。首先可以写出下面的 DP 代码：

for(int i=1;i<=n;i++)
    for(int j=1;j<i;j++)
        if(abs(a[i]-a[j])<=d)
            dp[i]=max(dp[i],dp[j]+1);

初始化：dp_i=1。因为每个数可以单独成一段。

由于能转移到 i 的 j 一定满足 (i-d\le j\le i+d)。我们不妨设 dp_i 表示最后一个选 \mathbf i 的最优解。那么就有如下 DP 方程：

显然中间这一段可以用线段树维护。

核心代码：

for(int i=1;i<=N;i++)
{
    int num=dp.query(max(1ll,a[i]-d),min(500000ll,a[i]+d))+1;
    dp.update(a[i],a[i],num);
    ans=max(num,ans);
}

知识点：线段树，DP

AT_abc339_g [ABC339G] Smaller Sum

分块板板题。

看到这道题，就知道这是一道板板分块了。先分成每块长 S。分下列几种情况讨论：

• - 散块：暴力！此时时间复杂度 $O(S)$。 - 中间的块：可以考虑先将每一块排序，二分+前缀和出答案。此时时间复杂度 $O\left(\dfrac{n}{S}\times \log S\right)

预处理：要将这 \dfrac{n}{S} 块排序，时间复杂度 O\left(\dfrac{n}{S}S\log S\right)=O(n\log S)。

可以发现，其实重头在查询整块，如果令 S=\sqrt{n}，直接 O(q\sqrt n\log \sqrt n)，很容易就炸掉了（别问我怎么知道的）。

因为 q=2\times 10^5，考虑 S=2\times 10^3 就能很轻松过掉了。

signed main()
{
    int n=read(),tot=0;
    int kc=2000;
    for(int i=1;i<=n;i++)
    {
            a[i]=read();
            id[i]=(i-1+kc)/kc;
            if(id[i]!=id[i-1]) L[i]=i,LLL[++tot]=i;
            else L[i]=L[i-1];
    }
    L[n+1]=n+1;LLL[tot+1]=n+1;
    for(int i=1;i<=tot;i++)
    {
            for(int j=LLL[i];j<LLL[i+1];j++)
                w[j]=a[j];
            sort(w+LLL[i],w+LLL[i+1]);
            for(int j=LLL[i];j<LLL[i+1];j++) sum[j]=sum[j-1]+w[j];
    }
    int q;
    long long lastans=0;
    for(cin>>q;q--;)
    {
            long long l=read(),r=read(),k=read();
            l^=lastans,r^=lastans,k^=lastans;
            lastans=0;
            if(id[l]==id[r])
            {
                for(int i=l;i<=r;i++) lastans+=(a[i]<=k)*a[i];
                write(lastans);puts("");
                continue;
            }
            for(int i=l;id[i]==id[l];i++) lastans+=(a[i]<=k)*a[i];
            for(int i=r;id[i]==id[r];i--) lastans+=(a[i]<=k)*a[i];
            for(int i=id[l]+1;i<id[r];i++)
            {
            auto K=upper_bound(w+LLL[i],w+LLL[i+1],k)-w;
            lastans+=sum[K-1]-sum[LLL[i]-1];
            }
            write(lastans);puts("");
    }
    return 0;
}

知识点：分块（其实也可以主席树）

AT_abc350_f [ABC350F] Transpose

一眼板板题！

先大小写转化、括号匹配，无需多盐。

接着 dfs。显然每次碰到括号就 dfs 一次即可。

void dfs(int l,int r,bool pf)
{
    if(pf)
    {
        for(int i=l;i<=r;i++)
        {
          if(s[i]=='(')
          {
              dfs(i+1,dy[i]-1,pf^1);
              i=dy[i];
          }
          else
              cout<<s[i];
        }
    }
    else
    {
        for(int i=r;i>=l;i--)
        {
            if(s[i]==')')
            {
                dfs(dy[i]+1,i-1,pf^1);
                i=dy[i];
            }
            else
                cout<<s[i];
        }
    }
}

知识点：搜索，栈。

后记：经过 lihongqian__int128 神犇提醒，我才知道这题正解应该是线段树。对于一次转换，位置 i 会被转换到 l+r-i，其中 l,r 是左右括号的坐标。这个操作相当于一个先乘 -1，再加上 l+r 的操作。线段树维护。

AT_abc350_g [ABC350G] Mediator

看起来是一道很难的题，但是暴力过了。

但思考一下会发现也不太好卡。

• 预处理：预处理 f_i，f_{i,j} 表示 i\to j 是否有边。这样的时间复杂度其实是 2\times 度数，接近 O(n)。
• 修改：O(1) 一次。这个操作估计会执行 n-1 次。（这样才能让查询效果最大化）
• 查询：O(S_{v_i}+S_{u_i}) 一次。

发现了一件可悲的事情：时间复杂度接近 O(nq)。但是暴力跑不满。如果要跑满，可以用记忆化水掉。这样最多跑到 O\left(\dfrac{1}{2}nq\right)。加上三秒时限，加上 ATC 神机...

Day 2 刷题

P5903 【模板】树上 K 级祖先

顾名思义，求树上 K 级祖先的算法叫做树上 K 级祖先。

考虑每一次查询等价于 x 往上跳 k 次，正常时间复杂度是 O(qn) 的。怎么优化这个过程呢？一看就可以用倍增。预处理 x 的 2^p 祖先，二进制拆分即可。

树上 K 级祖先的时间复杂度：预处理 O(n\log n)，每次查询 O(\log n)。

void logg()
{
    Log2[0]=Log2[1]=0;
    for(int i=2;i<=500000;i++)
        Log2[i]=Log2[i/2]+1;
}
void dfs(int x,int father)
{
    depth[x]=depth[father]+1;
    for(int i=1;i<=Log2[depth[x]];i++)
        fa[x][i]=fa[fa[x][i-1]][i-1];//2^i=2^i-1+2^i-1
    for(int i=0;i<G[x].size();i++)
        if(G[x][i]!=father) dfs(G[x][i],x);
}
int KZX(int x,int k)
{
    int f=0;
    while(k)
    {
        if(k%2) x=fa[x][f];
        f++,k/=2;
    }
    return x;
}

P2396 yyy loves Maths VII

备注：记 l(i)=\text{lowbit}(i)。lowbit(i) <=> (i&(-i))；将 a\operatorname{xor} b 写作 a\oplus b。

话说那个让 yyy 写程序的那个人怎么能算，怎么没见他去算呢。手捏 24！

虽然 24! 做不了，但是 2^{24} 还是绰绰有余的。定义状态 s 的第 i 位等于 1 是，表示使用这张卡片。否则不使用。

那 s 的距离怎么算呢？显然等于 dis_s=dis_{l(s)}+dis_{s\oplus l(s)}。

如果 dis_s 是一个厄运数字，那么就不需要计算了，否则考虑进行 DP。

方程很显然：对于每一位为 1 的卡片，考虑不拿这张卡片后再拿这张卡片。即 dp_s 一定可以从 dp_{s\oplus (2^i)}(s_i=1) 转移过来。也就是：

其中 w 为位数。

初始化？dis_{2^i}=a_i，dp_0=1（什么都不选也是一种方案）。

void dp(int x)
{
    for(int i=x,j;i;i^=j)
        j=lowbit(i),(f[x]+=f[x^j])%=mod;
}

Day 2 考试

T1

简述题意：求一个数 n，使得 k 不是 n 的倍数，k^2 是 n 的倍数。

不愧是签到题。容易想到如果 n=\prod {p_i}^{e_i}，则 k=\prod {p_i}^{\left\lfloor \dfrac{e_i}{2}\right\rfloor}。验证一下即可。

T2

简述题意：有两种操作，操作 1 使得 a_i 加上 1，代价 x；操作 2 使得 a_i 减去 1，代价 b。对于所有的 k\in[1,n]，使 a_1\sim a_k 全部相等的最小代价是多少。

容易想到，最后所有 a_i 变成的值一定会 a_1\sim a_k 的一个值（这个值成为阈值）。再一想，按 a_i 排序，k 的阈值最多与 k-1 的阈值差一位。bound 一下即可。

T3

简述题意：把一个数加上 x 的代价为 x^2+c。求把 1\sim n 这 n 个数进行若干次操作后，使所有数大于等于 k 的最小代价。c\le 10^4，数据随机生成。

定义 dp_i 表示将一个数加上 i 的最优解。打表后发现，dp_i 有下面性质。

性质 1 告诉我们，a_i 变为 k 的最小价值一定是加 k-a_i；性质 2 告诉我们，对于前 c 个数，可以暴力算，后面的数，按循环节来算。

由于数据随机生成，这种算法几乎卡不掉。

T4

简述题意：定义一条路径的价值为 2^d，其中 d 是路径上边的数量，求经过 x,y 的所有路径价值和。

显然可以先预处理 x 的子树（y为根）、y 的子树（x为根），x 到 y 的路径的价值。相同的加在一起，最后相乘。前两个换根/预处理，最后一个 LCA。

Day 3

CF915E Physical Education Lessons

动态开点板子题。

如果你需要维护一个 [1,10^9] 的区间，你或许会掏出离散化。但如果它强制在线呢？动态开点！ \ \ 动态开点的宗旨是：要用什么点就建立什么节点。以前来说，u 的两个儿子是 2u 和 2u+1，但现在变成了 ls,rs。\ \ 由于每次操作的时间复杂度是 O(\log n)，每次操作就可能创建 O(\log n) 级别的点。操作 m 次后，也只会创造 O(m\log n) 个节点。时间复杂度同样还是 O(\log n) 一次。

by sLMxf

知识点 get！

CF208E Blood Cousins

首先把这颗树拍平成一个序列。这里的 P 级表祖一定是 v 的 K 级祖先。所以先求出 v 的 p 级祖先。

那么现在的问题就变成了这样：给定一个序列，求区间 [l,r] 中有多少个值等于 k。

好像没什么好用的数据结构？那就分块启动！

AT_abc180_f [ABC180F] Unbranched

构式数学题。一个一个条件分析。

• 没有自环：好像只要正经点，这条件其实没什么用。
• 点的度数不超过 2：手玩一下就能发现最后这张图只会有一堆链和环构成。
• 连通块最大个数等于 L：考虑 DP。因为等于 L 太难受了，所以考虑统计不超过 L，因为这样就能变成 ans(L)-ans(L-1) 了，非常爽！

考虑一下怎么 DP。定义状态：

表示选 i 个点，j 条边。

问题是转移方程怎么写？由于每个连通块只能是链或环，考虑一下分类讨论。

在分讨之前，我们先讨论链、环的可能数。

• 链：假设这条链长度为 k
• 环：假设这个环长度为 k(k>1)。

定义：

即链与环的方案数函数。

考虑除了枚举 i(i\le n),j(j\le m)，再枚举一个 k(k\le L)，分讨 k 对答案的贡献。其中 k 相当于代表 L 那一位。

• 如果这 k 个结点构成的是链。
  这 k 个节点使用了 k-1 条边，其他的 i-k 个节点使用了 j-k+1 条边，也就是状态 dp_{i-k,j-k+1}。选 k 个节点的方案数为剩下的 n-i+k-1 个点中选 k-1 个点，方案数为 \dbinom{n-i+k-1}{k-1}，贡献为 l(k)。所以总的贡献为： \sum _{k=1}^L dp_{i-k,j-k+1}\times \dbinom{n-i+k-1}{k-1}\times l(k)
• 如果这 k 个结点构成的是环。 同链，总贡献为： \sum _{k=1}^L dp_{i-k,j-k}\times \dbinom{n-i+k-1}{k-1}\times h(k)

初始化 dp_{0,0}=1，一个点、一条边都不选是一种方案。

然后这题套个逆元就做完了。

for(int i=1;i<=n;i++)
    for(int j=0;j<=m;j++)
    {
        for(int k=1;k<=min(l,min(i,j+1));k++)
            dp[i][j]=(dp[i][j]+dp[i-k][j-k+1]*C(n-i+k-1,k-1)%mod*l(k)%mod)%mod;
        for(int k=2;k<=min(l,min(i,j));k++)
            dp[i][j]=(dp[i][j]+dp[i-k][j-k]*C(n-i+k-1,k-1)%mod*h(k)%mod)%mod;
    }

Day 4 考试

T1 扑克牌

如果能配出 p 副牌，则一定能配出 p-1 副牌；如果不能配出 p 副牌，则一定不能配出 p+1 副牌。所以答案具有单调性。

设答案为 ans，考虑答案：

1 2 3 4 ... k ... n  -- 1
1 2 3 4 ... k ... n  -- 2
J 2 3 4 ... k ... n  -- 3
J 2 3 4 ... k ... n  -- 4
1 J 3 4 ... k ... n  -- 5
1 2 J 4 ... k ... n  -- 6
. . . . ... . ... n  .. .
. . . . ... . ... n  .. .
. . . . ... . ... n  .. .
1 2 3 4 ... J ... n  -- ans

则第 i 种牌要用 \max\{ans-a_i,0\} 张 J 来配。记

则 g(ans)\le ans。所以 g(ans)\le m 且 g(ans)\le ans。贪心+二分即可。

T2 T3

石堆没讲

T4 San

这么小的范围，折半搜索即可。

Day 5 考试

CSP-J 模拟，不属于 CSP-S 范围，不讲了。

Day 5 刷题

CF383C Propagating tree

定义 dep_i 为节点 i 的深度。对于深度为奇数的节点，对权值的贡献为正。对于深度为偶数的节点，对权值的贡献为负。

最后统计答案时，乘上自己对权值的贡献即可。

至于操作：拍成 DFS 序，树状数组维护即可。

喵喵喵，没了。

while(m--)
{
  int op,x,Val;
  cin>>op>>x;
  if(op==1)
  {
    cin>>Val;
    add(dfn[x],dep[x]*Val); 
    add(r[x]+1,-dep[x]*Val);
  }
  else
  {
    cout<<dep[x]*sum(dfn[x])+val[x]<<endl;
  }
}

Day 6 刷题

CF1439C Greedy Shopping

一道很水的题。

操作 1 水水就过去了。

操作 2 ，我们发现要卡暴力最好的办法是这样的：

但是这样会有一个性质：每一次 y 至多会变成 \dfrac{y}{2}。所以这样的时间复杂度是 O(\log y) 的。

考虑线段树二分，这样时间复杂度 O(q\log n\log y)，就这样水过去了！！！

int query(int l,int u=1,int L=1,int R=n)
{
    if(l<=L&&R<=n)
    {
        if(a.w[u]<=y)
        {
            y-=a.query(L,R);
            return R-L+1;
        }
        else if(a.W[u]>y)
        {
            return 0;
        }
    }
    if(a.lzy[u]) a.pushdown(u,L,R);
    int ans=0;
    int mid=(L+R)>>1;
    if(l<=mid)  ans+=query(l,u*2,L,mid);
    if(mid+1<=n)  ans+=query(l,u*2+1,mid+1,R);
    return ans;
}

Week 1 到此结束