记录没好的集训
第二天传送门
第一题：字符串
很水不讲了（bushi
时间：0.2s 空间：64M
【题目描述】
给定一个字符串，然后将字符串倒序输出。
【输入描述】
输入一个字符串S(2<S长度<100)
【输出描述】
将字符串S倒序输出
【样例输入】
abc
【样例输出】
cba
没啥好讲的，上代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
string a;
cin >> a;
reverse(a.begin(), a.end());//没想到吧，有反转（doge
cout << a;
return 0;
}
第二题：剪绳子
时间：0.2s 空间：64M
【题目描述】
一条绳子从中间剪一刀可以剪成两段绳子；如果对折1次，中间剪一刀可以剪出3段绳子；如果连续对折2次，中间剪一刀可以剪出5段绳子；那么，连续对折n次，中间剪一刀可以剪出多少段绳子？
通过编写程序，在给定绳子对折次数，计算出中间剪一刀后可剪出绳子的段数。
【输入描述】
输入一个正整数n(2<n<20)作为绳子对折的次数
【输出描述】
输出一个正整数，表示对折n次后的绳子中间剪一刀可以剪出绳子的段数
【样例输入】
2
【样例输出】
5
对折n次后的绳子中间剪一刀可以剪出绳子的段数是2^n+1
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
cout << pow(2, n) + 1;
return 0;
}
第三题：合数求和
时间：0.2s 空间：64M
【题目描述】
合数指自然数中除了能被1和它本身整除外，还能被其他数（0除外）整除的数。最小的合数是4。
如：合数4既可以被1和4整除，还能被2整除。
给定一个正整数N，计算出4到N之间所有合数的和。
例如：N等于7，其中4到N之间合数有4、6，所有合数和等于10（4+6=10）
【输入描述】
输入一个正整数N(4<N<101)
【输出描述】
输出一个整数，表示4到N之间(包含4和N)所有合数的和
【样例输入】
7
【样例输出】
10
#include <bits/stdc++.h>
using namespace std;
bool check(int x){
for (int i = 2;i <= sqrt(x);i++){
if (x % i == 0) return true;
}
return false;
}
int main(){
int n,ans = 0;
cin>>n;
for (int i = 4;i <= n;i++){
if (check(i)) ans += i;
}
cout<<ans<<endl;
return 0;
}
第四题 求和比较
开始难起来力（悲
时间：0.2s 空间：64M
【题目描述】
小蓝在学习C++数组时，突发奇想想知道如果将一个连续的正整数数组拆分成两个子数组，然后对拆分出的两个子数组求和并做差，且差值正好等于一个固定的正整数，像这样同一连续的正整数数组拆分方案有多少种。
我们一起帮助小蓝设计一下规则：
第一给出两个正整数N和M；
第二从1到N组成一个连续正整数数组A（A={1,2,3,4……N}）；
第三将数组A拆分成两个子数组A1、A2（1.两个子数组中不能出现相同的数；2.子数组中的数字可以是连续的也可以是不连续的；3.拆分出的两组子数组的元素个数可以不同，但总数量等于A数组元素个数）；
第四对A1、A2两个子数组分别求和；
第五对A1、A2两个子数组的和做差（大的数字减去小的数字）；
第六如果差值正好等于固定值M，则判定此拆分方案成立。
如：N=5，M=1，连续正整数数组A={1, 2, 3, 4, 5}。
符合条件的拆分方案有3种：
A1={1, 2, 4}, A2={3, 5}, 其中A1的和为7，A2的和为8，和的差值等于1
A1={1, 3, 4}, A2={2, 5}, 其中A1的和为8，A2的和为7，和的差值等于1
A1={3, 4}, A2={1, 2, 5}, 其中A1的和为7，A2的和为8，和的差值等于1
【输入描述】
输入两个正整数N和M(3<N<30)和M(0≤M≤500)，两个正整数由一个空格隔开
【输出描述】
输出一个正整数，表示1到N（包含1和N）连续的正整数数组中有多少种方案，使得拆分的两个子数组部分的差值等于M。
【样例输入】
5 1
【样例输出】
3
我觉得用dfs吧·····
#include<bits/stdc++.h>
using namespace std;
int n,m,sum,x,cnt,a[35];
void dfs(int k){
if(sum==x)cnt++;
if(sum>x)return;
for(int i=a[k-1]+1;i<=n;i++){
sum+=i;
a[k]=i;
dfs(k+1);
sum-=i;
}
}
int main(){
cin>>n>>m;
x=(1+n)*n/2-m;
//剪枝
if(x%2!=0){
cout<<0;
return 0;
}
x/=2;
dfs(1);
if(m==0){
cout<<cnt/2;
return 0;
}
cout<<cnt;
return 0;
}
第五题：最大价值
感谢老师馈赠的背包（喜
时间：0.2s 空间：64M
【题目描述】
一名种菜的农民伯伯。需要在给定的时间内完成种菜，现有m种不同的蔬菜提供给农民伯伯选择，且每种蔬菜种植花费的时间不同，每种蔬菜成熟后售卖的价值也不同。
要求：
1.在限定的总时间内进行蔬菜种植，并且种植蔬菜的种类不能超出限制的数量；
2.选择最优的种植方案使得蔬菜成熟后售卖的总价值最大（可选择不同的蔬菜种植）。
例如：
给定的总时间限制为55，种植蔬菜的种类限制为3；
3种蔬菜，种菜的花费时间及售卖价格分别为：第一种21和9，第二种20和2，第三种30和21。
最优的种植方案是选择种植第一种和第三种，两种蔬菜种植总时间30+21，未超过总时间限制55。所种植蔬菜为两种，也未超过种类限制的3种。最大总价值为9+21=30，这个方案是最优的。
【输入描述】
第一行输入两个正整数 t(1<=t<=600)和 m(1<=m<=50)，用一个空格隔开，t代表种菜总时间限制，m代表最多可种植蔬菜种类的限制；
接下来的m行每行输入两个正整数 t1(1 < t1 < 101) 和 p(1 < p < 101) 且用一个空格隔开，t1表示每种蔬菜种植需要花费的时间，p表示对应蔬菜成熟后售卖的价格。
【输出描述】
输出一个正整数，表示选择最优的种植方案后，蔬菜成熟后售卖的最大总价值。
【样例输入】
53 3
21 9
20 2
30 21
【样例输出】
30
#include <bits/stdc++.h>
using namespace std;
int m,n,w[55],c[55],dp[605];
int main(){
cin>>m>>n;
for (int i = 1;i <= n;i++) cin>>w[i]>>c[i];
//一维优化
for (int i = 1;i <= n;i++){
for (int j = m;j >= 1;j--){
//牛波一公式
if (j >= w[i]) dp[j] = max(dp[j],dp[j - w[i]] + c[i]);
}
}
cout<<dp[m]<<endl;
return 0;
}
第六题：黑精灵与白精灵
时间：0.2s 空间：64M
【题目描述】
在一个矩阵精灵王国里有两个精灵，一个叫黑精灵，一个叫白精灵。他们住在一个N*M的矩阵方格中的不同位置，黑精灵住在矩阵方格的左上角（1，1），白精灵住在矩阵方格的右下角方格里（N，M）。
在这个矩阵方格例还有一对可穿越的们，这对穿越门的位置不固定，位置可变换（穿越门不会出现在矩阵方格左上角和右下角位置，也不会重叠出现，有且只有一对）。穿越门的功能是当进去其中一扇门的位置后可直接穿越到另一扇门的位置。
一天黑精灵要去白精灵家做客，需要穿过方格矩阵到达白精灵家，穿行矩阵方格要求：
1.每次只能走一个方格，可以向上、向下、向左、向右行走；
2.每走一个方格记为一步，但从一扇门穿越到另一扇门穿越门不记步数（从方格走到穿越门和从穿越门到其他方格都计1步）；
3.可借助穿越门去白精灵家（可减少行走步数）。
为了尽快到达白精灵家，请你帮助黑精灵找一条最短路线，并且计算出最短路线的步数。
例如：
给出一个3*4的矩阵方格，并给出第一个穿越门的坐标位置N1，M1（2，3），第二个穿越门的坐标位置N2，M2（3，1），已知黑精灵初始坐标位置左上角（1，1），白精灵坐标位置右下角（N，M）。
假设用两个大写字母“D”表示矩阵方格中穿越门的位置，1代表黑精灵，2代表白精灵，用数字0表示剩余矩阵方格。
如下图所示：
按照穿行矩阵方格要求为左上角方格的黑精灵到右下角方格白精灵家找一条最短路线，计算出最短路线的步数。
路线：从黑精灵初始位置（1，1）到正下方方格（2，1）走1步，正下方方格（2，1）到其下方穿越们（3，1）“D”走1步，然后穿越到另一扇穿越门（2，3）向正下方（3，3）走1步，最后到大白精灵家（3，4）需要走1步，故最短路线需要4步。
【输入描述】
第一行输入两个以一个空格隔开的正整数 N(2<N<101), M(2<M<101)，分别表示N行M列的方格矩阵。
接下来第二行输入两个以一个空格隔开的正整数：N1(N1<=N)，M1(M1<=M)，代表第一个穿越门位于第N1行第M1列；
接下来第三行输入两个以一个空格隔开的正整数：N2(N2<=N)，M2(M2<=M)，代表第二个穿越门位于第N2行第M2列；
注意：两个穿越门位置不能重叠，即不能同时满足N1=N2和M1=M2；两个穿越门位置也不能位于左上角（1，1）和右下角（M，N）；第一个穿越门位置要在第二个穿越门前边或者上边。
【输出描述】
输出一个整数，表示黑精灵去白精灵家最短路线需要走多少步（可借助穿越门，减少步数），如果没有能到达白精灵家的路线或者其他情况统一输出数字“0”。
【样例输入】
3 4
2 3
3 1
【样例输出】
4
看似是BFS，实际是曼哈顿（急
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
int n1, m1;
int n2, m2;
int x, y;
cin >> n >> m;
cin >> n1 >> m1;
cin >> n2 >> m2;
// (1, 1) -> (n1, m1) + (n2, m2) -> (n, m)
x = (n1 - 1) + (m1 - 1) + (n - n2) + (m - m2);
// (1, 1) -> (n2, m2) + (n1, m1) -> (n, m)
y = (n2 - 1) + (m2 - 1) + (n - n1) + (m - m1);
cout << min(x, y) << endl;
return 0;
}