虽然最近打了很多场CF，也涨了很多分，但是好久没写CF的题解了。
前几次刚刚紫名的CF，太伤感情了，一下子就掉下来了，不懂你们Div.1。
珂学的那场我只做了第一题……悲伤。
这次的Educational Round打的还可以，虽然吧没有涨分（因为我是紫色的啊）。
做了前4题，后面3题也比较简单，陆续也做完了。
所以心情好，来写一篇题解！
【A】花园
题意：
长度为\(k\)的线段，用若干个长度为\(a_i\)的线段，正好覆盖。（\(a_i|k\)）
给定\(n\)个\(a_i\)，求出最小的\(k/a_i\)，前提是\(a_i|k\)。
题解：
大模拟。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define ll long long
#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define F2(i,a,b) for(int i=(a);i<(b);++i)
#define dF(i,a,b) for(int i=(a);i>=(b);--i)
#define dF2(i,a,b) for(int i=(a);i>(b);--i)
#define eF(i,u) for(int i=h[u];i;i=nxt[i])
using namespace std;
const int INF=0x3f3f3f3f;
inline int Gcd(int X,int Y){return Y?Gcd(Y,X%Y):X;}
inline int Max(int X,int Y){return X<Y?Y:X;}
inline int Min(int X,int Y){return X<Y?X:Y;}
inline ll Max(ll X,ll Y){return X<Y?Y:X;}
inline ll Min(ll X,ll Y){return X<Y?X:Y;}
int n,k,x;
int ans=;
int main(){
scanf("%d%d",&n,&k);
while(n--) {scanf("%d",&x); if(k%x==) ans=Min(ans,k/x);}
printf("%d",ans);
return ;
}
【B】浏览器
题意：
看样例解释猜题意。
对于浏览器顶部的标签，你有这样的操作：关闭这个标签左/右侧的所有标签，把鼠标移到左/右一个标签。
给定标签数目\(n\)，鼠标现在所在的标签\(p\)，问你留下标签区间\([l,r]\)的最少操作次数。
题解：
大模拟，注意看左边/右边到底有没有标签。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define ll long long
#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define F2(i,a,b) for(int i=(a);i<(b);++i)
#define dF(i,a,b) for(int i=(a);i>=(b);--i)
#define dF2(i,a,b) for(int i=(a);i>(b);--i)
#define eF(i,u) for(int i=h[u];i;i=nxt[i])
using namespace std;
const int INF=0x3f3f3f3f;
inline int Gcd(int X,int Y){return Y?Gcd(Y,X%Y):X;}
inline int Max(int X,int Y){return X<Y?Y:X;}
inline int Min(int X,int Y){return X<Y?X:Y;}
inline ll Max(ll X,ll Y){return X<Y?Y:X;}
inline ll Min(ll X,ll Y){return X<Y?X:Y;}
inline int Abs(int X){return X<?-X:X;}
int n,p,l,r;
int main(){
scanf("%d%d%d%d",&n,&p,&l,&r);
if(l==&&r==n){puts("");return ;}
if(l==){printf("%d",Abs(p-r)+);return ;}
if(r==n){printf("%d",Abs(p-l)+);return ;}
printf("%d",Min(Abs(p-r),Abs(p-l))+r-l+);
return ;
}
【C】数位重排
题意：
给定两个数\(a,b\)，求出把\(a\)在十进制下数位重排后不超过\(b\)的最大数，不能有前导零。
题解：
暴力DFS。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define ll long long
#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define F2(i,a,b) for(int i=(a);i<(b);++i)
#define dF(i,a,b) for(int i=(a);i>=(b);--i)
#define dF2(i,a,b) for(int i=(a);i>(b);--i)
#define eF(i,u) for(int i=h[u];i;i=nxt[i])
using namespace std;
const int INF=0x3f3f3f3f;
inline int Gcd(int X,int Y){return Y?Gcd(Y,X%Y):X;}
inline int Max(int X,int Y){return X<Y?Y:X;}
inline int Min(int X,int Y){return X<Y?X:Y;}
inline ll Max(ll X,ll Y){return X<Y?Y:X;}
inline ll Min(ll X,ll Y){return X<Y?X:Y;}
ll a,b,aa,bb;
int ca,cb;
int oo;
int use[];
int bs[];
int cs[];
void print(){
oo=;
// puts("!!");
for(int i=ca;i>=;--i) printf("%d",cs[i]);
}
void dfs(int stp,bool deng){
if(stp==) {print(); return;}
if(oo) return;
for(int i=deng?bs[stp]:;i>=;--i){
if(stp==ca&&i==) continue;
if(!use[i]) continue;
use[i]--; cs[stp]=i;
dfs(stp-,deng?(i==bs[stp]):);
use[i]++;
}
}
int main(){
scanf("%lld%lld",&a,&b); aa=a,bb=b;
while(aa) use[aa%]++,aa/=,++ca; while(bb) bs[cb+]=bb%,bb/=,++cb;
if(cb>ca){
for(int i=;i>=;--i) while(use[i]) use[i]--,printf("%d",i);
return ;
}
dfs(ca,);
return ;
}
【D】几乎无环图
题意：
给定一个有向图，问能否删掉一条边后，这个图变成无环图。\(2\leq n\leq 500,1\leq m\leq min(n(n-1),1000000)\)
题解：
先找到一个环（找不到就YES）。
找环用DFS/拓扑排序，我写的时候脑子不好，用了恶心的DFS。
这个环上最多\(n\)条边，对每条边都试一次，看看还有没有环。
为什么要先找到一个环？
拓扑排序/DFS的复杂度是\(O(n+m)\)的。
那么如果直接对每条边试着删除的话，总复杂度\(O((n+m)^2)\)，就T飞了。
先找到一个环的话，总复杂度\(O(n(n+m))\)，能过。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define ll long long
#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define F2(i,a,b) for(int i=(a);i<(b);++i)
#define dF(i,a,b) for(int i=(a);i>=(b);--i)
#define dF2(i,a,b) for(int i=(a);i>(b);--i)
#define eF(i,u) for(int i=h[u];i;i=nxt[i])
using namespace std;
const int INF=0x3f3f3f3f;
inline int Gcd(int X,int Y){return Y?Gcd(Y,X%Y):X;}
inline int Max(int X,int Y){return X<Y?Y:X;}
inline int Min(int X,int Y){return X<Y?X:Y;}
inline ll Max(ll X,ll Y){return X<Y?Y:X;}
inline ll Min(ll X,ll Y){return X<Y?X:Y;}
int n,m;
int h[],nxt[],to[],tot;
inline void ins(int x,int y){nxt[++tot]=h[x];to[tot]=y;h[x]=tot;}
int used[],ret[];
int o,oo,ooo;
int stk[],top,pos[];
int fk[][];
bool use[];
int cnt;
void dfs(int u){
// printf(" u: %d\n",u);
used[u]=cnt; stk[++top]=u; pos[u]=top;
eF(i,u){
if(used[to[i]]==) dfs(to[i]);
else{if(used[to[i]]==cnt&&ret[to[i]]==){/*printf("error : %d -> %d\n",u,to[i]);*/o=pos[to[i]]; return;}}
if(o) return;
} --top; ret[u]=;
}
void dfs2(int u){
// printf(" u: %d\n",u);
used[u]=cnt;
eF(i,u) if(!use[i]){
// printf("%d -> %d\n",u,to[i]);
if(used[to[i]]==) dfs2(to[i]);
else{if(used[to[i]]==cnt&&ret[to[i]]==){/*printf("error : %d -> %d\n",u,to[i]);*/ooo=; return;}}
if(ooo) return;
} ret[u]=;
}
int main(){
scanf("%d%d",&n,&m);
if(m->n*(n-)/) {puts("NO"); return ;}
if(m<=) {puts("YES"); return ;}
int x,y;
F(i,,m) scanf("%d%d",&x,&y), ins(x,y), fk[x][y]=tot;
F(i,,n){
o=; top=; cnt=i;
if(!used[i]) dfs(i);
if(o) {oo=; break;}
}
if(!oo) {puts("YES"); return ;}
// F(i,o,top)
// printf(",%d",stk[i]); puts("");
F(i,o,top){
// printf(" %d\n",stk[i]);
memset(used,,sizeof used);
memset(ret,,sizeof ret);
ooo=;
if(i!=top) use[fk[stk[i]][stk[i+]]]=;
else use[fk[stk[i]][stk[o]]]=;
F(j,,n){
cnt=j;
if(used[j]==) dfs2(j);
// printf("%d %d %d\n",j,used[j],ooo);
// puts("====");
if(ooo) break;
}
if(!ooo) {puts("YES"); return ;}
if(i!=top) use[fk[stk[i]][stk[i+]]]=;
else use[fk[stk[i]][stk[o]]]=;
} puts("NO");
return ;
}
【E】体育课
题意：
震惊，Alex发现自己虽然是个ACMer，但是他还是得参加体育期末考！【多么的讽刺啊……】
Alex要算出自己到期末的\(n\)天中，还有多少天能上体育课？
可惜学校时常更改一段时间的有/无上课的状态，可能把一整段区间都变成不上课或者上课。
你需要算出每一次更改后的答案。\(1\leq n\leq 10^9,1\leq q\leq 3\cdot 10^5\)。
题解：
离散化，线段树，没什么好说的。
#include<algorithm>
#include<cstdio>
#define F(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
int n,q;
int x[],y[],opt[];
int sq[],cnt;
int siz[];
int sz[],dat[],lzy[];
void build(int i,int l,int r){
if(l==r) {sz[i]=siz[l]; return;}
int mid=l+r>>;
build(i<<,l,mid), build(i<<|,mid+,r);
sz[i]=sz[i<<]+sz[i<<|];
}
void init(){
scanf("%d%d",&n,&q);
F(i,,q) scanf("%d%d%d",x+i,y+i,opt+i), sq[++cnt]=x[i]-, sq[++cnt]=y[i];
sort(sq+,sq+cnt+);
int Cnt=cnt, lst=-; cnt=;
F(i,,Cnt) if(sq[i]!=lst) sq[++cnt]=sq[i], lst=sq[i];
F(i,,cnt-) siz[i]=sq[i+]-sq[i];
F(i,,q) x[i]=lower_bound(sq+,sq+cnt+,x[i]-)-sq, y[i]=lower_bound(sq+,sq+cnt+,y[i])-sq-;
cnt--;
}
inline void pushdown(int i){
if(lzy[i]==) dat[i<<]=sz[i<<], dat[i<<|]=sz[i<<|], lzy[i<<]=lzy[i<<|]=;
if(lzy[i]==) dat[i<<]=dat[i<<|]=, lzy[i<<]=lzy[i<<|]=;
lzy[i]=;
}
void M(int a,int b,int i,int l,int r,int typ){
if(a<=l&&r<=b) {dat[i]=(typ==?(sz[i]):); lzy[i]=typ; return;}
if(r<a||b<l) return;
pushdown(i);
int mid=l+r>>;
M(a,b,i<<,l,mid,typ), M(a,b,i<<|,mid+,r,typ);
dat[i]=dat[i<<]+dat[i<<|];
}
int main(){
init();
build(,,cnt);
F(i,,q){
if(opt[i]==) M(x[i],y[i],,,cnt,);
else M(x[i],y[i],,,cnt,);
printf("%d\n",n-dat[]);
}
return ;
}
【F】海棠数组树的失衡度
题意：
给你一棵树，节点有权值，计算\(\sum_{i=1}^n\sum_{j=i}^nI(i,j)\)。
\(I(i,j)\)表示\(i\)到\(j\)的路径上的最大点权-最小点权。
题解：
考虑最大最小分开计算，最后最大减最小。
以最大点权为例，如何计算？
假设这个点是\(x\)，考虑计算与\(x\)直接或间接联通的点中，到\(x\)的路径中的点权都不比\(x\)大的点。
通过这些点的个数来计算答案。
可以证明，这些点和\(x\)形成的图是一棵树。
我们以\(x\)为根，\(x\)对答案的贡献是\(val_x\cdot[siz_x^2-\sum_{k=x.son}siz_k^2]\)。
那么怎么找到到\(x\)的路径上的点权都不比\(x\)大的点呢？
考虑按照\(val\)为顺序加入点，用并查集维护连通性，就能算答案了。
#include<algorithm>
#include<cstdio>
#include<cstring>
#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define F2(i,a,b) for(int i=(a);i<(b);++i)
#define dF(i,a,b) for(int i=(a);i>=(b);--i)
#define eF(i,u) for(int i=h[u];i;i=nxt[i])
int n,a[],I[],siz[];
inline bool cmp(int p1,int p2){return a[p1]<a[p2];}
int h[],nxt[],to[],tot;
inline void ins(int x,int y){nxt[++tot]=h[x];to[tot]=y;h[x]=tot;}
bool vis[];
int fa[];
int ff(int x){return fa[x]?fa[x]=ff(fa[x]):x;}
long long ans;
int main(){
scanf("%d",&n);
F(i,,n) scanf("%d",a+i), I[i]=i;
int x,y,u; long long tmp;
F2(i,,n) scanf("%d%d",&x,&y), ins(x,y), ins(y,x);
std::sort(I+,I+n+,cmp);
F(i,,n){
siz[u=I[i]]=; tmp=; vis[u]=;
eF(j,u)
if(vis[to[j]]) siz[u]+=siz[ff(to[j])], tmp+=1ll*siz[ff(to[j])]*siz[ff(to[j])], fa[ff(to[j])]=u;
ans+=a[u]*(1ll*siz[u]*siz[u]-tmp);
}
memset(fa,,sizeof fa);
dF(i,n,){
siz[u=I[i]]=; tmp=; vis[u]=;
eF(j,u)
if(!vis[to[j]]) siz[u]+=siz[ff(to[j])], tmp+=1ll*siz[ff(to[j])]*siz[ff(to[j])], fa[ff(to[j])]=u;
ans-=a[u]*(1ll*siz[u]*siz[u]-tmp);
}
printf("%lld",ans>>);
return ;
}
【G】互质数组
题意：
我们说数组\(a\)是互质的，当且仅当\(gcd(a_1,a_2,a_3,\cdots,a_n)=1\)。
给定\(k\)，对于每个\(i\;(1\leq i\leq k)\)，求出长度为\(n\)，且其中元素为\(1\)到\(i\)中的正整数的互质数组的个数。
答案对1000000007取模，再通过玄学的方式算出最终答案。
题解：
容斥+数论（莫比乌斯函数）。
考虑容斥，先计算所有的个数，再扣掉元素是\(2\)的倍数的数组的个数，\(3\)的倍数……
\(4\)的倍数不用扣掉，因为\(2\)已经扣掉过了。
但是\(6\)的倍数被\(2\)和\(3\)扣掉了两遍，要加回来。
对于是\(x\)的倍数，容斥系数就是\(\mu(x)\)——\(x\)的莫比乌斯函数。
对于\(i\)的答案，是\(\sum_{j=1}^{i}\mu(j)(\left\lfloor\frac{i}{j}\right\rfloor)^n\)。
对于每个\(i\)，我们使用差分的技巧统计答案。
#include<cstdio>
#define Mod 1000000007
int n,k,Ans;
bool isnprime[]={,};
int mobius[]={,};
int primes[],pnum;
int ans[];
int pows[];
void Mobius(int num){
for(int i=;i<=num;++i){
if(!isnprime[i])
primes[++pnum]=i, mobius[i]=-;
for(int j=;j<=pnum&&i*primes[j]<=num;++j){
isnprime[i*primes[j]]=;
if(i%primes[j]==) break;
mobius[i*primes[j]]=-mobius[i];
}
}
}
inline int Pow(int base,int exp){
int sum=;
while(exp){
if(exp&) sum=(long long)sum*base%Mod;
base=(long long)base*base%Mod; exp>>=;
} return sum;
}
int main(){
scanf("%d%d",&n,&k);
Mobius(k);
pows[]=;
for(int i=;i<=k;++i) pows[i]=Pow(i,n);
for(int i=;i<=k;++i){
if(!mobius[i]) continue;
for(int j=;j*i<=k;++j){
ans[j*i]-=mobius[i]*pows[j-];
ans[j*i]+=mobius[i]*pows[j];
ans[j*i]=((ans[j*i]%Mod)+Mod)%Mod;
}
}
for(int i=;i<=k;++i) ans[i]=(ans[i-]+ans[i])%Mod, Ans=(Ans+(ans[i]^i))%Mod;
printf("%d",Ans);
return ;
}