CSP提高组45题

其他

---

2020.10.14

第一天。

• CF696C PLEASE *

题意：$3$个杯子，$m$个回合，每一次等概率将中间的杯子与左/右杯子交换，求中间的杯子在中间的概率，需要约分。

数学题，推柿子+快速幂。

定义$1$为有钥匙的杯子，$0$为没有钥匙的杯子，那么共有$100,010,001$三种状态，满足题意的状态为$010$。

画出树状图可以知道所有状态都可以变为$2$种状态，且$010$不能变为$010$，$100,001$可以变为$010$。

设第$n$次操作$010$的情况数为$f_n$，那么非$010$的数量为$2^n-f_n$，且只有非$010$有贡献，故$f_{n+1}=2^n-f_n$。

设$n$次操作后的答案为$g_n$，那么$g_n=\frac{f_n}{2^n}=\frac{2^{n-1}-f_{n-1}}{2^n}=\frac{2^{n-1}-g_{n-1}\cdot 2^{n-1}}{2^n}=\frac{1-g_{n-1}}{2}$。

那么有$-\frac{1}{2}(ans_n-\frac{1}{3})=ans_{n+1}-\frac{1}{3}$。

设$a_n=g_n-\frac{1}{3}$，那么$a_n=-\frac{1}{2}a_{n-1}$，且$a_1=-\frac{1}{3}$。

那么有$a_n=(-\frac{1}{3})\cdot (-\frac{1}{2})^{n-1}$。

然后有$g_n=a_n+\frac{1}{3}=(-\frac{1}{3})\cdot (-\frac{1}{2})^{n-1}+\frac{1}{3}$。

当$n$为奇数时，$g_n=\frac{2^{n-1}-1}{2^{n-1}\times 3}$，因为$n-1$为偶数，所以$2^{n-1}=4^{\frac{n-1}{2}}\equiv1\pmod 3$，所以$\gcd(2^{n-1}-1,2^{n-1}\times 3)=3$，所以可以进行一次约分，而且因为$2^{n-1}-1$不是偶数，所以$\gcd(\frac{2^{n-1}-1}{3},2^{n-1})=1$。

当$n$为偶数时，$g_n=\frac{2^{n-1}+1}{2^{n+1}\cdot 3}$，因为$n-1$为奇数，所以$2^{n-1}=2^{n-2}\cdot 2\equiv 1\cdot 2=2\pmod 3$，所以$\gcd(2^{n-1}+1,2^{n-1}\times 3)=3$，所以还是可以约分，同样的约分到了最简。

因此答案就是：

$$ans=\frac{(2^{n-1}-(-1)^{n-1})/3}{2^{n-1}}$$

可以用费马小定理解决输入时取模问题。

• P1825 [USACO11OPEN]Corn Maze S。

题意很清晰，搜索水题，不解释。

没判墙竟然有$26$分，震惊了。

• UVA1395 苗条的生成树 Slim Span

题意：求生成树中最大边与最小边最小的差值.

水题，把边按权值排序，每一条边往后取，做$m$遍$\text{kruscal}$就$\text{A}$了，记得判$-1$。（加强版为P4234 最小差值生成树，用$\text{lct}$维护最小生成树配合尺取法做到$O(n\log n)$）

• CF865D Buy Low Sell High

题意：给定$n$天的股票价格，每天可以买进一股或卖出一股，也可以什么都不干，求赚的最多钱（可以赊账）。

反悔贪心，考虑$a-b=(c-b)+(a-c)$这个转化，可以同时使用贪心策略（当前股价减最小股价），和反悔策略（当前股价减之前选择贪心过的最小股价），这样可以用堆维护之前的贪心操作进行反悔保证正确性，复杂度$O(n\log n)$。

for(int i=1;i<=n;i++){
    int t1,t2;
    scanf("%lld",&a[i]);
    if(!q.empty()&&a[i]+q.top()>0){
        ans+=a[i]+q.top();
        q.pop();
        q.push(-a[i]); 
    }
    q.push(-a[i]);
}

---

2020.10.15

第二天。

• UVA1218 完美的服务 Perfect Service *

题意：给一棵树染黑白，每个白点附近恰好有一个黑点，求最小的黑点数。

树形dp，第一眼看成了没有上司的舞会，最后越想越歪，只好看了题解。

设$f_{x,0},f_{x,1},f_{x,2}$为$x$为服务器，父亲为服务器的客户端，和父亲为客户端的客户端的最少服务器个数，然后直接dp。

$$f_{x,0}=1+\sum_{y\in son(x)} \min\{f_{y,0},f_{y,1}\}\\f_{x,1}=\sum_{y\in son(x)}f_{y,2}\\f_{x,2}=\min_{y\in son(x)}\{f_{y,0}+\sum_{z\in son(x),z\ne y}f_{y,2}\}$$

优化一下$f_{x,2}=\min_{y\in son(x)}\{f_{x,1}-f_{y,2}+f_{y,0}\}$，然后就能做了。

• UVA562 Dividing coins

题意：把一堆硬币分成两堆让两堆硬币差最小。

背包水题，直接把硬币推出一个背包，然后取能组合出的一堆硬币总数$x$中$|sum-2x|$最小的$|sum-2x|$。

• CF366C Dima and Salad *

题意：给定$n$个物品，每个物品有两个权值$a$和$b$，选定若干个物品，让他们$a$之和等于$k$倍$b$之和，且让$a$之和最大。

简单背包题，本来可以想出来的，却看了题解，艹。

假设我们选的物品是$s$集合$s_1\cdots s_k$，我们有$a_{s_1}+a_{s_2}+\cdots+a_{s_k}=k(b_{s_1}+b_{s_2}+\cdots+b_{s_k})$，然后变一下型就是$(a_{s_1}-kb_{s_1})+(a_{s_2}-kb_{s_2})+\cdots+(a_{s_k}-kb_{s_k})=0$。

因此我们考虑每个物品$x$体积为$a_x-kb_x$，价值为$a_x$，然后按照体积的正和负做两个背包，最后合并一下两个背包就好了（注意特判没有选任何物品的情况）。

• P6142 [USACO20FEB]Delegation P

题意：将一棵树分为若干条链，使链长度的最小值最大，求这个最大的最小值。

这道题就是P5021 赛道修建的改版，首先二分这个长度$len$，设每个点$x$可以向上延伸$up_x$的长度，然后每个点将它所有儿子的$up$值加一（加上儿子到父亲的边）放在一个$\text{set}$里，使用贪心的思想，用双指针不断抵消相加大于$len$最小的长度，然后特判一下就可以了，复杂度$O(n\log n)$，细节有点多。

int ok=1;
while(!s.empty()){
    multiset<int>::iterator it=s.lower_bound(lim-(*s.begin()));
    if(it==s.begin())
        it++;
    if(it==s.end()){
        if(x==1||ok==0){
            flg=1;
            break;
        }
        ok=0,up[x]=(*s.begin());
    }
    else s.erase(it);
    s.erase(s.begin());
}

---

2020.10.16

第三天。

• P5851 [USACO19DEC]Greedy Pie Eaters P *

题意：$m$个蛋糕，$n$个互不相同的区间，每个区间有权值$w_i$，可以按照一定的顺序取若干个区间，取每个区间会取走里面所有的蛋糕，只有一个区间里有蛋糕才能取这个区间，求能取的区间$w$之和最大值。

区间dp，有点神，只会$O(n^4)$做法/fad。

设$f_{x,y}$为取$x$到$y$的$w$之和最大值，然后我们有转移$f_{x,y}=\max_{k=x}^y\{f_{x,k}+f_{k+1,y}\}$。

但是我们这种转移不能加入一只牛，我们考虑改进这个转移$f_{x,y}=\max_{k=x}^y\{f_{x,k-1}+maxx_{x,y,k}+f_{k+1},y\}$，其中$maxx_{x,y,k}$代表还剩下蛋糕$i$，选择范围在$[x,y]$内的区间$w$最大是多少。

然后就可以做到$O(n^3)$转移了，细节有亿点多。

for(int i=1;i<=m;i++){
    int w,l,r;
    scanf("%d%d%d",&w,&l,&r);
    for(int j=l;j<=r;j++)
        maxx[l][r][j]=max(maxx[l][r][j],w);
}
for(int k=1;k<=n;k++)
    for(int i=k;i>=1;i--)
        for(int j=k;j<=n;j++){
            if(i>1)
                maxx[i-1][j][k]=max(maxx[i-1][j][k],maxx[i][j][k]);
            if(j<n)
            maxx[i][j+1][k]=max(maxx[i][j+1][k],maxx[i][j][k]);
        }
for(int i=1;i<=n;i++)
    f[i][i]=maxx[i][i][i];
for(int len=2;len<=n;len++)
for(int i=1;i+len-1<=n;i++){
    int j=i+len-1;
    for(int k=i;k<=j;k++)
        f[i][j]=max(f[i][j],f[i][k-1]+maxx[i][j][k]+f[k+1][j]);
}

• P3605 [USACO17JAN]Promotion Counting P *

题意：给定一棵以$1$为根的带点权的树，对于每个点，计算它子树中值比它大的点数。

统计题，本来想线段树合并，却发现题解有更简单的$\text{BIT}$做法。

因为$\text{dfs}$中一颗子树的访问一定是连续的，因此进$\text{dfs}$时到出$\text{dfs}$时一定包括且只包括$x$子树中所有的贡献，这样我们减去不属于$x$子树内的贡献（即在访问$x$之前的贡献）就好了。

void dfs(int x,int last){
    ans[x]-=(query(tot)-query(val[x]));
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        dfs(y,x);
    }
    ans[x]+=(query(tot)-query(val[x]));
    update(val[x],1);
}

• CF510B Fox And Two Dots

题意：给定一个颜色矩阵，求里面是否有相同颜色的，长度大于等于$4$的简单回路（即不经过相同结点的回路）。

简单搜索题，对于每个点搜索一遍与它颜色相同的其他点，如果搜回来了就判断长度是否大于等于$4$，因为数据范围很小，所以很容易过。

---

2020.10.17

第四天。

• UVA10827 Maximum sum on a torus

题意：求连续矩阵（可跨越上下左右边界）的最大权值和。

这里举个例子，可以这样选：

√ × × × √
√ × × × √
√ × × × √
× × × × ×
× × × × ×

√ √ × √ √
√ √ × √ √
× × × × ×
√ √ × √ √
√ √ × √ √

首先有一个简化版UVA108 Maximum Sum

先做一遍前缀和，然后枚举所有的矩阵求和最大值。

这道题，我们只需要把矩阵复制$4$份做一遍上面的操作就可以了，记得约束矩阵大小（宽度与高度不能大于$n$），复杂度$O(n^4)$，有一个$16$的大常数，但是可以卡过去。

当然，上面那道简化版有$O(n^3)$做法：设$f_{i,j,k}$代表第$i$行第$j$到$k$个数一直往上扩展，最大的矩阵权值和是多少，然后转移也很方便：$f_{i,j,k}=\max\{f_{i-1,j,k},0\}+val$（设$val$为第$i$行第$j$到第$k$个数的和）。

但这道题要约束矩阵大小，因此不能适用上述做法。

其实这道题也有$O(n^3)$的算法，但是并不想写。

• CF665E Beautiful Subarrays

题意：给定一个长度为$n$的序列$a$，求有多少个子序列的异或和大于等于$k$，序列的异或和为序列中所有数异或起来的结果。

自己想出了做法，鸡冻。

首先根据异或的性质，求出异或的前缀和，把异或和转化为有多少个数对满足异或起来大于等于$k$（其中数对需要在异或前缀和数组中）。

然后我们对异或前缀和数组建一颗$\text{01trie}$，并求出每个点子树中终止点的个数$size_x$（终止点就是$\text{01trie}$插入时最后一个点），查询的时候按位查询。

具体地，我们对于每一位分类讨论，设第$i$位$x$为$y$，第$i$位$k$为$p$（$y,p\in\{0,1\}$），假如我们前$i$位与$k$都相同：

• 如果$p=1$，那么异或起来必须为$1$，直接跳一个$y\oplus p$；
• 如果$p=0$，那么异或起来可以是$1$可以是$0$，不难发现异或起来为$1$的情况一定全部满足答案，因此我们加上跳到$y\oplus 1$的所有情况$size$，并跳一个$y\oplus p$来循环计算异或起来为$0$的贡献。

long long calc(int x,int k){
    int now=root;
    long long res=0;
    for(int i=30;i>=0;i--){
        int y=((x>>i)&1),p=((k>>i)&1);
        if(p==0)
            res+=1ll*size[chd[now][y^1]];
        now=chd[now][y^p];
    }
    res+=size[now];
    return res;
}

但是这样并不行，因为我们提前把$\text{01trie}$建出来了，这样会两个异或起来不能成为一个区间的数的贡献加进答案。

可以边修改边查询，把$\text{insert}$直接改成经过的所有点都增加$size$，在每一次查询前插入上一个前缀和，这样我们可以保证查询的所有贡献都是有效的了。

时间复杂度$O(n\log \max\{k,maxa\})$。

• UVA11021 Tribles *

题意：有一种生物只有一天的寿命，一天后有$p_i$的几率分裂成$i$个相同的生物（$0\leqslant i<n$），求$m$天后$k$个这样的生物死亡的几率（不到$m$天死亡也可以）。

设一个生物前$i$天死亡的几率为$f_i$，那么由乘法原理可得答案为$f_m^k$。

然后考虑如何求$f_i$，考虑一开始一个生物，然后分裂出了$j$个生物，那么由加法原理得$f_i=\sum_{j=0}^{n-1} p_j\cdot f_{i-1}^j$。

直接$O(nm\log k)$递推即可。

• P2886 [USACO07NOV]Cow Relays G

题意：给定一张无向连通图，求起点$s$到终点$t$长度为$n$的最短路。

矩阵快速幂，有亿点细节。

矩阵快速幂解决图上问题是老生常谈了（不会可以点进去看一看），这道题，我们重定义矩阵乘法：若$A\times B=C$，则有$C_{i,j}=\min_{k=1}^n\{A_{i,k}+B_{k,j}\}$。

很容易证明这个矩阵乘法的结合律，即$A\times B=B\times A$。

然后可以直接套上矩阵快速幂的板子。

注意：输入边时顺序是权值，起始点，终止点；在离散化点的标号后记得离散化起点和终点；邻接矩阵不能有$g_{i,i}=0$，而是$g_{i,i}=inf$。

• UVA11361 Investigating Div-Sum Property

题意：求区间$[A,B]$内数字和能被$k$整除且数字可被$k$整除的数数量。

简单数位dp，手打一遍过。

记忆化搜索的时候记几个参数$len,cnt,sum,flg$，当前处理的数位长度，当前数位和模$k$，当前数字模$k$，是否卡位（即前面的数位是否与上限的数位完全契合）。

然后就很容易搜索了，注意$cnt$最大值不会超过$10$倍数位，因此数组可以开小一点，避免MLE。

int dfs(int len,int cnt,int sum,int flg,int k){
    if(len==0)
        return (cnt==0&&sum==0);
    if(vis[len][cnt][sum][flg]==stp)//时间戳标记
        return rec[len][cnt][sum][flg];
    int res=0;
    for(int i=0;i<=9;i++)
        if(flg==0||i<=num[len])
            res+=dfs(len-1,(cnt+i)%k,(sum*10+i)%k,i==num[len]&&flg,k);
    vis[len][cnt][sum][flg]=stp;
    return rec[len][cnt][sum][flg]=res;
}

• P3119 [USACO15JAN]Grass Cownoisseur G

题意：给定一个有向图，求经过$1$，允许最多反向走一次边的最长回路。（路径的长度为路径上点的个数）

毒瘤细节题。

我们首先做一遍$\text{tarjan}$，然后缩个点，建一个新图。

对于每个点用拓扑排序求出它到$1$所在的连通块和$1$所在的连通块到它的最长路径，然后枚举每一条路径来计算这一条路径走反向的答案。

复杂度：$O(n+m)$

ans=size[bel[1]];
for(int i=1;i<=m;i++){
    int x=bel[xx[i]],y=bel[yy[i]];
    if(x==y)
        continue;
    if(ok[x][0]&&ok[y][1])
        ans=max(ans,dis[x][0]+dis[y][1]-size[bel[1]]);
    if(ok[y][0]&&ok[x][1])
        ans=max(ans,dis[y][0]+dis[x][1]-size[bel[1]]);
}

---

2020.10.18

第五天。

• CF875F Royal Questions *

题意：

• $n$个王子，$m$个公主，每个公主有嫁妆$w_i$；
• 王子和公主都只能有一个伴侣，每个公主有两个喜欢的王子（只能挑选喜欢的王子作为伴侣）；
• 作为国王，你要选择王子的伴侣，达到收获的嫁妆最多。
• 数据范围：$2\leqslant n\leqslant 2\times 10^5,1\leqslant m\leqslant 2\times 10^5$。

考虑定义一条有向边$u\rightarrow v$的意义为$u$把公主让给了$v$，那么每个点一定入度为$1$，所有的边会形成一个外向基环树森林。

贪心地把公主按照嫁妆从大到小排序，每个公主看成一条无向边连接两个王子，那么可行的方案一定会形成一个基环树森林。

用并查集维护所有王子组成的基环树，用标记$flg$来记录一个并查集代表的集合为基环树还是树，然后考虑选择一条边的方法：

• 如果合并的两个点属于同一个并查集：
• • 如果这个并查集是一棵树，那么可以选，并标记为基环树；
• • 否则不选。
• 如果合并的两个点不属于一个并查集：
• • 如果合并两棵树，那么可以选，标记为树；
• • 如果合并一棵树，一棵基环树，那么可以选，标记为基环树；
• • 否则不选。

for(int i=1;i<=m;i++){
    int x=find(g[i].x),y=find(g[i].y);
    if(x==y){
        if(flg[x]==0)
            flg[x]=1,ans+=g[i].z;
        continue;
    }
    if(flg[x]+flg[y]<=1){
        f[y]=x,flg[x]=flg[x]+flg[y];
        ans+=g[i].z;
    }
}

• CF1139E Maximize Mex *

题意：

• $n$名学生，$m$个社团，每个学生$i$属于社团$c_i$，能力值为$p_i$；
• 学校有一个为期为$d$天的活动，第$i$天，学生$k_i$会推出社团；
• 定义一个队伍的能力值为所有学生的能力值的$mex$，即所有学生能力值组成的集合中没有出现的最小非负整数；
• 每一天学校都要从各社团选出一个人组成队伍使队伍的能力值最大，求每一天的能力值。
• 数据范围：$1\leqslant n,m\leqslant 5\times 10^3,0\leqslant p_i\leqslant 5\times 10^3$。

考虑将每个社团抽象为一个点，每个能力值抽象为一个点，社团与所有它成员的能力值连边，那么我们可以用匈牙利算法来解决这个$mex$：每一次多取一个能力值，如果可以那么$mex$加一，否则当前$mex$就是最终答案。

可以不断删边（标记每一条边删掉就好了），然后用匈牙利做到$O((maxp\cdot n+m)\cdot d)$，但是仍然无法通过。

考虑将删边转化为加边（时间倒流），然后不难发现$mex$是递增的。

因为$mex$是递增的，所以每一次匈牙利都可以从上一次结束的位置开始，这样我们的复杂度就优化成了$O(maxp\cdot d+maxp\cdot n)$。

for(int i=d;i>=1;i--){
    for(int j=ans;;j++){
        stp++;
        if(dfs(j)==0){
            ans=j;
            break;
        }
    }
    res[i]=ans;
    add(p[k[i]],c[k[i]]);
}

• UVA11481 Arrange the Numbers *

题意：给定$n,m,k$，求$n$个数的排列中前$m$个数恰好有$k$个不是错排的方案数。

• CF319C Kalila and Dimna in the Logging Industry

题意：给定$n$棵树，高度为$a_1$到$a_n$，权值为$b_1$到$b_n$，当一颗树的$a$为$0$时就说它被砍倒了。有一个电锯，每一次砍伐树会让一棵树的高度$-1$，砍伐的费用为当前砍倒的编号的最大的树的$b$，第一次砍伐不需要费用。保证$a_i<a_{i+1},b_i>b_{i+1},a_1=1,b_n=0$，求砍倒所有树的最小费用。

很显然，我们第一次砍的一定是第一棵树，且砍倒最后一棵树以后就不需要任何费用了，这样，题意就转化为如何花费最小的费用砍倒第$n$棵树。

有一个很显然的贪心思想，我们砍树一定从前往后砍（中间可以跳过一些树），因为我们砍这棵树一定无法更新砍树的费用。

设$f_i$为砍倒第$i$棵树的费用，那么可以列出转移方程$f_i=\min_{j=1}^{i-1}\{f_j+b_j\cdot a_i\}$。

这个$O(n^2)$一定无法通过题目，因此需要优化。

考虑斜率优化：设$j,k$两个$i$的决策点满足$k<j<i$，且$j$比$k$更优，那么有：

$$f_j+b_j\cdot a_i\leqslant f_k+b_k\cdot a_i$$

变一下形式：$f_j+b_j\cdot a_i\leqslant f_k+b_k\cdot a_i$$\Rightarrow f_j-f_k\leqslant a_i\cdot(b_k-b_j)$$\Rightarrow \frac{f_j-f_k}{b_k-b_j}\leqslant a_i$$\Rightarrow -\frac{f_j-f_k}{b_j-b_k}\leqslant a_i$$\Rightarrow\frac{f_j-f_k}{b_j-b_k}\geqslant -a_i$。

化成斜率式之后，由于$a$是递增的，因此用单调队列维护一个上凸壳就好了。

时间复杂度：$O(n)$。

• CF739B Alyona and a tree

题意：一棵$n$个节点带点权$a$和边权的树，定义树上距离$dis(u,v)$为$u$到$v$的边权和，定义$u$控制$v$当且仅当$v$在$u$子树中且$dis(u,v)\leqslant a_v$，求每个点能控制多少个点。

很经典的一道题了。

首先把每个点控制的点数转化为每个点能对多少个点产生贡献，然后因为边权非负，我们可以预处理一下边权的前缀和，然后倍增跳祖先到最远可以控制的点就可以了。

用树上差分统计答案就可以了。

void dfs(int x){
    for(int i=1;i<=20;i++)
        fore[x][i]=fore[fore[x][i-1]][i-1];
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        dis[y]=dis[x]+worth[i],fore[y][0]=x;
        dfs(y);
    }
    int y=x;
    ans[fore[x][0]]++;
    for(int i=20;i>=0;i--)
        if(dis[x]-dis[fore[y][i]]<=a[x])
            y=fore[y][i];
    ans[fore[y][0]]--;
}

• P1453 城市环路

题意：给定一棵$n$个点的基环树，每个点有点权。两个相邻的点不能同时选中，选择若干点求最大点权和乘实数$p$的值。

基环树基础练习题。

用一个很显然的基环树套路，切断环上的一条边，对于这一条边的左右端点各做一个P1352 没有上司的舞会，然后求最大值就可以了。

• CF1077F2 Pictures with Kittens (hard version)

题意：给定长度为$n$的数列$a$，选择$m$个元素，使连续的$k$个元素至少有一个被选中，使权值和最大。

设$f_{i,j}$为前$j$个数选择了$i$个数，且满足条件的最大权值和。

很显然有一个转移：$f_{i,j}=\max_{p=j-k}^j\{f_{i-1,p}\}+a_j$，用单调队列可以加速到$O(n\cdot m)$。

f[0][0]=0;
for(int i=1;i<=m;i++){
    l=1,r=0,q[++r]=0;
    for(int j=1;j<=n;j++){
        while(l<=r&&j-q[l]>k)
            l++;
        f[i][j]=f[i-1][q[l]]+a[j];
        while(l<=r&&f[i-1][j]>=f[i-1][q[r]])
            r--; 
        q[++r]=j;
    }
}
for(int i=n-k+1;i<=n;i++)
    ans=max(ans,f[m][i]);

---

2020.10.19

第六天。

• P5837 [USACO19DEC]Milk Pumping G

题意：给定一个由$n$个节点，$m$个管道组成的无向图，每条管道有两个权值$f$和$c$，$f$代表最大流量，$c$代表使用该管道需要的费用，每一条路径上的流量为这条路径上的最小$f$，求如何使用管道使流量与费用之比最小。

数据范围：$2\leqslant n\leqslant1000,1\leqslant m\leqslant 1000,1\leqslant f,c\leqslant 1000$。

可以枚举最大流量$maxf$，然后用把所有流量限制小于$maxf$的边去掉，把花费变成边权作一遍$dijkstra$，得到的花费就是最小的了，最后在所有答案中取一个$\max$就好了。

• CF817D Imbalanced Array

题意：给定一个$n$个元素组成的数组，求所有子数组最大值减去最小值之和。

单调栈板子题，用单调栈维护每个点要成为最大值/最小值，最多可以向左/向右扩展多远，然后算一下贡献就可以了。

代码以求最大值为例：

top=0;
for(int i=1;i<=n;i++){
    while(top>0&&a[i]>=a[stk[top]])
        maxqr[stk[top]]=i-1,top--;
    maxql[i]=stk[top]+1,stk[++top]=i;
}
while(top>0)
    maxqr[stk[top]]=n,top--;

• SP116 INTERVAL - Intervals *

题意：$n$个区间，每个区间为$[a_i,b_i]$，里面至少要取$c_i$个数，求满足条件的情况下最少要取多少个数。

差分约束裸题，可以用$\text{Bellman Ford}$实现。

for(int i=1;i<=m;i++){
    int x,y,z;
    scanf("%d%d%d",&x,&y,&z);
    add(y,x-1,-z);
}
for(int i=1;i<=n;i++)
    add(i-1,i,1),add(i,i-1,0);
if(Bellman_Ford()==0)
    printf("%d\n",dis[n]-dis[0]);

• CF1290C Prefix Enlightenment *

---

2020.10.20

第七天。

• CF1336C Kaavi and Magic Spell *

题意：给定一个字符串$S$和一个字符串$T$，每次可以删掉$S$的第一个字符，然后放到一个初始为空的字符串$A$ 的首部或尾部，求有多少种不同的方法使得最后$T$是$A$的前缀。

区间dp，设$f_{i,j}$为区间$[i,j]$有多少种方法用$s_{1\cdots j-i+1}$拼出$t_{i\cdot j}$，边界为$f_{i,i}=2$（可以放空串的前面或空串的后面）。

转移很显然，对于长度为$len$的区间$[i,j]$：

• 如果$s_{len}=t_i$，那么有$f_{i,j}\leftarrow f_{i+1,j}$；
• 如果$s_{len}=t_j$，那么有$f_{i,j}\leftarrow f_{i,j-1}$。

记得对所有超越边界的转移进行特判。

for(int i=1;i<=n;i++)
    if(a[1]==b[i]||i>m)
        f[i][i]=2;
for(int len=2;len<=n;len++)
    for(int i=1;i+len-1<=n;i++){
        int j=i+len-1;
        if(a[len]==b[i]||i>m)
            f[i][j]=(f[i][j]+f[i+1][j])%mod;
        if(a[len]==b[j]||j>m)
            f[i][j]=(f[i][j]+f[i][j-1])%mod;
    }

• CF1238E Keyboard Purchase *

题意：给定一个长度为$n$的密码，且其由前$m$个小写字母组成。在输入密码的过程中，你的手指需要在密码相邻的两个字母在键盘上的位置移动，缓慢度为这两个位置的距离。对于一个键盘，输入密码的缓慢度为输入密码的缓慢度之和，请设计一个键盘，让缓慢度最小。

数据范围：$1\leqslant n\leqslant 10^5,1\leqslant m\leqslant 20$。

状压dp。

看到这么小的$m$，我们就可以大概猜出要压这个$m$，于是套路的设计状态：$f_i$为设计的键盘（不需要设计完）用到的所有字母压缩起来是$i$的最小缓慢度。

但是有一个问题，对于这个状态，我们不能知道它字母的顺序，所以并不能统计答案。

我们要设计一种无后效性的dp：每一次装一个字母就直接统计出来它的所有贡献（费用提前思想）。

考虑装一个字母的贡献：会让所有相邻且一个装了一个没装的字母对距离加一，这样我们就可以快速地统计出来答案了。

设$cnt_{i,j}$为$i,j$相邻的状态数，很容易统计出来，然后就是套路的状压dp了。

for(int i=1;i<n;i++)
    cnt[s[i]-96][s[i+1]-96]++,cnt[s[i+1]-96][s[i]-96]++;
st=(1<<m)-1,f[0]=0;
for(int i=1;i<=st;i++){
    int sum=0;
    f[i]=inf;
    for(int j=1;j<=m;j++)
        for(int k=j+1;k<=m;k++)
            if(((i>>(j-1))&1)^((i>>(k-1))&1))
                sum+=cnt[j][k];
    for(int j=1;j<=m;j++)
        if((i>>(j-1)&1))
            f[i]=min(f[i],f[i^(1<<(j-1))]+sum);
}

• CF1215E Marbles *

题意：有$n$个珠子，第$i$个珠子颜色是$c_i$，每次操作把相邻的两个珠子交换。现在要把相同颜色的珠子排列在相连的一段，问至少要多少次操作。

数据范围：$1\leqslant n\leqslant 4\times 10^5,1\leqslant c_i\leqslant 20$。

考虑冒泡排序的过程，我们很显然知道操作数量为逆序对数量。但是这里是要让序列连续，所以需要给每个颜色标一个号。

不能单纯的进行标号，也不能对标号进行状压，这是$20!$的。

如果我们每一次标号都标一个更大的数的话，那么我们就可以设出一个没有后效性的状态$f_i$表示状态为$i$的集合逆序对数量的最小值，这里集合$i$中二进制为$1$的位置标示已经进行标号的颜色，$0$的位置则相反。

转移很套路，枚举每一种颜色进行标号就好了。但是暴力计算的的复杂度并不行，需要优化。

设$cnt_{x,y}$为所有数对$(i,j)$满足$i<j,a_i=x,a_j=y$的数量，可以进行$O(20n)$的统计。

复杂度为$O(2^{20}\cdot 20\cdot 20+20n)$。

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++)
        cnt[j][a[i]]+=now[j];
    now[a[i]]++;
}
t=(1<<m)-1,f[0]=0;
for(int i=1;i<=t;i++){
    f[i]=inf;
    for(int j=1;j<=m;j++){
        if((i>>(j-1))&1){
            int sum=0;
            for(int k=1;k<=m;k++)
                if((j!=k&&(i>>(k-1))&1))
                    sum+=cnt[k][j];
            f[i]=min(f[i],f[i^(1<<(j-1))]+sum);
        }
    }
}

• CF1406C Link Cut Centroids

题意：给定一棵节点数为$n$的树，删一条边然后加上一条边，使得该树的重心唯一。（删掉的边和加上的边可以是同一条）

这道题以前做的时候还是黄题，突然就蓝了。

如果给定的树只有一个重心，那么随便删了重加就好了。

如果有两个重心，由常识可得树的两个重心相邻，且两颗重心的子树大小相同。那么可以随便删某一个重心的一个叶子结点，接在另一个重心的子树上就好了。

void find(int x,int last){
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        find(y,x);
        if(flg)
            return ;
    }
    flg=1;
    printf("%d %d\n",x,last);
    if(p2==0)
        printf("%d %d\n",x,last);
    else printf("%d %d\n",x,p2);
}
find(p1,p2);//p1,p2为重心

• UVA1184 Air Raid

题意：求最小路径点覆盖。

一个定理：最小路径点覆盖等于点数减去最大匹配（记得拆点，成为二分图形式）。

然后匈牙利就好了。

简单证一下吧：将一个点拆成入点和出点，求最大匹配。那么每个入点最大度数为$1$，出点最大度数为$1$，若将每个点的入点和出点连一条边，入点出点形成的一定是若干条路径。而如果这些路径不是最小路径点覆盖的话，那么两个可以合并的路径之间的边一定会对二分图的最大匹配进行一次贡献，因此这些路径一定是最小路径点覆盖。

加强版：P2764 最小路径覆盖问题

输出路径可以直接用$match$跳。

for(int i=1;i<=m;i++){
    int x,y;
    scanf("%d%d",&x,&y);
    add(x,y);
}
for(int i=1;i<=n;i++){
    stp++;
    ans+=dfs(i);
}
for(int i=1;i<=n;i++)
    lst[i]=match[i],nxt[match[i]]=i;
for(int i=1;i<=n;i++)
    if(lst[i]==0){
        for(int j=i;j!=0;j=nxt[j])
            printf("%d ",j);
        puts("");
    }
printf("%d\n",n-ans);

• CF617E XOR and Favorite Number

题意：给定一个长度为$n$的序列$a$，然后再给一个数字$k$，再给出$m$组询问，每组询问给出一个区间，求这个区间里面有多少个子区间的异或值为$k$。

数据范围：$1\leqslant n,m\leqslant 10^5,0\leqslant k,a_i\leqslant 10^6$。

莫队水题。

根据莫队的性质很显然可以转化题意为给定区间$[l-1,r]$，求区间内多少个数对异或起来为$k$（其中数对为异或前缀和）。然后做一次莫队，莫队的加入和删除都可以直接暴力做，因为值域非常小。

//b为异或前缀和
void add(int x){
    now+=cnt[k^b[x]];
    cnt[b[x]]++;
}
void del(int x){
    cnt[b[x]]--;
    now-=cnt[k^b[x]];
}

• POJ2777 Count Color

题意：给定长度为$L$的序列$a$，一开始全为颜色$1$，一共有$T$种颜色。需要支持$O$次操作，一共两种：区间覆盖颜色，区间查询颜色数量。

数据范围：$1\leqslant L\leqslant 10^5,1\leqslant T\leqslant 30,1\leqslant O\leqslant 10^5$。

线段树简单题。

首先上一个线段树，然后这个操作有几个思路：

• 直接建$T$棵线段树，暴力修改和查询，时间复杂度$O(OT\log L)$，空间复杂度$O(TL\log L)$。
• 线段树每个结点维护$T$个颜色的数量，暴力修改和查询，时间复杂度$O(OT\log L)$，空间复杂度$O(L\log L)$。
• 线段树每个结点维护$T$个颜色的存无，用$\text{bitset}$维护，时间复杂度$O(\frac{OT\log L}{\omega})$，空间复杂度$O(L\log L)$，常数很小。

这里采取第三种写法，仅给出$\text{pushup,getlazy,pushdown}$部分：

bitset<maxk>val[maxn<<2];
inline void pushup(int now){
    val[now]=val[lc[now]]|val[rc[now]];
}
inline void getlazy(int now,int v){
    val[now].reset();
    val[now][v]=1;
    lazy[now]=v;
}
inline void pushdown(int now){
    if(lazy[now]==0)
        return ;
    getlazy(lc[now],lazy[now]),getlazy(rc[now],lazy[now]);
    lazy[now]=0;
}

---

2020.10.21

第八天。

• POJ1200 Crazy Search

题意：给定一个字符串，一共$nc$种字符，求它长度为$n$的字符个数。

将每个串看成一个$nc$进制的数，然后暴力查答案就好了。

mod=1;
for(int i=1;i<=m;i++)
    mod*=cnt;
now=1;
for(int i=1;i<m;i++)
    now=now*cnt+a[i];
for(int i=m;i<=n;i++){
    now=(now*cnt+a[i])%mod;
    if(hash[now]==0)
        hash[now]=1,ans++;
}

• POJ3259 Wormholes

题意：农夫约翰有$F$个农场，每个农场有$N$块地，其间有$M$条双向路（需要耗费时间），$W$条时光隧道（会时光倒流时间）。问是否可能回到过去？

数据范围：$1\leqslant F\leqslant 5,1\leqslant N\leqslant 500,1\leqslant M\leqslant 2500,1\leqslant W\leqslant 200$。

直接按照题意建边，然后时光隧道赋负权值，道路赋正权值，跑一个$\text{Bellman-Ford}$判负环。

• HDU3534 Tree *

题意：求直径的长度与直径的数量。

我们枚举每个点，如果它作为中间点，那么直径应该是经过它的最长链和次长链拼起来，然后树形dp就好了。

记得有多组数据。

void dfs(int x,int last){
    flen[x]=0,flens[x]=1;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        dfs(y,x);
        int val=flen[y]+worth[i];
        if(flen[x]+val==ans)
            anss+=1ll*flens[x]*flens[y];
        if(flen[x]+val>ans)
            ans=flen[x]+val,anss=1ll*flens[x]*flens[y];
        if(val==flen[x])
            flens[x]+=flens[y];
        if(val>flen[x])
            flen[x]=val,flens[x]=flens[y];
    }
}

• POJ3322 Bloxorz I

题意：$n$行$m$列，有一个木块在上面移动，有些格子不能放，有些格子不能竖着放，求到终点的最小步数。

毒瘤搜索，写了很久，但是不难调。

对于$3$种状态（立着，横着躺，竖着躺）每种做一个不一样的转移，然后直接$\text{bfs}$就好了。

这个转移有点难算，建议手动模拟一下就知道怎么转移了。

int dx[13]={0,1,0,0,-2,-1,1,0,0,-1,2,0,0};
int dy[13]={0,0,1,-2,0,0,0,-1,2,0,0,-1,1};
int ds[13]={0,2,1,1,2,1,1,0,0,0,0,2,2};
struct status{
    int x,y,s,d;
}tmp;
queue<status>q;
//s=0立着，s=1横着躺，s=2竖着躺（注意，横着躺默认位置为左边，竖着躺默认位置为上面）
int bfs(){
    while(!q.empty())
        q.pop();
    tmp.x=sx,tmp.y=sy,tmp.s=ss,tmp.d=0,vis[sx][sy][ss]=0;
    q.push(tmp);
    while(!q.empty()){
        status now=q.front();
        int x=now.x,y=now.y,s=now.s,d=now.d,is=s==0? 1:(s==1? 5:9),ie=s==0? 4:(s==1? 8:12);
        q.pop();
        for(int i=is;i<=ie;i++){
            int ux=x+dx[i],uy=y+dy[i],us=ds[i];
            if(vis[ux][uy][us]<=d+1)
                continue;
            if(ux<1||ux>n||uy<1||uy>m||(us==1&&uy+1>m)||(us==2&&ux+1>n))
                continue;
            if(a[ux][uy]==-1||(us==0&&a[ux][uy]==0)||(us==1&&a[ux][uy+1]==-1)||(us==2&&a[ux+1][uy]==-1))
                continue;
            if(us==0&&a[ux][uy]==2)
                return d+1;
            if(vis[ux][uy][us]<=d+1)
                continue;
            vis[ux][uy][us]=d+1;
            tmp.x=ux,tmp.y=uy,tmp.s=us,tmp.d=d+1;
            q.push(tmp);
        }
    }
    return -1;
}

• POJ2374 Fence Obstacle Course

题意：给出$n$个平行于$x$轴的栅栏$[l_i,r_i]$，求从第$n$个栅栏的某个位置$s$出发，绕过所有栅栏到达另一侧位置（即$x$轴上）的最短水平距离。

数据范围：$1\leqslant n\leqslant 5\times 10^4,|s|,|l_i|,|r_i|\leqslant 10^5$。

很显然有一个dp方式：

设$f_{x,t}(t\in\{0,1\})$为到达栅栏$x$的左边/右边的最小距离。对于一个端点，考虑转移过来的一定是它向上走碰到的第一个栅栏，这样就可以有$O(n^2)$的转移。

考虑线段树优化一下，我们完成每一个栅栏后就将这个栅栏对应的区间在线段树上覆盖一遍，覆盖的值为这个栅栏的编号，查询的时候直接查询这一个位置是什么编号，然后直接转移。

注意有负下标，需要给每一个位置加上一个大数变成正数。

memset(f,0x3f,sizeof(f));
build(1,maxx+base,1);
for(i=1;i<=n;i++){
    int flg0=query(1,maxx+base,1,l[i]+base),flg1=query(1,maxx+base,1,r[i]+base);
    if(flg0==0)
        f[i][0]=abs(l[i]);
    else f[i][0]=min(f[i][0],min(f[flg0][0]+abs(l[i]-l[flg0]),f[flg0][1]+abs(l[i]-r[flg0])));
    if(flg1==0)
        f[i][1]=abs(r[i]);
    else f[i][1]=min(f[i][1],min(f[flg1][0]+abs(r[i]-l[flg1]),f[flg1][1]+abs(r[i]-r[flg1])));
    update(1,maxx+base,1,l[i]+base,r[i]+base,i);
}
printf("%lld\n",min(f[n][0]+abs(l[n]-s),f[n][1]+abs(r[n]-s)));

---

2020.10.22

第九天。

• UVA11212 编辑书稿 Editing a Book *

题意：$n$个数字，需要进行若干次区间剪切和粘贴操作来将它们进行排序，求最小操作数。

直接写个IDA*，这里的估价函数为设的是有多少个数字的后继是正确的，然后不难发现一次操作最多让估价函数改变$3$，就可以进行一次比较强的剪枝。

void work(int x,int y,int z){
    int b[maxn],cnt=0;
    for(int i=y+1;i<=z;i++)
        b[++cnt]=a[i];
    for(int i=x;i<=y;i++)
        b[++cnt]=a[i];
    for(int i=x;i<=z;i++)
        a[i]=b[i-x+1];
}
void revwork(int x,int y,int z){
    int b[maxn],cnt=0;
    for(int i=x+(z-y);i<=z;i++)
        b[++cnt]=a[i];
    for(int i=x;i<=x+(z-y)-1;i++)
        b[++cnt]=a[i];
    for(int i=x;i<=z;i++)
        a[i]=b[i-x+1];
}
int ida_star(int now,int goal){
    int val=check();
    if(val==0)
        return 1;
    if(now==goal)
        return 0;
    if((goal-now+1)*3<val)
        return 0;
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            for(int k=j+1;k<=n;k++){
                work(i,j,k);
                if(ida_star(now+1,goal))
                    return 1;
                revwork(i,j,k);
            }
    return 0;
}

• UVA10319 Manhattan *

题意：一个$n\times m$的矩阵，每一行和每一列必须选定一个方向，只能沿着这个方向走。给定$k$对起点与终点，询问是否有一种方向选定方案使得每一对起点走到终点最多只需要拐一次弯。

数据范围：$1\leqslant n,m\leqslant 30,1\leqslant k\leqslant 200$。

$\text{2-SAT}$神仙题。

对于每一行$row_a$，套路地拆点：$row_a$表示向左，$rev_{row_a}$表示向右；同样的对于每一列$line_b$，$line_b$表示向上，$rev_{line_b}$表示向下。

然后，对于每一对起点终点$(a,b)\rightarrow(c,d)$，首先讨论不需要拐弯的特殊情况，即起点，终点处于同一行或同一列，这样我们直接强制确定某一行/列的方向就好了。

关于如何强制确定一个命题：将这个命题的反命题向这个命题连边，那么就一定无法选定这个命题的反命题了。

关于要拐弯的情况，以起点$(4,4)$终点$(1,2)$为例，我们需要保证以下命题成立：

$$(row_4\cap line_2)\cup(line_4\cap row_1)=true$$

意思就是第四行向左且第二列向上，或第四列向上且第一行向左。

这样我们就要想办法建出来图来满足这种形式的命题$(a\cap b)\cup(c\cap d)$：

有一个逻辑恒等式可以套上去：

$$(a\cap b)\cup(c\cap d)=(a\cup c)\cap(a\cup d)\cap(b\cup c)\cap(b\cup d)$$

（读者自证不难）

这样，我们就可以按照上述式子建图了。

注意要对于$a,c$和$b,d$的大小关系分类讨论。

时间复杂度：$O(n\cdot m+k)$

具体见：题解 UVA10319 【Manhattan】

• CF1228E Another Filling the Grid

题意：给定一个$n\times n$的矩阵，用$[1,k]$中的数填充。要使每行每列最小值都为$1$，问有多少种写法（对$10^9+7$取模）。

数据范围：$1\leqslant n\leqslant 250,1\leqslant k\leqslant 10^9$。

容斥又不会做，就是反演这种东西，才能维持的了生活。

首先，因为要使每行每列最小值为$1$，所以每一行都要有$1$。

正难则反，我们不能很快地计算$i$行$j$列每一行列都有$1$，可以尝试设$f_{i,j}$表示矩阵中恰好$i$行$j$列全部没有$1$，$g_{i,j}$表示矩阵中有$i$行$j$列全部没有$1$。

$g_{i,j}$很容易计算，设$now=n^2-(n\cdot i)(n\cdot j)$，则有

$$g_{i,j}={n\choose i}{m\choose j}(k-1)^{now}k^{n^2-now}$$

根据$g_{i,j}$的定义，很显然有：

$$g_{i,j}=\sum_{x=i}^n\sum_{y=j}^n{x\choose i}{y\choose j}f_{x,y}$$

对于上面的式子，我们可以使用二维二项式反演来得到另一个式子：

$$f_{i,j}=\sum_{x=i}^n\sum_{y=i}^n{x\choose i}{y\choose j}(-1)^{(x-i)+(y-j)}g_{x,y}$$

最后，我们的答案就是$f_{0,0}$了。

具体地，我们可以首先$O(n+\log mod)$预处理逆元，然后$O(n^2)$求$g$数组，然后通过$i=0,j=0$带入上式得到$\sum_{x=0}^n\sum_{y=0}^n{x\choose 0}{y\choose 0}(-1)^{(x-0)+(y-0)}g_{x,y}=\sum_{x=0}^n\sum_{y=0}^n(-1)^{x+y}g_{x,y}$，直接$O(n^2)$计算就好了。

复杂度：$O(n^2)$。

具体看题解 CF1228E 【Another Filling the Grid】。

---

2020.10.23

第十天。

• P1080 国王游戏 *

题意：$n$个大臣排成一列，国王站在最前面，每个人手上有两个数，每个大臣获得的金币为他前面所有人左手上的数的乘积除以他右手上的数，需要让金币最多的大臣金币最少。

贪心毒瘤题。

有一个贪心策略：按照左手上的数乘右手上的数进行从小到大排序，证明就不写了。（提示：可以交换两个相邻的人，观察答案的变化）

记得写高精。

• CF785E Anton and Permutation *

题意：对于一个长度为$n$的序列进行$k$ 次操作，每次操作都是交换序列中的某两个数。对于每一个操作，回答当前序列中有多少个逆序对。

分块毒瘤题。

对于每一个块用$\text{vector}$维护它排序后的序列，对于每一次操作，暴力查询这两个数对答案的所有贡献并删去，然后在原序列修改并暴力重构数字所在块，并最后加上这两个数对答案新的贡献。

记得将这两个数之间的贡献也算进去。

int BF(int x,int y,int v,int t){
    int res=0;
    for(int i=x;i<=y;i++)
        if((t==0&&a[i]<v)||(t==1&&a[i]>v))
            res++;
    return res;
}
int query(int x,int y,int v,int t){
    if(x>y)
        return 0;
    int p=pos[x],q=pos[y];
    if(p==q)
        return BF(x,y,v,t);
    int res=BF(x,r[p],v,t)+BF(l[q],y,v,t);
    for(int i=p+1;i<=q-1;i++){
        if(t==0)
            res+=(lower_bound(b[i].begin(),b[i].end(),v)-b[i].begin());
        else res+=(b[i].size()-(upper_bound(b[i].begin(),b[i].end(),v)-b[i].begin()));
    }
    return res;
}
ans-=(long long)(query(x+1,n,a[x],0)+query(1,x-1,a[x],1));
ans-=(long long)(query(y+1,n,a[y],0)+query(1,y-1,a[y],1));
if(a[x]>a[y])
    ans++;
update(x,y);
ans+=(long long)(query(x+1,n,a[x],0)+query(1,x-1,a[x],1));
ans+=(long long)(query(y+1,n,a[y],0)+query(1,y-1,a[y],1));
if(a[x]>a[y])
    ans--;

实际上修改操作可以直接用$\text{vector}$的自带操作做到$O(\log\sqrt{n})$。

void update(int x,int y){
    int p=pos[x],q=pos[y];
    b[p].erase(lower_bound(b[p].begin(),b[p].end(),a[x]));
    b[q].erase(lower_bound(b[q].begin(),b[q].end(),a[y]));
    b[p].insert(lower_bound(b[p].begin(),b[p].end(),a[y]),a[y]);
    b[q].insert(lower_bound(b[q].begin(),b[q].end(),a[x]),a[x]);
    swap(a[x],a[y]);
}

时间复杂度：$O(m\sqrt{n}\log\sqrt{n})$。

---

最终成果：十天刷完CSP45题。