Codeforces Round #499 (Div. 1) Solution
https://codeforces.com/contest/1010
為啥我\(\rm Div.1\)能\(A4\)題還是\(\rm specialist....\)
A. Fly
二分答案，送分題。
#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 ll long long #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 a[maxn],b[maxn],n,m;int check(lf x) {for(int i=1;i<=n-1;i++) {x-=(x+m)/(lf)a[i];x-=(x+m)/(lf)b[i+1];if(x<0) return 0;}x-=(x+m)/(lf)a[n];x-=(x+m)/(lf)b[1];if(x<0) return 0;return 1;
}int main() {read(n),read(m);FOR(i,1,n) read(a[i]);FOR(i,1,n) read(b[i]);lf l=0,r=2e9;while(r-l>1e-6) {lf mid=(l+r)*0.5;if(check(mid)) r=mid;else l=mid;}if(l>1e9) puts("-1");else printf("%.10lf\n",l);return 0;
}B. Rocket
簡單的交互題。
第一輪先每次都問\(1\)，問出這個位置是真還是假，然后二分答案就好了。
#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 ll long long #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 a[maxn],n,m;int main() {read(n),read(m);for(int i=1;i<=m;i++) {puts("1");fflush(stdout);read(a[i]);if(!a[i]) return 0;}int l=1,r=n;for(int i=m+1;i<=60;i++) {int mid=(l+r)>>1,x;write(mid);fflush(stdout);read(x);if(!x) return 0;if(x==a[(i-1)%m+1]) l=mid+1;else r=mid-1;}return 0;
}C. Border
小凱的疑惑。
先把所有數求\(\gcd\)，那么這就是我們可以湊出來的最小的非\(0\)數了，具體參見小凱的疑惑，兩個互質的數\(a,b\)不可以湊出來的最小的數是\(ab-a-b\)。
#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 ll long long #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 a[maxn],n,m,c[maxn][2],f[maxn],g[maxn],op[maxn],vis[maxn];int main() {read(n),read(m);int t=m;for(int i=1;i<=n;i++) read(a[i]),t=__gcd(t,a[i]);int x=t;while(!vis[x]) vis[x]=1,x=(x+t)%m;int ans=0;for(int i=0;i<m;i++) ans+=vis[i];write(ans);for(int i=0;i<m;i++) if(vis[i]) printf("%d ",i);puts("");return 0;
}D. Mars rover
簡單的\(\rm tree\ dp\)，設\(f[i]\)表示\(i\)的子樹傳上來的數，\(g[i]\)表示\(i\)這個點的結果反轉，忽視\(i\)的子樹，\(1\)的結果。
那么直接深搜暴力更新就好了，先更新\(f\)在更新\(g\)。
#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 ll long long #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 a[maxn],n,m,c[maxn][2],f[maxn],g[maxn],op[maxn];char s[5];void dfs(int x) {if(c[x][0]) dfs(c[x][0]);if(c[x][1]) dfs(c[x][1]);int a=f[c[x][0]],b=f[c[x][1]];if(op[x]==1) f[x]=a&b;else if(op[x]==2) f[x]=a|b;else if(op[x]==3) f[x]=a^b;else if(op[x]==4) f[x]=!a;
}void dp(int x,int fa,int e) {if(x!=1) {int o=op[fa];if(o==1) {if((f[e]&(!f[x]))!=f[fa]) g[x]=g[fa];else g[x]=f[1];} else if(o==2) {if((f[e]|(!f[x]))!=f[fa]) g[x]=g[fa];else g[x]=f[1];} else if(o==3) {if((f[e]^(!f[x]))!=f[fa]) g[x]=g[fa];else g[x]=f[1];} else if(o==4) g[x]=g[fa];}if(c[x][0]) dp(c[x][0],x,c[x][1]);if(c[x][1]) dp(c[x][1],x,c[x][0]);
}int main() {read(n);for(int i=1;i<=n;i++) {scanf("%s",s+1);if(s[1]=='A') op[i]=1;else if(s[1]=='O') op[i]=2;else if(s[1]=='X') op[i]=3;else if(s[1]=='N') op[i]=4;else op[i]=5;if(op[i]<=3) read(c[i][0]),read(c[i][1]);else if(op[i]==4) read(c[i][0]);else read(f[i]);}dfs(1);g[1]=!f[1];dp(1,0,0);for(int i=1;i<=n;i++) if(op[i]==5) putchar(g[i]+'0');return 0;
}E. Store
\(\rm kd\ tree\)，不想寫先咕著...
F. Tree
這是一道毒瘤題。
由于這題非常巧妙而且非常毒瘤我就新開了一篇來寫。
題解看這里：Codeforces Round #499 (Div. 1) F. Tree
這里扔個代碼把：
#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 ll long long #define pii pair<int,int >
#define vec vector<int >#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define _sz(x) ((int)x.size())#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++) const int maxn = 1<<19|10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 998244353;int add(int x,int y) {return x+y>=mod?x+y-mod:x+y;}
int del(int x,int y) {return x-y<0?x-y+mod:x-y;}
int mul(int x,int y) {return 1ll*x*y-1ll*x*y/mod*mod;}int qpow(int a,int x) {int res=1;for(;x;x>>=1,a=mul(a,a)) if(x&1) res=mul(res,a);return res;
}namespace poly {int N,w[maxn],pos[maxn],bit,mxn,t[2][maxn];void init(int l) {for(mxn=1;mxn<=l;mxn<<=1) ;w[0]=1,w[1]=qpow(3,(mod-1)/mxn);for(int i=2;i<=mxn;i++) w[i]=mul(w[i-1],w[1]);}void ntt(int *r,int op) {FOR(i,1,N-1) if(pos[i]>i) swap(r[pos[i]],r[i]);for(int i=1,d=mxn>>1;i<N;i<<=1,d>>=1)for(int j=0;j<N;j+=i<<1)for(int k=0;k<i;k++) {int x=r[j+k],y=mul(r[i+j+k],w[k*d]);r[j+k]=add(x,y),r[i+j+k]=del(x,y);}if(op==-1) {reverse(r+1,r+N);int d=qpow(N,mod-2);for(int i=0;i<N;i++) r[i]=mul(r[i],d);}}vec pmul(vec a,vec b) {if(1ll*_sz(a)*_sz(b)<=5000) {vec c;c.resize(_sz(a)+_sz(b)-1);FOR(i,0,_sz(a)-1) FOR(j,0,_sz(b)-1) c[i+j]=add(c[i+j],mul(a[i],b[j]));return c;}for(N=1,bit=0;N<_sz(a)+_sz(b);N<<=1,bit++);FOR(i,0,N-1) pos[i]=pos[i>>1]>>1|((i&1)<<(bit-1));FOR(i,0,_sz(a)-1) t[0][i]=a[i];FOR(i,_sz(a),N) t[0][i]=0;FOR(i,0,_sz(b)-1) t[1][i]=b[i];FOR(i,_sz(b),N) t[1][i]=0;ntt(t[0],1),ntt(t[1],1);FOR(i,0,N-1) t[0][i]=mul(t[0][i],t[1][i]);ntt(t[0],-1);vec c;FOR(i,0,_sz(a)+_sz(b)-1) c.pb(t[0][i]);return c;}vec padd(vec a,vec b) {if(_sz(a)>_sz(b)) {FOR(i,0,_sz(b)-1) a[i]=add(a[i],b[i]);return a;}FOR(i,0,_sz(a)-1) b[i]=add(a[i],b[i]);return b;}
}ll k;
int n,ch[maxn],head[maxn],tot,sz[maxn],F[maxn],cnt;
struct edge{int to,nxt;}e[maxn<<1];vec f[maxn],r[maxn];void ins(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;}void dfs(int x,int fa) {sz[x]=1;F[x]=fa;for(int i=head[x],v;i;i=e[i].nxt)if((v=e[i].to)!=fa) {dfs(v,x);sz[x]+=sz[v];if(sz[ch[x]]<sz[v]) ch[x]=v;}
}void solve(int lt,int rt,vec &a,vec &b) {if(lt==rt) return a=b=r[lt],void();vec al,ar,bl,br;int mid=(lt+rt)>>1;solve(lt,mid,al,bl),solve(mid+1,rt,ar,br);b=poly::pmul(bl,br);a=poly::padd(poly::pmul(ar,bl),al);
}vec dfs2(int x) {for(int t=x;t;t=ch[t]) {for(int i=head[t];i;i=e[i].nxt) if(e[i].to!=F[t]&&e[i].to!=ch[t]) f[t]=dfs2(e[i].to);if(_sz(f[t])<1) f[t].resize(1);f[t][0]++;f[t].insert(f[t].begin(),0);}cnt=0;for(int t=x;t;t=ch[t]) r[++cnt]=f[t];vec a,b;solve(1,cnt,a,b);return a;
}int main() {read(n),scanf("%lld",&k);poly::init(n<<1);k%=mod;for(int i=1,x,y;i<n;i++) read(x),read(y),ins(x,y),ins(y,x);dfs(1,0);vec res=dfs2(1);int t=1,ans=0;for(int i=1;i<_sz(res);i++) {ans=add(ans,mul(res[i],t));t=mul(t,mul((k+i)%mod,qpow(i,mod-2)));}write(ans);return 0;
}
函數)
