A – Chocolate Thief 巧克力小偷
题意：
我给了一些学生巧克力，以奖励他们的杰出表现。巧克力是一个立方体形状的东西，它有长度、宽度和高度。所有学生得到的巧克力数量相同；它们的尺寸可能不同，但体积是相同的。现在，一些学生声称他们中间有一个巧克力小偷。因此，对我来说，找出巧克力小偷并不是一件容易的事，所以我在请求你的帮助。
你将得到学生的名字和他们巧克力的尺寸；你必须找出巧克力小偷的名字。你可以假设最多只有一个小偷，如果有小偷的话，他只从另一个学生（而不是多个学生）那里拿走了一部分巧克力。
nenu 蓝桥杯训练赛（简单模拟+思维） – Virtual Judge (vjudge.net)
思路：
一个很简单的模拟，既然正常巧克力的体积都相同，那我们就计算所有巧克力的体积，比别人大的那个就是小偷，比别人小的那个就是被偷的那个。所以我们可以提出一种暴力一点的思路，就是求平均值体积之后，再遍历一遍，找到那个体积大的和那个体积小的就行。如果所有人巧克力体积都一样，说明没有小偷，直接输出。
代码C++：
#include<bits/stdc++.h>
using namespace std;
struct stu{
string name;
int a,b,h;
}s[10000];
int t,tt;
void solve(){
int n;
cin >> n;
string temp1,temp2;
int maxx = -1,minn = 100000000,aver = 0;
//循环一次，求平均值，找到最大和最小的
for(int i = 1;i <= n;i++){
cin >> s[i].name >> s[i].a >> s[i].b >> s[i].h;
maxx = max(s[i].a * s[i].b * s[i].h,maxx);
minn = min(s[i].a * s[i].b * s[i].h,minn);
aver += s[i].a * s[i].b * s[i].h;
}
aver /= n;
//如果最大值和最小值相等，说明没有小偷
if(maxx == minn){
cout << "Case " << t - tt << ": no thief\n";
}else{
//发现存在小偷了之后，记录小偷的名称【其实也可以在第一次循环里记录的，这个优化交给读者】
for(int i = 1;i <= n;i++){
if(s[i].a * s[i].b * s[i].h > aver) {
temp1 = s[i].name;
}else if(s[i].a * s[i].b * s[i].h < aver) {
temp2 = s[i].name;
}
}
cout << "Case " << t - tt << ": " << temp1 << " took chocolate from " << temp2 << "\n";
}
}
int main(){
cin >> t;
tt = t;
while(tt--) solve();
}B – Hidden Secret! 隐藏的秘密
题意：
这个问题中，你需要判断一个名字是否隐藏在另一个名字中。规则如下：
- 你可以自由地将一些大写字母改成小写，或者反之。
- 你可以自由地添加/移除空格。
- 你可以重新排列字母。
如果两个名字完全匹配，那么你可以说一个名字隐藏在另一个名字中。
nenu 蓝桥杯训练赛（简单模拟+思维） – Virtual Judge (vjudge.net)
思路：
给你两行名字，让你判断一行名字有没有隐藏在另一个名字里，并且你可以随意排列你的字母。既然我可以随意排列字母，那字母的顺序就不重要，我们只要关注这一行出现的字母是否能在另一行出现一次就行了。所以我们只需要考虑两行字母的种类和字母的个数。我们分别统计两行字母的个数，如果一行字母的个数全都大于另一行字母的个数，说明这个字母能在这一行随意出现。
打个比方，假设第一行是aaabbb，第二行是ab，我们发现第一行的a有3个，b有三个，都大于第二行的a、b个数，说明第二行的字母可以随意在第一行出现，因为第一行的字母是“够用”的。
所以我们的思路就是数这两行的字母个数，只要一行各个字母个数都大于另一行，就是Yes。否则，就是No。
代码C++：
/*
* 这段代码只是一种实现方式，同样的思路可以有很多不同的实现方式的，这段代码其实可以不用这么复杂，读者可以自行优化
*/
#include<bits/stdc++.h>
using namespace std;
int alp[1000];
int t,tt;
void solve(){
string a,b;
getline(cin,a);
getline(cin,b);
int len1 = a.size();
int len2 = b.size();
for(int i = 0;i < 200;i++){
alp[i] = 0;
}
//统计第一行中字母表各个字母的个数
for(int i = 0;i < len1;i++){
if(a[i] >= 'a' && a[i] <= 'z'){
alp[a[i] - 'a']++;
}
if(a[i] >= 'A' && a[i] <= 'Z'){
alp[a[i] - 'A']++;
}
}
//减去第二行中字母表各个字母的个数
for(int i = 0;i < len2;i++){
if(b[i] >= 'a' && b[i] <= 'z'){
alp[b[i] - 'a']--;
}
if(b[i] >= 'A' && b[i] <= 'Z'){
alp[b[i] - 'A']--;
}
}
int flag1 = 0;
for(int i = 0;i < 26;i++){
if(alp[i] < 0){
flag1 = 1;
}
}
//没有负的，说明第一行的字母个数比第二行都多
if(flag1 == 0){
cout << "Case " << t - tt << ": Yes" << "\n";
return;
}
flag1 = 0;
for(int i = 0;i < 26;i++){
if(alp[i] > 0){
flag1 = 1;
}
}
//没有正的，说明第二行的字母个数比第一行都多
if(flag1 == 0){
cout << "Case " << t - tt << ": Yes" << "\n";
return;
}
//否则，就输出No
cout << "Case " << t - tt << ": No" << "\n";
}
int main(){
cin >> t;
tt = t;
cin.ignore();
while(tt--) solve();
}C – Scarecrow 稻草人
题意：
塔索拥有一片非常长的田地。他计划在即将到来的种植季节种植不同类型的作物。然而，这片区域到处都是乌鸦，塔索担心它们可能会吃掉大部分作物。因此，他决定在田地的不同位置放置一些稻草人。
这片田地可以被建模为 1 x N 的网格。田地的一些部分是不育的，这意味着你不能在上面种植任何作物。当稻草人放置在一个位置时，它会覆盖它所在的单元格以及其左右紧邻的单元格。根据田地的描述，需要放置最少数量的稻草人来覆盖所有有用的田地部分吗？有用的部分指的是可以种植作物的单元格。
输入以一个整数 T（≤ 50）开始，表示测试用例的数量。
每个案例以一个包含整数 N（0 < N < 100）的行开始。下一行包含 N 个字符来描述田地。点号 . 表示可以种植作物的地方，井号 # 表示不育的区域。
nenu 蓝桥杯训练赛（简单模拟+思维） – Virtual Judge (vjudge.net)
思路：
其实就是问你一行田地，要放几个稻草人覆盖有用的田地。一个稻草人能覆盖三个位置，然后问你需要有几个稻草人。这题在脑海中模拟一下，其实就是每个 . 都需要稻草人，既然需要最少的，我们就从左往右一点点想。我们可以采用贪心的策略，每次遇到一个 . 之后，我们知道这个点需要被稻草人保护，所以稻草人数量+1，然后我们跑到三格之后继续考虑。因为我们知道那个 . 必须被稻草人保护，所以那个稻草人是必须的，既然一定会放一个稻草人在这，那稻草人保护范围内的格子到底是什么这件事，我们根本不需要考虑，因为这里一定会放置一个稻草人。我们只需要跑到三格之后继续之前的步骤就行。
代码C++：
#include<bits/stdc++.h>
using namespace std;
int t,tt;
void solve(){
int n;
cin >> n;
string s;
cin >> s;
int count = 0;
for(int i = 0;i < n;i++){
if(s[i] == '.'){
count++;
i += 2;
}
}
cout << "Case " << t - tt << ": " << count << "\n";
}
int main(){
cin >> t;
tt = t;
while(tt--) solve();
}D – Again Array Queries 再次数组查询
题意：
给定一个包含 n 个整数的数组，同时给定数组中的两个索引 i 和 j（i ≠ j）。你需要找到该范围内两个整数，使它们的差值最小。数组的索引从 0 到 n-1。
输入以一个整数 T（T ≤ 5）开始，表示测试用例的数量。
每个测试用例包含两个整数 n（2 ≤ n ≤ 10^5）和 q（1 ≤ q ≤ 10000）。下一行包含 n 个用空格分隔的整数，这些整数构成了数组。这些整数的取值范围在 [1, 1000] 之间。
接下来的 q 行，每行包含两个整数 i 和 j（0 ≤ i < j < n）。
nenu 蓝桥杯训练赛（简单模拟+思维） – Virtual Judge (vjudge.net)
思路：
这题题意都能理解，但是思路不太容易想到。我们就是想知道说在 i 和 j 之间最小的差值是多少。其实就是我们可以把第 i 个到第 j 个之间的数组排个序，然后看看哪一段间距最小【因为差值一定是最近的两个数字之间的差值】。但是我们做不到10000次询问里，每次都把 i 到 j 之间的那部分数组都排序一次，因为这样 n * nlogn 的极限情况是一定会超时的【笔者尝试了好几次】。这题的突破点在于，所有整数的取值范围是有限的，只有[1, 1000]的数据范围。我们可以遍历一遍这个范围，看看从 i 到 j 里出现过的那些数字都在哪。假设一个数字出现两次，说明存在最小差值0。假设所有数字都只出现一次，那我就看上一次出现的数字和这一次出现的数字之间的差值是多少。最后从头走到尾一遍，取差值的最小值就好。
代码C++：
#include<bits/stdc++.h>
using namespace std;
int t,tt;
int a[100007];
int cnt[1007];
void solve(){
cout << "Case " << t - tt << ":" << "\n";
int n,q;
cin >> n >> q;
for(int i = 0;i < n;i++){
cin >> a[i];
}
for(int i = 1;i <= q;i++){
int l,r;
cin >> l >> r;
memset(cnt,0,sizeof(cnt));
for(int j = l;j <= r;j++){
cnt[a[j]]++;
}
int ans = 0x3f3f3f3f;
int pre = -ans;
for(int j = 1;j <= 1000;j++){
//没出现过的数字就跳过
if(cnt[j] == 0){
continue;
}
//说明有数字重复出现
if(cnt[j] >= 2){
ans = 0;
break;
}
ans = min(ans,j - pre);
//pre存储上一次出现过的数字
pre = j;
}
cout << ans << "\n";
}
}
int main(){
cin >> t;
tt = t;
while(tt--) solve();
}E – Scenes From a Memory 记忆场景
题意：
在催眠会议期间，尼古拉斯突然记起了一个正整数 n，这个数在十进制表示中不包含零。
不久，当他回到家时，他变得好奇：可以从这个数中移除最多多少位数字，使得这个数变成非质数，也就是变成合数或者等于一？
对于某些数字来说，这是不可能的：例如，对于数字 53，不可能通过删除部分数字来得到一个非质数的整数。然而，对于本问题测试用例中的所有 n，保证可以通过删除部分数字来得到一个非质数。
注意，你不能删除数中的所有数字。
质数是除了一和其本身外没有其他因数的数。合数是有两个以上因数的数。1 既不是质数也不是合数。
每个测试包含多个测试用例。
第一行包含一个正整数 t（1≤t≤10^3），表示测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个正整数 k（1≤k≤50）——数字的位数。
每个测试用例的第二行包含一个正整数 n，在十进制表示中不包含零（10^(k−1)≤n<10^k）。保证总是可以通过删除少于 k 位数字使得数变成非质数。
保证所有测试用例中 k 的总和不超过 10^4。
对于每个测试用例，你需要打印两行数字。在第一行打印你在数字中保留的位数。在第二行打印所有删除后留下的数字。
在存在多个解决方案时，我们可以选择打印任何一个。
nenu 蓝桥杯训练赛（简单模拟+思维） – Virtual Judge (vjudge.net)
思路：
简单来说，就是给你一个很大很大的数字，然后删掉任意几位，让这个数字变成一个合数或者1，怎么删不重要，反正最后得到的数字满足条件就行了。然后因为这个数字可能很大很大，所以我们用字符串来处理。如果字符串中包含1或者4或者6或者8或者9，我们就只保留该数字，其它全部删掉就好了；如果只包含2或者3或者5或者7，我们就找他们可能凑成的所有两位数就可以了。所有对于第二种情况，我们暴力遍历字符串里所有可能组成的两位数，如果哪个两位数是合数，我们就直接输出，然后结束。
代码C++：
#include<bits/stdc++.h>
using namespace std;
int t,tt;
int cnt[100];
bool _is(int n){
int flag = 0;
for(int i = 2;i <= sqrt(n);i++){
//不是素数
if(n % i == 0){
flag = 1;
}
}
if(flag) return false;
return true;
}
void solve(){
memset(cnt,0,sizeof(cnt));
string n;
int k;
cin >> k;
cin >> n;
for(int i = 0;i < k;i++){
int temp = n[i] - '0';
cnt[temp]++;
if(temp == 1 || temp == 4 || temp == 6 || temp == 8 || temp == 9){
cout << 1 << "\n" << temp << "\n";
return;
}
}
//2 3 5 7的情况
cout << 2 << "\n";
for(int i = 0;i < k;i++){
for(int j = i + 1;j < k;j++){
int num = (n[i] - '0') * 10 + n[j] - '0';
if(!_is(num)){
cout << num << "\n";
return;
}
}
}
}
int main(){
cin >> t;
tt = t;
while(tt--) solve();
}F – Maximum Product 最大乘积
题意：
给定一个整数数组，找出所有五个索引 (i, j, k, l, t)（i < j < k < l < t）中 a_i × a_j × a_k × a_l × a_t 的最大可能值。
nenu 蓝桥杯训练赛（简单模拟+思维） – Virtual Judge (vjudge.net)
思路：
正反排序数组，数组a从小到大，数组b从大到小，然后从数组a中选取 0 ~ 5 个，从数组b中选取 5 – i 个【 i 表示从数组a中选取的个数】，这样就是正的和负的都有可能被选中。然后把选中的这些数字相乘，枚举所有可能，取最大值，就能得到结果。
这题的思路可能比较难想到，但是其实仔细想一想，这是显而易见的，因为最大乘积的因子，一定是由最大的这几个正数和绝对值最大的这几个负数组成。
这题数据范围会超过 int ，所有需要开 long long 防止溢出。
代码C++：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int a[100007];
int b[100007];
bool cmp(int a,int b){
return a > b;
}
void solve(){
int n;
cin >> n;
for(int i = 1;i <= n;i++){
cin >> a[i];
b[i] = a[i];
}
sort(a + 1,a + n + 1);
sort(b + 1,b + n + 1,cmp);
ll ans = -INF;
for(int i = 0;i <= 5;i++){
int j = 5 - i;
ll sum = 1;
//取最大的几个正数
for(int k = 1;k <= i;k++){
sum *= a[k];
}
//取绝对值最大的几个负数
for(int k = 1;k <= j;k++){
sum *= b[k];
}
ans = max(ans,sum);
}
cout << ans << "\n";
}
int main(){
int t;
cin >> t;
while(t--) solve();
}G – Sifid and Strange Subsequences “Sifid和奇怪的子序列”
题意：
一个序列 (b1,b2,…,bk) 被称为奇怪的，如果其任何一对元素之间的绝对差值大于或等于序列中的最大元素。形式上来说，如果对于所有 1≤i<j≤k 的 (i,j) 对，我们有 |ai−aj|≥MAX，其中 MAX 是序列中的最大元素，则它是奇怪的。
特别是，任何长度至多为 1 的序列都是奇怪的。 例如，序列 (-2021,−1,−1,−1) 和 (-1,0,1) 是奇怪的，但 (3,0,1) 不是，因为 |0−1|<3。
Sifid 有一个整数数组 a。Sifid 喜欢所有大的东西，因此在 a 的所有奇怪子序列中，他想找到最长的子序列的长度。你能帮帮他吗？序列 c 是数组 d 的子序列，如果 c 可以通过删除几个（可能为零或全部）元素从 d 获得。
nenu 蓝桥杯训练赛（简单模拟+思维） – Virtual Judge (vjudge.net)
思路：
对于这种思维题，我们其实可以来思考题目的定义本身可以怎么被表述。题目是让我们找最长的奇怪子序列，这个序列的特点就是其中任意数之差的绝对值要大于这两个数。
我们可以把玩一下样例，分类讨论一下。
如果序列全是负数的情况，一定是满足的，毕竟所有的绝对值一定都比负数大。
假设序列有大于或等于两个正数，我们会发现，这两个数的差的绝对值一定会小于这两个数，所以这个序列一定不奇怪。
假设序列里就一个正数，就比较复杂了，比如（-1，0，2）这个序列就不是个奇怪序列，因为|-1 – 0| = 1 ＜ 2，所以这个正数选还是不选，取决于非正数们的最小差值是否大于等于这个正数，所以我们可以找到最小的正数做特判就好了。
总结完了，也就是说，我们要的最长序列的组成就是所有负数 + 所有的0 + 特别判断。
代码C++：
#include<bits/stdc++.h>
using namespace std;
int a[1000000];
void solve(){
int n;
cin >> n;
int sum = 0;
int minn = 0x3f3f3f3f;
int flag = 0;
for(int i = 1;i <= n;i++){
cin >> a[i];
if(a[i] > 0) {
minn = min(minn,a[i]);
flag = 1;
}
}
sort(a + 1,a + n + 1);
//如果是非正数我们都取
for(int i = 1;i <= n;i++){
if(a[i] <= 0) sum++;
}
//存在正数
if(flag){
int temp = 0x3f3f3f3f;
//考虑是否要取最小的正数
for(int i = 2;i <= n;i++){
if(a[i] > 0) break;
temp = min(a[i] - a[i - 1],temp);
}
//非正数们的最小差值要大于等于最小的正数，才能sum+1
for(int i = 1;i <= n;i++){
if(temp >= minn){
sum++;
break;
}
}
}
cout << sum << "\n";
}
int main(){
int t;
cin >> t;
while(t--) solve();
}H – Nastia and Nearly Good Numbers Nastia和几乎好的数
题意：
Nastia有两个正整数A和B。她定义：
- 如果一个整数能被A和B的乘积整除，那么这个整数就是好的；
- 否则，如果一个整数能被A整除，那么这个整数就是近似好的。
例如，如果A=6，B=4，那么整数24和72是好的，整数6，660和12是近似好的，整数16，7既不好也不近似好。
你的任务是找到三个不同的正整数x，y，和z，使得它们中恰好有一个是好的，其他两个是近似好的，并且x+y=z。
输入格式： 第一行包含一个单独的整数t (1≤t≤10000) — 测试用例的数量。
每个测试用例的第一行包含两个整数A和B (1≤A，B≤10^6) — Nastia拥有的数字。
输出格式： 对于每个测试用例，打印：
- 如果存在答案，打印”YES”，并给出三个不同的正整数x，y，和z (1≤x，y，z≤10^18)，使得它们中恰好有一个是好的，其他两个是近似好的，并且x+y=z。
- 如果不存在答案，打印”NO”。
你可以用任何大小写打印”YES”或”NO”。如果有多个答案，打印任何一个即可。
nenu 蓝桥杯训练赛（简单模拟+思维） – Virtual Judge (vjudge.net)
思路：
现在我们来梳理题目，就是我们需要找一找有没有一组不同的x y z满足x + y = z且其中一个是好的，另外两个是近似好的。也就是有一个变量可以被AB整除，另外两个都是可以被A整除，不能被B整除。我们可以发现所有变量都能被A整除，我们把x、y、z同除以A，可以得到一个B的表达式。首先我们来思考，什么时候会输出NO？对于A来说，我们一定能找到一组xyz的公因子是A。对于B来说，如果B为1,则条件1和2没用区别了，因为谁都能被AB的乘积整除了，如果一个数是近似好的，它也一定是好的。所有这个时候就不会满足【其中一个是好的，另外两个是近似好的】的条件。
所有当B = 1的时候输出NO。
当B > 1的时候，则有AB = A + A * (B – 1)一定是满足x + y = z的条件。此时，z一定是好的，A和A * (B – 1)一定是近似好的。看起来已经满足条件了。
但是。
我们会发现B = 2的时候，x 和 y相等，这与题目要求不符合。所以我们的构造可以换成 A(B + 1) = AB + A，此时一样满足条件，且不存在相等的情况。此时x为AB，y为A，z为A(B + 1)。
这题注意要开long long。
代码C++：
#include<bits/stdc++.h>
using namespace std;
void solve(){
long long a,b;
cin >> a >> b;
if(b == 1){
cout << "NO" << "\n";
return;
}else{
cout << "YES" << "\n";
cout << a * b << " " << a << " " << a * (b + 1) << "\n";
}
}
int main(){
int t;
cin >> t;
while(t--) solve();
}I – A-B Palindrome A-B 回文
题意：
你将得到一个由字符 ‘0’，’1′ 和 ‘?’ 组成的字符串s。你需要将字符串s中的所有 ‘?’ 字符替换为 ‘0’ 或 ‘1’，使得替换后的字符串成为一个回文串，并且恰好有a个 ‘0’ 字符和b个 ‘1’ 字符。注意，每个 ‘?’ 字符的替换都是独立于其他字符的。
如果一个长度为n的字符串t满足所有的 t[i]=t[n−i+1] (1≤i≤n)，那么我们称这个字符串为回文串。
例如，如果 s=”01?????0″, a=4 和 b=4，那么你可以按以下方式替换 ‘?’ 字符：
- “01011010”;
- “01100110”.
对于给定的字符串s和数字a和b，将字符串s中的所有 ‘?’ 字符替换为 ‘0’ 或 ‘1’，使得字符串成为一个回文串，并且恰好有a个 ‘0’ 字符和b个 ‘1’ 字符。
输入格式： 第一行包含一个单独的整数t (1≤t≤10^4)。然后是t个测试用例。
每个测试用例的第一行包含两个整数a和b (0≤a,b≤2⋅10^5，a+b≥1)。
每个测试用例的第二行包含一个长度为a+b的字符串s，由字符 ‘0’，’1′ 和 ‘?’ 组成。
保证所有测试用例的字符串s的长度总和不超过2⋅10^5。
输出格式： 对于每个测试用例，输出：
- 如果不能将字符串s中的所有 ‘?’ 字符替换为 ‘0’ 或 ‘1’ 使得字符串成为一个回文串并且恰好包含a个 ‘0’ 和b个 ‘1’，则输出 “-1″；
- 否则，输出替换后得到的字符串。
如果有多种适当的替换方式，你可以输出任何一种。
nenu 蓝桥杯训练赛（简单模拟+思维） – Virtual Judge (vjudge.net)
思路：
这题大致意思就是让我们找回文字符串。其实读完题自然就能得到一个很朴素的思路。就是我们先左右对称着看，先让字符串想办法对称，然后再去看看剩余可用的 ‘0’ 和 ‘1’ 的个数是否满足双问号的情况。
也就是说，我们先考虑，剩余的a、b可否满足一边是问号，另一边不是问号的情况，如果可以，我们就填进去。
如果对称两边都不是问号，那我们就看看它们是否相等，不相等就直接结束。
最后的最后，我们才开始考虑双问号的情况，我们每次减2个a或者b，看看最后能不能满足。注意，要考虑字符串长度为奇数的情况，此时对称两边会指向最中间的那个字符，我们需要特别判断一下，此时只要减1个a或者b就行。
最后判断a和b的个数是否满足了，满足就正确，不满足就输出-1。
总结一下，这道题类似一种双指针，用一个 i 和 n – i – 1 来找回文也是很常见的做法了。
这道题算是个模拟题，需要读者有一定耐心，笔者的代码可能比较繁复、不易理解，推荐读者根据思路自行撰写。
代码C++：
#include<bits/stdc++.h>
using namespace std;
void solve(){
int a,b;
cin >> a >> b;
string s;
cin >> s;
int n = s.size();
for(int i = 0;i < n;i++){
if(s[i]=='0')
a--;
if(s[i]=='1')
b--;
}
for(int i = 0;i <= n/2;i++){
//都不是问号的情况
if(s[i] != '?' && s[n - i - 1] != '?'){
if(s[i] != s[n - i - 1]){
cout << -1 << "\n";
return;
}
}else if(s[i] == '?' && s[i] == s[n - i - 1]){//都是问号
continue;
}else{//有一边是问号的情况
if(s[i] != '?'){
if(s[i] == '0') {
a--;
s[n - i - 1] = '0';
}
else {
b--;
s[n - i - 1] = '1';
}
}else{
if(s[n - i - 1] == '0') {
a--;
s[i] = '0';
}
else {
b--;
s[i] = '1';
}
}
if(a < 0 || b < 0){
cout << -1 << "\n";
return;
}
}
}
//最后单独处理都是问号的情况
for(int i = 0;i <= n/2;i++){
if(s[i] == '?' && s[i] == s[n - i - 1] && i != n - i - 1){
if(a >= 2){
a -= 2;
s[i] = s[n - i - 1] = '0';
}else if(b >= 2){
b -= 2;
s[i] = s[n - i - 1] = '1';
}
}
if(s[i] == '?' && i == n - i - 1){
if(a > 0){
a -= 1;
s[i] = '0';
}else{
b -= 1;
s[i] = '1';
}
}
}
if(a != 0 || b != 0){
cout << -1 << "\n";
return;
}
cout << s << "\n";
}
int main(){
int t;
cin >> t;
while(t--) solve();
}J – Repainting Street 重绘街道
题意：
这是一条有n栋房子的街道，这些房子按顺序从1到n编号。房子i最初被涂成了颜色ci。如果所有房子都被涂成相同的颜色，那么这条街道就被认为是美丽的。画家Tom负责使街道变得美丽。Tom的绘画能力由一个整数k定义。
在一天中，Tom可以进行以下由两个步骤组成的重绘过程：
- 他选择两个整数l和r，满足1≤l≤r≤n且r−l+1=k。
- 对于每个满足l≤i≤r的房子i，他可以用他想要的任何颜色重新涂装它，或者忽略它，让它保持当前的颜色。
注意，同一天内，Tom可以使用不同的颜色来重绘不同的房子。
Tom想知道，要使街道变得美丽，需要的最少天数是多少。
输入格式： 输入的第一行包含一个单独的整数t（1≤t≤10^4），即测试用例的数量。接下来是测试用例的描述。
每个测试用例描述的第一行有两个整数n和k（1≤k≤n≤10^5）。
第二行包含n个空格分隔的整数。其中第i个整数表示ci（1≤ci≤100），即房子i最初的颜色。
保证所有测试用例中的n的总和不超过10^5。
输出格式： 打印t行，每行一个整数：Tom为每个测试用例使街道变美所需的最少天数。
nenu 蓝桥杯训练赛（简单模拟+思维） – Virtual Judge (vjudge.net)
思路：
这道题其实就是很暴力的做法。我们看到题目，发现每次要涂色对吧，而且每次涂色就是涂一片区域，所以我们每次遇到需要涂色的情况，就把这篇区域都涂上，然后跳到这片区域之后继续看还有没有需要涂色的情况。我们会发现其实涂色的情况只有100种，非常的少，我们把每一种情况都考虑一次：第一次，我们认为所有房子都要是颜色1，第二次我们认为所有房子都要是颜色2……这样把所有情况都枚举一次，取最小值就是结果了。
简单来想就是，我们遇到和我们想要的颜色不相同的就涂色，然后如果再遇到就再涂色，这种情况一定不会漏掉任何一个房子。然后把100种情况都试一试就行了。实现起来的代码有点类似于C – 稻草人那道题，都是判断之后就跳过一个区域。
虽然讲起来比较复杂，但是代码还是很好懂的。
代码C++：
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 7;
int a[MAXN];
void solve(){
int n,k;
cin >> n >> k;
for(int i = 1;i <= n;i++){
cin >> a[i];
}
int sum = 0x3f3f3f3f;
//枚举一百种颜色
for(int i = 1;i <= 100;i++){
int cnt = 0;
//每一轮都选中一种颜色，看看如果全部变成这种颜色要多少次
for(int j = 1;j <= n;j++){
//遇到需要涂色的就开始涂，然后跳过涂完的区域
if(a[j] != i){
cnt++;
j += k - 1;
continue;
}
}
sum = min(cnt,sum);
}
cout << sum << "\n";
}
int main(){
int t;
cin >> t;
while(t--) solve();
}总结
这一套题难度偏低，代码量主要集中于模拟，有些许思维量。
可以总结出以下几点：
- 多读题，分析题目本身的定义，或许就有了构造的思路。假设没有什么思路，尽自己所能开始分类讨论，探究每一种情况。【分类讨论的方向可以从样例开始考虑，通常是分类讨论数字的大小或者个数、正负等等】
- 看到很小的那种数据范围，比如D题的[1,1000]或者J题的[1,100]，其实都提醒了我们一些做题的突破点，可以暴力突破。
- 看到【你可以输出任何一种】，通常表示题目有特殊的构造方法，尽量考虑特判，把玩样例。