唔..NOIP2010比较简单,总体感觉不错.
Problem 1: 机器翻译
水题,队列的简单应用.
读入时判断是否在内存中,可以用hash优化.如果不在内存中push进内存,放不下了pop header不用说了.上代码(未hash优化)
//Bazinga!#include "cstdio"int sum,i,m,n;struct Q{ int len,head,tail,qub[1001],i; void push(int n){ qub[tail]=n; ++tail; if(len==m){ ++head; }else{ ++len; } } void has(int n){ for(i=head;i hash优化版(不加也没关系...加了纯属多耗内存,但是在大数据前肯定要快.)
#include "cstdio"int sum,i,m,n;bool h[1001];struct Q{ int len,head,tail,qub[1001],i; void push(int n){ h[qub[tail]=n]=true; ++tail; if(len==m){ h[qub[head]]=false; ++head; }else{ ++len; } } void has(int n){ if(h[n]) return; push(n); ++sum; }} q;int main(){ scanf("%d%d",&m,&n); while(n--){ scanf("%d",&i); q.has(i); } printf("%d", sum); return 0;} Problem 2: 乌龟棋
非常经典的动态规划题目,不算难,但是对刚接触DP的人来说也不容易.
设$f[i,j,k,l]$为1格卡~4格卡各使用了i~l张能获得的最高分,则动规方程为
$f[i,j,k,l]=score[i+2j+3k+4l]+max\left( f[i-1,j,k,l],f[i,j-1,k,l],f[i,j,k-1,l],f[i,j,k,l-1]\right)$
边界条件$f[0,0,0,0]=score[0]$..
上代码:
//ug! So comfortable!#include "cstdio"int f[41][41][41][41],c[5],s[350],m,n,i,j,k,l;int t1,t2,t3,t4,t5;inline int mx(int a,int b){ if(a>b){ return a;}else{ return b;}}int main(){ scanf("%d%d",&n,&m); for(i=0;i <=t1;++i){ for(j=0;j<=t2;++j){ for(k=0;k<=t3;++k){ for(l=0;l<=t4;++l){ t5=j+k+(l<<1); t5<<=1; if(i>0) f[i][j][k][l]=mx(f[i][j][k][l],f[i-1][j][k][l]); if(j>0) f[i][j][k][l]=mx(f[i][j][k][l],f[i][j-1][k][l]); if(k>0) f[i][j][k][l]=mx(f[i][j][k][l],f[i][j][k-1][l]); if(l>0) f[i][j][k][l]=mx(f[i][j][k][l],f[i][j][k][l-1]); f[i][j][k][l]+=s[t5+i+k]; } } } } printf("%d", f[t1][t2][t3][t4]); return 0;} Problem 3: 关押罪犯
一道使用并查集的贪心算法题.输入所有怨气值,从大到小排序,一个个减小看有没有与现有的方案冲突;若冲突,输出当前怨气值,退出;不冲突,输出0.
一般解法是利用二分图二分答案,这样的时间复杂度是$\left( \text{It's really not clear. Depends on one's code.}\\ \text{There are many ways to implement the algorithm}\\ \text{and does not contains the same time complexity,}\\ \text{pretty sorry but I can't help.}\right)$.这样的想法很明确,但是不好写,而且慢.
用并查集写的,很短,很快,时间复杂度大约$\text{O}\left( \alpha\left( n\right) m\right)$.
顺便贴上我的代码:
#include "cstdio"#include "algorithm"using namespace std;struct edge{ int a,b,c; bool operator <(const edge x)const{ return c>x.c; }} e[100010];int n,m,f[40020],x,y,t,p,i,j;int find(int x){ t=x; p=x; //find root while(t=f[t],t!=x){ x=t; } //path compressing while(f[p]=t,p=f[p],p!=t){}; return t;}int main(){ scanf("%d%d",&n,&m); for(i=0;i Problem 4: 引水入城
这是一道非常综合的题目,分两个小题.
1) 是否所有沙漠城市都有水供应. BFS即可
2) 最少需要多少个湖泊城市建立抽水站而第 2) 小题仔细想又可以分为
2.1) 求每个湖泊城市覆盖的沙漠城市范围
2.2) 求如何用最少的线段覆盖整条线段第一个BFS可过,用一种类似DP的方法亦可(这种方法存在反例,但是数据比较弱,除了第一个测试数据跑不过以外全可,非常快).
第二个贪心.$\text{The final tip:}$
$\text{Be careful using DFS because of system stack overflow and it's performance loss.}\color{orange}{\text{YOU'VE BEEN WARNED}}$
I TOLD YOU DONT LOOK AT THIS BUT YOU ARE NOT LISTENING!!!! #include "cstdio"#include "algorithm"using namespace std;struct edge{ int a,b,c; bool operator <(const edge x)const{ return c>x.c; }} e[100010];int n,m,f[40020],x,y,t,p,i,j;int find(int x){ t=x; p=x; //find root while(t=f[t],t!=x){ x=t; } //path compressing while(f[p]=t,p=f[p],p!=t){}; return t;}int main(){ scanf("%d%d",&n,&m); for(i=0;i #include "cstdio"#include "algorithm"#define max(a,b) (a>b?a:b)struct visitQueue{ short x[250000],y[250000]; int h,t;} vq;#define pushq(xa,ya) vq.x[vq.t]=xa,vq.y[vq.t]=ya,++vq.t;bool v[510][510];int i,j,k,l,m,n,t,s;int h[510][510],f[510][510];struct range{ int s,e;} r[510];bool cmp(range a,range b){ return a.s 1&&h[i-1][j] 1&&h[i][j-1] 0){ printf("0\n%d",t); return 0; } printf("1\n"); for(j=1;j<=n;++j){ if(h[m][j-1] 1){ f[m][j]=f[m][j-1]; }else{ f[m][j]=j; } } for(i=m-1;i>0;--i){ for(j=1;j<=n;++j){ f[i][j]=f[i+1][j]; if(j>1 && h[i][j-1] 0;--j){ if(h[m][j+1] 0;--i){ for(j=n;j>0;--j){ f[i][j]=f[i+1][j]; if(j f[i][j]){ f[i][j]=f[i][j+1]; } } } for(j=1;j<=n;++j){ r[j].e=f[1][j]; } std::sort(r,r+n,cmp); l=0; i=0; s=0; while(i<=n && s k){ k=r[i].e; } ++i; } s=k; } } printf("%d",l); return 0;}