CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!) A-D
A
題解
知識點：貪心。
注意到 \(a[1] \neq 1\) ， \(1\) 永遠不可能換到前面；\(a[1] = 1\) 可以交換後面任意元素。
時間複雜度 \(O(n)\)
空間複雜度 \(O(n)\)
程式碼
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[20];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
if (a[1] == 1) cout << "YES" << '\n';
else cout << "NO" << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
B
題解
知識點：貪心，枚舉。
分兩類，一種是純 \(1\) 或 \(0\) ，另一種是雜合。
顯然後者的情況中，把所有數字全選了是最優的；前者枚舉一下所有純子串即可。兩種情況，取最大值。
時間複雜度 \(O(n)\)
空間複雜度 \(O(n)\)
程式碼
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool solve() {
int n;
cin >> n;
string s;
cin >> s;
s = "?" + s;
int cnt0 = 0, cnt1 = 0;
for (int i = 1;i <= n;i++) {
if (s[i] == '0') cnt0++;
else cnt1++;
}
ll mx = 1LL * cnt0 * cnt1;
int i = 1, j = 1;
while (i <= n) {
while (j <= n && s[j] == s[i]) j++;
mx = max(mx, 1LL * (j - i) * (j - i));
i = j;
}
cout << mx << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
C
題解
知識點：構造。
注意到，只有 \(a=b\) 或者 \(a\) 每位都不等於 \(b\) 的對應位才可行。
考慮先把 \(a\) 串的 \(1\) 一個一個消掉，然後發現 \(b\) 會出現全 \(0\) 全 \(1\) 的情況，接下來分類討論：
- 如果 \(a = b\) ，那麼 \(a\) 中 \(1\) 為偶數時得到的 \(b\) 是 \(0\) ，否則是 \(1\) 。
- 如果 \(a\) 每位都不等於 \(b\) 的對應位 ，那麼消掉一個 \(1\) 以後又會回到情況1，因此和情況 \(1\) 相反。
全是 \(0\) 直接可以結束，全是 \(1\) 可以先把 \([1,n]\) 取反，然後選擇 \([1,1],[2,n]\) 即可。
時間複雜度 \(O(n)\)
空間複雜度 \(O(n)\)
程式碼
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool solve() {
int n;
cin >> n;
string a, b;
cin >> a >> b;
a = "?" + a;
b = "?" + b;
int cnt = 0;
for (int i = 1;i <= n;i++) cnt += a[i] == b[i];
if (cnt != 0 && cnt != n) return 0;
bool flag = cnt == n ? 0 : 1;
vector<pair<int, int>> ans;
for (int i = 1;i <= n;i++) {
if (a[i] == '1') {
ans.push_back({ i, i });
flag ^= 1;
}
}
if (flag) {
ans.push_back({ 1,n });
ans.push_back({ 1,1 });
ans.push_back({ 2,n });
}
cout << "YES" << '\n';
cout << ans.size() << '\n';
for (auto [i, j] : ans) cout << i << ' ' << j << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << "NO" << '\n';
}
return 0;
}
D
題解
知識點：質因數分解，容斥原理，數論。
題目要求我們每個 \(b_i\) 的方案數，然後得到總的方案數。
顯然有 \(gcd(a_{i-1},b_i) = a_i\) ，注意到 \(a_i\) 必須是 \(a_{i-1}\) 的因子否則不可能得到答案，因此特判一下 \(a_{i} | a_{i-1}\) 。
於是，我們要找到所有的 \(b_i\) ，滿足 \(gcd(\frac{a_{i-1}}{a_i},\frac{b_i}{a_i}) = 1\) 且 \(a_i | b_i\) ，其中 \(\frac{b_i}{a_i} \in [1,\frac{m}{a_i}]\) ，即我們從 \([1,\frac{m}{a_i}]\) 整數中找到和 \(\frac{a_{i-1}}{a_i}\) 互素的個數。
這是一個典型的容斥問題。先對 \(\frac{a_{i-1}}{a_i}\) 分解素因數，得到其素因子種類。我們先計算出區間中包含 \(\frac{a_{i-1}}{a_i}\) 因子的數的個數，注意奇加偶減，然後用總數 \(\frac{m}{a_i}\) 減去個數，即與之互素的數的個數，於是我們就得到了 \(b_i\) 的種類。
遍歷每個 \(a_i\) 即可。
時間複雜度 \(O(n(\log a_i + 10\cdot 2^{10}))\)
程式碼
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 998244353;
int a[200007];
bool vis[100007];
int prime[100007];
int cnt;
void euler_screen(int n) {
for (int i = 2;i <= n;i++) {
if (!vis[i]) prime[++cnt] = i;
for (int j = 1;j <= cnt && i * prime[j] <= n;j++) {
vis[i * prime[j]] = 1;
if (!(i % prime[j])) break;//如果到了i的最小質因子就不用繼續，因為接下去的數x一定能被(i,x)之間的數篩掉
}
}
}///歐拉篩，O(n)，每個合數只會被最小質因子篩掉
bool solve() {
int n, m;
cin >> n >> m;
for (int i = 1;i <= n;i++) cin >> a[i];
int ans = 1;
for (int i = 2;i <= n;i++) {
if (a[i - 1] % a[i]) {
ans = 0;
break;
}
int d = a[i - 1] / a[i];//不能出現的因子
int base = m / a[i];//包含a[i]的數個數
vector<int> ft;//對d分解因子種類
for (int j = 1;j <= cnt && prime[j] <= d / prime[j];j++) {
if (d % prime[j] == 0) ft.push_back(prime[j]);
while (d % prime[j] == 0) d /= prime[j];
}
if (d > 1) ft.push_back(d);
int sum = 0;//容斥原理，求[1,base]中沒有d中因子的數個數
for (int j = 1; j < (1 << ft.size()); j++) {
int mul = 1, feat = 0;
for (int k = 0; k < ft.size(); k++) {
if (j & (1 << k)) {
mul *= ft[k];
feat++;
}
}
if (feat & 1) sum = (sum + 1LL * base / mul % mod) % mod;
else sum = (sum - 1LL * base / mul % mod + mod) % mod;
}
sum = (base - sum + mod) % mod;
ans = 1LL * ans * sum % mod;
}
cout << ans << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
euler_screen(100007);
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
