Gym 100524A Astronomy ProblemGym 100524G Game of Col on Bamboo ForestsGym 100512B Betting FastGym 100512D Dynamic LCA

Gym 100524A Astronomy Problem

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> #include<iomanip> #include<vector> #include<string> #include<queue> #include<stack> #include<map> #include<sstream> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (1000000007) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector<int> #define pi pair<int,int> #define SI(a) ((a).size()) #define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans); #define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl; #define PRi2D(a,n,m) For(i,n) { \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } #pragma comment(linker, "/STACK:102400000,102400000") typedef __int64 ll; typedef long double ld; typedef unsigned long long ull; typedef pair<ll,ll> pll; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return ((a-b)%F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } int n,m; #define MAXN (3010) pair<ll,ll> p[MAXN]; ll len(pll a){return a.fi*a.fi+a.se*a.se;} bool cmp(pll a,pll b) { if(len(a)==len(b)) return a.se<b.se; return len(a)<len(b); } ll a2[MAXN]; int n2; ll find(ll x){ return lower_bound(a2,a2+n2,x)-a2; } ll find(ll x,vector<ll> &v){ return lower_bound(v.begin(),v.end(),x)-v.begin(); } int id[MAXN]; vector<ll> v[MAXN*MAXN]; bool B[MAXN*MAXN]={0}; int main() { freopen("astronomy.in","r",stdin); freopen("astronomy.out","w",stdout); while(cin>>n&&n) { MEM(B) Rep(i,n) p[i].fi=read(),p[i].se=read(); sort(p,p+n,cmp); Rep(i,n) a2[i]=len(p[i]); n2=unique(a2,a2+n)-a2; Rep(i,n) id[i]=find(len(p[i])); Rep(i,n) Fork(j,i+1,n-1) v[id[i]*n2+id[j]].pb(len(mp(p[i].fi-p[j].fi,p[i].se-p[j].se))); m=read(); Rep(i,m) { ll a,b,c; scanf("%I64d%I64d%I64d",&a,&b,&c); if (a>b) swap(a,b); int p1=find(a),p2=find(b); if(max(p1,p2)>=n2 || a2[p1]!=a || a2[p2]!=b ) { puts("0"); continue; } { int now=p1*n2+p2; if(!B[now]) sort(v[now].begin(),v[now].end()); B[now]=1; int k=upper_bound(v[now].begin(),v[now].end(),c)-lower_bound(v[now].begin(),v[now].end(),c); printf("%d\n",k); } } Rep(i,n2*n2) v[i].clear(); } return 0; }

Gym 100524G Game of Col on Bamboo Forests

sg(x)=(x==1)?1:0

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> #include<iomanip> #include<vector> #include<string> #include<queue> #include<stack> #include<map> #include<sstream> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (242121643) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector<int> #define pi pair<int,int> #define SI(a) ((a).size()) #define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans); #define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl; #define PRi2D(a,n,m) For(i,n) { \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } #pragma comment(linker, "/STACK:102400000,102400000") typedef long long ll; typedef long double ld; typedef unsigned long long ull; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return ((a-b)%F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } #define MAXN (200) ll C[MAXN][MAXN]; void prework() { MEM(C) C[0][0]=1; For(i,100) { C[i][0]=1; For(j,i) C[i][j]=add(C[i-1][j-1],C[i-1][j]); } } int main() { freopen("game.in","r",stdin); freopen("game.out","w",stdout); int n,k; prework(); while(cin>>n>>k&&n&&k) { int p1=0,p2=0; For(i,n) { int c=read(); if(c==1) ++p1; else ++p2; } ll ans=0; for(int i=1;i<=p1;i+=2) { if (0<=k-i&&k-i<=p2) { upd(ans,mul(C[p1][i],C[p2][k-i])); } } cout<<ans<<endl; } return 0; }

Gym 100512B Betting Fast

发现一个秘密，每次压多比较有利

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> #include<iomanip> #include<vector> #include<string> #include<queue> #include<stack> #include<map> #include<sstream> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (1000000007) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector<int> #define pi pair<int,int> #define SI(a) ((a).size()) #define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans); #define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl; #define PRi2D(a,n,m) For(i,n) { \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } #pragma comment(linker, "/STACK:102400000,102400000") typedef long long ll; typedef long double ld; typedef unsigned long long ull; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return ((a-b)%F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } #define MAXN (100000+10) #define MAXT (100+10) int n,s,p,t; double p1,p2; double f[MAXN][MAXT]; int b[MAXN][MAXT]={0}; int cas=1; double dfs(int s,int t) { //has s yuan ,lef t games if (s==0) return 0; if (s==n) return 1; if (t==0) return 0; if (b[s][t]==cas) return f[s][t]; b[s][t]=cas; double ans=0; int x=min(s,n-s); ans=max(ans,p2*dfs(s-x,t-1)+p1*dfs(s+x,t-1)); return f[s][t]=ans; } int main() { freopen("betting.in","r",stdin); freopen("betting.out","w",stdout); while(cin>>n>>s>>p>>t) { if (n==0) return 0; p1=(double)p/100; p2=1.0-p1; printf("%.13lf\n",dfs(s,t)); cas++; } return 0; }

Gym 100512D Dynamic LCA

题意：维护树：换根+求lca

只要在图上画画就能看出规律

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> #include<vector> #include<iomanip> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) #define MAXN (600000+10) #define MAXM (600000+10) #define pb push_back #define mp make_pair #pragma comment(linker, "/STACK:1024000000,1024000000") typedef int ll; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int n,m; int edge[MAXM],Next[MAXM],Pre[MAXN],siz=1; void addedge(int u,int v) { edge[++siz]=v; Next[siz]=Pre[u]; Pre[u]=siz; } void addedge2(int u,int v){addedge(u,v);addedge(v,u);} bool vis[MAXN]; int cnt,id[MAXN]; int son[MAXN],dep[MAXN],sz[MAXN],top[MAXN],pre[MAXN],q[MAXN]; void build() { MEM(vis) cnt=0; MEM(id) MEM(son) MEM(dep) MEM(sz) MEM(top) MEM(pre) MEM(q) int r=1; vis[dep[1]=q[1]=1]=1; For(i,r) { int u=q[i]; Forp(u) { int v=edge[p]; if (vis[v]) continue; else vis[v]=1; dep[ q[++r]=v ]=dep[u]+1; pre[v]=u; } } ForD(i,r) { sz[pre[q[i]]] += ++sz[q[i]]; if (sz[son[pre[q[i]]]]<sz[q[i]] ) son[pre[q[i]]] = q[i]; } For(i,r) { if (!top[q[i]]) for(int x=q[i];x;x=son[x]) { top[x]=q[i]; id[x]=++cnt; } } } int lca(int a,int b) { while(1) { if (top[a]==top[b]) return dep[a]<=dep[b] ? a:b; if (dep[top[a]]<dep[top[b]]) swap(a,b); a=pre[top[a]]; } } int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } int main() { freopen("dynamic.in","r",stdin); freopen("dynamic.out","w",stdout); while(cin>>n&&n) { MEM(edge) MEM(Next) MEM(Pre) siz=1; For(i,n-1) addedge2(read(),read()); build(); int m=read(); int ro=1; while(m--) { char s[2]; scanf("%s",s); if (s[0]=='!') { ro=read(); } else { int u=read(),v=read(); int p=lca(u,ro),p2=lca(v,ro),p3=lca(u,v); int ans; if (p==p2) ans=p3; else if (p==p3) ans=p2; else if(p2==p3) ans=p; else ans=p3; printf("%d\n",ans); } } } return 0; }