NOIP 2010

机器翻译
乌龟棋
关押罪犯
引水入城

机器翻译

Solution

  维护一个队列, 每次从词典中查词时将单词加入队列(代表内存), 当内存满的时候, 从队首弹出一个代表清空最早的单词.

Code

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
#include<iostream>
#include<cstdio>
#include<queue>
#define N 1005
using namespace std;
queue<int>que;
int vis[N];
int main(){
int n,m,q,ans=0;
scanf("%d%d",&m,&n);
for(int i=1;i<=n;++i){
scanf("%d",&q);
if(!vis[q]){
if(que.size()==m){
vis[que.front()]=false;
que.pop();
}
que.push(q);
vis[q]=1;
ans++;
}
}
printf("%d",ans);
return 0;
}

乌龟棋

Solution

  比较原始的动态规划, $f(i,j,k,l)$表示使用了$i,j,k,l$张$1,2,3,4$的牌, 然后依次枚举$l,k,j,i$来更新$f(i,j,k,l)$.

Code

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
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#define N 45
using namespace std;
int dp[N][N][N][N];
int s1,s2,s3,s4;
int value[505];
int n,m,s;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&value[i]);
for(int i=1;i<=m;++i){
scanf("%d",&s);
if(s==1)s1++;if(s==2)s2++;
if(s==3)s3++;if(s==4)s4++;
}
int ans=0;
for(int d=0;d<=s4;++d)
for(int c=0;c<=s3;++c)
for(int b=0;b<=s2;++b)
for(int a=0;a<=s1;++a){
int siz=a+b*2+c*3+d*4;
if(siz>n)continue;
dp[a][b][c][d]+=value[siz+1];
int ma=dp[a][b][c][d];
if(a)ma=max(ma,dp[a-1][b][c][d]+value[siz+1]);
if(b)ma=max(ma,dp[a][b-1][c][d]+value[siz+1]);
if(c)ma=max(ma,dp[a][b][c-1][d]+value[siz+1]);
if(d)ma=max(ma,dp[a][b][c][d-1]+value[siz+1]);
dp[a][b][c][d]=ma;
// cout<<dp[a][b][c][d]<<endl;
if(siz+1==n)ans=max(ma,ans);
}
printf("%d",ans);
// system("pause");
return 0;
}

关押罪犯

做法

  并查集, 最开始有$2n$个集合, 代表每个点所属的集合和敌对的人所属的集合, 然后将所有敌对关系从大到小排序, 依次将一个点加入另一个点的敌对集合, 直到无法再加时就是最终的答案.

Code

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<iostream>
#include<cstring>
#include<cstdio>
#define N 515
#define inf 0x3f3f3f3f
using namespace std;
int dx[N]={0,0,-1,1};
int dy[N]={1,-1,0,0};
int h[N][N];
int be[N][N];
int also[N];
bool vis[N][N];
int n,m;
int color;
int flag=inf,en;
int visit[N];
struct Segment{
int u,v;
inline bool operator<(const Segment& s)const{
if(v!=s.v)return v>s.v;return u<s.u;
}
}e[N];
int tot;
inline bool Chu(int x,int y){
if(x<1||y<1||x>n||y>m)return false;
return true;
}
void dfs(int x,int y,int f){
vis[x][y]=true;
for(int i=0;i<4;++i){
int xx=dx[i]+x,yy=dy[i]+y;
if(vis[xx][yy])continue;
if(!Chu(xx,yy))continue;
if(h[xx][yy]>=h[x][y])continue;
be[xx][yy]=f;
if(xx==n)flag=min(flag,yy),en=max(en,yy);
dfs(xx,yy,f);
}
}
int main(){
scanf("%d%d",&n,&m);
if(n==1){
cout<<"1\n4";
return 0;
}
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
scanf("%d",&h[i][j]);
// cout<<"*****************\n";
for(int i=1;i<=m;++i){
memset(vis,false,sizeof(vis));
if(h[1][i-1]>h[1][i])continue;
if(h[1][i+1]>h[1][i])continue;
flag=inf;
dfs(1,i,i);if(flag==inf)continue;
e[++tot]=(Segment){flag,en};
// cout<<flag<<' '<<en<<' '<<i<<endl;
}
int ans=0;
for(int i=1;i<=m;++i){
if(!be[n][i])++ans;
// cout<<be[n][i]<<' ';
}
if(ans){
printf("0\n%d",ans);
return 0;
}
int l,r=1;int maxl,pos;ans=0;
while(r<m+1){
for(int i=1;i<=tot;++i){
if(e[i].v>500||e[i].u>500)break;
if(e[i].u<=r&&!visit[i])
if(e[i].v>maxl){
pos=i,maxl=e[i].v;
}
}
visit[pos]=true;
r=maxl+1;ans++;
} if(!ans)ans=1;
printf("1\n%d",ans);
// system("pause");
return 0;
}

引水入城

Solution

  并没有像他们说的那样会超时, 虽然使用了非常暴力的做法来处理.首先找出每个点能覆盖的处在沙漠中点的区间.然后做线段覆盖, 我处理的真的是非常随便.注意有一个数据是沙漠也是城市, 特判过; 另外如果一个临湖点比另一个一个相邻的点低, 就不需要遍历这个点了, 因为是肯定是它的子集.

Code

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<iostream>
#include<cstring>
#include<cstdio>
#define N 515
#define inf 0x3f3f3f3f
using namespace std;
int dx[N]={0,0,-1,1};
int dy[N]={1,-1,0,0};
int h[N][N];
int be[N][N];
int also[N];
bool vis[N][N];
int n,m;
int color;
int flag=inf,en;
int visit[N];
struct Segment{
int u,v;
inline bool operator<(const Segment& s)const{
if(v!=s.v)return v>s.v;return u<s.u;
}
}e[N];
int tot;
inline bool Chu(int x,int y){
if(x<1||y<1||x>n||y>m)return false;
return true;
}
void dfs(int x,int y,int f){
vis[x][y]=true;
for(int i=0;i<4;++i){
int xx=dx[i]+x,yy=dy[i]+y;
if(vis[xx][yy])continue;
if(!Chu(xx,yy))continue;
if(h[xx][yy]>=h[x][y])continue;
be[xx][yy]=f;
if(xx==n)flag=min(flag,yy),en=max(en,yy);
dfs(xx,yy,f);
}
}
int main(){
scanf("%d%d",&n,&m);
if(n==1){
cout<<"1\n4";
return 0;
}
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
scanf("%d",&h[i][j]);
// cout<<"*****************\n";
for(int i=1;i<=m;++i){
memset(vis,false,sizeof(vis));
if(h[1][i-1]>h[1][i])continue;
if(h[1][i+1]>h[1][i])continue;
flag=inf;
dfs(1,i,i);if(flag==inf)continue;
e[++tot]=(Segment){flag,en};
// cout<<flag<<' '<<en<<' '<<i<<endl;
}
int ans=0;
for(int i=1;i<=m;++i){
if(!be[n][i])++ans;
// cout<<be[n][i]<<' ';
}
if(ans){
printf("0\n%d",ans);
return 0;
}
int l,r=1;int maxl,pos;ans=0;
while(r<m+1){
for(int i=1;i<=tot;++i){
if(e[i].v>500||e[i].u>500)break;
if(e[i].u<=r&&!visit[i])
if(e[i].v>maxl){
pos=i,maxl=e[i].v;
}
}
visit[pos]=true;
r=maxl+1;ans++;
} if(!ans)ans=1;
printf("1\n%d",ans);
// system("pause");
return 0;
}
-------------本文结束感谢您的阅读-------------