problem D(10) Popcorn n个物品取m个方法数C(n,m)
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e3+20; int main() { //freopen("popcorn.in","r",stdin); int t; cin>>t; while(t--) { int n,m,ans=1; cin>>n>>m; //C(n,m)=n!/(n-m)!m! //=n-m+1..n / 1..m for(int i=1;i<=m;i++) { ans*=n-i+1; ans/=i; } cout<<ans<<endl; } return 0; }Problem H(20) Commandos(简单DP)
10*10*10三维地图,点A(F,Y,X)每次可以移动到(F-1,Y,X),(F,Y+1,X),(F,Y,X+1)； 有N<=1e3个地点(F,Y,X)有人质a[i] 求从点(10,1,1)出发最多能救多少人质 从移动方式得出该图是为无环的 所以dp[f][x][y]表示从(f,x,y)出发最多能救多少人 记忆化转移状态即可 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=20; int n; int g[N][N][N],dp[N][N][N]; int DP(int f,int x,int y) { if(dp[f][x][y]!=-1) return dp[f][x][y]; int &res=dp[f][x][y]; if(f<1||x>10||y>10) return 0; res=max(DP(f-1,x,y),max(DP(f,x+1,y),DP(f,x,y+1)))+g[f][x][y]; return res; } int main() { //freopen("commandos.in","r",stdin); int t; cin>>t; while(t--) { int f,x,y,h; cin>>n; memset(dp,-1,sizeof(dp)); memset(g,0,sizeof(g)); for(int i=0;i<n;i++) { cin>>f>>x>>y>>h; g[f][x][y]=h; } cout<<DP(10,1,1)<<endl; } return 0; } Problem E(30) Jumping (建图后BFS)题意:x轴上有点1~N,每个点i可以跳到i-a[i],i+a[i].求每个点i跳到n的最少次数 不是无环图 无法DP. 建图:若i能跳到j 则j->i 连接一条边,初始时把定点n压入队列做BFS从小到大更新答案即可 O(2*N)
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+20; const int inf=2e6; int n,a[N],ans[N],vis[N]; vector<int> e[N]; struct node{ int u,d; node(int a,int b):u(a),d(b) { } }; queue<node> q; void bfs() { while(!q.empty()) q.pop(); q.push(node(n,0)); ans[n]=0; vis[n]=1; while(!q.empty()) { node t=q.front(); q.pop(); int u=t.u,d=t.d; for(int i=0;i<e[u].size();i++) { int v=e[u][i]; if(!vis[v]) { vis[v]=1; ans[v]=d+1; q.push(node(v,d+1)); } } } } int main() { // freopen("jumping.in","r",stdin); int t; cin>>t; while(t--) { cin>>n; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) { ans[i]=-1; scanf("%d",&a[i]); //i能到j j->i if(i-a[i]>=1) e[i-a[i]].push_back(i); if(i+a[i]<=n) e[i+a[i]].push_back(i); } bfs(); for(int i=1;i<=n;i++) printf("%d\n",ans[i]),e[i].clear(); } return 0; } Problem J(40) Whistle's to the car (dfs+树上差分)题意:n个结点,带权的树,v控制u当且仅当 u为v的子孙&& dist[u,v]<=a[u],n<=2e5,问每个结点控制的数量? 设d[i]为i->rt的距离,dist[u,v]=d[u]-d[v],根据u来更新答案,控制u的v必须满足 ,d[v]>=d[u]-a[u] d[i]随着深度递增,若在dfs过程中保存u的祖先的d值,可以二分找到第一个满足的pos,则ans[pos~fa[u]]都应该+1 怎么判断祖先v被加了多少次? sum[pos~fa[u]]+1,在树上进行差分:让sum[fa[pos]]--,sum[fa[u]]++,问v被加了多少次? 只要累加v的子树的sum,(v不在某个u的[pos~fa[u],则累加时,该段sum被抵消)
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> ii; const int N=2e6+20; ll a[N],sum[N],d[N],n; vector<ii> e[N];//w,v vector<ii> que; void dfs(int u,int fa) { sum[fa]++; ll t=d[u]-a[u]; int pos=lower_bound(que.begin(),que.end(),ii(t,0))-que.begin(); pos--;//fa[pos] if(pos>=0) sum[que[pos].second]--; que.push_back(ii(d[u],u)); for(int i=0;i<e[u].size();i++) { ll v=e[u][i].second,w=e[u][i].first; if(v==fa) continue; d[v]=d[u]+w; dfs(v,u); sum[u]+=sum[v];// } que.pop_back();//u不在为任何结点的祖先 } int main() { freopen("car.in","r",stdin); int t; cin>>t; while(t--) { cin>>n; for(int i=1;i<=n;i++) scanf("%I64d",&a[i]),e[i].clear(),sum[i]=0,d[i]=0; ll p,w; int i; for(int k=2;k<=n;k++) { scanf("%d%I64d%I64d",&i,&p,&w); e[i].push_back(ii(w,p)); e[p].push_back(ii(w,i)); } dfs(1,0); for(int i=1;i<=n;i++) printf("%I64d%c",sum[i],i==n?'\n':' '); } return 0; }Problem G(40) The Galactic Olympics 排列+第二类Stirling数
题意:k不同个人,n场不同比赛 k<=1e6,n<=1e3,每人至少要参加一场比赛,问方法数? 先转化成:对于n个不同的球放入,k个相同的盒子 每个盒子不为空方法数 即第二类Stirling 考虑最后一个人单独一个盒子 或者放到某个盒子中.则S(n,k)=S(n-1,k-1)+S(n-1,k)*k 最后在考虑k个人的顺序 ans=S(n,k)*k!
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e3+20; const ll mod=1e9+7; ll S[N][N]; int main() { // freopen("galactic.in","r",stdin); memset(S,0,sizeof(S)); S[0][0]=S[1][1]=1; for(ll i=2;i<=2000;i++) { for(ll j=1;j<=i;j++) { S[i][j]=(S[i-1][j-1]+S[i-1][j]*(ll)j)%mod; } } int t; cin>>t; while(t--) { ll n,k; cin>>n>>k; if(k>n) { puts("0"); continue; } ll ans=S[n][k]; for(ll i=1;i<=k;i++) ans=(ans*i)%mod; cout<<ans<<endl; } return 0; }
Problem A(50) The Game of osho 博弈SG
题意:给出G(G<100)个子游戏,每个子游戏由(Bi,Ni)(Bi,Ni<=1e9),每次可以使Ni-Bi^k(k=0,1,2..) Bi^k<=Ni 玩家可以选择任意一个子游戏操作,不能操作算输 子游戏:相当于nim游戏中的一堆石子 因为b^0=1 所以最终局面肯定为(0,0...0),求出f(i):第i个子游戏的SG(mex)值若f(1)^f(2)^..f(n)=x(x!=0) 则必然有后继状态SG值为f[i]^x 则可以转移到0,所以SG值异或和!=0为必胜态(每次都可以转移到0)
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e3+20; /* ll SG(ll b,ll n) { set<ll> s; if(n==0) return 0; if(b==1) return n; ll x=1; while(x<=n) { s.insert(SG(b,n-x)); x=x*b; } ll y=0; while(s.count(y))//logn(b) y++; return y; } */ //打表得规律 ll calc_SG(ll b,ll n) { if(b%2) { if(n%2) return (ll)1; else return (ll)0; } else { if((n-b)%(b+1)==0) return (ll)2; ll p=n/(b+1);//反转多少次 (1,0)->(0,1)->(1,0) ... if(p%2) return n%2==0; else return n%2; } } int main() { //freopen("powers.in","r",stdin); int t; cin>>t; while(t--) { ll G,b,n; cin>>G; ll ans=0; for(int i=0;i<G;i++) { cin>>b>>n; ans^=calc_SG(b,n); } if(ans) puts("1"); else puts("2"); } return 0; }