【蓝桥杯】C++ 第20场 小白入门赛
一、四个亲戚
题目
四个亲戚
题目分析
字面意思：Daiyu+‘kind’
代码
#include <iostream>
using namespace std;
int main()
{
cout<<"Daiyu'kind'";
return 0;
}
二、黛玉泡茶
题目
黛玉泡茶
题目分析
1.我们可以c
2.然后c
3.计算c，如果不能，整除后的答案还要加1
代码
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n, m, k;
int c[1000];
cin >> n >> m >> k;
for (int i = 0; i < n; i++)
{
cin >> c[i];
}
sort(c, c + n);//需要斟满的茶杯最小容量
long long int sum = 0, count = 0;
for (int i = 0; i < k; i++) //需要斟满的茶杯最小容量
{
sum += c[i];
}
if (sum % m != 0)//需要斟满的茶杯最小容量
{
count = sum / m + 1;
}
else
{
count = sum / m;
}
cout << count;
return 0;
}
三、宝玉请安
题目
宝玉请安
题目分析
分为三种情况，将宝玉、衡芜苑和潇湘馆所在位置距离正门的步数分别记为x,y,z。
1.当x<y且x<z时，步数为y与z两者之中最大者减去x
2.当x>y且x>z时，步数为x减去y与z两者之中最小者
3.当x位于y，z之间，先计算x距离y的距离与x距离z的距离那个小，即为mid，然后再将mid加上y与z之间的距离即为最大步数
代码
#include <iostream>
using namespace std;
int main()
{
int t;
cin >> t;
for (int i = 0; i < t; i++)
{
int x, y, z, count=0;
cin >> x >> y >> z;
if (x < y && x < z)
{
count = max(y, z) - x;
}
else if (x > y && x > z)
{
count = x - min(y, z);
}
else
{
int mid = min(max(y, z) - x, x - min(y, z));
count = mid + (max(y, z) - min(y, z));
}
cout << count << endl;
}
return 0;
}
四、贾母祝寿
题目
贾母祝寿
题目分析
思路一
这个思路是考试的时候写题想的，样例是对的，但是不能过。
过程就是硬推操作过程，然后将数组进行绝对值处理，然后排序，输出最大值
思路二
后面发现只需要抓住一个点，最值只会出现在首尾。
每次操作时，如果是1，则让首加y，如果是2，则让尾减y，还要注意x==n的特殊情况
代码
代码一
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
long long int n, q;
cin >> n >> q;
vector<long long int> a(n, 0);
for (long long int i = 0; i < q; i++)
{
long long int t, x, y;
cin >> t >> x >> y;
if (t == 1)
{
for (long long int j = 0; j < x ; j++)
{
a[j] += y;
}
}
else if (t == 2)
{
// 从数组末尾开始向前遍历 x 个元素
for (long long int j = n - 1; j >= n - x ; j--)
{
a[j] -= y;
}
}
}
transform(a.begin(), a.end(), a.begin(), [](long long int val) { return abs(val); });
auto max_brightness = *max_element(a.begin(), a.end());
// 输出最大亮度值
cout << max_brightness << endl;
return 0;
}
代码二
#include <iostream>
using namespace std;
int main()
{
int n, q;
long long int ans1 = 0, ans2 = 0;
cin >> n >> q;
for (int i = 0; i < q; i++)
{
int t, x, y;
cin >> t >> x >> y;
if (t == 1)
{
ans1 += y;
if (x == n)
{
ans2 += y;
}
}
else
{
ans2 -= y;
if (x == n)
{
ans1 -= y;
}
}
}
ans2 = -ans2;
if (ans1 > ans2)
{
cout << ans1;
}
else
{
cout << ans2;
}
return 0;
}
五、清洁客房
题目
清洁客房
题目分析
1.使用动态规划的方法
2.当只有1间客房时，且要求使用1种清洁等级（至少为1），则有9种方案（从1到9），所以为dp[1][1]=9
3.对于第i间客房，如果只用1种清洁等级，那么它必须和前一间客房使用相同的等级，所以 dp[i][1] = dp[i-1][1]。
4.如果用2种清洁等级，那么第i间客房可以选择和前一间客房相同的等级（此时前i-1间客房已经用了2种等级），或者选择一个新的等级（此时前i-1间客房只用了1种等级，且第i间客房的等级不能和前一间相同，所以有9-1=8种选择）。因此，dp[i][2] = dp[i-1][2] * 2 + dp[i-1][1] * 9。
5.如果用3种清洁等级，那么第i间客房可以选择和前一间客房相同的等级（此时前i-1间客房已经用了3种等级），或者选择一个新的等级（此时前i-1间客房用了2种等级，且第i间客房的等级不能和前一间相同，也不能和之前已经用过的另一种等级相同，所以有9-2=7种选择，但因为前i-1间客房的两种等级可以互换，所以实际上是8种选择）。因此，dp[i][3] = dp[i-1][3] * 3 + dp[i-1][2] * 8。
举例
假设n=3，我们要求的是3间客房使用3种不同清洁等级的方案数。
- 对于第1间客房，有9种选择（1到9）。
- 对于第2间客房，如果它和第1间客房使用相同的等级，那么前2间客房只用了1种等级；如果它选择一个新的等级，那么前2间客房用了2种等级。
- 对于第3间客房，如果它和前一间客房使用相同的等级，那么前3间客房可能用了1种或2种或3种等级；如果它选择一个新的等级，那么前3间客房一定用了3种等级
代码
#include <iostream>
using namespace std;
const int mod = 1e9 + 7;
const int n = 1e5 + 6;
long long int dp[n][4];
int main()
{
dp[1][1] = 9;//当只有1间客房时，且要求使用1种清洁等级（至少为1），则有9种方案（从1到9）
for (int i = 2; i < n; i++)
{
//对于i间客房，使用1种清洁等级时，只能继承前一间客房的1种清洁等级
dp[i][1] = dp[i - 1][1] % mod;
/*对于i间客房，使用2种清洁等级时，可以是在前一间客房使用2种等级的
基础上再添加一种相同的等级（乘以2），或者是在前一间客房使用1种等级
的基础上添加一种新的等级（乘以9，因为新的等级可以是1到9中的任意一
种，但不能是之前使用的那个等级，但0不能作为新的等级）*/
dp[i][2] = (dp[i - 1][2] * 2 + dp[i - 1][1] * 9) % mod;
/*对于i间客房，使用3种清洁等级时，可以是在前一间客房使用3种等级的
基础上再添加一种相同的等级（乘以3，因为3种等级都可以作为新的“相
同”等级），或者是在前一间客房使用2种等级的基础上添加一种新的等级
（乘以8，因为新的等级可以是剩下的7种等级中的任意一种，但0不能作为新的等级）*/
dp[i][3] = (dp[i - 1][3] * 3 + dp[i - 1][2] * 8) % mod;
}
int t;
cin >> t;
for (int i = 0; i < t; i++)
{
int n;
cin >> n;
cout << dp[n][3] << endl;
}
return 0;
}