day1
主要讲的就是数据结构。。
难度从普及的栈和队列飞到了线段树。。。！！？？
我就A了一题。比较简单的并查集：支持删点。。。
workteam
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; inline int read(){ int t=1,num=0;char c=getchar(); while(c>‘9‘||c<‘0‘){if(c==‘-‘)t=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){num=num*10+c-‘0‘;c=getchar();} return num*t; } const int maxn=150010; int fa[maxn],sum,cnt[maxn],n,m,id[maxn],tot; void init(){ sum=tot=n; for(int i=1;i<=n;i++) id[i]=fa[i]=i,cnt[i]=1; } int find(int x){ if(fa[x]==x)return x; return fa[x]=find(fa[x]); } void unite(int x,int y){ x=find(x);y=find(y); if(x==y)return; fa[x]=y;sum--; cnt[y]+=cnt[x]; } void move(int x){ if(cnt[find(id[x])]<=1)return; cnt[find(id[x])]--;sum++; id[x]=++tot;fa[id[x]]=id[x]; cnt[id[x]]=1; } int main() { freopen("workteam.in","r",stdin); freopen("workteam.out","w",stdout); n=read();m=read();init(); for(int i=1;i<=m;i++){ int x=read(); if(x==1){ int a=read(),b=read(); unite(id[a],id[b]); } else if(x==2){ int a=read();move(a); } else if(x==3){ int a=read(),b=read(); if(find(id[a])==find(id[b]))puts("Yes"); else puts("No"); } else if(x==4){ int a=read(); printf("%d\n",cnt[find(id[a])]); } else printf("%d\n",sum); } return 0; }
day2嘛，
对于我也是很丧的。。
也就A了T1，就是裸的分治
road
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; int get(int n,int x,int y){ if(n==0)return 1; int mid=1<<(n-1),b=mid*mid; if(x<=mid&&y<=mid)return get(n-1,y,x); if(x<=mid&&y>mid)return b+get(n-1,x,y-mid); if(x>mid&&y>mid)return b+b+get(n-1,x-mid,y-mid); return b*3+get(n-1,mid+1-y,mid+mid+1-x); } int main() { freopen("road.in","r",stdin); freopen("road.out","w",stdout); int n,T,i1,j1,i2,j2; scanf("%d%d",&n,&T); while(T--){ scanf("%d%d%d%d",&i1,&j1,&i2,&j2); printf("%d\n",abs(get(n,i1,j1)-get(n,i2,j2))); } return 0; }
day3
恩。。好吧，这天的T1是裸的广搜，随便乱打一下就好
maze
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> using namespace std; int n,m,a[101][101],d[101][101],sx,sy,tx,ty; const int x[4]={-1,0,0,1}; const int y[4]={0,-1,1,0}; const int INF=2000000000; char c[101]; typedef pair<int,int> P; void solve(){ queue<P> q;q.push(P(sx,sy)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) d[i][j]=INF; d[sx][sy]=0; while(!q.empty()){ P p=q.front();q.pop(); int i1=p.first;int j1=p.second; for(int i=0;i<4;i++){ int i2=i1+x[i],j2=j1+y[i]; if(i2>n||i2<1||j2>m||j2<1||a[i2][j2]==0)continue; if(d[i2][j2]==INF){d[i2][j2]=d[i1][j1]+1;q.push(P(i2,j2));} if(i2==tx&&j2==ty)break; } } } int main() { freopen("maze.in","r",stdin); freopen("maze.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%s",c); for(int j=0;j<m;j++){ if(c[j]==‘S‘)sx=i,sy=j+1,a[i][j+1]=1; else if(c[j]==‘T‘)tx=i,ty=j+1,a[i][j+1]=1; else if(c[j]==‘#‘)a[i][j+1]=0; else a[i][j+1]=1; } } solve();printf("%d\n",d[tx][ty]); return 0; }
day4
这天是计算几何，丧那。
T2用极角排序，然后提取公因式。。
area
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #define LL long long using namespace std; inline int read(){ int t=1,num=0;char c=getchar(); while(c>‘9‘||c<‘0‘){if(c==‘-‘)t=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){num=num*10+c-‘0‘;c=getchar();} return num*t; } struct Yzy{int x,y;}a[2017],b[2017]; LL ans=0;int n,cnt; bool cmp(Yzy i,Yzy j){return i.x*j.y>j.x*i.y;} int main() { freopen("area.in","r",stdin); freopen("area.out","w",stdout); n=read(); for(int i=1;i<=n;i++) a[i].x=read(),a[i].y=read(); sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++){ cnt=0;LL x=0,y=0; for(int j=i+1;j<=n;j++) b[++cnt].x=a[j].x-a[i].x,b[cnt].y=a[j].y-a[i].y; sort(b+1,b+cnt+1,cmp); for(int j=1;j<=cnt;j++)x+=b[j].x,y+=b[j].y; for(int j=1;j<=cnt;j++) x-=b[j].x,y-=b[j].y,ans+=(LL)(b[j].x*y-x*b[j].y); } if(ans&1)printf("%lld.5",ans/2); else printf("%lld.0",ans/2); return 0; }
day5
这天的动态规划，也不是一般的丧
唯一做出的也只有这post
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; inline int read(){ int t=1,num=0;char c=getchar(); while(c>‘9‘||c<‘0‘){if(c==‘-‘)t=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){num=num*10+c-‘0‘;c=getchar();} return num*t; } int n,m,s[310][310],a[310],f[310][35]; int abc(int num){return num>0?num:-(num);} void init(){ memset(s,0,sizeof(s)); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++){ int mid=(i+j)/2; for(int k=i;k<=j;k++) s[i][j]+=abc(a[k]-a[mid]); } } int main() { freopen("post.in","r",stdin); freopen("post.out","w",stdout); n=read();m=read(); if(n<=m){puts("0");return 0;} for(int i=1;i<=n;i++)a[i]=read(); init();memset(f,127,sizeof(f)); for(int i=1;i<=n;i++)f[i][1]=s[1][i]; for(int i=1;i<=n;i++){ for(int j=2;j<=m;j++){ for(int k=1;k<=i-1;k++){ f[i][j]=min(f[i][j],f[k][j-1]+s[k+1][i]); } } } printf("%d\n",f[n][m]); return 0; }
day6也是动态规划。。
不过，算是做出两题
fibonacci
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; long long f[90],a[90],n,g[90][2]; int m=0,t; int main() { //freopen("fibonacci.in","r",stdin); //freopen("fibonacci.out","w",stdout); scanf("%d",&t);f[1]=1;f[2]=2; for(int i=3;i<=88;i++)f[i]=f[i-1]+f[i-2]; while(t--){ scanf("%lld",&n);m=0; for(int i=88;i>=1;i--) if(f[i]<=n)n-=f[i],a[++m]=1LL*i; for(int i=1;i<=m/2;i++)swap(a[i],a[m-i+1]); g[1][1]=1;g[1][0]=(a[1]-1)>>1; for(int i=2;i<=m;i++){ g[i][1]=g[i-1][0]+g[i-1][1]; g[i][0]=((a[i]-a[i-1]-1)>>1)*g[i-1][1] +((a[i]-a[i-1])>>1)*g[i-1][0]; } printf("%lld\n",g[m][0]+g[m][1]); } return 0; }
wolf
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int INF=1500000000; inline int read(){ int t=1,num=0;char c=getchar(); while(c>‘9‘||c<‘0‘){if(c==‘-‘)t=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){num=num*10+c-‘0‘;c=getchar();} return num*t; } int f[410][410],n,ans=0,b[410]; int main() { freopen("wolf.in","r",stdin); freopen("wolf.out","w",stdout); n=read(); for(int i=1;i<=n;i++)ans+=read(); for(int i=1;i<=n;i++)b[i]=read(); memset(f,0,sizeof(f)); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i<j)f[i][j]=INF; } } b[0]=b[n+1]=0; for(int i=1;i<=n;i++)f[i][i]=b[i-1]+b[i+1]; for(int l=1;l<=n;l++){ for(int i=1;i<=n-l;i++){ int j=i+l; for(int k=i;k<=j;k++) f[i][j]=min(f[i][j],f[i][k-1]+f[k+1][j]+b[i-1]+b[j+1]); } } printf("%d\n",ans+f[1][n]); return 0; }
day7讲的是数论
我开始觉得烦了。。。
写博客好麻烦。。。
这天嘛。。
T1小学奥数，加上快速幂，随便乱搞。。
apexis
#include<cstdio> const int mod=1e9+7; long long n,a,b,num=2,tot=1; int main() { freopen("apexis.in","r",stdin); freopen("apexis.out","w",stdout); scanf("%I64d%I64d%I64d",&a,&b,&n); if(a<b){long long c=a;a=b;b=c;} if(n&1){long long na=a+b,nb=a-b;a=na;b=nb;} n=n>>1; while(n){ if(n&1)tot=(num*tot)%mod; n=n>>1;num=(num*num)%mod; }a=(a*tot)%mod;b=(b*tot)%mod; printf("%I64d %I64d\n",a,b); return 0; }
day8讲的是图论。。
masquerade
莫名奇妙的做法。。
拿了90分
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<queue> using namespace std; inline int read(){ int t=1,num=0;char c=getchar(); while(c>‘9‘||c<‘0‘){if(c==‘-‘)t=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){num=(num<<1)+(num<<3)+c-‘0‘;c=getchar();} return num*t; } const int maxn=100010; vector<int> g[maxn]; int d[maxn],n,m,p,hel[maxn],s,t,inq[maxn],q[4*maxn],qian,hou; void add(int f,int t){g[f].push_back(t);g[t].push_back(f);} int check(int k){ qian=hou=0; memset(d,-1,sizeof(d)); memset(inq,0,sizeof(inq)); d[s]=k;q[0]=s;inq[s]=1; while(qian<=hou){ int x=q[qian++];if(!d[x]){inq[x]=0;continue;} for(int i=0;i<g[x].size();i++){ int y=g[x][i]; if(d[y]<d[x]-1){ if(hel[y])d[y]=k; else d[y]=d[x]-1; if(!inq[y]){q[++hou]=y;inq[y]=1;} } } inq[x]=0; } if(d[t]==-1)return 0; return 1; } int erfen(int l,int r){ while(l<r){ int mid=(l+r)>>1; if(check(mid)==0)l=mid+1; else r=mid; } return l; } int main() { freopen("masquerade.in","r",stdin); freopen("masquerade.out","w",stdout); int T=read(); while(T--){ n=read();m=read();p=read(); int x,y; memset(hel,0,sizeof(hel)); for(int i=1;i<=n;i++)g[i].clear(); for(int i=1;i<=p;i++){x=read();hel[x]=1;} for(int i=1;i<=m;i++){ x=read();y=read();add(x,y); } s=read();t=read(); if(s==t){puts("0");continue;}if(s>t)swap(s,t); if(!check(n+1)){puts("-1");continue;} printf("%d\n",erfen(1,n)); } return 0; }
day9.........网络流，爆0了。、
好吧，其实T1不难
chessman
把问题转换一下。看做最多能少放多少棋子
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<queue> using namespace std; inline int read(){ int t=1,num=0;char c=getchar(); while(c>‘9‘||c<‘0‘){if(c==‘-‘)t=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){num=num*10+c-‘0‘;c=getchar();} return num*t; } const int INF=10000010; struct edge{int to;int c;int rev;}; vector<edge>g[210]; int iter[210],level[210]; void add(int f,int t,int c){ g[f].push_back((edge){t,c,g[t].size()}); g[t].push_back((edge){f,0,g[f].size()-1}); } void bfs(int s){ memset(level,0,sizeof(level)); queue<int>q;level[s]=1;q.push(s); while(!q.empty()){ int v=q.front();q.pop(); for(int i=0;i<g[v].size();i++){ edge &e=g[v][i]; if(e.c>0&&level[e.to]==0){ level[e.to]=level[v]+1; q.push(e.to); } } } } int dfs(int v,int t,int f){ if(v==t)return f; for(int &i=iter[v];i<g[v].size();i++){ edge &e=g[v][i]; if(e.c>0&&level[v]+1==level[e.to]){ int d=dfs(e.to,t,min(f,e.c)); if(d>0){ e.c-=d;g[e.to][e.rev].c+=d; return d; } } } return 0; } int flow(int s,int t){ int flow=0; while(1){ bfs(s); if(level[t]==0) return flow; memset(iter,0,sizeof(iter)); int f; while((f=dfs(s,t,INF))>0)flow+=f; } } int n,m,table[110][110],p,s=0,t=205,x,y,a[210],b[210]; int main() { freopen("chessman.in","r",stdin); freopen("chessman.out","w",stdout); memset(table,0,sizeof(table)); n=read();m=read();p=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=m;i++)a[i+n]=read(); for(int i=1;i<=p;i++) x=read(),y=read(),table[x][y]=1,b[x]++,b[y+n]++; for(int i=1;i<=n;i++){ if(m-b[i]<a[i]){puts("No Solution");return 0;} add(s,i,m-b[i]-a[i]); } for(int i=1;i<=m;i++){ if(n-b[i+n]<a[i+n]){puts("No Solution");return 0;} add(i+n,t,n-b[i+n]-a[i+n]); } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(!table[i][j])add(i,n+j,1); printf("%d\n",n*m-p-flow(s,t)); return 0; }
day10
这天是结业考。。。。
原本T3T4暴力可以使我275，刚好卡到18名（并列）。
结果打挂了，只剩220、
T1command,随便乱搞。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int a[400010],b[800020],m=400005,tmp=0; int n,u,d,l,r;char c[400010];long long ans=0; int main() { freopen("command.in","r",stdin); freopen("command.out","w",stdout); scanf("%d",&n);scanf("%s",c); if(n>5000){ for(int i=0;i<n;i++){ if(c[i]==‘L‘)a[i+1]=a[i]-1; else a[i+1]=a[i]+1; } for(int i=1;i<=n;i++)b[a[i]+m]++; ans+=b[m]; for(int i=1;i<=n;i++){ if(c[i-1]==‘L‘)tmp++; else tmp--; b[m-tmp]--;ans+=b[m-tmp]; } } else{ for(int i=0;i<n;i++){ u=d=l=r=0; for(int j=i;j<n;j++){ if(c[j]==‘U‘)u++; else if(c[j]==‘D‘)d++; else if(c[j]==‘L‘)l++; else r++; if(u==d&&l==r)ans++; } } } cout<<ans<<"\n"; return 0; }
T2position
跑循环节，mod一下，复杂度O（N）
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> using namespace std; inline int read(){ int t=1,num=0;char c=getchar(); while(c>‘9‘||c<‘0‘){if(c==‘-‘)t=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){num=num*10+c-‘0‘;c=getchar();} return num*t; } const int mn=100010; int n,q,wh[mn],a[mn],b[mn],used[mn],head[mn],len[mn],num[mn]; vector<int> g[mn]; int main() { freopen("position.in","r",stdin); freopen("position.out","w",stdout); memset(used,0,sizeof(used)); memset(len,0,sizeof(len)); n=read();q=read(); for(int i=1;i<=n;i++){ a[i]=read();b[i]=read(); wh[a[i]]=i; } for(int i=1;i<=n;i++){ int tmp=i,he=i; while(!used[he]){ head[he]=i; g[i].push_back(he); used[he]=1; he=wh[b[he]]; len[tmp]++; num[he]=len[tmp]; } } for(int i=1;i<=q;i++){ int s=read(),k=read(); int x=head[s]; int y=k%len[x]; y=(y+num[s])%(len[x]); printf("%d\n",g[x][y]); } return 0; }
好了，总算是完了
本文由Yzyet编写，网址为www.cnblogs.com/Yzyet。非Yzyet同意，禁止转载，侵权者必究。
原文：http://www.cnblogs.com/Yzyet/p/7252895.html