KJY0047 - J1阶段测试题解

题目1：SYAP0001. 闯关

解题思路：

暴力思路：每次碰到奇数都使用一次 $for$ 循环将后续的数值 $+1$, 时间复杂度 $O(n^2)$
优化思路：可以用一个计数器 $cnt$ 来存储后续数值需要增加多大，如果碰到奇数则让计数器 $+1$，每次新读入一个数 $x$，都让 $x+cnt$ 得到的值才是当前关卡真正的恐怖值，不要忘记要开 $longlong$。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define int long long 
signed main(){int cnt = 0; // 计数器int ans = 0; // 恐怖值总和int n, m;cin >> n >> m;for(int i = 1; i <= n; i ++){int x;cin >> x;x += cnt; // 真正的关卡恐怖值if(x % 2){ans += x;cnt ++;} else{ans += x;}if(ans > m){ // 闯关失败cout << "No" << endl;cout << i << endl;return 0; }	}cout << "Yes" << endl;cout << ans << endl;return 0;
}

题目2：SYAP0023. 分割

解题思路

本题考的知识点是 map 的使用，由于我们每个字段中的数值都要求唯一，那么我们从左到右贪心的遍历数组，如果当前的 $x$ 在之前出现过，则需要重新分段，否则我们就尽可能让没出现的过的数放在当前段中。

代码实现

#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin >> n;map<int, int> mp; // 用来存储当前段中数值出现次数int sum = 0;for(int i = 1; i <= n; i ++){int x;cin >> x;if(mp[x] == 1){ // 如果出现过，则需要重新分段mp.clear(); // 清空 mapsum ++; // 分段次数增加}mp[x] ++;}cout << sum << endl;return 0;
}

题目3：P1247. brz的雪糕

解题思路

本道题是 前缀和 专题中做过的题，为了测试同学们是否做过的题目真正的掌握了。我们可以刚开始预处理一个前缀和数组 $s$ ，如果 $a[i]==a[i-1]$ 则 $s[i]=s[i-1]$, 否则如果 $a[i]!=a[i-1]$ 则 $s[i]=s[i-1]+1$，那么每次询问我们可以直接返回 $s[r]-s[l]+1$ 即可。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N]; 
int s[N];
int main(){int n, k, q;cin >> n >> k >> q;for(int i = 1; i <= n; i ++){cin >> a[i]; s[i] = s[i - 1] + (a[i] != a[i - 1]);}while(q --){int l, r;cin >> l >> r;if(s[r] - s[l] + 1 >= k) cout << "Yes" << endl;else cout << "No" << endl; } return 0;
}

题目4：SYAP0030. 销毁（easy）

解题思路

因为我们要求 最多能剩下 多少 互不相同 的卡牌，所以我们可以先统计出有多少张卡牌是没意义的，易知 $所有卡牌的总数-有多少种不同的卡牌$ 得到的值即为没有意义的卡牌数量。例如只有 3 种卡牌 2 3 5，他们的数量分别是 1 6 8，那么没有意义的卡牌数量即为 (1 - 1) + (6 - 1) + (8 - 1) = 12 , 这 12 张卡牌是可以随意销毁的，因为它 不会影响我们的最终答案 。又由于，我们每次只会销毁 2 张卡牌，所以如果我们 无意义的卡牌数量是奇数，则意味这有意义的卡牌要损失 1 张，否则有意义的卡牌无需损失

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int sum[N]; 
int main(){int n;cin >> n;for(int i = 1; i <= n; i ++){int x;cin >> x;sum[x] ++; // 统计卡牌数量} int ans = 0; // 无意义的卡牌数量int res = 0; // 统计卡牌的种类for(int i = 1; i <= 1e6; i ++){if(sum[i]){ans += sum[i] - 1;res ++;}}ans %= 2;cout << res - ans << endl; // 如果是奇数则会 -1return 0;
}

题目5：SYAP0031. 销毁（hard）

解题思路
思路和上题差不多，只不过需要存储最后保留的字典序最小的方案，使用一个 $vector$ 存储即可

代码实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
int sum[N];
signed main(){int n, k;cin >> n >> k;vector<int> v;for(int i = 1; i <= n; i ++){int x;cin >> x;sum[x] ++ ;} int ans = 0;for(int i = 1; i <= 1e6; i ++){if(sum[i]){ans += sum[i] - 1;v.push_back(i); // 有多少种不同的数值放 vector 中}}ans %= k;if(ans) ans = k - ans; // 需要销毁多少有意义的卡牌if(ans > v.size()){ // 如果销毁数量 > 不同数值个数则无解cout << "-1" << endl;return 0;}sort(v.begin(), v.end()); // 排序按字典序从小到大cout << v.size() - ans << endl;for(int i = 0; i < v.size() - ans; i ++){cout << v[i] << ' ';}cout << endl;
}