【蒟蒻】BZOJ-LYDSY的各种

Jacinth posted @ 2015年10月07日 14:14 in BZOJ-LYDSY with tags BZOJ , 651 阅读

感谢lbn187提供了一份非常详尽的BZOJ题目表，然后就造成了一场~~惊天动地的~~灾难

不知道是谁先开始刷的，然后就gg了，一天被逼着刷了11道（然而感觉好像忘了截图留念）

然而还是被mars_cat大神给碾压了，怪我？

于是这就是一个蒟蒻的记录（不要问我为什么这些题看上去都这么简单，因为窝太弱了！！）

BZOJ-2463

小学奥数（才不会说窝数学渣呢），不必多讲QAQ

BZOJ-2463
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15	`#include <iostream>` `#include <cstdio>` `#include <cstdlib>` `#include <cstring>` `using` `namespace` `std;` `int` `n;` `int` `main()` `{` `scanf("%d",&n);` `while` `(n)` `{` `if` `(n&1)` `puts("Bob");` `else` `puts("Alice");` `scanf("%d",&n);` `}` `return` `0;` `}`

BZOJ-1192

找规律，分别选取2^0,2^1,2^2……等数就可以满足要求咯

BZOJ-1192
1 2 3 4 5 6 7 8 9 10 11 12 13 14	`#include <iostream>` `#include <cstdio>` `#include <cstdlib>` `#include <cstring>` `using` `namespace` `std;` `int` `n,xx,tot,x;` `int` `main()` `{` `scanf("%d",&n);` `tot=0;` `while` `(n) tot++,n>>=1;` `printf("%d\n",tot);` `return` `0;` `}`

BZOJ-1968

算是一道规律题吧，计算每个数在1到n中作为约数出现了几次，事实上就是[n/i]

加起来就可以啦

BZOJ-1968
1 2 3 4 5 6 7 8 9 10 11 12 13	`#include <cstdio>` `#include <cstring>` `#include <iostream>` `using` `namespace` `std;` `int` `ans,n;` `int` `main()` `{` `scanf("%d",&n);` `ans=0;` `for` `(int` `i=1;i<=n;++i) ans+=n/i;` `printf("%d\n",ans);` `return` `0;` `}`

BZOJ-2748

DP题，一开始弄成一维了，然后就WA

后来醒悟过来原来它只能从上一次的地方转移过来，然后就欢快得gg了

BZOJ-2748
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	`#include <iostream>` `#include <cstdio>` `#include <cmath>` `#include <cstring>` `using` `namespace` `std;` `int` `n,s,t,ans;` `int` `a[100];` `bool` `f[60][1010];` `int` `main()` `{` `scanf("%d%d%d",&n,&s,&t);` `for` `(int` `i=1;i<=n;++i)` `scanf("%d",&a[i]);` `memset(f,0,sizeof(f));` `f[0][s]=1;` `ans=0;` `for` `(int` `i=1;i<=n;++i)` `{` `bool` `ff=0;` `for` `(int` `j=0;j<=t;++j)` `if` `(f[i-1][j])` `{` `if` `(j-a[i]>=0)` `{` `f[i][j-a[i]]=1,ff=1;` `if` `(i==n && j-a[i]>ans) ans=j-a[i];` `}` `if` `(j+a[i]<=t)` `{` `f[i][j+a[i]]=1,ff=1;` `if` `(i==n && j+a[i]>ans) ans=j+a[i];` `}` `}` `if` `(!ff) {` `puts("-1");` `return` `0;` `}` `}` `printf("%d\n",ans);` `return` `0;` `}`

BZOJ-1088

DP题，考虑前两个如何安排的就可以推算出之后的所有了

感觉有点像分类讨论哎

BZOJ-1088
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 <iostream>` `#include <cstdio>` `#include <cstring>` `#include <cmath>` `#define NN 10010` `using` `namespace` `std;` `int` `a[NN],f[NN];` `int` `n,ans;` `int` `Check()` `{` `for` `(int` `i=2;i<n;++i)` `{` `f[i+1]=a[i]-f[i]-f[i-1];` `if` `(f[i+1]<0)` `return` `0;` `}` `if` `(a[n]-f[n]-f[n-1]!=0)` `return` `0;` `return` `1;` `}` `int` `main()` `{` `scanf("%d",&n);` `for` `(int` `i=1;i<=n;++i)` `scanf("%d",&a[i]);` `if` `(a[1]==0)` `{` `memset(f,0,sizeof(f)); ans+=Check();` `}` `else` `if` `(a[1]==1)` `{` `memset(f,0,sizeof(f));` `f[1]=1; ans+=Check();` `memset(f,0,sizeof(f));` `f[2]=1; ans+=Check();` `}` `else` `{` `memset(f,0,sizeof(f));` `f[1]=f[2]=1; ans+=Check();` `}` `printf("%d\n",ans);` `return` `0;` `}`

BZOJ-4143

按照日期排个序，算每一天最早结束和最晚开始的会议是否有重合就可以了（这算贪心吧？）

BZOJ-4143
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	`#include <iostream>` `#include <cstring>` `#include <cstdlib>` `#include <cstdio>` `#include <algorithm>` `using` `namespace` `std;` `struct` `REC` `{` `int` `a,b,num,d;` `};` `REC s[500050];` `int` `k,n,m,max_begin,min_end,max_begin_num,min_end_num;` `bool` `cmp(REC xx,REC yy)` `{` `return` `xx.d<yy.d;` `}` `int` `main()` `{` `scanf("%d%d",&n,&m);` `for` `(int` `i=1;i<=n;++i)` `scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].d),s[i].num=i;` `sort(s+1,s+1+n,cmp);` `k=0;` `for` `(int` `i=1;i<=m;++i)` `{` `while` `(s[k].d<i) k++;` `if` `(s[k].d!=i)` `{` `puts("NIE");` `continue; }` `max_begin=s[k].a; min_end=s[k].b; max_begin_num=min_end_num=s[k].num;` `while` `(s[k+1].d==i)` `{` `k++;` `if` `(s[k].a>max_begin) max_begin=s[k].a,max_begin_num=s[k].num;` `if` `(s[k].b<min_end) min_end=s[k].b,min_end_num=s[k].num;` `}` `if` `(max_begin<=min_end)` `puts("NIE");` `else` `{` `printf("TAK %d %d\n",max_begin_num,min_end_num);` `}` `}` `return` `0;` `}`

BZOJ-1207

又是一道DP题，打一次鼹鼠必定是从以前的某一次打鼹鼠转移过来的，f[i]表示打掉第i只鼹鼠时最多打死了几只，最后求一下最大值

据说某黑科技可以缩短时间（吗？）

BZOJ-1207
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	`#include <iostream>` `#include <cstdio>` `#include <cmath>` `#include <cstring>` `#include <algorithm>` `#define NN 10010` `using` `namespace` `std;` `int` `n,m,ans;` `int` `f[NN],dp[NN],x[NN],y[NN],t[NN];` `int` `main()` `{` `scanf("%d%d",&n,&m);` `for` `(int` `i=1;i<=m;++i)` `scanf("%d%d%d",&t[i],&x[i],&y[i]);` `f[1]=1; dp[1]=1; ans=1;` `for` `(int` `i=2;i<=m;++i)` `{` `f[i]=1;` `for` `(int` `j=i-1;j>=1;--j)` `{` `if` `(dp[j]+1<=f[i])` `break;` `if` `(f[j]+1>f[i])` `{` `if` `(abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j]) f[i]=f[j]+1;` `}` `}` `dp[i]=max(dp[i-1],f[i]);` `if` `(f[i]>ans) ans=f[i];` `}` `printf("%d\n",ans);` `return` `0;` `}`

BZOJ-1083

最小生成树题，第一问的答案必定是n-1（怪我？），于是事实上就可以排个序，从小到大开始生成最小生成树，最后加进来的就是答案了

BZOJ-1083
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	`#include <iostream>` `#include <cstring>` `#include <cstdio>` `#include <algorithm>` `using` `namespace` `std;` `struct` `REC` `{` `int` `u,v,c;` `};` `REC a[10010];` `int` `father[330];` `int` `ans,n,m;` `int` `find_father(int` `xx)` `{` `return` `(xx==father[xx]?xx:(father[xx]=find_father(father[xx])));` `}` `bool` `cmp(REC xx,REC yy)` `{` `return` `xx.c<yy.c;` `}` `int` `main()` `{` `scanf("%d%d",&n,&m);` `for` `(int` `i=1;i<=m;++i)` `scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].c);` `for` `(int` `i=1;i<=n;++i) father[i]=i;` `sort(a+1,a+1+m,cmp);` `ans=0;` `for` `(int` `i=1;i<=m;++i)` `{` `int` `xx=find_father(a[i].u),yy=find_father(a[i].v);` `if` `(xx!=yy)` `{` `father[xx]=yy;` `ans=a[i].c;` `}` `}` `printf("%d %d\n",n-1,ans);` `return` `0;` `}`

============================这是一条欢快的分割线，据说以上题目NOIP普及组难度

BZOJ-1821

最小生成树&贪心辣

先排序，我们把边权最小的全分给n个部落的内部，然后剩下的边最小的就是答案。将边权较小的边分给k个部落，用并查集生成最小树，使得内部的边总是小于连到外部的边。然后分剩下k个点即可，剩下的k个点的那条边一定是部落之间最小的且最长的边。（语文渣只能拉一小段题解了，我错了）

BZOJ-1821
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 <iostream>` `#include <cmath>` `#include <cstdio>` `#include <cstdlib>` `#include <algorithm>` `#include <cstring>` `#define NN 1010` `using` `namespace` `std;` `struct` `REC` `{` `int` `x,y;` `};` `REC p[NN];` `struct` `Edeg` `{` `int` `x,y,len;` `};` `Edeg e[NNNN];` `int` `tot,n,k,ans;` `int` `father[NN];` `int` `find_father(int` `xx)` `{` `return` `xx==father[xx]?xx:(father[xx]=find_father(father[xx]));` `}` `int` `Len(int` `xx,int` `yy)` `{` `int` `x=p[xx].x-p[yy].x,y=p[xx].y-p[yy].y;` `return` `xx+y*y;` `}` `bool` `cmp(Edeg xx,Edeg yy)` `{` `return` `xx.len<yy.len;` `}` `int` `main()` `{` `scanf("%d%d",&n,&k);` `for` `(int` `i=1;i<=n;++i)` `scanf("%d%d",&p[i].x,&p[i].y),father[i]=i;` `tot=0;` `for` `(int` `i=1;i<=n;++i)` `for` `(int` `j=i+1;j<=n;++j)` `{` `e[++tot].x=i; e[tot].y=j; e[tot].len=Len(i,j);` `}` `sort(e+1,e+tot+1,cmp); ans=0;` `for` `(int` `i=1;i<=tot;++i)` `{` `int` `xx=find_father(e[i].x),yy=find_father(e[i].y);` `if` `(xx!=yy)` `{` `if` `(n>k) n--,father[xx]=yy;` `else` `{printf("%.2f\n",sqrt(e[i].len));` `return` `0;}` `}` `}` `return` `0;` `}`

BZOJ-1034

排个序，然后贪心，大的对战大的，反正总而言之要让a数组赢

BZOJ-1034
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	`#include <iostream>` `#include <cstdio>` `#include <cstdlib>` `#include <cstring>` `#include <algorithm>` `#define NN 100010` `using` `namespace` `std;` `int` `a[NN],b[NN];` `int` `n;` `bool` `cmp(int` `xx,int` `yy) {return` `xx<yy;}` `int` `work(int` `xx,int` `yy)` `{` `int` `tmp=0,lx,ly,rx,ry;` `lx=ly=1; rx=ry=n;` `while` `(lx<=rx && ly<=ry)` `{` `if` `(xx[lx]>yy[ly]) {tmp+=2; lx++; ly++;}` `else` `if` `(xx[rx]>yy[ry]) {tmp+=2; rx--; ry--;}` `else` `{tmp+=(xx[lx]==yy[ry]); lx++; ry--;}` `}` `return` `tmp;` `}` `int` `main()` `{` `scanf("%d",&n);` `for` `(int` `i=1;i<=n;++i)` `scanf("%d",&a[i]);` `for` `(int` `i=1;i<=n;++i)` `scanf("%d",&b[i]);` `sort(a+1,a+1+n,cmp); sort(b+1,b+1+n,cmp);` `printf("%d %d\n",work(a,b),2*n-work(b,a));` `return` `0;` `}`

BZOJ-4145

状压DP，每个商店内跑一个背包就可以了，复杂度O（nm2^m)

BZOJ-4145
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	`#include <iostream>` `#include <cstdio>` `#include <cstring>` `#include <cstdlib>` `using` `namespace` `std;` `int` `m,n,mm;` `int` `dp[110][1<<16],d[110],c[110][20];` `int` `main()` `{` `scanf("%d%d",&n,&m);` `for` `(int` `i=1;i<=n;++i)` `{` `scanf("%d",&d[i]);` `for` `(int` `j=1;j<=m;++j)` `scanf("%d",&c[i][j]);` `}` `memset(dp,0x3f,sizeof(dp));` `dp[0][0]=0; mm=1<<m;` `for` `(int` `i=1;i<=n;++i)` `{` `for` `(int` `j=0;j<mm;++j) dp[i][j]=dp[i-1][j]+d[i];` `for` `(int` `k=1;k<=m;++k)` `for` `(int` `j=0;j<mm;++j)` `if` `(~j & (1<<(k-1)))` `dp[i][j\|(1<<(k-1))]=min(dp[i][j\|(1<<(k-1))],dp[i][j]+c[i][k]);` `for` `(int` `j=0;j<mm;++j) dp[i][j]=min(dp[i][j],dp[i-1][j]);` `}` `printf("%d\n",dp[n][mm-1]);` `return` `0;` `}`

BZOJ-2563

考虑先手选择每个点对答案的影响

我们先预先把所有的权值都在初始答案中减掉，最后就是：

一个点如果不选，本身对答案的贡献是0；一个点如果选，本身对答案的贡献是2*w；

一条边如果两个端点都不选，对答案的贡献是0；如果两个端点中只选择一个，对答案的贡献是c；如果两个端点都选，对答案的贡献是2*c

计算所有点的贡献，然后排序轮流取

BZOJ-2563
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	`#include <iostream>` `#include <cstdio>` `#include <cstdio>` `#include <cstring>` `#include <algorithm>` `#define NN 10010` `using` `namespace` `std;` `int` `ans,n,m,x,y,z;` `int` `a[NN];` `int` `main()` `{` `scanf("%d%d",&n,&m);` `memset(a,0,sizeof(a)); ans=0;` `for` `(int` `i=1;i<=n;++i)` `{` `scanf("%d",&x);` `ans-=x; a[i]=x<<1;` `}` `for` `(int` `i=1;i<=m;++i)` `{` `scanf("%d%d%d",&x,&y,&z);` `a[x]+=z,a[y]+=z,ans-=z;` `}` `sort(a+1,a+1+n);` `for` `(int` `i=2;i<=n;i+=2)` `ans+=a[i];` `printf("%d\n",ans);` `return` `0;` `}`

BZOJ-1303

数学题，计算前后多几个少几个的组合个数，然后前后互为相反数的乘起来

BZOJ-1303
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	`#include <iostream>` `#include <cstdio>` `#include <cstring>` `#include <cstdlib>` `#include <algorithm>` `#define midd 100001` `#define NN 200100` `using` `namespace` `std;` `int` `mid,ans,tmp,n,m;` `int` `x[NN],y[NN],a[NN];` `int` `main()` `{` `scanf("%d%d",&n,&m); mid=0;` `memset(x,0,sizeof(x));` `memset(y,0,sizeof(y));` `for` `(int` `i=1;i<=n;++i)` `{` `scanf("%d",&a[i]);` `if` `(a[i]==m) mid=i;` `}` `x[midd]=y[midd]=1;//注意初值` `tmp=midd;` `for` `(int` `i=mid-1;i>=1;--i)` `{` `if` `(a[i]<m) tmp--;` `else` `tmp++;` `x[tmp]++;` `}` `tmp=midd;` `for` `(int` `i=mid+1;i<=n;++i)` `{` `if` `(a[i]<m) tmp--;` `else` `tmp++;` `y[tmp]++;` `}` `ans=0;` `for` `(int` `i=midd-n;i<=midd+n;++i)` `ans+=y[i]*x[(midd<<1)-i];` `printf("%d\n",ans);` `return` `0;` `}`

BZOJ-4001

算一下前面几个找规律（窝才不会说其实有严格证明的呢，然而其实窝数学渣，具体证明并没有看懂QAQ）

证明见此→_→： http://blog.miskcoo.com/2015/04/bzoj-4001

BZOJ-4001
1 2 3 4 5 6 7 8 9 10 11	`#include <iostream>` `#include <cstdio>` `#include <cstring>` `using` `namespace` `std;` `int` `n;` `int` `main()` `{` `scanf("%d",&n);` `printf("%.9lf\n",(double)(n/2.0/(2n-1)(n+1)));` `return` `0;` `}`

BZOJ-1024

DFS题，表示具体什么的详见程序吧（此题有压代码嫌疑）

BZOJ-1024
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	`#include <iostream>` `#include <cstdio>` `#include <cstring>` `#include <cmath>` `using` `namespace` `std;` `int` `x,y,n;` `double` `DFS(double` `xx,double` `yy,int` `nn)` `{` `if` `(nn==1)` `return` `(double)(max(xx,yy)/min(xx,yy));` `double` `temp=1e30;` `for` `(int` `i=1;i<nn;++i)` `{` `double` `tmp=min(max(DFS(xx/nni,yy,i),DFS(xx/nn(nn-i),yy,nn-i)),max(DFS(xx,yy/nni,i),DFS(xx,yy/nn(nn-i),nn-i)));` `temp=min(tmp,temp);` `}` `return` `temp;` `}` `int` `main()` `{` `scanf("%d%d%d",&x,&y,&n);` `printf` `("%.6f\n",DFS(x,y,n));` `return` `0;` `}`

BZOJ-1037

又是一道DP题

i表示选择了几个人，j表示选择了几个男生，x表示男生比女生多几个，y表示女生比男生多几个

BZOJ-1037
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	`#include <iostream>` `#include <cstdio>` `#include <cstring>` `#include <algorithm>` `#include <queue>` `#include <cmath>` `#include <cstdlib>` `#define mod 12345678` `#define KK 25` `#define NN 160` `using` `namespace` `std;` `int` `f[NN<<1][NN][KK][KK];` `int` `ans,n,m,k;` `int` `main()` `{` `scanf("%d%d%d",&n,&m,&k);` `memset(f,0,sizeof(f));` `f[0][0][0][0]=1;` `for` `(int` `i=0;i<n+m;++i)` `for` `(int` `j=0;j<=n;++j)` `for` `(int` `x=0;x<=k;++x)` `for` `(int` `y=0;y<=k;++y)` `if` `(f[i][j][x][y])` `{` `if` `(j+1<=n && x+1<=k)` `f[i+1][j+1][x+1][max(y-1,0)]=(f[i+1][j+1][x+1][max(y-1,0)]+f[i][j][x][y])%mod;` `if` `(i-j+1<=m && y+1<=k)` `f[i+1][j][max(x-1,0)][y+1]=(f[i+1][j][max(x-1,0)][y+1]+f[i][j][x][y])%mod;` `}` `ans=0;` `for` `(int` `i=0;i<=n;++i)` `for` `(int` `x=0;x<=k;++x)` `for` `(int` `y=0;y<=k;++y)` `ans=(ans+f[n+m][i][x][y])%mod;` `printf("%d\n",ans);` `return` `0;` `}`

BZOJ-1296

DP题（此题有故意拉长代码嫌疑）

对每一块进行一个三次方的DP，然后再总的弄个背包

BZOJ-1296
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	`#include <iostream>` `#include <cstdio>` `#include <cstring>` `#include <cstdlib>` `#include <cmath>` `#include <string>` `#define NN 60` `#define TT 2510` `using` `namespace` `std;` `int` `f[NN][NN];` `int` `dp[NN][TT];` `int` `sum[NN];` `int` `n,m,t,ans;` `char` `s[100];` `int` `main()` `{` `scanf("%d%d%d",&n,&m,&t);` `memset(f,0,sizeof(f));` `memset(dp,0,sizeof(dp));` `for` `(int` `i=1;i<=n;++i)` `{` `scanf("%s",s+1);` `for` `(int` `j=1;j<=m;++j)` `if` `(s[j]=='1')` `sum[j]=sum[j-1]+1;` `else` `sum[j]=sum[j-1];` `for` `(int` `j=1;j<=m;++j)` `for` `(int` `x=1;x<=m;++x)` `{` `f[x][j]=0;` `for` `(int` `y=0;y<x;++y)` `{` `int` `tmp;` `tmp=sum[x]-sum[y];` `tmp=max(tmp,x-y-tmp);` `f[x][j]=max(f[x][j],f[y][j-1]+tmp);` `}` `}` `for` `(int` `j=1;j<=t;++j)` `{` `int` `tmp=min(m,j);` `for` `(int` `x=1;x<=tmp;++x)` `{` `dp[i][j]=max(dp[i][j],dp[i-1][j-x]+f[m][x]);` `}` `}` `}` `ans=0;` `for` `(int` `i=1;i<=t;++i)` `ans=max(ans,dp[n][i]);` `printf("%d\n",ans);` `return` `0;` `}`

BZOJ-1029

主要是贪心，按照截止时间排序然后按次序判断剩余时间是否足够

若足够就加入，不足够则判断

若其持续时间比已加入的最大值长则放弃

若比最大值短，放弃最大值的那个把新的加进去

其中要用到堆来维护（STL大发好）

BZOJ-1029
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	`#include <iostream>` `#include <cstdio>` `#include <cstring>` `#include <queue>` `#include <cstdlib>` `#include <cmath>` `#include <algorithm>` `#define NN 150100` `using` `namespace` `std;` `struct` `REC` `{` `int` `ta,tb;` `};` `REC a[NN];` `int` `n,recent;` `bool` `cmp(const` `REC xx,const` `REC yy)` `{` `return` `xx.tb<yy.tb;` `}` `priority_queue <int,vector<int>,less<int> > que;` `int` `main()` `{` `scanf("%d",&n);` `for` `(int` `i=1;i<=n;++i)` `scanf("%d%d",&a[i].ta,&a[i].tb);` `sort(a+1,a+1+n,cmp);` `recent=0;` `for` `(int` `i=1;i<=n;++i)` `{` `if` `(recent+a[i].ta<=a[i].tb)` `{` `recent+=a[i].ta;` `que.push(a[i].ta);` `}` `else` `if` `(que.size())` `{` `int` `tmp=que.top();` `if` `(tmp<a[i].ta)` `continue;` `que.pop();` `que.push(a[i].ta);` `recent-=(tmp-a[i].ta);` `}` `}` `printf("%d\n",que.size());` `return` `0;` `}`

BZOJ-1216

堆的处理，就是写完有点晕

BZOJ-1216
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	`#include <iostream>` `#include <cstdio>` `#include <cstring>` `#include <queue>` `#include <algorithm>` `using` `namespace` `std;` `struct` `REC` `{` `int` `num,st,l,yx;` `};` `REC a[1000010];` `struct` `NODE` `{` `int` `t,d;` `};` `bool` `operator <(const` `NODE xx,const` `NODE yy)` `{` `if` `(a[xx.d].yx==a[yy.d].yx)` `return` `a[xx.d].st>a[yy.d].st;` `else` `return` `a[xx.d].yx<a[yy.d].yx;` `}` `struct` `rec` `{` `int` `t,d;` `};` `bool` `cmp(rec xx,rec yy)` `{` `return` `xx.t<yy.t;` `}` `rec ans[1000010];` `priority_queue <NODE,vector<NODE> > que;` `int` `k,now;` `int` `main()` `{` `k=1;` `while` `(scanf("%d%d%d%d",&a[k].num,&a[k].st,&a[k].l,&a[k].yx)!=EOF) ans[k].d=k,k++;` `a[k].st=0x7fffffff; now=0;` `for` `(int` `i=1;i<=k;++i)` `{` `int` `t=a[i].st-now;` `while` `(!que.empty() && que.top().t<=t)` `{` `now+=que.top().t;` `ans[que.top().d].t=now;` `t-=que.top().t;` `que.pop();` `}` `if` `(i==k)` `break;` `if` `(!que.empty() && t)` `{` `NODE xx=que.top(); que.pop();` `xx.t-=t; que.push(xx);` `}` `now=a[i].st;` `NODE x; x.t=a[i].l,x.d=i;` `que.push(x);` `}` `sort(ans+1,ans+k,cmp);` `for` `(int` `i=1;i<k;++i)` `printf("%d %d\n",a[ans[i].d].num,ans[i].t);` `return` `0;` `}`

BZOJ-2456

神题一枚，据说窝删几个库就从Memory_Limit_Exceed到Accepted了

BZOJ-2456
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20	`#include <cstdio>` `using` `namespace` `std;` `int` `now,t,n,xx;` `int` `main()` `{` `scanf("%d",&n);` `now=0; t=0;` `while` `(n--)` `{` `scanf("%d",&xx);` `if` `(xx==now) t++;` `else` `{` `t--;` `if` `(t<=0) t=1,now=xx;` `}` `}` `printf("%d\n",now);` `return` `0;` `}`

BZOJ-2761

论如何使用set去重

BZOJ-2761
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	`#include <iostream>` `#include <cstdio>` `#include <cstring>` `#include <cstdlib>` `#include <set>` `using` `namespace` `std;` `set <int> se;` `int` `T,n,xx,tot;` `int` `a[50010];` `int` `main()` `{` `scanf("%d",&T);` `while` `(T--)` `{` `scanf("%d",&n);` `se.clear();` `tot=0;` `for` `(int` `i=1;i<=n;++i)` `{` `scanf("%d",&xx);` `if` `(se.find(xx)!=se.end())` `continue;` `else` `a[++tot]=xx,se.insert(xx);` `}` `for` `(int` `i=1;i<tot;++i)` `printf("%d ",a[i]);` `printf("%d\n",a[tot]);` `}` `return` `0;` `}`

BZOJ-2005

数学题~~~不过要倒着来，然后暴力容斥

BZOJ-2005
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24	`#include <iostream>` `#include <cstdio>` `#include <cstring>` `#include <cstdlib>` `#include <cmath>` `#define LL long long` `using` `namespace` `std;` `LL f[100010],ans;` `int` `n,m;` `int` `main()` `{` `scanf("%d%d",&n,&m);` `ans=0;` `for` `(int` `i=min(n,m);i>=1;--i)` `{` `f[i]=(LL)(n/i)(LL)(m/i);` `for` `(int` `j=2;j<=min(n,m)/i;++j) f[i]-=f[ij];` `ans+=(f[i](2i-1));` `}` `printf("%lld\n",ans);` `return` `0;` `}`

BZOJ-1491

可以算是比较典型的Floyd题目了吧，只是在计算的同时要记录经过的边数

BZOJ-1491
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 <iostream>` `#include <cstdio>` `#include <cstring>` `#include <cstdlib>` `#include <cmath>` `using` `namespace` `std;` `int` `n,m,x,y,z;` `int` `mp[110][110];` `double` `a[110][110];` `double` `ans[110];` `int` `main()` `{` `scanf("%d%d",&n,&m);` `for` `(int` `i=1;i<=n;++i)` `for` `(int` `j=1;j<=n;++j)` `mp[i][j]=1e9;` `for` `(int` `i=1;i<=m;++i)` `{` `scanf("%d%d%d",&x,&y,&z);` `mp[x][y]=mp[y][x]=z;` `a[x][y]=a[y][x]=1;` `}` `for` `(int` `k=1;k<=n;++k)` `for` `(int` `i=1;i<=n;++i)` `for` `(int` `j=1;j<=n;++j)` `{` `if` `(mp[i][k]+mp[k][j]<mp[i][j])` `mp[i][j]=mp[i][k]+mp[k][j],a[i][j]=0;` `if` `(mp[i][j]==mp[i][k]+mp[k][j])` `a[i][j]+=a[i][k]a[k][j];` `}` `for` `(int` `i=1;i<=n;++i)` `a[i][i]=0;` `for` `(int` `k=1;k<=n;++k)` `for` `(int` `i=1;i<=n;++i)` `for` `(int` `j=1;j<=n;++j)` `{` `if` `(mp[i][j]==mp[i][k]+mp[k][j] && a[i][j]>0)` `ans[k]+=a[i][k]a[k][j]/a[i][j];` `}` `for` `(int` `i=1;i<=n;++i)` `printf("%.3lf\n",ans[i]);` `return` `0;` `}`

BZOJ-1025

事实上是求n的任意拆分最小公倍数有几种可能

BZOJ-1025
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	`#include <iostream>` `#include <cstdio>` `#include <cstring>` `#include <cstdlib>` `#include <cmath>` `#define NN 1001` `#define LL long long` `using` `namespace` `std;` `int` `tot,n;` `int` `prime[NN];` `bool` `ff[NN];` `LL dp[NN][NN];` `LL ans;` `int` `main()` `{` `scanf("%d",&n);` `memset(ff,0,sizeof(ff));` `memset(prime,0,sizeof(prime));` `memset(dp,0,sizeof(dp));` `tot=0;` `for` `(int` `i=2;i<=NN;i++)` `{` `if` `(!ff[i]) prime[++tot]=i;` `for` `(int` `j=1;j<=tot;++j)` `{` `if` `(iprime[j]>NN)` `break;` `ff[iprime[j]]=1;` `if` `(i%prime[j]==0)` `break;` `}` `}` `dp[0][0]=1;` `for` `(int` `i=1;i<=tot;++i)` `{` `for` `(int` `j=0;j<=n;++j)` `dp[i][j]=dp[i-1][j];` `for` `(int` `j=prime[i];j<=n;j*=prime[i])` `{` `for` `(int` `k=0;k<=n-j;++k)` `dp[i][k+j]+=dp[i-1][k];` `}` `}` `ans=0;` `for` `(int` `i=0;i<=n;++i) ans+=dp[tot][i];` `printf("%lld\n",ans);` `return` `0;` `}`

BZOJ-2957

想着要学习一下分块的算法，然后就往下找到了某题上赫然写着分块二字，就开始被虐了TAT。。。蒟蒻第一次写分块啊，可惜发现自己把最后计算答案的地方写炸了，表示脑残了，早知道不手打二分直接用lower_bound了，害得窝对自己的二分很没有信心QAQ，然后浪费了好多查错的时间╮(╯▽╰)╭

BZOJ-2957
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	`#include <iostream>` `#include <cstdio>` `#include <cmath>` `#include <cstring>` `#include <cstdlib>` `#define I int` `#define D double` `#define NN 100005` `#define NNN 330` `using` `namespace` `std;` `struct` `REC` `{` `int` `l;` `D num[NNN];` `void` `add(D xx) {num[++l]=xx;}` `int` `finds(D xx)` `{` `int` `left=1,right=l,tmp=0;` `while` `(left<=right)` `{` `int` `mid=(left+right)>>1;` `if` `(num[mid]>xx) tmp=mid,right=mid-1;` `else` `left=mid+1;` `}` `return` `tmp;` `}` `};` `REC q[NN];` `int` `n,m,x,y,len,cnt,now,ans,lenn[NN];` `D w[NN],maxx;` `int` `main()` `{` `scanf("%d%d",&n,&m);` `len=(I)sqrt((D)n);` `while` `(lenlen>n) len--;` `cnt=n/len+(n%len==0?0:1);` `for` `(int` `i=1;i<cnt;++i) lenn[i]=len;` `lenn[cnt]=n-(cnt-1)len;` `for` `(int` `i=1;i<=m;++i)` `{` `scanf("%d%d",&x,&y);` `w[x]=(D)y/(D)x;` `now=(x-1)/len+1;` `maxx=0; q[now].l=0;` `for` `(int` `j=len(now-1)+1;j<=len(now-1)+lenn[now];++j)` `if` `(w[j]>maxx)` `q[now].add(w[j]),maxx=w[j];` `ans=q[1].l;` `maxx=q[1].num[ans];` `for` `(int` `j=2;j<=cnt;++j)` `if` `(q[j].num[q[j].l]>maxx)` `{` `ans+=q[j].l-q[j].finds(maxx)+1;` `maxx=q[j].num[q[j].l];` `}` `printf("%d\n",ans);` `}` `return` `0;` `}`

BZOJ-1050

最小生成树，先排序，然后暴力枚举开头的那条边辣，求个最小值，约个分，不过要注意整除的情况辣

BZOJ-1050
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	`#include <iostream>` `#include <cstdio>` `#include <cstring>` `#include <cmath>` `#include <cstdlib>` `#include <algorithm>` `#define D double` `using` `namespace` `std;` `struct` `REC` `{` `int` `x,y,v;` `};` `REC a[5005];` `int` `mn,mx,k,fa[505],n,m,s,t;` `D minn;` `int` `gcd(int` `a,int` `b){while` `(a)a ^= b ^= a ^= b %= a;` `return` `b;}` `int` `FF(int` `xx) {return` `(fa[xx]==xx?xx:(fa[xx]=FF(fa[xx])));}` `bool` `cmp(REC xx,REC yy) {return` `xx.v<yy.v;}` `int` `main()` `{` `scanf("%d%d",&n,&m);` `for` `(int` `i=1;i<=m;++i)` `scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v);` `sort(a+1,a+1+m,cmp);` `scanf("%d%d",&s,&t);` `minn=0x7fffffff;` `for` `(int` `w=1;w<=m;++w)` `{` `for` `(int` `i=1;i<=n;++i) fa[i]=i;` `for` `(int` `i=w;i<=m;++i)` `{` `fa[FF(a[i].x)]=FF(a[i].y);` `if` `(FF(s)==FF(t))` `{` `D tmp=(D)a[i].v/(D)a[w].v;` `if` `(tmp<minn)` `{` `minn=tmp,mx=a[i].v,mn=a[w].v;` `break;` `}` `}` `}` `}` `if` `(minn==0x7fffffff)` `puts("IMPOSSIBLE");` `else` `{` `k=gcd(mn,mx);` `mn/=k,mx/=k;` `if` `(mn==1)` `printf("%d\n",mx);` `else` `printf("%d/%d\n",mx,mn);` `}` `return` `0;` `}`

BZOJ-1007

唔，判断写炸错了好久哎(╥╯^╰╥)

其实就是先按斜率排序，再将最小的两条线入栈，然后依次处理每条线，如果其与栈顶元素的交点在上一个点的左边，则将栈顶元素出栈。因为对如任意一个开口向上的半凸包，从左到右依次观察每条边和每个顶点，发现其斜率不断增大，顶点的横坐标也不断增大。（以上来自网络）_(:зゝ∠)_

BZOJ-1007
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	`#include <iostream>` `#include <cstdio>` `#include <cstdlib>` `#include <cstring>` `#include <cmath>` `#include <algorithm>` `#define eps 1e-8` `#define D double` `#define NN 50010` `using` `namespace` `std;` `struct` `REC {D x,y;` `int` `num;};` `REC a[NN],st[NN];` `int` `tot,n,ans[NN];` `bool` `cmp(REC xx,REC yy)` `{` `if` `(fabs(xx.x-yy.x)<eps)` `return` `xx.y<yy.y;` `else` `return` `xx.x<yy.x;` `}` `D cacl(REC xx,REC yy) {return` `(D)(xx.y-yy.y)/(D)(yy.x-xx.x);}` `bool` `Judge(REC xx,REC yy,REC zz) {return` `cacl(xx,yy)>=cacl(xx,zz);}` `int` `main()` `{` `scanf("%d",&n);` `for` `(int` `i=1;i<=n;++i)` `scanf("%lf%lf",&a[i].x,&a[i].y),a[i].num=i;` `sort(a+1,a+1+n,cmp);` `st[1]=a[1],tot=1,ans[1]=a[1].num;` `for` `(int` `i=2;i<=n;++i)` `{` `while` `(tot)` `{` `if` `(tot>=1 &&` `fabs(st[tot].x-a[i].x)<eps) tot--;` `else` `if` `(tot>1 && Judge(st[tot-1],st[tot],a[i])) tot--;` `else` `break;` `}` `st[++tot]=a[i],ans[tot]=a[i].num;` `}` `sort(ans+1,ans+1+tot);` `for` `(int` `i=1;i<=tot;++i)` `printf("%d ",ans[i]);` `puts("");` `return` `0;` `}`

BZOJ-2150

实际上就是二分图匹配吧，先处理一下能走的点弄成一张图，然后就暴力了

BZOJ-2150
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	`#include <cstdio>` `#include <iostream>` `#include <cstring>` `#include <cmath>` `#include <cstdlib>` `#include <algorithm>` `#define NN 55` `using` `namespace` `std;` `struct` `REC` `{` `int` `ne,v;` `};` `REC e[NNNN4];` `int` `head[NNNN],match[NNNN],a[NN][NN],m,n,r,c,sum=0,tot=0,ans=0;` `bool` `vis[NN*NN];` `char` `ch[NN];` `void` `Build(int` `xx,int` `yy){e[++tot].ne=head[xx]; head[xx]=tot; e[tot].v=yy;}` `void` `judge(int` `s,int` `xx,int` `yy)` `{` `if` `(xx<=0 \|\| yy<=0 \|\| xx>m \|\| yy>n)` `return;` `if` `(a[xx][yy]) Build(s,a[xx][yy]);` `}` `bool` `Check(int` `xx)` `{` `for` `(int` `i=head[xx];i;i=e[i].ne)` `{` `int` `vv=e[i].v;` `if` `(!vis[vv])` `{` `vis[vv]=1;` `if` `(!match[vv] \|\| Check(match[vv]))` `{` `match[vv]=xx;` `return` `1;` `}` `}` `}` `return` `0;` `}` `int` `main()` `{` `scanf("%d%d%d%d",&m,&n,&r,&c);` `memset(a,0,sizeof(a));` `memset(match,0,sizeof(match));` `memset(e,0,sizeof(e));` `sum=0;` `for` `(int` `i=1;i<=m;++i)` `{` `scanf("%s",ch);` `for` `(int` `j=0;j<n;++j)` `if` `(ch[j]=='.') a[i][j+1]=++sum;` `}` `for` `(int` `i=1;i<=m;++i)` `for` `(int` `j=1;j<=n;++j)` `if` `(a[i][j])` `{` `judge(a[i][j],i+r,j+c); judge(a[i][j],i+r,j-c);` `judge(a[i][j],i+c,j+r); judge(a[i][j],i+c,j-r);` `}` `for` `(int` `i=1;i<=sum;++i)` `{` `memset(vis,0,sizeof(vis));` `if` `(Check(i)) ++ans;` `}` `printf("%d\n",sum-ans);` `return` `0;` `}`

BZOJ-4029

感觉想起来还是挺有难度的贪心题。。。不过写起来还是蛮容易的辣

BZOJ-4029
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	`#include <iostream>` `#include <cstdio>` `#include <cmath>` `#include <cstring>` `#include <cstdlib>` `using` `namespace` `std;` `int` `T,l,r,minn,ans;` `int` `add(int` `xx)` `{` `int` `sum=1;` `while` `(xx%10==0) xx/=10,sum=10;` `return` `sum;` `}` `int` `calc(int` `xx)` `{` `while` `(xx%10==0) xx/=10;` `int` `tmp=xx%10,a=0;` `while` `(xx) xx/=10,a++;` `if` `(tmp==5)` `return` `2a-1;` `else` `return` `2*a;` `}` `int` `main()` `{` `scanf("%d",&T);` `while` `(T--)` `{` `scanf("%d%d",&l,&r);` `minn=calc(l); ans=l;` `while` `(l<=r)` `{` `l+=add(l);` `if` `(l>r)` `break;` `int` `tmp=calc(l);` `if` `(tmp<minn) minn=tmp,ans=l;` `}` `printf("%d\n",ans);` `}` `return` `0;` `}`

~~某天吐槽：一下子做这么多题，记录起来真累~~

~~从此以后感觉这里成了一个坑~~

[回复]

hhw 说:
2015年10月13日 19:41

%%%日切11题大爷

Pluto_Rabbit's Blog

蒟蒻妹纸一枚，轻拍