https://codeforces.com/contest/1205
A. Almost Equal
随便构造一下吧…太水了不说了,放个代码吧。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
| #include<bits/stdc++.h> using namespace std; void read(int &x) { x=0;int f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f; } void print(int x) { if(x<0) putchar('-'),x=-x; if(!x) return ;print(x/10),putchar(x%10+48); } void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');} #define lf double #define pii pair<int,int > #define vec vector<int > #define pb push_back #define mp make_pair #define fr first #define sc second #define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++) const int maxn = 1e6+10; const int inf = 1e9; const lf eps = 1e-8; const int mod = 1e9+7; int n,a[maxn]; int main() { read(n);if(!(n&1)) return puts("NO"),0; puts("YES"); for(int i=1,p=1;i<=n;i++,p^=1) if(p) a[i]=i; else a[i]=n*2-i+2; for(int i=1+n,p=1;i<=n*2;i++,p^=1) if(p) a[i]=a[i-n]+1; else a[i]=a[i-n]-1; for(int i=1;i<=n*2;i++) printf("%d ",a[i]);puts(""); return 0; }
|
B. Shortest Cycle
很显然可以发现每一位至多只能有两个数这一位是$1$,否则我们就得到了一个最小的长度为$3$的环。
那么一共就只有$100$多个点了,直接$\rm floyd$找最小环就好了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
| #include<bits/stdc++.h> using namespace std; #define int long long void read(int &x) { x=0;int f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f; } void print(int x) { if(x<0) putchar('-'),x=-x; if(!x) return ;print(x/10),putchar(x%10+48); } void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');} #define lf double #define pii pair<int,int > #define vec vector<int > #define pb push_back #define mp make_pair #define fr first #define sc second #define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++) const int maxn = 1e6+10; const int inf = 1e8; const lf eps = 1e-8; const int mod = 1e9+7; int dis[150][150],n,a[maxn],w[150][150]; int cmp(int a,int b) {return a>b;} signed main() { read(n); for(int i=1;i<=n;i++) read(a[i]); sort(a+1,a+n+1,cmp);while(n&&a[n]==0) n--; if(n>130) return puts("3"),0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j]=w[i][j]=inf; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if((a[i]&a[j])&&i!=j) dis[i][j]=w[i][j]=1; int ans=inf; for(int k=1;k<=n;k++) { for(int i=1;i<k;i++) for(int j=i+1;j<k;j++) ans=min(ans,dis[i][j]+w[i][k]+w[k][j]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); }write(ans==inf?-1:ans); return 0; }
|
C. Palindromic Paths
好多细节然后比赛的时候没写出来。。。
首先可以发现我们可以先处理出每个$i+j$为偶数的点,然后假设$(1,2)$为$0$,也能处理出$i+j$为奇数的点。
现在得到的这张图如果错误只有可能是所有奇数点反过来了。
我们一定能在主对称轴上找到一个$3\times 3$的矩形满足$s_{i,i}=1,s_{i+2,i+2}=0,i\%2=1$,其中矩形是$(i,i)\sim (i+2,i+2)$,$s$表示当前点的值。
那么我们就把问题转化成了$n=3$。
那么我们询问$(1,1),(2,3)$和$(1,2),(3,3)$,然后随便判一下就好了(细节真的多。。),具体参考下代码。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
| #include<bits/stdc++.h> using namespace std; void read(int &x) { x=0;int f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f; } void print(int x) { if(x<0) putchar('-'),x=-x; if(!x) return ;print(x/10),putchar(x%10+48); } void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');} #define lf double #define pii pair<int,int > #define vec vector<int > #define pb push_back #define mp make_pair #define fr first #define sc second #define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++) const int maxn = 1e6+10; const int inf = 1e9; const lf eps = 1e-8; const int mod = 1e9+7; int s[55][55],n; int query(int x,int y,int xx,int yy) { printf("? %d %d %d %d\n",x,y,xx,yy);fflush(stdout); int bo;read(bo);return bo; } void get(int x,int y,int xx,int yy) { if(query(x,y,xx,yy)) s[xx][yy]=s[x][y]; else s[xx][yy]=!s[x][y]; } int main() { read(n); s[1][1]=1;int p=0; get(1,1,2,2),get(1,1,1,3),get(1,1,3,1),get(2,2,3,3); get(1,2,3,2),get(1,2,2,3);s[2][1]=query(2,1,2,3)?s[2][3]:!s[2][3]; for(int i=4;i<=n;i++) for(int j=1;j<=3;j++) get(i-2,j,i,j); for(int i=1;i<=n;i++) for(int j=4;j<=n;j++) get(i,j-2,i,j); for(int i=1;i<=n;i+=2) { if(!(s[i][i]==1&&s[i+2][i+2]==0)) continue; if(query(i,i,i+1,i+2)) p=!s[i+1][i+2]; else if(query(i,i+1,i+2,i+2)) p=s[i][i+1]; else { if(s[i][i+1]==s[i+1][i+2]) p=s[i][i+1]==s[i][i+2]; else p=!s[i][i+1]; }break; } puts("!"); for(int i=1;i<=n;i++,puts("")) for(int j=1;j<=n;j++) if((i+j-1)&1) printf("%d",s[i][j]); else printf("%d",s[i][j]^p); fflush(stdout); return 0; }
|
D. Almost All
挺神的题。。反正我没想到
首先考虑个子问题,假设我们现在有棵$n$个点的数,如何凑出$[0,n-1]$。
那么假设根节点有$k$个儿子分别为$x_1..x_k$,那么对于某个儿子$x_p$给这条边附上$1+\sum_{i=1}^{p-1}sz_{x_i}$的权值,然后递归做子问题就好了,正确性显然。
那么如果我们能找到一个点,然后把这个点的儿子分成两份,假设前一份$sz$之和为$a$,后一份为$b$,我们就可以凑出$ab+a-1$个值,因为我们可以把后一份整体乘上$a+1$。
那么这个数最大显然是要$a,b$越接近越好,所以如果选定一个点,那么我们每次把最小的两个儿子合并一定最优。
可以发现如果我们选重心可以最大化这个东西:
- 如果当前有$4$个儿子,并且每个都小于$n/2$,那么显然合法。
- 如果只有三个,最大的那个一定会大于$n/3$小于$n/2$,把两个小的合并就合法了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
| #include<bits/stdc++.h> using namespace std; void read(int &x) { x=0;int f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f; } void print(int x) { if(x<0) putchar('-'),x=-x; if(!x) return ;print(x/10),putchar(x%10+48); } void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');} #define lf double #define pii pair<int,int > #define vec vector<int > #define pb push_back #define mp make_pair #define fr first #define sc second #define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++) const int maxn = 1e6+10; const int inf = 1e9; const lf eps = 1e-8; const int mod = 1e9+7; int rt,f[maxn],sz[maxn],head[maxn],tot,n; struct edge{int to,nxt;}e[maxn<<1]; void ins(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;} void get_rt(int x,int fa) { sz[x]=1; for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa) get_rt(e[i].to,x),sz[x]+=sz[e[i].to],f[x]=max(f[x],sz[e[i].to]); f[x]=max(f[x],n-sz[x]); if(f[x]<f[rt]) rt=x; } priority_queue<pair<int,int > > q; int fa[maxn]; int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);} void put_ans(int x,int fa,int t) { int p=1; for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa) { printf("%d %d %lld\n",x,e[i].to,1ll*p*t); put_ans(e[i].to,x,t);p+=sz[e[i].to]; } } int main() { read(n); if(n==1) return 0; if(n==2) return puts("1 2 1"),0; for(int i=1;i<=n;i++) fa[i]=i; for(int x,y,i=1;i<n;i++) read(x),read(y),ins(x,y),ins(y,x); f[rt]=1e9;get_rt(1,0); int x=rt; for(int v,i=head[x];i;i=e[i].nxt) get_rt(v=e[i].to,x),q.push(mp(-sz[v],v)); while(q.size()>2) { int x=q.top().sc,a=q.top().fr;q.pop(); int y=q.top().sc,b=q.top().fr;q.pop(); fa[find(y)]=find(x); q.push(mp(a+b,x)); } int a=q.top().sc,s=-q.top().fr;q.pop(); int b=q.top().sc;q.pop(); int p=1; for(int i=head[x];i;i=e[i].nxt) if(find(e[i].to)==a) { printf("%d %d %d\n",x,e[i].to,p); put_ans(e[i].to,x,1),p+=sz[e[i].to]; } p=1; for(int i=head[x];i;i=e[i].nxt) if(find(e[i].to)==b) { printf("%d %d %lld\n",x,e[i].to,1ll*p*(s+1)); put_ans(e[i].to,x,s+1),p+=sz[e[i].to]; } return 0; }
|
E. Expected Value Again
显然可以发现如果串$s$有一个长度为$i$的答案,那么当且仅当$s$有一个长度为$|s|-i$的循环节。
设$p_x(s)$表示$s$有没有长度为$x$的循环节,有为$1$,否则为$0$。
那么答案可以写成$E((p_1(s)+p_2(s)+\cdots +p_{n-1}(s))^2)$。
那么根据期望的线性性,直接把里面展开答案就是:
也就是说对于一个$i,j$,如果$s$同时有长度为$i,j$的循环节就会给期望贡献一种方案,假设我们把所有必须相等的位置连边,就会给期望一个$k^{cnt-n}$的贡献,其中$cnt$是连通块的个数。
这里假设$i>j$,否则也是一样的。
那么我们可以把这$n$个位置分成$i$组写成一个环,也就是$\bmod i $的剩余系。
那么$i$的关系以及处理完了,我们需要在这个环上面连边,也就是$x$向$(x+j) \bmod i$连边。
如果$i+j\leqslant n$,那么环上每个点都能向后连边,显然会构成$\gcd(i,j)$个连通块。
否则环上只有前$n-j$个点可以连边,我们考虑能形成多少个环,假设有$c$个,那么答案就是$n-(n-i)-(n-j)+c=i+j-n+c$。
画个图就知道,第一条连成环的边起点是$i-\gcd(i,j)+1$,所以一共会连成$\max(0,n-j-(i-\gcd(i,j)+1)+1)$。
那么代上去答案就是$\max(i+j-n,\gcd(i,j))$。
那么整合一下上面的东西,题目求的答案就是:
然后大力出奇迹就好了,其实后面的计算并不是重点,稍微说一下吧。
考虑枚举$\gcd(i,j)$和$i+j$的值:
$cnt$的定义(注意下面都是整除):
反演一下:
带上去算就好了。
$cnt$一共有$O(n\log n)$个,每次计算一行$cnt$要$O(n\log n)$,所以总复杂度大概是$O(n\log ^2 n)$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
| #include<bits/stdc++.h> using namespace std; void read(int &x) { x=0;int f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f; } void print(int x) { if(x<0) putchar('-'),x=-x; if(!x) return ;print(x/10),putchar(x%10+48); } void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');} #define lf double #define pii pair<int,int > #define vec vector<int > #define pb push_back #define mp make_pair #define fr first #define sc second #define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++) const int maxn = 2e5+10; const int inf = 1e9; const lf eps = 1e-8; const int mod = 1e9+7; int n,k,pri[maxn],tot,mu[maxn],vis[maxn],pw[maxn],cnt[maxn]; void sieve() { mu[1]=1; for(int i=2;i<maxn;i++) { if(!vis[i]) pri[++tot]=i,mu[i]=-1; for(int j=1;j<=tot&&i*pri[j]<maxn;j++) { vis[i*pri[j]]=1; if(i%pri[j]==0) break; mu[i*pri[j]]=-mu[i]; } } } int qpow(int a,int x) { int res=1; for(;x;x>>=1,a=1ll*a*a%mod) if(x&1) res=1ll*res*a%mod; return res; } int main() { read(n),read(k);sieve(); pw[0]=1;int ans=0; for(int i=1;i<=n;i++) pw[i]=1ll*pw[i-1]*k%mod; for(int d=1;d<=n-1;d++) { int m=(2*n-2)/d; for(int t=1;t<=m;t++) for(int s=t;s<=m;s+=t) cnt[s]+=mu[t]*(min(s-1,(n-1)/d)/t-max(0,(s*d-n)/d)/t); for(int s=1;s<=m;s++) ans=(ans+1ll*pw[max(s*d-n,d)]*cnt[s]%mod)%mod; for(int i=0;i<=m+2;i++) cnt[i]=0; }ans=1ll*ans*qpow(qpow(k,n),mod-2)%mod; write(ans); return 0; }
|
F. Beauty of a Permutation
太神啦写不动…好像是新的黑科技,叫什么析合树。