「CF293X」Croc Champ 2013 – Round 2
A. Weird Game
两个人都应该采取贪心策略
根据规则，先取0而对方不取0则败，所以有1则取1，当然尽量取对方也是1的那些
取0的时候同理，尽量取对方是1的那些
我们模拟游戏进程得出两个人的最终序列比较即可
|
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 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define N 100005 #define pa pair<int,int> #define mod 1000000007 #define ll long long using namespace std; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,now,t[3]; char a[2000005],b[2000005]; string s[2]; int main() { n=read(); scanf("%s",a+1); scanf("%s",b+1); for(int i=1;i<=2*n;i++) if(a[i]=='1'&&b[i]=='1') { s[now].push_back('1'); now^=1; } else if(a[i]=='1')t[0]++; else if(b[i]=='1')t[1]++; else t[2]++; while(1) { if(t[now])t[now]--,s[now].push_back('1'); else { if(t[now^1])t[now^1]--; else if(t[2])t[2]--; else break; s[now].push_back('0'); } now^=1; } if(s[0]>s[1])puts("First"); else if(s[0]<s[1])puts("Second"); else puts("Draw"); return 0; } |
B. Distinct Paths
容易发现，n+m-1>K时是无解的，那么有解的棋盘就很小了，状压使用的颜色+dfs
然而这样的状态还是太多，我们发现dfs到一个格子的时候，所有未在棋盘上出现的颜色并无差别，所以只要搜其中一种将结果记录下即可
注意模运算速度感人
|
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 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define mod 1000000007 #define ll long long using namespace std; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,m,K; int a[1005][1005],s[25][25],c[25]; int bin[2005]; ll dfs(int x,int y) { if(y==m+1)x++,y=1; if(x==n+1)return 1; int t=s[x-1][y]|s[x][y-1]; int res=0,f=-1; for(int i=(1<<K)-1-t;i;i-=i&-i) { int u=bin[i&-i]; if(a[x][y]!=0&&a[x][y]!=u+1)continue; s[x][y]=t|(1<<u); c[u]++; if(c[u]==1) { if(f==-1)f=dfs(x,y+1); res+=f; } else res+=dfs(x,y+1); if(res>=mod)res-=mod; c[u]--; } return res; } int main() { n=read();m=read();K=read(); if(n+m-1>K) { puts("0"); return 0; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { a[i][j]=read(); c[a[i][j]-1]++; } for(int i=0;i<K;i++)bin[1<<i]=i; printf("%I64d\n",dfs(1,1)); return 0; } |
C. Cube Problem
\[(a+b+c)^3-a^3-b^3-c^3=3(a+b)(b+c)(c+a)\]
求出n/3的所有约数，枚举两个，算出另一个check一下即可
|
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 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define N 100005 #define pa pair<int,int> #define mod 1000000007 #define ll long long using namespace std; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } ll n,q[100005]; int ans,top; int main() { n=read(); if(n%3==0) { n/=3; for(ll i=1;i*i<=n;i++) if(n%i==0) q[++top]=i; for(int i=1;i<=top;i++) for(int j=i;j<=top;j++) { ll a=q[i],b=q[j],c=n/a/b; if(n%(a*b)==0&&(a+b+c)%2==0&&a+b>c&&a+c>b&&b+c>a) ans++,ans+=(i!=j); } } printf("%d\n",ans); return 0; } |
D. Ksusha and Square
大意是在一个凸多边形内（包括边上）随机选俩不同的格点，以它们连线为正方形对角线，求这个正方形的期望面积
正方形面积等于\(((x_1-x_2)^2+(y_1-y_2)^2)/2\)
我们要算出所有正方形面积和除以正方形个数
这个式子行列是独立的，且我们很容易可以得出凸多边形内每个x/y坐标的点的个数
发现问题转换为
求\(\sum_i \sum_j a_i \times a_j(i-j)^2\)
设\[s_0=\sum_i a_i\ ,s_1=\sum_i a_i \times i\ ,s_2=\sum_i a_i \times i^2\]则\[\sum_i \sum_j a_i \times a_j(i-j)^2\]\[=\sum_i a_i\sum_j a_j(i^2-2ij+j^2)\]\[=s_0 \times s_2-\sum_i a_i \times i\sum_j a_j(i-2j)\]\[=s_0 \times s_2-s_1^2\]
On可以得出结果注意一些精度问题
E. Close Vertices
|
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 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define mod 1000000007 #define inf 1000000000 #define ll long long using namespace std; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } double ans; int n,m=1000000; int d[2000005],u[2000005]; int x[100005],y[100005]; void solve() { for(int i=-m;i<=m;i++)d[i+m]=inf,u[i+m]=-inf; int lm=m,rm=-m; for(int i=1;i<=n;i++) lm=min(lm,x[i]),rm=max(rm,x[i]); for(int i=1;i<=n;i++) { if(x[i]==x[i+1]) { u[x[i]+m]=max(u[x[i]+m],y[i]); d[x[i]+m]=min(d[x[i]+m],y[i]); continue; } bool flag=0; if(x[i]>x[i+1]) { swap(x[i],x[i+1]),swap(y[i],y[i+1]); flag=1; } for(int j=x[i];j<=x[i+1];j++) { double now=(double)(j-x[i])/(x[i+1]-x[i])*(y[i+1]-y[i])+y[i]; d[j+m]=min((int)ceil(now),d[j+m]); u[j+m]=max((int)floor(now),u[j+m]); } if(flag) swap(x[i],x[i+1]),swap(y[i],y[i+1]); } double s0=0,s1=0,s2=0; for(ll i=lm;i<=rm;i++) { ll t=u[i+m]-d[i+m]+1; s0+=t;s1+=t*i;s2+=t*i*i; } ans+=(double)(s0*s2-s1*s1)/s0/(s0-1); } int main() { n=read(); for(int i=1;i<=n;i++) x[i]=read(),y[i]=read(); x[n+1]=x[1];y[n+1]=y[1]; solve(); for(int i=1;i<=n+1;i++) swap(x[i],y[i]); solve(); printf("%.10lf\n",ans); return 0; } |
E. Close Vertices
点分治水题
一维排序一维树状数组维护一下
就是麻烦。。
|
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 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define mod 1000000007 #define inf 1000000000 #define ll long long using namespace std; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } ll tot; int n,sum,cnt,l,w,rt; int size[100005],last[100005],f[100005]; int dep[100005],dis[100005]; int t[100005]; bool vis[100005]; vector<pair<int,int> >q; vector<int>rec; struct edge{ int to,next,v; }e[200005]; void add(int x,int val) { for(int i=x;i<=n;i+=i&-i) t[i]+=val; } int query(int x) { if(x<=0)return 0; int ans=0; for(int i=x;i;i-=i&-i) ans+=t[i]; return ans; } void insert(int u,int v,int w) { e[++cnt]=(edge){v,last[u],w};last[u]=cnt; e[++cnt]=(edge){u,last[v],w};last[v]=cnt; } void getrt(int x,int fa) { f[x]=0;size[x]=1; for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa&&!vis[e[i].to]) { getrt(e[i].to,x); size[x]+=size[e[i].to]; f[x]=max(f[x],size[e[i].to]); } f[x]=max(f[x],sum-size[x]); if(f[x]<f[rt])rt=x; } void getdp(int x,int fa) { q.push_back(make_pair(dis[x],dep[x])); for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa&&!vis[e[i].to]) { dep[e[i].to]=dep[x]+1; dis[e[i].to]=dis[x]+e[i].v; getdp(e[i].to,x); } } ll cal() { int now=0;ll ans=0; sort(q.begin(),q.end()); for(int i=(int)q.size()-1;i>=0;i--) { while(now<q.size()&&q[now].first+q[i].first<=w) { add(q[now].second,1); rec.push_back(q[now].second); now++; } if(q[i].first*2<=w&&q[i].second*2<=l)ans--; ans+=query(l-q[i].second); } return ans/2; } void ini() { q.clear(); for(int i=0;i<rec.size();i++) add(rec[i],-1); rec.clear(); } void solve(int x) { vis[x]=1; for(int i=last[x];i;i=e[i].next) if(!vis[e[i].to]) { dep[e[i].to]=1; dis[e[i].to]=e[i].v; getdp(e[i].to,x); } for(int i=0;i<q.size();i++) if(q[i].first<=w&&q[i].second<=l)tot++; tot+=cal();ini(); for(int i=last[x];i;i=e[i].next) if(!vis[e[i].to]) { dep[e[i].to]=1; dis[e[i].to]=e[i].v; getdp(e[i].to,x); tot-=cal();ini(); } for(int i=last[x];i;i=e[i].next) if(!vis[e[i].to]) { sum=size[e[i].to];rt=0; getrt(e[i].to,0); solve(rt); } } int main() { n=read();l=read();w=read(); for(int i=2;i<=n;i++) { int p=read(),w=read(); insert(p,i,w); } rt=0;f[0]=inf;sum=n; getrt(1,0); solve(rt); cout<<tot<<endl; return 0; } |
计数器 9786133
OI 课件=>
OI 课件=>
求题目
请问题目在哪里可以找到= =