继续闷声作大死。
手速场的悲哀。
T4表不知道为什么叫不上去。
贴一下code好了。
T1
#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘; return x*f; } typedef long long ll; int f(int a,int b) {return !b?0:f(b,a%b)+a/b;} void solve() { int n=read(),m=read(); printf("%d\n",f(n,m)); } int main() { dwn(T,read(),1) solve(); return 0; }
T2
#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘; return x*f; } typedef long long ll; int n,A[15],x[15],y[15],vis[10][10]; void solve() { n=read(); rep(i,1,n) { A[i]=read(); x[i]=(A[i]-1)/3;y[i]=(A[i]-1)%3; } rep(i,1,n) if(A[i]<1||A[i]>9) { puts("invalid");return; } if(n<4) { puts("invalid");return; } memset(vis,0,sizeof(vis)); vis[x[1]][y[1]]=1; rep(i,2,n) { if(vis[x[i]][y[i]]) { puts("invalid");return; } if(x[i]==x[i-1]&&abs(y[i]-y[i-1])==2&&!vis[x[i]][(y[i]+y[i-1])/2]) { puts("invalid");return; } if(y[i]==y[i-1]&&abs(x[i]-x[i-1])==2&&!vis[(x[i]+x[i-1])/2][y[i]]) { puts("invalid");return; } if(abs(y[i]-y[i-1])==2&&abs(x[i]-x[i-1])==2&&!vis[1][1]) { puts("invalid");return; } vis[x[i]][y[i]]=1; } puts("valid"); } int main() { dwn(T,read(),1) solve(); return 0; }
T3
#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘; return x*f; } typedef long long ll; const int maxn=2010; const int mod=1000000007; int n; ll f[maxn][26][5]; void solve() { n=read(); memset(f,0,sizeof(f)); rep(i,0,25) f[1][i][1]=1; rep(i,1,n-1) rep(j,0,25) rep(k,1,3) { ll& ans=f[i][j][k]; if(k+1<=3) (f[i+1][j][k+1]+=ans)%=mod; rep(w,0,25) if(j!=w) (f[i+1][w][1]+=ans)%=mod; } ll ans=0; rep(j,0,25) rep(k,1,3) (ans+=f[n][j][k])%=mod; printf("%I64d\n",ans); } int main() { dwn(T,read(),1) solve(); return 0; }
T4（TLE）
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i;i=next[i]) using namespace std; const int BufferSize=1<<16; char buffer[BufferSize],*head,*tail; inline char Getchar() { if(head==tail) { int l=fread(buffer,1,BufferSize,stdin); tail=(head=buffer)+l; } return *head++; } inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘; return x*f; } const int maxn=5010; int n,m,sumv[maxn*3],is[maxn]; void build(int o,int l,int r) { if(l==r) sumv[o]=1,is[l]=0; else { int mid=l+r>>1,lc=o<<1,rc=lc|1; build(lc,l,mid);build(rc,mid+1,r); sumv[o]=sumv[lc]+sumv[rc]; } } void update(int o,int l,int r,int p) { if(l==r) sumv[o]--,is[l]=1; else { int mid=l+r>>1,lc=o<<1,rc=lc|1; if(p<=sumv[lc]) update(lc,l,mid,p); else update(rc,mid+1,r,p-sumv[lc]); sumv[o]=sumv[lc]+sumv[rc]; } } void solve() { m=n=read();build(1,1,n); int p=0; rep(i,1,n-1) { (p+=i-1)%=m; update(1,1,n,p+1); m--; } rep(i,1,n) if(!is[i]) printf("%d\n",i); } int main() { dwn(T,read(),1) solve(); return 0; }
T5
#include<cstdio> #include<cctype> #include<queue> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘; return x*f; } typedef long long ll; const int maxn=510; const int maxm=600010; const int inf=1e9; struct ZKW { int n,m,s,t; ll cost,ans; int first[maxn],next[maxm]; struct Edge {int from,to,flow;ll cost;}edges[maxm]; int inq[maxn],vis[maxn]; ll d[maxn]; void init(int n) { this->n=n;m=0; fill(first+1,first+n+1,-1); fill(inq+1,inq+n+1,0); cost=ans=0; } void AddEdge(int u,int v,int cap,ll cost) { edges[m]=(Edge){u,v,cap,cost};next[m]=first[u];first[u]=m++; edges[m]=(Edge){v,u,0,-cost};next[m]=first[v];first[v]=m++; } int BFS() { fill(d+1,d+n+1,1ll<<60);d[t]=0; deque<int> Q;Q.push_front(t); while(!Q.empty()) { int x=Q.front();Q.pop_front();inq[x]=0; ren { Edge& e=edges[i^1]; if(e.flow&&d[e.from]>d[x]+e.cost) { d[e.from]=d[x]+e.cost; if(!inq[e.from]) { if(!Q.empty()&&d[e.from]<d[Q.front()]) Q.push_front(e.from); else Q.push_back(e.from); } } } } rep(i,0,m-1) edges[i].cost+=d[edges[i].to]-d[edges[i].from];cost+=d[s]; return cost<0; } int DFS(int x,int a) { if(x==t||!a) {ans+=a*cost;return a;} int flow=0,f;vis[x]=1; ren { Edge& e=edges[i]; if(!e.cost&&e.flow&&!vis[e.to]&&(f=DFS(e.to,min(a,e.flow)))) { e.flow-=f;edges[i^1].flow+=f; flow+=f;a-=f;if(!a) break; } } return flow; } ll solve(int s,int t) { this->s=s;this->t=t;ans=cost=0; while(BFS()) do fill(vis+1,vis+n+1,0);while(DFS(s,2*inf)); return ans; } }sol; int n,k,m,p,q,P[maxn],s[maxn],t[maxn]; void solve() { ll res=0,mx=0; n=read();k=read(); rep(i,1,n) P[i]=read(); m=read();p=read();q=read(); rep(i,1,m) s[i]=read(),t[i]=read(); rep(i,1,p-1) mx+=P[i]; if(mx>k) { puts("No solution"); return; } int S=2*n+1,T=2*n+2,Pre=2*n+3,New=2*n+4;sol.init(2*n+4); sol.AddEdge(S,Pre,k,0);sol.AddEdge(S,New,inf,q); rep(i,1,n) { sol.AddEdge(i,i+n,P[i],-inf),res+=(ll)P[i]*inf; sol.AddEdge(i+n,T,inf,0); if(i<n) sol.AddEdge(i,i+1,inf,0); rep(j,1,m) if(i+t[j]<=n) sol.AddEdge(i+n,i+t[j],inf,s[j]); } rep(i,1,n) sol.AddEdge(Pre,i,inf,0); rep(i,p,n) sol.AddEdge(New,i,inf,0); res+=sol.solve(S,T); if(res>=inf) puts("No solution"); else printf("%I64d\n",res); } int main() { dwn(T,read(),1) solve(); return 0; }
原文：http://www.cnblogs.com/wzj-is-a-juruo/p/5271211.html
