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;
}