最后一次NOIP了，390（最后一个程序dfs改快一点就可以400最后一个题有更好的算法，O(n^2)的）。
代码贴在这里，题解网上已经有了，就不必写了。
CODE:
/*
AUTHOR: Su Jiao
DATE: 2010-11-20
DESCRIPTION:
$DESCRIPTION
*/
#include <stdio.h>
#define PROBLEM “translate”
FILE* file;
const int QUEUE_SIZE=1<<20;
int M,N;
int queue[QUEUE_SIZE];
bool in_queue[QUEUE_SIZE];
int head,tail;
int answer;
int main()
{
file=fopen(PROBLEM“.in”,“r”);
fscanf(file,“%d%d”,&M,&N);
for (int i=0;i<N;i++)
{
int word;
fscanf(file,“%d”,&word);
if (!in_queue[word])
{
in_queue[queue[tail++]=word]=true;
if (tail-head>M)
in_queue[queue[head++]]=false;
answer++;
}
}
fclose(file);
file=fopen(PROBLEM“.out”,“w”);
fprintf(file,“%d\n”,answer);
fclose(file);
return 0;
}
#include <stdio.h>
#define PROBLEM “tortoise”
FILE* file;
const int MAXN=1<<10;
const int MAXCARD=1<<6;
const int MAXCARD_NUMBER=1<<3;
int N,M;
int a[MAXN];
int card[MAXCARD_NUMBER];
int f[MAXCARD][MAXCARD][MAXCARD][MAXCARD];
int main()
{
file=fopen(PROBLEM“.in”,“r”);
fscanf(file,“%d%d”,&N,&M);
for (int i=0;i<N;i++)
fscanf(file,“%d”,a+i);
for (int i=0;i<M;i++)
{
int b;
fscanf(file,“%d”,&b);
card[b]++;
}
fclose(file);
for (int i1=0;i1<=card[1];i1++)
for (int i2=0;i2<=card[2];i2++)
for (int i3=0;i3<=card[3];i3++)
for (int i4=0;i4<=card[4];i4++)
{
int get=a[1*i1+2*i2+3*i3+4*i4];
if (i1>0&&f[i1][i2][i3][i4]<f[i1-1][i2][i3][i4])
f[i1][i2][i3][i4]=f[i1-1][i2][i3][i4];
if (i2>0&&f[i1][i2][i3][i4]<f[i1][i2-1][i3][i4])
f[i1][i2][i3][i4]=f[i1][i2-1][i3][i4];
if (i3>0&&f[i1][i2][i3][i4]<f[i1][i2][i3-1][i4])
f[i1][i2][i3][i4]=f[i1][i2][i3-1][i4];
if (i4>0&&f[i1][i2][i3][i4]<f[i1][i2][i3][i4-1])
f[i1][i2][i3][i4]=f[i1][i2][i3][i4-1];
f[i1][i2][i3][i4]+=get;
}
file=fopen(PROBLEM“.out”,“w”);
fprintf(file,“%d\n”,f[card[1]][card[2]][card[3]][card[4]]);
fclose(file);
return 0;
}
#include <stdio.h>
#define PROBLEM “prison”
FILE* file;
const int MAXN=1<<20;
const int MAXM=1<<20;
const int UNCOLORED=-1,RED=0,BLUE=1;
struct Prison{int a,b,c;};
struct struct_edge{int v;struct_edge* n;};
typedef struct_edge* Edge;
int N,M;
Prison prison[MAXM];
Edge adj[MAXN];
struct_edge pool[MAXM*2];
Edge top;
int color[MAXN];
int answer=(~0u)>>1;
void quick_sort(int l,int r)
{
int i=l,j=r,mid=prison[(l+r)>>1].c;
while (i<=j)
{
while (i<=j&&prison[i].c>mid) i++;
while (i<=j&&prison[j].c<mid) j–;
if (i<=j)
{
Prison swap;
swap=prison[i],prison[i]=prison[j],prison[j]=swap;
i++,j–;
}
}
if (l<j) quick_sort(l,j);
if (i<r) quick_sort(i,r);
}
void add_edge(int u,int v)
{
top->v=v,top->n=adj[u],adj[u]=top++;
top->v=u,top->n=adj[v],adj[v]=top++;
}
void build_graph(int end)
{
top=pool;
for (int i=1;i<=N;i++) adj[i]=0;
for (int i=0;i<=end;i++)
add_edge(prison[i].a,prison[i].b);
}
bool color_node(int u,int which_color=RED)
{
if (color[u]!=UNCOLORED) return color[u]==which_color;
else
{
color[u]=which_color;
for (Edge i=adj[u];i;i=i->n)
if (!color_node(i->v,!which_color)) return false;
return true;
}
}
bool is_binary_graph()
{
for (int i=1;i<=N;i++) color[i]=UNCOLORED;
for (int i=1;i<=N;i++)
if (color[i]==UNCOLORED)
if (!color_node(i)) return false;
return true;
}
int main()
{
file=fopen(PROBLEM“.in”,“r”);
fscanf(file,“%d%d”,&N,&M);
for (int i=0;i<M;i++)
fscanf(file,“%d%d%d”,&prison[i].a,&prison[i].b,&prison[i].c);
fclose(file);
quick_sort(0,M-1);
int L=0,R=M;
while (L+1!=R)
{
int mid=(L+R)>>1;
build_graph(mid);
if (is_binary_graph()) L=mid;
else R=mid;
}
if (R!=M) answer=prison[R].c;
else answer=0;
file=fopen(PROBLEM“.out”,“w”);
fprintf(file,“%d\n”,answer);
fclose(file);
return 0;
}
#include <stdio.h>
#define PROBLEM “flow”
FILE* file;
const int MAXN=1<<10;
const int MAXM=1<<10;
const int oo=(~0u)>>1;
int N,M;
int height[MAXN][MAXM];
int color[MAXN][MAXM];
int adjs[MAXM];
int adj[MAXM][MAXM];
bool watered[MAXM];
int unwatered;
int begin[MAXM];
int end[MAXM];
int f[MAXM][MAXM];
int need;
void dfs(int x,int y,int start)
{
if (color[x][y]!=start)
{
color[x][y]=start;
if (height[x+1][y]<height[x][y]) dfs(x+1,y,start);
if (height[x-1][y]<height[x][y]) dfs(x-1,y,start);
if (height[x][y+1]<height[x][y]) dfs(x,y+1,start);
if (height[x][y-1]<height[x][y]) dfs(x,y-1,start);
if (x==N) adj[start][adjs[start]++]=y;
}
}
int main()
{
file=fopen(PROBLEM“.in”,“r”);
fscanf(file,“%d%d”,&N,&M);
for (int i=1;i<=N;i++)
for (int j=1;j<=M;j++)
fscanf(file,“%d”,height[i]+j);
fclose(file);
file=fopen(PROBLEM“.out”,“w”);
for (int i=1;i<=N;i++) height[i][0]=height[i][M+1]=oo;
for (int i=1;i<=M;i++) height[0][i]=height[N+1][i]=oo;
for (int i=1;i<=M;i++)
dfs(1,i,i);
for (int i=1;i<=M;i++)
for (int j=0;j<adjs[i];j++) watered[adj[i][j]]=true;
for (int i=1;i<=M;i++)
if (!watered[i]) unwatered++;
if (unwatered)
fprintf(file,“%d\n%d\n”,0,unwatered);
else
{
for (int i=1;i<=M;i++)
{
begin[i]=oo,end[i]=0;
for (int j=0;j<adjs[i];j++)
begin[i]=begin[i]<adj[i][j]?begin[i]:adj[i][j],
end[i]=end[i]>adj[i][j]?end[i]:adj[i][j];
}
f[0][0]=true;
for (int i=1;i<=M;i++)
if (begin[i]<=end[i])
for (int k=1;k<=M;k++)
{
if (f[k-1][end[i]]) f[k][end[i]]=true;
for (int j=begin[i]-1;j<=end[i];j++)
if (f[k-1][j]) f[k][end[i]]=true;
}
for (int i=1;i<=M;i++)
if (f[i][M])
{
need=i;
break;
}
fprintf(file,“%d\n%d\n”,1,need);
}
fclose(file);
return 0;
}