Codeforces Educational Round 92 赛后解题报告
惨 huayucaiji 惨
A. LCM Problem
赛前：A题嘛，总归简单的咯
赛后：A题这种**题居然想了20min
我说这句话，肯定是有原因的，我们看到 \(\operatorname{lcm}\) 会想到之前一些题：题目,我的题解
自然就往 \(a\times b=\operatorname{gcd}(a,b)\times \operatorname{lcm}(a,b)\) 的方向思考，但是，这太麻烦了，我们可以这样想一个问题：
如果我们现在有两个数 \(x,y\)。其中 \(x<y\)。那么我们一定有：
\]
我们可以简略地证明一下，首先因为 \(x<y\)，所以他们的 \(\operatorname{lcm}\) 一定大于 \(x\)。其次我们令 \(g=\operatorname{gcd}(x,y),x=q\cdot g,y=p\cdot g\)。所以 \(\operatorname{gcd}(p,q)=1\)，即 \(p,q\) 互质，那么我们知道 \(\operatorname{lcm}(x,y)=g\cdot p\cdot q=x\cdot p\)。因为 \(p\) 是整数，又因为 \(x\neq y\)。所以 \(p\) 最小取 \(2\)。故 \(\operatorname{lcm}(x,y)\geq 2x\)。
我们只需要判断是否 \(2\times l\leq r\) 即可
//Don't act like a loser.
//You can only use the sode for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#include<bits/stdc++.h>
using namespace std;
int read() {
char ch=getchar();
int f=1,x=0;
while(ch<'0'||ch>'9') {
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
int l,r,t;
signed main() {
t=read();
while(t--) {
l=read();r=read();
bool flag=0;
if(l*2<=r) {
printf("%d %d\n",l,l*2);
}
else {
printf("-1 -1\n");
}
}
return 0;
}
B. Array Walk
我们先来分析题目中一个重要的条件：
Also, you can't perform two or more moves to the left in a row.
我们不能一次向左移动两格。所以这代表一次左后必定是右。那么我们很容易可以想到一个贪心的策略，我们无论如何，先走到 \(k+1\)。我们再来反悔，由于 \(z\) 很小，我们可以枚举往后走几步，并且维护前面相邻两个数的和的最大值，选择在这里后退前进。于是我们可以得到下面的程序：
//Don't act like a loser.
//You can only use the sode for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#include<bits/stdc++.h>
using namespace std;
int read() {
char ch=getchar();
int f=1,x=0;
while(ch<'0'||ch>'9') {
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
const int maxn=1e5+10;
int n,a[maxn],sum[maxn],maxx[maxn],k,z;
signed main() {
int t=read();
while(t--) {
n=read();k=read();z=read();
for(int i=1;i<=n;i++) {
a[i]=read();
sum[i]=sum[i-1]+a[i];
}
fill(maxx,maxx+n+1,0);
for(int i=1;i<=n;i++) {
maxx[i]=max(maxx[i-1],a[i]+a[i-1]);
}
int ans=sum[k+1];
for(int i=1;i<=z;i++) {
if(k+1-2*i>=2) {
ans=max(ans,maxx[k+1-2*i]*i+sum[k+1-2*i]);
}
}
printf("%d\n",ans);
}
return 0;
}
呵呵,WA。
我们再来仔细想想比如对于：
1
5 4 2
50 40 30 20 10
我们的最优方案是 \(50->40->50->40->50\) 答案为 \(230\)。但是我们上面的程序给出的答案是 \(50->40->50->40->30\)。答案为 \(210\)。为什么呢？原因就是我们珂以退回去后就不行再往前走了，留在后面的格子里。所以我们还要加上这一段代码：
if(k+2-2*i>=2) {
ans=max(ans,sum[k+1-2*i]+i*(a[k-i*2+1]+a[k-i*2+2]));
}
注意一些下标的问题哦~
C. Good String
这个题比B简单吧
我们可以通过题目得出以下结论：
\]
所以我们有 \(s_1=s_3=s_5=....s_{n-1}=q\)，\(s_2=s_4=s_6=.....s_{n}=p\)。
我们只需要枚举 \(p,q\) 即可，每次枚举出来后，顺次统计以下最少要删多少字符，用贪心一个一个扫就是最优的，这里就不再证明了。但是我们还有一些特殊情况要处理。
如果我们最后删减版序列是 \(pqpqp\)。那么我们得出的两序列是 \(ppqpq\) 和 \(qpqpp\)。显然在 \(p\neq q\) 时不等。所以当 \(p\neq q\) 且 \(len\) 是奇数时，删去的数还要在加一。
注意特判 \(len=1\)。
//Don't act like a loser.
//You can only use the sode for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#include<bits/stdc++.h>
using namespace std;
int read() {
char ch=getchar();
int f=1,x=0;
while(ch<'0'||ch>'9') {
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
int n;
string s;
signed main() {
int t=read();
while(t--) {
cin>>s;
n=s.size();
if(n==1) {
cout<<0<<endl;//特判 n=1
continue;
}
int ans=n;
for(int i=0;i<=9;i++) {
for(int j=0;j<=9;j++) {
int num=0,sum=0;//num记录当前应该匹配哪个数
for(int k=0;k<n;k++) {
if(!num) {
if(s[k]-'0'!=i) {
sum++;
}
else {
num=1-num;
}
}//分类
else {
if(s[k]-'0'!=j) {
sum++;
}
else {
num=1-num;
}
}
}
if(i!=j&&num) {
sum++;//删去的数+1
}
ans=min(ans,sum);
}
}
printf("%d\n",ans);
}
return 0;
}
D. Segment Intersections
我们先打开单词小本本记录一下 intersection 这个词（虽然我会）。它的意思是交叉，十字路口。
我们切入正题。
首先我们会发现问题分成两个类别。第一类是 \([l_1,r_1],[l_2,r_2]\) 有交集。即 \(\min(r_1,r_2)-\max(l_1,l_2)\geq 0\)。交集的长度（即题目中的 \(\operatorname{intersection\ length}\)）也就为 \(\min(r_1,r_2)-\max(l_1,l_2)\)。如下图：
那么此时我们选择这种做法（也就是官方解法）。我们每次将 \([l_1,r_1]\) 扩展为 \([l_1,r_1+1]\)，或者同理将 \([l_2,r_2]\) 扩展为 \([l_2-1,r_2]\)，知道两个区间完全相同为止，在这样扩充时，我们每用一步，就可以让交集长度增加 \(1\)。是最划算的。但是一旦两个区间完全相同，即 \(l_1=l_2,r_1=r_2\) 时，我们不能在这样操作了，我们必须让两个区间的同一边长度都增加 \(1\)，才能让交集长度增加 \(1\)。这是唯一的选择了。那么第一类我们讨论完了。
再来看第二类，也就是一开始没有交集。那么我们可以让它有交集在用第一种情况的处理方法来处理。我们要枚举一个 \(cnt\)，代表要让多少对区间有交集。我们完全没有必要让所有的区间成双成对地有交集，毕竟有的用不上嘛~。我们让一堆区间有交集的最小步数就为 \(\max(l_1,l_2)-\min(r_1,r_2)\)。注意还要乘以 \(cnt\)。最后用第一种情况的处理方法来处理即可。时间复杂度为 \(O(n)\)。
注意细节！比如开 long long
//Don't act like a loser.
//You can only use the code for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#include<bits/stdc++.h>
#define int long long//不开long long 见祖宗！
using namespace std;
int read() {
char ch=getchar();
int f=1,x=0;
while(ch<'0'||ch>'9') {
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
int calc(int n,int k,int l1,int r1,int l2,int r2) {
if(k<=0) {
return 0;
}
if((max(r1,r2)-min(l1,l2))*n>=k+(min(r1,r2)-max(l1,l2))*n)//注意细节 {
return k;
}
else {
int tmp=(max(l1,l2)-min(l1,l2)+max(r1,r2)-min(r1,r2))*n;//细节
return tmp+(k-tmp)*2;
}
}
signed main() {
int t=read();
while(t--) {
int n,k,l1,l2,r1,r2;
n=k=l1=l2=r1=r2=0;
cin>>n>>k>>l1>>r1>>l2>>r2;
int ans=0x7fffffffffffffff;
if(min(r1,r2)<max(l1,l2)) {
for(int i=1;i<=n;i++) {
ans=min(ans,(max(l1,l2)-min(r1,r2))*i+calc(i,k,min(l1,l2),min(r1,r2),min(r1,r2),max(r1,r2)));//细节，我们要进行计算的是我们处理完的区间，是有交集的，保证有交集即可。
}
}
else {
ans=calc(n,k-(min(r1,r2)-max(l1,l2))*n,l1,r1,l2,r2);
}
printf("%lld\n",ans);//lld的细节
}
return 0;
}
E. Calendar Ambiguity
我们会发现这个题目只有一个可以入手的点，其他都是定义类条件。
A pair (x,y) such that x<y is ambiguous if day x of month y is the same day of the week as day y of month x.
用数学方法表示也就是
\]
而 \(d-1\) 是一个定值。我们只需要关注 \(x-y\)。但是注意了，我们的 \(d-1\) 和 \(w\) 可能有相同的质因子，这些就没有必要再在 \(x-y\) 包含了。所以我们令 \(w'=\frac{w}{\gcd(d-1,w)}\)。我们要求的就是有多少对 \((x,y)\) 满足 \(x-y\equiv 0\ (\operatorname{mod}\ w')\)。
为了求解这个问题，我们可以考虑弱化条件。假设我们现在求解有多少对 \((x,y)\) 满足 \(x-y=k\cdot w'\)。那么我们可以用数学方法来解决，就有 \(\min(m,d)-k\cdot w'\) 对。这个应该十分好理解。 我们再把条件还原，我们就可以枚举 \(k\)，在累加答案。由于 \(x-y\leq \min(m,d)\)所以最后的答案就是：
\]
聪明的小伙伴可能会发现，这样的时间复杂度实在太大，到了 \(O(t\cdot\lfloor\frac{\min(m,d)}{w'}\rfloor)\) 应该是过不了的，大家可以试一试。那么我们就要想如何优化。我们再次观察这个式子，发现是一个等差数列,公差是 \(-w'\)。我们用高斯公式就可以解决这个问题。首项为 \(\min(d,m)-w'\)，末项为 \(\min(d,m)-\lfloor\frac{\min(m,d)}{w'}\rfloor\cdot w'\)，项数为 \(\lfloor\frac{\min(m,d)}{w'}\rfloor\)。所以最终答案为：
\]
这样时间复杂度为 \(O(\log(m+d))\)。
时间复杂度的大户竟是计算 \(\gcd\) 你敢相信？
//Don't act like a loser.
//You can only use the code for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read() {
char ch=getchar();
int f=1,x=0;
while(ch<'0'||ch>'9') {
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
int m,d,w;
int gcd(int x,int y) {
return y==0? x:gcd(y,x%y);
}
signed main() {
int t=read();
while(t--) {
m=read();d=read();w=read();
w=w/gcd(w,d-1);
int n=min(m,d);
int num=n/w;
int ans=(2*n-w*num-w)*num/2;
cout<<ans<<endl;
}
return 0;
}
F. Bicolored Segments
拿出单词小本本，我们再来记一个单词：
embed：嵌入，本题中意思就是一个区间被另一个区间所包含。
回归正题，我在写这篇题解时看了洛谷上一篇和我思路差不多的大佬写的题解，他的线段树优化DP写的不错的，大家可以看看，但是我觉得他的解法二不太清晰，特别是那个“对抗抵消”。可能蒟蒻不太能理解qwq，这里换一个角度在重新讲一下。
我们这样想，既然有两种不同颜色的区间，就代表我们可以理解把它们为一个二分图的节点。如果你愿意，我们再把所有互为“不好的”区间连边。我们就得到了一个看着不错二分图。举个例子，我们题目中的样例二构图：
样例二：
5
5 8 1
1 3 2
3 4 2
6 6 1
2 10 2
我们构成的二分图：
我们再看这个图，是不是有一点感觉了，我们要求的正是这个图的最大点独立集。求最大点独立集，我们就要求最大匹配。这两个概念不知道的同学可以上网搜。我们令最大点独立集的答案为 \(x\)，最大匹配的答案为 \(y\)。我们有 \(x+y=n\)。\(n\) 就是点的个数。证明略我们的问题成功转化为这个二分图求最大匹配。
我相信不会有人想着真的把图建出来用网络流求解吧，不会吧，不会吧。
咳咳，我一开始就这么想的
不扯远了，但确实我们的第一反应应该是网络瘤，毕竟是它的好伙伴二分图嘛。但是我们建图的时间复杂度就是 \(O(n^2)\)，Dinic 做二分图的时间复杂度 \(O(m\sqrt{n})\)，显然爆炸。我们要像一种高效的方法才行。
我们先和上面的那篇 blog 一样，按每个区间的右端点为第一关键字排序，搞两个 multiset 记录我们选择了哪些区间。接下来的操作还是一样，但是我们的解释不太一样。我们要求的是最大匹配，如果我们在异色的 multiset 中，存在与我们现在考虑的这个区间形成“不好区间”的区间的话，我们就选择这两个点之间的这条边作为最大匹配中的一条边，把那个 muliset 中的点给抹掉，并且现在的这个区间也不加入到 multiset 中，因为我们这两个点不能再出现在最大匹配的边里了，这是最大匹配的定义要求的。否则这个区间我们可以加入到 multiset 中。这样解释应该更清楚一些吧（自认为）。也就不用去理解“对抗抵消”了。
//Don't act like a loser.
//You can only use the code for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read() {
char ch=getchar();
int f=1,x=0;
while(ch<'0'||ch>'9') {
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
const int maxn=2e5+10;
int n=0,ans=0;
struct segment {
int l,r,col;
const operator < (const segment& y) {
return r<y.r;
}
}s[maxn];
multiset<int> sel[2];
signed main() {
n=read();
for(int i=1;i<=n;i++) {
s[i].l=read();
s[i].r=read();
s[i].col=read()-1;
}
sort(s+1,s+n+1);
ans=n;
for(int i=1;i<=n;i++) {
if(sel[1-s[i].col].lower_bound(s[i].l)!=sel[1-s[i].col].end()) {
ans--;
sel[1-s[i].col].erase(sel[1-s[i].col].lower_bound(s[i].l));
}
else {
sel[s[i].col].insert(s[i].r);
}
}
cout<<ans<<endl;
return 0;
}
G. Directing Edges
有点意思的一道题
首先推荐阅读一下DP之神UM的一篇关于换根DP的blog。阅读完后再来看本题解效果更佳。
好，我们切回正题。首先我们来简化条件。如果现在给我们的是一颗有 \(n\) 个点的树。让我们来做这个问题，我们该怎么做呢？比如我们考虑下图这棵树：
我们容易想到我们要做的是 DP。我们定义：\(f_u\) 表示以 \(u\) 为根节点的子树里，保证 \(u\) 是饱和的情况下，我们所能获得的最大收益为多少。假设我们已经知道了所有 \(u\) 的子节点的值，即 \(f_{v_1},f_{v_2},f_{v_3}....f_{v_d}\) 的值（其中 \(v_1,v_2....v_d\) 为 \(u\) 的子节点）那么我们现在需要考虑的就是连接 \(u,v_i\) 的边的方向到底是什么了。现在我们就来考虑一下 \(3\) 对 \(f_1\) 的贡献。
如果我们的特殊点是 \(3,9,11\)，现在我们考虑蓝色的边的方向。我们发现所有的特殊点都在以 \(3\) 为根的子树中。为了让 \(1\) 饱和，那么蓝色的边的方向就应该是由 \(3\) 到 \(1\)，从而让所有的特殊点都指向 \(1\)，同时 \(f_1\) 也得到了 \(f_3\) 的全部收益。这种情况只有在所有特殊点都在一颗子树中时成立，我们可以决定这课子树到其父节点这条边的方向。 如下图：
如果我们的特殊点是 \(1,2,6,8\)，现在我们考虑蓝色的边的方向。我们发现所有的特殊点都不在以 \(3\) 为根的子树中。为了获得 \(f_3\) 的收益，蓝色的边的方向就应该是由 \(1\) 到 \(3\)。这种情况只有在所有特殊点都在一颗子树外时成立，我们可以决定这课子树到其父节点这条边的方向。 如下图：
还有一种情况就是在某一子树外和子树中都有特殊点，那么为了获得 \(f_3\) 的收益，同时让 \(1\) 饱和，我们必须要让这条边成为双向边。订单式如果这条边成为双向边的代价 \(w_i>f_3\)。我们宁愿抛弃 \(f_3\)。因为此时它带来的增益是负的。
因此我们总结一下：对于一个节点 \(u\)，已知他的儿子 \(f_{v_1},f_{v_2},f_{v_3}....f_{v_d}\) 的值。我们令连接 \(u,v_i\) 的边编号为 \(j\)，\(size_u\) 为以 \(u\) 为根节点的子树中有特殊点个数，那么我们有：
\]
\]
显然，我们想要算 \(u\) 一定为饱和点的时候最大收益就是 \(u\) 为根的时候 \(f_u\) 的值。但是我们要把每个点的答案都算出来，时间复杂度就上升到了 \(O(n^2)\)。实在太大，无法接受。所以我们要采用换根DP的方式来优化复杂度。我们再来定义 \(dp_u\) 为满足 \(u\) 一定饱和的情况下，在以 \(u\) 的根节点的子树外的最大收益。我们先以 \(1\) 为根节点做一遍DFS求出 \(f\) 数组的值。接着再做一遍DFS，算出 \(dp\) 数组。具体的方法可以参照UM的blog，读者自己思考完成。实在不会可以看看代码。最后 \(ans_u=f_u+dp_u-c_u\)。因为 \(dp_u,f_u\) 中都包含 \(c_u\)，也就是这个节点本身的收益。
提示一下初值：\(dp_u=f_u=c_u\) 哦~
但是我们上面讨论的是树的情况下。但如果是一张图呢？我们就要来进行一下问题的转化。
我们一般把一个无向图转化为树的方法就是双联通分量缩点。我们来证明一下一个缩完点的双连通分量等同于树上的一个点。首先，我们知道一个双联通分量内部的边有向化，一定有至少一种方案使其成为强连通分量。所以这个双联通分量内部的点，要么全部饱和，要么全不饱和，其其内部的遍全有向化，代价为 \(0\)。因此，我们只需要缩个点，在进行换根DP即可解决此题。
代码至少150+，大家自便（不压行）~
//Don't act like a loser.
//You can only use the code for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read() {
char ch=getchar();
int f=1,x=0;
while(ch<'0'||ch>'9') {
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
const int maxn=3e5+10;
int n=0,m=0,k=0,h[maxn]={},cnt=0,low[maxn]={},dfn[maxn]={},col[maxn]={},num[maxn]={},size[maxn]={},d[maxn]={},tot=0;
int col_cnt=0,time_cnt=0,w[maxn]={},c[maxn]={},val[maxn]={},spe[maxn]={},f[maxn]={},dp[maxn]={};
vector<pair<int,int> > g[maxn];
bool vis[maxn]={},spec[maxn];
struct edge {
int v,w,next;
}e[maxn<<1];
void addedge(int u,int v,int w) {
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=h[u];
h[u]=cnt;
}
void insert(int u,int v,int w) {
addedge(u,v,w);
addedge(v,u,w);
}
void dfs1(int u,int fa) {
vis[u]=1;
low[u]=dfn[u]=++time_cnt;
int sz=g[u].size();
for(int i=0;i<sz;i++) {
int v=g[u][i].first;
if(v!=fa) {
if(!vis[v]) {
dfs1(v,u);
low[u]=min(low[u],low[v]);
}
else {
low[u]=min(low[u],dfn[v]);
}
}
}
d[++tot]=u;
}
void dfs2(int u,int fa) {
col[u]=col_cnt;
spe[col_cnt]+=spec[u]? 1:0;
val[col_cnt]+=c[u];
int sz=g[u].size();
for(int i=0;i<sz;i++) {
int v=g[u][i].first;
if(dfn[u]>dfn[v]||low[v]>dfn[u]) {//判断是否是桥。
continue;
}
if(!col[v]) {
dfs2(v,u);
}
}
}
void tarjan() {
dfs1(1,0);
for(int i=n;i;i--) {//反向循环
if(!col[d[i]]) {
col_cnt++;
dfs2(d[i],0);
}
}
for(int u=1;u<=n;u++) {//缩点后的建图
int sz=g[u].size();
for(int i=0;i<sz;i++) {
int v=g[u][i].first;
if(u<v&&col[u]!=col[v]) {//注意一条边不要建两次~
insert(col[u],col[v],w[g[u][i].second]);
}
}
}
}
void dfs3(int u,int fa) {//以1为根的DFS
f[u]=val[u];
size[u]=spe[u];
for(int i=h[u];i;i=e[i].next) {
int v=e[i].v;
if(v!=fa) {
dfs3(v,u);
size[u]+=size[v];
if(size[v]==0||size[v]==k) {
f[u]+=f[v];
}
else {
f[u]+=max(0LL,f[v]-e[i].w);
}
}
}
}
void dfs4(int u,int fa) {//换根的部分
int sum=0;
for(int i=h[u];i;i=e[i].next) {
int v=e[i].v;
if(v!=fa) {
if(size[v]==k||size[v]==0) {//注意分类
sum+=f[v];
}
else {
sum+=max(0LL,f[v]-e[i].w);
}
}
}
for(int i=h[u];i;i=e[i].next) {
int v=e[i].v;
if(v!=fa) {
dp[v]=val[v];
if(size[v]==0||size[v]==k) {//分类，由上而下更新dp数组
dp[v]+=dp[u]+sum-f[v];
}
else {
dp[v]+=max(0LL,dp[u]+sum-max(0LL,f[v]-e[i].w)-e[i].w);
}
dfs4(v,u);
}
}
}
signed main() {
n=read();
m=read();
k=read();
for(int i=1;i<=k;i++) {
spec[read()]=1;
}
for(int i=1;i<=n;i++) {
c[i]=read();
}
for(int i=1;i<=m;i++) {
w[i]=read();
}
for(int i=1;i<=m;i++) {
int a=read(),b=read();
g[a].push_back(make_pair(b,i));
g[b].push_back(make_pair(a,i));//第一次建图
}
tarjan();
dfs3(1,0);
dp[1]=val[1];
dfs4(1,0);
for(int i=1;i<=n;i++) {
printf("%lld ",dp[col[i]]+f[col[i]]-val[col[i]]);//注意-val[i]
}
return 0;
}