目录
\(NOIP2010\)提高组真题部分整理
\(T1\)机器翻译：
题目背景：
题目描述：
输入输出格式：
输入格式：
输出格式：
输入输出样例：
输入样例：
3 7
1 2 1 5 4 4 1
输出样例：
5
说明：
题解：
这道题应该是一道典型的队列题目。用队列来模拟翻译软件内存的调用与存储情况，如果有当前单词，就继续，如果没有，就将当前单词入队。然后根据队列中的元素个数来判断是否要将队尾元素出队。
这道题做完了，我只想总结一下队列的\(STL\)函数：
代码：
#include<cstdio>
#include<iostream>
#include<queue> //队列的STL函数所必备的头文件
using namespace std;
inline int read()//读入优化（就是传说中的快读）
{
int F=1,num=0;
char c=getchar();
while(!isdigit(c)){if(c=='-') F=-1; c=getchar();}
while(isdigit(c)){num=num*10+c-'0'; c=getchar();}
return num*F;
}
queue<int>q;//定义队列q
bool a[1500];//用a[i]来判断单词i是否在队列中出现过
int n,m;
int ans=0;//查询单词的次数
int main()
{
m=read(),n=read();
for(int i=1;i<=n;++i)//循环读入单词
{
int x=read();
if(a[x]==true) continue;//如果队列中有该单词，就继续读入
else if(q.size()<m)//如果队列中的元素不超过m个，即内存没有满
{
q.push(x);//将这个单词加入队列（加入内存）
ans++;//从外存查询单词的次数加一
a[x]=true;//现在队列中有了该元素，即内存中有了该单词
}
else if(q.size()==m)//如果队列已满，即内存炸了
{
a[q.front()]=false;//将队头元素弹出之前要将该元素标为“没有在队列中出现”
q.pop();//弹出队头元素
q.push(x);//将当前元素入队
ans++;//又在外存中查询了一次词典
a[x]=true;//当前的元素标记为已出现
}
}
printf("%d",ans);//直接输出查词典的数量就结束了
return 0;
}
\(T2\)乌龟棋
题目背景：
题目描述：
输入输出格式：
输入格式：
输出格式：
输入输出样例：
输入样例：
9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1
输出样例：
73
说明：
题解：
\(30\)分题解：
这道题我刚开始想到的是深度优先搜索（主要是最近做的搜索题太多了），但是这种方法只能得到\(30\)分，原因就是数据太毒，如果用搜索的话，复杂度应该是\(O(2^n)\)的，根本不能对其有任何奢望。但是代码还是可以看看的：
\(30\)分代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
inline int read()//读入优化
{
int F=1,num=0;
char c=getchar();
while(!isdigit(c)){if(c=='-') F=-1; c=getchar();}
while(isdigit(c)){num=num*10+c-'0'; c=getchar();}
return F*num;
}
int pos[5]={0,1,2,3,4};//这个数组存储当前出的卡片种类
int n,m;
int qi_pan[400];//棋盘上的对应得分
int ka_pian[150];//对应卡片的种类
int ans,sum;//ans是答案，sum是当前搜索的得分（将这两个值进行比较，就能得出最大值）
int num[5];//num[i]表示卡片类型为i的卡片数量
void dfs(int k,int d)//dfs(k,d)表示当前位置是k，已经用了d张卡牌
{
if(k==n)//如果当前位置已经到了终点
{
ans=max(ans,sum);//比较最大值
return ;//回溯
}
if(d==m)//如果当前已经用了所有的卡牌（因为题目保证用完所有卡牌后正好走到终点，所以这两个判断都是一样的）
{
ans=max(ans,sum);//比较最大值
return ;//回溯
}
else//如果没有到达终点
{
for(int i=1;i<=4;++i)//调用四种前进方式
{
if(num[pos[i]]>0)//如果当前前进方式仍有卡牌
{
int r=k+pos[i];//定义r为接下来搜索的起点
num[pos[i]]--;//减少一张卡牌
sum+=qi_pan[r];//已经得到的分加上当前的得分
dfs(r,d++);//继续搜索
sum-=qi_pan[r];
d--;
num[pos[i]]++;//回溯，将三个被更改过的变量进行还原
}
else//如果没有卡牌可以使用
continue;//看看下一张有没有用过（因为总会有没有用过的卡片的）
}
}
}
int main()
{
n=read(),m=read();//读入n和m
for(int i=1;i<=n;++i) qi_pan[i]=read();//读入这个棋盘
for(int i=1;i<=m;++i)
{
ka_pian[i]=read();//读入每个卡片的种类
num[ka_pian[i]]++;//处理num数组
}
dfs(1,0);//从第一个位置开始搜索，一张卡片都没有用
printf("%d",ans+qi_pan[1]);//输出时别忘了加上第一格所加的分数
return 0;//然后我们就愉快地得到30分啦！
}
\(100\)分题解：
搜索会炸，那么我们应该如何优化呢？
答案就是\(dp\)！
但是我们如何设状态呢？
接下来提供一种思路：
\(100\)分代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
inline int read()//一模一样的快读
{
int F=1,num=0;
char c=getchar();
while(!isdigit(c)){if(c=='-') F=-1; c=getchar();}
while(isdigit(c)){num=num*10+c-'0'; c=getchar();}
return num*F;
}
int n,m;
int qi_pan[400];//定义同上
int num[5];//定义同上
int dp[45][45][45][45];//4维dp的每一维都要在40位以上，否则就会RE
int main()
{
n=read(),m=read();
for(int i=1;i<=n;++i) qi_pan[i]=read();
for(int i=1;i<=m;++i)
{
int x=read();
num[x]++;
}
for(int i=0;i<=num[1];++i)
for(int j=0;j<=num[2];++j)
for(int k=0;k<=num[3];++k)
for(int l=0;l<=num[4];++l)
{
int now=1+1*i+2*j+3*k+4*l;//计算当前的得分
if(i) dp[i][j][k][l]=max(dp[i][j][k][l],dp[i-1][j][k][l]+qi_pan[now]);
if(j) dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j-1][k][l]+qi_pan[now]);
if(k) dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j][k-1][l]+qi_pan[now]);
if(l) dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j][k][l-1]+qi_pan[now]);//状态转移方程
}
printf("%d",dp[num[1]][num[2]][num[3]][num[4]]+qi_pan[1]);//我们要的答案就是所有卡牌都用上后的最大得分加上第一个位置对应的分数
return 0;//AC了
}
\(T4\)引水入城：
（\(T3\)关押罪犯博主暂时不会，就先咕咕咕了）
题目描述：
输入输出格式：
输入格式：
输出格式：
输入输出样例：
输入样例\(1\)：
2 5
9 1 5 4 3
8 7 6 1 2
输出样例\(1\)：
1
1
输入样例\(2\)：
3 6
8 4 5 6 4 4
7 3 4 3 3 3
3 2 2 1 1 2
输出样例\(2\)：
1
3
说明：
样例\(1\)说明：
样例\(2\)说明：
数据范围：
题解：
刚拿到题时，本人表示一脸懵逼。我$@%@#%@#@#，这@%@#%&@^!题啊？？？
解决方法当然是问大佬啊！\(\Omega\omega\Omega\)
首先我们考虑一个问题：
这样的话，我们可以跑一个搜索，处理出第一行每一个城市所对应的最后一行区间左右端点。然后跑一边贪心，处理区间覆盖问题就可以了
代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
inline int read()//又是这个快读
{
int F=1,num=0;
char c=getchar();
while(!isdigit(c)){if(c=='-') F=-1; c=getchar();}
while(isdigit(c)){num=num*10+c-'0'; c=getchar();}
return num*F;
}
int dx[5]={0,1,0,-1,0},dy[5]={0,0,1,0,-1};//存储搜索时的4个方向
int l[550][550],r[550][550];//l[x][y]和r[x][y]存储对应坐标(x,y)向下的左右区间端点
bool vis[550][550];//判断坐标是否被访问过
int map[550][550];//存图
int n,m;
void dfs(int x,int y)//搜索点(x,y)
{
vis[x][y]=true;//先标记为搜过
for(int i=1;i<=4;++i)//四个方向
{
int nx=x+dx[i],ny=y+dy[i];
if(nx<1||ny<1||nx>n||ny>m) continue;//如果出界了，就继续下一个方向
if(map[nx][ny]>=map[x][y]) continue;//如果不能流下，就继续下一个方向
if(!vis[nx][ny]) dfs(nx,ny);//如果当前点没有被搜索过，就搜索
l[x][y]=min(l[x][y],l[nx][ny]);//当前点的左端点为该点与下一个点的左端点的最小值（最靠左）
r[x][y]=max(r[x][y],r[nx][ny]);//当前点的右端点为该点与下一个点的右端点的最大值（最靠右）
}//其实这是一个递归过程，程序先找到最深的一层，然后用这一层的数值来更新前面几层的数值
}
int main()
{
n=read(),m=read();
memset(l,0x3f,sizeof(l));//清空l数组
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
map[i][j]=read();
for(int i=1;i<=m;++i) l[n][i]=r[n][i]=i;//初始化，令最后一排的每个城市的左端点和右端点都为自己
for(int i=1;i<=m;++i) if(!vis[1][i]) dfs(1,i);//如果第一行的某城市还没有被搜索过，就搜索这个城市
int how=0;//how是用来记录解的个数的
for(int i=1;i<=m;++i) if(!vis[n][i]) ++how;//从左往右扫一遍，如果有没有访问过的点，how+1
if(how!=0)//如果有未访问过的点
{
printf("0\n%d",how);//输出未访问过的点的个数，即没有水的城市的个数
return 0;//直接结束程序
}
int lft=1;//这个是用来存储当前的左端点的
while(lft<=m)//如果没有完全覆盖
{
int maxn=0;//其实是代表了右端点的最值
for(int i=1;i<=m;++i) if(l[1][i]<=lft) maxn=max(maxn,r[1][i]);//扫描一遍第一排的左端点，并且进行比较，来更新maxn的值，区间覆盖问题的思路
how++;//每选一个就将答案加一
lft=maxn+1;//然后找下一个区间
}
printf("1\n%d",how);//输出
return 0;
}