开一场CF自测

#26 能写多少写多少吧 A模拟就行 ```cpp #include<bits/stdc++.h> using namespace std; inline bool is(int x){ for(int i=2;i<=sqrt(x);i++){ if(x%i==0) return 0; } return 1; } inline bool check(int x){ int ans=0; for(int i=2;i<x;i++){ if(x%i==0&&is(i)) ans++; } if(ans==2) return 1; else return 0; } int main(){ int n;cin>>n;int ans=0; for(int i=2;i<=n;i++){ if(check(i)) ans++; } return printf("%d\n",ans),0; } ``` B 模拟出入栈，脑抽写错一次 -50 ```cpp #include<bits/stdc++.h> using namespace std; const int maxn=1e6+10; int n; char s[maxn]; int main(){ scanf("%s",s+1); n=strlen(s+1); int ans=0,now=0,nowans=0; for(int i=1;i<=n;i++){ if(s[i]=='(') now++; if(s[i]==')'&&now) now--,ans+=2; } return printf("%d\n",ans),0; } ``` C 为什么是黑题/jk/jk/jk，跑了算了 看完了 不难 好长的模拟 待会再写 D 好像是 很经典的括号匹配 甚至还放在了我当年卡特兰数的笔记里 转化为有一条直线$y=x+k$，你从0 0 走到n,m，每次随机向右或者向上，然后不能过线。 容斥，转化为方案数-过线方案数。 把那条线下面翻转上来。可以发现所有的不合法路径对应了一条由$(-1,k+1)$开始的路径 由组合数知识可以知道，总路径数的话是$n,m$排列数，是$n+m\choose n$ 不合法是$n+m\choose n+k+1$ 答案为$\frac{{n+m\choose n }-{n+m\choose n+k+1}}{(n+m)!}$ 然后发现上面那堆组合数可以化简。 ```cpp #include<bits/stdc++.h> using namespace std; int n,m,k; int main(){ double res=1; scanf("%d%d%d",&n,&m,&k); for(int i=0;i<=k;i++) res*=(double)(m-k+i)/(n+i+1); printf("%.4lf\n",min(max(1-res,0.0),1.0)); } ``` E 没看懂 先开F 草 没有F CE怎么都是构造题 扔了算了 写25算了 AB不写 C NOIP原题 每次更新只更新新连的两个端点即可 D 并查集就行了 远古CF题都这么奇怪的吗 ```cpp #include<bits/stdc++.h> using namespace std; const int maxn=1e6+10; int fa[maxn]; inline int getf(int x){ return x==fa[x]?x:fa[x]=getf(fa[x]); } int n,x[maxn],y[maxn]; int tot=0; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<n;i++){ int u,v; scanf("%d%d",&u,&v); int U=getf(u),V=getf(v); if(U==V) x[++tot]=u,y[tot]=v; else { fa[U]=V; } } printf("%d\n",tot); for(int i=2;i<=n;i++){ int s=getf(1); if(s!=getf(i)){ printf("%d %d %d %d\n",x[tot],y[tot],1,i); tot--; int U=getf(1),V=getf(i); fa[V]=U; } } return 0; } ```