2020ICPC·小米 网络选拔赛第一场（重温经典）

导语

队内练习，做的并不是很好，有很多地方其实是可以完善的，比如答题策略，自己的签到居然wa了一发，可耻。

涉及的知识点

图论、二维差分、搜索、线段树、数论、dp、贪心

链接：2020ICPC·小米 网络选拔赛第一场

题目

A

题目大意：给定一个序列，选出最多的数，使得选中的数之间互为倍数

思路：第一种思路是暴力，假设dp[i]为当前所选的所有数都是i的约数时的最大可选数量，则每次更新i的倍数即可，这种思路被卡了时间，在提交的时候也是有时过有时不过，第二种思路在第一种的基础上使用素数进行了优化，第一种思路其实在很多情况下被重复更新了，比如6即是2的倍数，也是3的倍数，但是在2和3的计算过程中被更新了两次，这里考虑用唯一分解定理来优化，当i为合数的时候，i是可以分成多个素数相乘的，即i可以通过重复数量更少的策略来减少无用更新，换个说法就是合数可以被若干个质数拼凑出来，那么处理的时候就没有必要考虑合数倍的i了，因为合数倍的i必然可以从多个质数的乘积乘i得到更新，所以dp更新的时候考虑质数倍i即可

代码（暴力）

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=1e7+10;
int n,t,dp[maxn],ans,cnt[maxn];
int main() {scanf("%d",&n);for(int i=1; i<=n; i++) {scanf("%d",&t);cnt[t]++;}for(int i=1; i<=maxn-10; i++)if(cnt[i]) {dp[i]+=cnt[i];for(int j=2*i; j<=maxn-10; j+=i)dp[j]=max(dp[j],dp[i]);ans=max(dp[i],ans);}printf("%d",ans);return 0;
}

代码（带素数优化dp）

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn=1e7+10;
bool IsPrime[maxn];//真值为素数
int Prime[maxn],ans,cnt[maxn],acc,n,t,dp[maxn],M;
void Choose(int n) { //筛选到nmemset(IsPrime,1,sizeof(IsPrime));//初始化//假设每个数为素数IsPrime[1]=IsPrime[0]=1;for(int i=2; i<=n; i++) {if(IsPrime[i])//如果这个数没筛掉，那么将其加入素数序列Prime[++ans]=i;for(int j=1; j<=ans&&i*Prime[j]<=n; j++) {IsPrime[i*Prime[j]]=0;if(!i%Prime[j])break;}}
}
int main() {Choose(maxn);//素数筛scanf("%d",&n);for(int i=1; i<=n; i++) {scanf("%d",&t);cnt[t]++;M=max(M,t);//获得最大值作为边界}for(int i=1; i<=maxn-10; i++) {dp[i]+=cnt[i];for(int j=1; j<=ans&&Prime[j]*i<=M; j++) {//类似素数筛int k=Prime[j]*i;dp[k]=max(dp[k],dp[i]);}acc=max(acc,dp[i]);}printf("%d",acc);return 0;
}

C

题目大意：签到题

思路：直接模拟即可，注意没有w的情况

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;int main() {char s[121212];scanf("%s",s+1);int len=strlen(s+1),ans=0,res=0;for(int i=1; i<=len; i++) {if(s[i]=='w')res++;else if(res) {ans+=res*2-1;res=0;}}if(res)ans+=2*res-1;printf("%d",ans);return 0;
}

D

题目大意：给出一个图，不保证连通，求分别把每个点删除后连通块的个数

思路：这里给出双连通分量及其相关定义

定义1： 在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合，以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，称该点集为割点集合（割集），类似的，如果有一个边集合，删除这个边集合后，原图变成多个连通块，称该点集为割边集合。一个图的边连通度的定义为最小割边集合中的边数。

定义2： 如果一个无向连通图的点/边连通度大于1，则称该图为点/边双连通的，简称双连通或重连通。一个图有割点，当且仅当这个图的点连通度为1，则割点集合的唯一元素被称为割点，又称为关节点。一个图有桥，当且仅当这个图的边连通度为1，则割边集合的唯一元素被称为桥，又称关节边。一个连通的无向图是双连通的，当且仅当它没有关节点

定义3： 图G的所有子图G’中，如果G’是双连通的，则称G’为双连通子图，如果一个双连通子图G’不是任何一个双连通子图的真子集，这G’为极大双连通子图。双连通分量或重连通分量就是图的极大双连通子图，特别的，点双连通分量又称做块。

定义4： 如果有向图G的任何两顶点都互相可达，则称图G为强联通图，否则为非强联通图

定义5： 如果有向图G不是强联通图，子图G’为强联通图，点v属于G’，任意包含v的强联通子图为G’子图，则称G’为G的极大强连通子图，也称强连通分量

题目的意思其实很清楚，就是去掉一个点之后判断多出了几个连通块，直接用tarjan就行，关于Tarjan可以参考
Tarjan相关，与其判断去掉一个点之后会多出几个连通块，不如判断该点是几个连通块的公用点，具体思路如代码

代码

#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const int maxn=5e6+10;
int n,m,head[maxn],cnt,low[maxn],dfn[maxn],acc[maxn],f[maxn],sum,ans;
struct node {int to,next;
} e[maxn];
void Add(int from,int to) {e[++cnt].next=head[from];e[cnt].to=to;head[from]=cnt;
}
void tarjan(int u) {//当前节点dfn[u]=++ans;//时间戳low[u]=ans;//初始化int c=0;for(int i=head[u]; i; i=e[i].next) {//遍历int v=e[i].to;//dfs下一个节点if(!dfn[v]) { //如果没访问过f[v]=u;c++;tarjan(v);//下一节点low[u]=min(low[u],low[v]);//回溯更新if(f[u]&&low[v]>=dfn[u])acc[u]++;//判断u是否为割点，如果是则增加//因为是对每个子树都这样操作的，等价于判断这个割点被几个连通块所共有了else if(f[u]==0&&c>=2)acc[u]++;//同上}if(v==f[u])continue;low[u]=min(low[u],dfn[v]);//回溯更新}
}
int main() {cin >>n>>m;while(m--) {int u,v;cin >>u>>v;Add(u,v);Add(v,u);}for(int i=1; i<=n; i++)if(!dfn[i]) {++sum;tarjan(i);}for(int i=1; i<=n; i++) {if(head[i]==0)printf("%d",sum-1);else printf("%d",sum+acc[i]);printf("%c",i!=n?' ':'\n');}return 0;
}

E

题目大意：给出一个长度为n的序列，有m次询问，询问的数字从1~m递增，对第i次询问，找出原序列中包含1 ~ i这i个数的长度最短的区间[l,r]的长度

思路：这题思路，真的巧，不觉得自己能讲清楚，如果看不懂可以看一下参考博客，综合一下应该就能看懂了

首先，由于询问的数字是递增的，那么当前询问的数i是可以利用先前询问的数i-1的结果的，对于求解区间长度，有一个基本的思路：固定左端点，寻找满足条件的最小右端点，设$R_{i,j}$为当询问为i时，以j为左端点的最小右端点，当i增加时，从$R_{i,j}->R_{i+1,j}$，易得$Ri+1,j\ge R_{i,j}$，$R_{i+1,j}$只可能不变或者跳转到一个大于$R_{i,j}$的i+1位置

假设t[i]为使得区间$[i,t[i]]$中包括1 ~ i所有值的右端点，针对具体i而言，区间最小长度为$t[i]-i+1$，可以添加一个minn记录最短区间长度

用pos[i+1][j-1]表示询问数为i+1时，i+1在序列中出现的第j-1个位置，如图，在pos[i+1][j-1] ~ pos[i+1][j]这一区间内，如果存在一个值x(此时数组记录的是i询问的结果)，使得其右端点在区间内，那么对于新询问i+1来说，t[x]需要扩充到pos[i+1][j]这个位置，同理，pos[i+1][j-1]+1 ~ x这个区间内的所有值的右端点都需要扩充到pos[i+1][j]，当然，如果t[x]原本的值就大于pos[i+1][j]就不需要扩充了

关于维护上述的修改和区间，需要使用线段树来实现，线段树节点记录的有：对应区间内右端点数组的最小值，满足条件的最小区间长度，更新标记，当区间长度为1的时候minn为单点值，对$[l,r]$中的t与$pos[i+1][j]$选择之前，先通过线段树找到$[l,r]$中如图所示的x，然后更新pos[i+1][j-1]+1 ~ x区间内的t值，假设递归到了$[l^{\prime },r^{\prime }]$,$l^{\prime }\ge l,r^{\prime }\le x$，对应节点为rt,最小区间长度更新为pos[i+1][j-1]-r’+1，因为线段树记录的是t数组的对应[l,r]区间内的最小长度和最小右端点，所以为了获得最小的区间长度，只需要减去r（最右边的t[i]）'即可

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
const int INF = 0x3f3f3f3f;//这个地方必须用正无穷
int n,m,a[maxn];
vector<int>pos[maxn];
struct node {int minn,lazy,val;
} seg[maxn<<2];
void pushup(int rt) {seg[rt].val=min(seg[rt<<1].val,seg[rt<<1|1].val);seg[rt].minn=min(seg[rt<<1].minn,seg[rt<<1|1].minn);
}
void pushdown(int rt,int l,int r) {if(seg[rt].lazy) {seg[rt<<1].lazy=seg[rt<<1|1].lazy=seg[rt].lazy;int mid=(l+r)>>1;seg[rt<<1].minn=seg[rt<<1|1].minn=seg[rt].lazy;seg[rt<<1].val=seg[rt].lazy-mid+1;seg[rt<<1|1].val=seg[rt].lazy-r+1;seg[rt].lazy=0;}
}
void update(int rt,int l,int r,int L,int R,int v) {if(l>=L&&R>=r) {seg[rt].lazy=seg[rt].minn=v;seg[rt].val=v-r+1;return ;}pushdown(rt,l,r);int mid=(l+r)>>1;if(mid>=L)update(rt<<1,l,mid,L,R,v);if(R>mid)update(rt<<1|1,mid+1,r,L,R,v);pushup(rt);
}
int query(int rt,int l,int r,int L,int R) {if(seg[rt].minn>=R)return 0;if(l==r)return l;pushdown(rt,l,r);int mid=(l+r)>>1,ans=0;if(R>mid)ans=query(rt<<1|1,mid+1,r,L,R);if(L<=mid&&!ans)ans=query(rt<<1,l,mid,L,R);return ans;
}
int main() {scanf("%d%d",&n,&m);for(int i=1; i<=n; i++)//录入scanf("%d",a+i);for(int i=1; i<=m; ++i)pos[i].push_back(0);//初始化，添加初始0位置for(int i=1; i<=n; ++i)pos[a[i]].push_back(i);//记录每个数字出现的位置//pos[i][j]为数值为i在序列中出现的第j个位置for(int i=1; i<=m; ++i) {//询问次数for(int j=1; j<pos[i].size(); j++) {int p=query(1,1,n,pos[i][j-1],pos[i][j]);//找到满足区间内满足条件的位置if(p)update(1,1,n,pos[i][j-1]+1,p,pos[i][j]);//把pos[i][j-1]+1~p区间上的最右值更新为i的下一位置}if(pos[i].back()<n)update(1,1,n,pos[i].back()+1,n,INF);printf(i==m?"%d\n":"%d ",seg[1].val);}return 0;
}

F

题目大意：有k种题目，每种题目有一个数量$a_i$，现在需要构造许多题目集，每个题目集的题目个数范围在$[L,R]$内，题目集里每种题目出现的数量必须在$[l_i,r_i]$内，求出能构成的最大的题目集数量（不要求题目集数量都相同）

思路：贪心+二分，首先需要特判一下给出的数量之前是否存在冲突，累和所有题目至少出现的数量s，如果s>R，代表无法构成，同理，如果至多出现的数量和小于L，也无法构成

由于要构造最多的题目集，那么每个题目集里的题目数量应该尽量少，设题目集的题目数目为P，则$P=max(L,\sum l_i)$，这一点很容易理解，因为题目数量必须同时满足大于L小于R和大于至少出现的数量和

理想状态下一个题目一个题目集，也就是右边界为题目总和，二分题目集的数量，假设当前二分值为A，首先判断每种题目能不能分出A个题目集，即$a_i\ge A\times l_i$是否满足，随后查看能否满足每个题目集题目个数是否能达到L，获得A个题目集在满足$\sum l_i$的前提下与$A\times L$值之间的差距，即需求，判断每种题目能够提供的题目个数的和能否满足需求，每种题目能够提供的个数为$min(a_i-A\times l_i，A\times (r_i-l_i))$，min中第一个为题目在分出A个题目集之后剩下的数量，第二个为满足$[l_i,r_i]$个数的前提下能提供最多的数量，因为两个条件都要满足，所以选取最小值

代码

#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const int maxn=5e6+10;
ll k,L,R,a[maxn],l[maxn],r[maxn],suml,sumr,minn;
__int128 read() {__int128 x=0,f=1;char ch=getchar();while(!isdigit(ch)&&ch!='-')ch=getchar();if(ch=='-')f=-1;while(isdigit(ch))x=x*10+ch-'0',ch=getchar();return f*x;
}void print(__int128 x) {if(x<0)putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+'0');
}
bool check(ll A) {ll need=A*(L-suml),sum=0;//获得还需要填充的题目数量for(int i=1; i<=k; ++i)if(a[i]<A*l[i])return 0;//如果该值不能凑出A题目集，说明不可取for(int i=1; i<=k; ++i)sum+=min(a[i]-A*l[i],A*(r[i]-l[i]));//获取能够填充的数量，判断能不能弥补差值return sum>=need;
}
int main() {k=read(),L=read(),R=read();ll low=0,high=0,ans=0;for(int i=1; i<=k; ++i) {a[i]=read();high+=a[i];//记录总和，作为右边界}for(int i=1; i<=k; ++i) {l[i]=read(),r[i]=read();suml+=l[i], sumr+=r[i];//记录左边界和与右边界和}if(suml>R||sumr<L) {//如果左边界和大于题目集右边界，如果右边界小于题目集左边界puts("0");return 0;}while(low<=high) {//二分题目集个数ll mid=(low+high)>>1;if(check(mid))ans=mid,low=mid+1;//判断这个个数能不能满足else high=mid-1;}print(ans);return 0;
}

G

题目大意：给出两个序列$A,B$，需要根据这两个序列构建出一棵无根树（任何节点都能当根），A为该树可能的拓扑序，B为可能的dfs序，判断是否存在这样的一棵树

思路：该题的思路其实很明确，用dfs序构造满足拓扑序的树或者用拓扑序构造满足dfs序的树，题解使用的是用拓扑序来满足dfs序，下面用图例说明一下

如图是五个点，点的编号是按照拓扑序从左到右排列的，默认将这些点连接成一条链，现在的目标是改变一些点的连接关系使得构造出的树在满足拓扑序的的前提下满足dfs序，对于树的构造，如果想要不改变拓扑序而进行操作，就需要将新加入的节点与已经构造点的集合构造边，下面为探讨过程

对于第一个链，箭头的方向表示dfs序的方向，那么在z之后构造出的集合就为x->y和x->z，z+1无论是在x,y之间或者y,z之间，解都一定存在(只针对x,y,z,z+1)
对于第二个链，在z插入之前构造的集合为y->x，插入之后构造的是x->y->z，同样z+1的解一定存在
对于第三个链，在z插入之前构造的集合为y->x，插入的z有两种选择，如果z选择了与y相连接，那么此时的集合变为y->x,y->z，如果z+1在x,y之间，为了维护dfs序，z+1需要接在z的后面，但是如果z+1接上z，就会导致拓扑序破坏，也就是该种情况下是一定无解的
对于第四个链，是第三条链的另一种选择，即选择集合中拓扑序最小的节点进行连接，同理可得一定有解

分析完成之后，我们可以得到这样的结论：当向集合中插入新的节点时，如果选择连接集合中拓扑序最小的节点，一定有解，选择连接其他节点不一定有解，由题目要求，需要求得能够得到的解，所以每次连接集合中拓扑序最小的节点即可

想明白这一点，题目就迎刃而解了，从左到右枚举B数组，对于一个B[i]，找到1 ~ i中在A中拓扑序最小的一个进行连接

还有一个队内大佬提供的$O(n\log n)$的算法，参悟之后再补

代码

#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const int maxn=5e6+10;
int n,a[maxn],b[maxn],pos[maxn],cur;
int main() {scanf("%d",&n);for(int i=1; i<=n; i++) {scanf("%d",a+i);pos[a[i]]=i;}for(int i=1; i<=n; i++)scanf("%d",b+i);printf("YES\n");cur=b[1];for(int i=2; i<=n; i++) {printf("%d %d\n",cur,b[i]);if(pos[cur]>pos[b[i]])cur=b[i];//获得已构造集合的最小值}return 0;
}

参考文献

1. 2020ICPC·小米 网络选拔赛第一场 全部题解
2. 2020ICPC·小米 网络选拔赛第一场 E题 Phone Network
3. 2020ICPC·小米 网络选拔赛第一场 E-Phone Network (思维 + 线段树)
4. acm-(线段树、区间最大最小)2020ICPC·小米 网络选拔赛第一场 E.Phone Network
5. G Tree Projection 2020ICPC·小米 网络选拔赛第一场
6. D、Router Mesh（tarjan求割点模板题）