【SinGuLaRiTy-1037】 Copyright (c) SinGuLaRiTy 2017. All Rights Reserved.
Chess
Time Limit: 2000/1000 MS (Java/Others) 
Memory Limit: 32768/32768 K (Java/Others)Sample Output
1
Code
基本组合数学求组合数
#include<cstring> #include<cstdio> #include<cmath> #include<algorithm> #include<iostream> #include<cstdlib> #define MAXN 1010 #define LL long long using namespace std; int T; LL n,m,p=1000000007; LL quick_mod(LL a,LL b) { LL ans=1; a%=p; while(b) { if(b&1) { ans=ans*a%p; b--; } b>>=1; a=a*a%p; } return ans; } LL C(LL n,LL m) { if(m>n) return 0; LL ans=1; for(int i=1;i<=m;i++) { LL a=(n+i-m)%p; LL b=i%p; ans=ans*(a*quick_mod(b,p-2)%p)%p; } return ans; } LL Lucas(LL n,LL m) { if(m==0) return 1; return C(n%p,m%p)*Lucas(n/p,m/p)%p; } int main() { scanf("%d",&T); while(T--) { cin>>n>>m; if(n>m) swap(n,m); if(n==0||m==0) { cout<<0; continue; } cout<<Lucas(m,n)<<endl; } return 0; }
Factory
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 132768/132768 K (Java/Others)
Sample Output
1
0
0
Code
预处理LCA+容斥原理
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<vector> #define inf 0x3f3f3f3f using namespace std; int fa[100010],anc[100010][32],deep[100010],dis[100010]; struct node { int to; int val; }; vector<struct node > edge[100010]; int T,n,m; vector<int > vec[100010]; void dfs(int x) { anc[x][0]=fa[x]; for(int i=1;i<=31;i++) { anc[x][i]=anc[anc[x][i-1]][i-1]; } int len=edge[x].size(); for(int i=0;i<len;i++) { struct node next=edge[x][i]; if(next.to!=fa[x]) { fa[next.to]=x; deep[next.to]=deep[x]+1; dis[next.to]=dis[x]+next.val; dfs(next.to); } } } int LCA(int x,int y) { if(deep[x]<deep[y]) swap(x,y); for(int i=31;i>=0;i--) { if(deep[y]<=deep[anc[x][i]]) { x=anc[x][i]; } } if(x==y) return x; for(int i=31;i>=0;i--) { if(anc[x][i]!=anc[y][i]) { x=anc[x][i]; y=anc[y][i]; } } return anc[x][0]; } void Init() { for(int i=0;i<=n;i++) { edge[i].clear(); vec[i].clear(); } memset(fa,0,sizeof(fa)); memset(anc,0,sizeof(anc)); } int main() { scanf("%d",&T); while(T--) { int u,v,w; scanf("%d%d",&n,&m); Init(); for(int i=1;i<n;i++) { scanf("%d%d%d",&u,&v,&w); edge[u].push_back((node){v,w}); edge[v].push_back((node){u,w}); } for(int i=1;i<=m;i++) { int x; scanf("%d",&x); for(int j=1;j<=x;j++) { int y; scanf("%d",&y); vec[i].push_back(y); } } fa[1]=1; dfs(1); int q; scanf("%d",&q); while(q--) { int ans=inf; scanf("%d%d",&u,&v); int l1=vec[u].size(); int l2=vec[v].size(); for(int i=0;i<l1;i++) { for(int j=0;j<l2;j++) { int lca=LCA(vec[u][i],vec[v][j]); ans=min(ans,dis[vec[u][i]]+dis[vec[v][j]]-dis[lca]*2); } } printf("%d ",ans); } } return 0; }
度度熊的交易计划
Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Sample Output
23
Code
最小费用最大流
#include<cstring> #include<cstdio> #include<cmath> #include<algorithm> #include<cstdlib> #include<iostream> #include<queue> #define INF 0x3f3f3f3f #define LL long long using namespace std; const int M=2010; const int N=510; struct edge { int to; int next; int cap; int cost; } e[11000]; int head[N],tot; int d[N], pre[N], path[N]; bool vis[N]; void init() { memset(head,-1,sizeof(head)); tot=0; } void addedge(int s,int t,int cap,int cost) { e[tot].to=t; e[tot].cap=cap; e[tot].cost=cost; e[tot].next=head[s]; head[s]=tot++; e[tot].to=s; e[tot].cap=0; e[tot].cost=-cost; e[tot].next=head[t]; head[t]=tot++; } int spfa(int s,int t) { memset(d,-INF,sizeof(d)); memset(pre,-1,sizeof(pre)); memset(path,-1,sizeof(path)); memset(vis,false,sizeof(vis)); int res=d[0]; d[s]=0; vis[s]=true; queue<int>q; q.push(s); while (!q.empty()) { int u=q.front(); q.pop(); vis[u]=false; for (int i=head[u];~i;i=e[i].next) { int v=e[i].to; if (d[v]<d[u]+e[i].cost&&e[i].cap>0) { d[v]=d[u]+e[i].cost; pre[v]=u; path[v]=i; if(!vis[v]) { vis[v]=true; q.push(v); } } } } return d[t]!=res; } int MinCostMaxFlow(int s,int t,int &cost) { int flow; flow=cost=0; while(spfa(s,t)) { int minn=INF; for(int i=t;i!=s&&~i;i=pre[i]) minn=min(minn,e[path[i]].cap); for(int i=t;i!=s&&~i;i=pre[i]) { e[path[i]].cap-=minn; e[path[i]^1].cap+=minn; } if(d[t]<0) break; flow+=minn; cost+=minn*d[t]; } return flow; } int main(void) { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { init(); int s=0,t=n+1,cost; for(int i=1;i<=n;i++) { int a,b,c,d; cin>>a>>b>>c>>d; addedge(s,i,b,-a); addedge(i,t,d,c); } while(m--) { int u,v,k; cin>>u>>v>>k; addedge(u,v,INF,-k); addedge(v,u,INF,-k); } MinCostMaxFlow(s,t,cost); cout<<cost<<endl; } return 0; }
小小粉丝度度熊
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)