一、四个亲戚
题目
四个亲戚
题目分析
字面意思：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;
}
