又是记录煤耗集训的一天~~~（喜
第一天传送门
第一题：数组-密码破译
水题我为什么要写（bushi
时间：1s 空间：256M
题目描述：
天天和亮亮会做些坏事。他们正在手机上互相发短信。明明已经明确拦截了他们通过技术手段发送的信息。但是，显然他无法理解这些信息。原因是此信息已加密。
这时，名侦探柯南发送了加密方法，你能帮忙解密这些信息吗？
已知所有信息都由小写字母组成。加密方法是将a改为b，b改为c，c改为d … z改为a（即将每个小写字母改成字母表中靠后的一个字母）。
输入格式：
由小写字母和空格组成的字符串。
输出格式：
表示解密后的信息的字符串。
样本输入1：
qzmf vn ldm xh ph pt fzm chzm gtzh rgh az
样本输出1：
rang wo men yi qi qu gan dian huai shi ba
样本输入2：
ygd fd sh lt ygdm rgh szh ihzm czm kd
样本输出2：
zhe ge ti mu zhen shi tai jian dan le
约定：
1<=字符串的长度<=100
getline很重要，避免吃空格
getline(cin,string);
#include<bits/stdc++.h>
using namespace std;
string s;
int n;
int main(){
getline(cin,s);
for(int i=0;i<=s.size();i++){
if(s[i]==' ')continue;
if(s[i]=='z')s[i]='a';
else s[i]=s[i]+1;
}
cout<<s;
}
#第二题 交换瓶子
时间：0.2s 空间：64M
【题目描述】
有N个瓶子，编号 1 ~ N，放在架子上。
比如有5个瓶子：
2 1 3 5 4
要求每次拿起2个瓶子，交换它们的位置。
经过若干次后，使得瓶子的序号为：
1 2 3 4 5
对于这么简单的情况，显然，至少需要交换2次就可以复位。
如果瓶子更多呢？你可以通过编程来解决。
【输入描述】
第一行: 一个正整数N（N<10000）, 表示瓶子的数目
第二行：N个正整数，用空格分开，表示瓶子目前的排列情况。
【输出描述】
输出数据为一行一个正整数，表示至少交换多少次，才能完成排序。
【样例输入1】
5
3 1 2 5 4
【样例输出1】
3
【样例输入2】
5
5 4 3 2 1
【样例输出2】
2
我用的改进的选择排序，肥肠不戳：
#include<bits/stdc++.h>
using namespace std;
int n,a[114514],k,ans;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n-1;i++){
k=i;
for(int j=i+1;j<=n;j++){
if(a[k]>a[j])k=j;
}
if(k!=i){
swap(a[i],a[k]);
ans++;
}
}
printf("%d",ans);
}
第三题：买菜做饭
每日dp（1/2）
Description
为了做饭，出题人拿了 k 块钱，准备去买食材。出题人准备买一只螃蟹和若干蔬菜。菜场里有 n 只螃蟹，第 i只螃蟹的价格为 c_i，美味值为 v_i，菜场里有 m 个蔬菜，第 i 个蔬菜的价格为 w_i，美味值为 p_i，求出题人的钱能换来最大的美味值。
Input
第一行三个正整数 k,n,m，
接下来 n 行，每行两个正整数 c_i,v_i，
接下来 m 行，每行两个正整数 w_i,p_i，
相邻整数均以空格分开
Output
一行一个整数，表示出题人的钱能换来最大的美味值
Sample input
23 2 2
2 3
3 4
10 10
10 10
Sample output
24
Note
all the numbers <= 3000
Time and memory limit
1s ，512M
#include<bits/stdc++.h>
using namespace std;
int w[3010],v[3010],c[3010],p[3010],b[3010];//数组要开大一些
int main()
{
int k,m,n;
cin>>k>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>c[i]>>v[i];
}
for(int i=1;i<=m;i++)
{
cin>>w[i]>>p[i];
}
for(int i=1;i<=m;i++)
{
for(int j=k;j>=w[i];j--)
{
b[j]=max(b[j],b[j-w[i]]+p[i]);
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=c[i];j<=k;j++)
{
ans=max(ans,b[j-c[i]]+v[i]);
}
}
printf("%d\n",ans);
return 0;
}
第四题：走迷宫
时间限制：2s 空间限制：256M
描述
给定一个迷宫。在迷宫中有一些障碍物无法通过，请计算出从左上角到右下角的移动方案总数。（一个位置不能经过两次，只能上下左右四个方向走）
输入格式
第一行包含两个整数n，m，表示迷宫的大小。1 <= N，M<= 6
接下来的n行，每行包含m个字符，代表迷宫。
＃代表障碍
*代表你可以去的位置
左上角和右下角用“*”表示
输出格式
一个整数。
样本输入1
5 6
*****#
*###*#
*###*#
*###*#
******
样本输出1
2
样本输入2
6 6
******
******
******
******
******
******
示例输出2
1262816
提示
答辩的搜索题
试试Python吧！
def dfs(x,y):
global a
global method
global n,m
if x==n-1 and y==m-1:
method+=1
return
if y<m-1 and a[x][y+1]=="*" and v[x][y+1]==0:
v[x][y+1]=1
dfs(x,y+1)
v[x][y+1]=0
if x<n-1 and a[x+1][y]=="*" and v[x+1][y]==0:
v[x+1][y]=1
dfs(x+1,y)
v[x+1][y]=0
if y>0 and a[x][y-1]=="*" and v[x][y-1]==0:
v[x][y-1]=1
dfs(x,y-1)
v[x][y-1]=0
if x>0 and a[x-1][y]=="*" and v[x-1][y]==0:
v[x-1][y]=1
dfs(x-1,y)
v[x-1][y]=0
return
n,m=map(int,input().split())
a=[]
v=[[0 for i in range(m)] for i in range(n)]
method=0
for i in range(n):
a.append(list(input()))
v[0][0]=1
dfs(0,0)
print(method)
第五题：Maze Visit Order
给定一个 n 行 m 列的迷宫，找出访问的单元格顺序，每次尝试按上、左、右、下的给定顺序移动。迷宫由0和1组成，其中1表示墙，0表示可以进入的有效单元格。我们的起始位置在左上角(0, 0)。
1 ≤ n，m ≤ 100
输入：
第一行是两个用空格分隔的整数 n 和 m，其中 n 是迷宫的行数，m 是迷宫的列数。
接下来的 n 行有 m 个用空格分隔的整数，表示墙或开放单元格。
输出：
一个 n x m 的矩阵，其中每个单元格表示单元格被访问的顺序。如果该单元格无法被访问，则将其放置为0。
示例输入：
3 4
0 0 0 0
1 0 1 0
0 0 0 0
示例输出：
1 2 3 4
0 9 0 5
10 8 7 6
答辩的搜索+10086
用一条路走到黑的dfs，因为是一条路径
#include<bits/stdc++.h>
using namespace std;
int n,a[114][114],vis[114][114],m,k,sum;
//方向数组很重要，6次才AC
int dx[]={-1,0,0,1};
int dy[]={0,-1,1,0};
void dfs(int x,int y){
if(sum==k+1){
return;
}
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(vis[nx][ny]==0 && nx>=1 && nx<=n && ny<=m && ny>=1){
sum++;
vis[nx][ny]=sum;
dfs(nx,ny);
}
}
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
if(a[i][j]==1){
vis[i][j]=-1;
continue;
}
k++;
}
}
if(vis[1][1]==-1){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
printf("0 ");
}
printf("\n");
}
return 0;
}
sum++;
vis[1][1]=1;
dfs(1,1);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(vis[i][j]==-1)printf("0 ");
else printf("%d ",vis[i][j]);
}
printf("\n");
}
}
第六题：制作沙拉
问题描述
有 n 个水果，每个水果有两个属性：美味值和卡路里值。
现在选用若干个（至少 1 个）水果制作一份特殊的沙拉，沙拉的美味值为所选的水果的美味值的和，沙拉的卡路里值为所选水果的卡路里值的和。
沙拉的美味值恰好是卡路里值的 K 倍。请计算该沙拉美味值最大为多少。
输入数据
第一行，两个整数 n, k (1 ≤ n ≤ 100, 1 ≤ k ≤ 10)；
第二行，包含 n 个整数，a1, a2, …, an (1 ≤ ai ≤ 100)，表示水果的美味值；
第三行，包含 n 个整数，b1, b2, …, bn (1 ≤ bi ≤ 100)，表示水果的卡路里值。
输出数据
共一行，一个整数，表示最大美味值，若无解则输出-1。
样例输入1
3 2
10 8 1
2 7 1
样例输出1
18
样例输入2
5 3
4 4 4 4 4
2 2 2 2 2
样例输出2
-1
每日DP（2/2）
新奇的写法
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n,k;
int sp[101],cr[101],a[101],b[101],ta=0,tb=0,f[10001],g[10001];
int getVal(int t){
return sp[t]-k*cr[t];
}
int main(){
cin>>n>>k;
for (int i=1;i<=n;i++)
cin>>sp[i];
for (int i=1;i<=n;i++)
cin>>cr[i];
int temp;
for (int i=1;i<=n;i++){
temp=getVal(i);
if (temp>=0)
a[ta++]=i;
else if (temp<0)
b[tb++]=i;
}
memset(f,0xf3,sizeof(f));
memset(g,0xf3,sizeof(g));
f[0]=0;
g[0]=0;
for (int i=0;i<ta;i++)
for (int j=10000;j>=getVal(a[i]);j--)
f[j]=max(f[j],f[j-getVal(a[i])]+sp[a[i]]);
for (int i=0;i<tb;i++)
for (int j=10000;j>=-getVal(b[i]);j--)
g[j]=max(g[j],g[j+getVal(b[i])]+sp[b[i]]);
int ss;
int maxx=-1;
for (ss=10000;ss>=1;ss--)
if (f[ss]>0&&g[ss]>0){
maxx=max(f[ss]+g[ss],maxx);
}
cout<<maxx;
return 0;
}
