Codeforces Round #833 (Div. 2) A-D.md
A
題解
知識點：數學。
注意到 \(n\) 為奇數時，不考慮連續性，一共有 \(\lceil \frac{n}{2} \rceil ^2\) 個格子，接下來證明一定能湊成方塊。
從下往上從大到小擺，第 \(1\) 層擺 \(1 \times \lceil \frac{n}{2} \rceil\) 的矩形，第 \(i\geq 2\) 層顯然可以成對擺放 \(1 \times \lceil \frac{n-i}{2} \rceil\) 和 \(1\times (\lceil \frac{n}{2} \rceil -\lceil \frac{n-i}{2} \rceil)\) 的矩形。
\(n\) 為偶數時，總數最多構成 \(\lceil \frac{n}{2} \rceil ^2\) 大小的方形，和奇數情況一樣，但會最後多一個最長的矩形。
時間複雜度 \(O(1)\)
空間複雜度 \(O(1)\)
代碼
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool solve() {
int n;
cin >> n;
cout << (n + 1) / 2 << '\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
題解
知識點：枚舉。
顯然根據鴿巢原理，合法的串長度不會超過 \(100\) ，對每位向前枚舉 \(100\) 位即可。
時間複雜度 \(O(100\cdot n)\)
空間複雜度 \(O(n)\)
代碼
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[100007];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) {
char ch;
cin >> ch;
a[i] = ch - '0';
}
ll ans = 0;
for (int i = 1;i <= n;i++) {
vector<int> cnt(10);
int vis = 0, mx = 0;
for (int j = i;j >= 1 && i - j + 1 <= 100;j--) {
if (cnt[a[j]] == 0) vis++;
cnt[a[j]]++;
mx = max(mx, cnt[a[j]]);
if (mx <= vis) ans++;
}
}
cout << ans << '\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
題解
知識點：貪心，枚舉。
一個 \(0\) 能被修改成任意數字，它能影響到自己到下一個 \(0\) 之前的所有前綴和的貢獻（下一個 \(0\) 能繼續調整，所以不納入這個 \(0\) ）。
我們統計兩個 \(0\) 中間（包括左邊的 \(0\) ，但不包括右邊的）前綴和種類，然後把 \(0\) 調整成能將最多數量的一種前綴和變為 \(0\) 即可。
從後往前枚舉，最左邊一段左側沒有 \(0\) 因此只有前綴和為 \(0\) 的才有貢獻。
時間複雜度 \(O(n \log n)\)
空間複雜度 \(O(n)\)
代碼
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[200007];
ll sum[200007];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i], sum[i] = sum[i - 1] + a[i];
int ans = 0, mx = 0;
map<ll, int> mp;
for (int i = n;i >= 1;i--) {
mp[sum[i]]++;
mx = max(mp[sum[i]], mx);
if (a[i] == 0) {
ans += mx;
mx = 0;
mp.clear();
}
}
ans += mp[0];
cout << ans << '\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;
}
D
題解
方法一
知識點：構造。
首先設 \(d\) 的尾 \(0\) 數為 \(k\) ，如果 \(a\) 或 \(b\) 的尾 \(0\) 數小於 \(k\) ，那麼一定無解。因為 \(d\) 的因子包括 \(2^k\) ，而 \(a\) 或 \(b\) 的因子或以後也不會包括 \(2^k\) ，因為尾部有 \(1\) 。
如果有解，我們考慮用 \(x\) 把 \(a\) 和 \(b\) 同步，又要保證能被 \(d\) 整除。因此我們可以從第 \(k\) 位開始到第 \(29\) 位，如果 \(x\) 第 \(i\) 位為 \(0\) 則用 \(d\) 的第一個 \(1\) 通過加法填充這位 ，即 \(x + d \cdot 2^{i-k}\) ，這隻會影響第 \(i\) 位之後的位，之前的不會影響。
於是我們把 \(a,b\) 前 \(30\) 位同步，於是一定有 \(a|x = b|x = x\) ，且或以後能被 \(d\) 整除 。
時間複雜度 \(O(1)\)
空間複雜度 \(O(1)\)
方法二
知識點：數論，構造。
方法一得到的結論是： \(x\) 前 \(30\) 位除去 \(k\) 個尾 \(0\) 都用 \(d\) 加成 \(1\) 。設後 \(30\) 位為 \(p\) 於是 \(x = p\cdot 2^{30} + (2^{30} – 2^k)\) 。
我們嘗試直接求出這個 \(p\) ：
p\cdot 2^{30} + (2^{30} – 2^k) &\equiv 0 & &\pmod d\\
p\cdot 2^{30-k} + (2^{30-k} – 1) &\equiv 0 & &\pmod{\frac{d}{2^k}}\\
p &\equiv \bigg(\frac{1}{2} \bigg)^{30-k} – 1 & &\pmod{\frac{d}{2^k}}\\
p &\equiv \bigg(\frac{\frac{d}{2^k}+1}{2} \bigg)^{30-k} – 1 + \frac{d}{2^k} & &\pmod{\frac{d}{2^k}}\\
\end{aligned}
\]
時間複雜度 \(O(1)\)
空間複雜度 \(O(1)\)
代碼
方法一
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool solve() {
int a, b, d;
cin >> a >> b >> d;
int k = __builtin_ctz(d);
if (k > __builtin_ctz(a) || k > __builtin_ctz(b)) return false;
ll x = 0;
for (int i = k;i < 30;i++) if (!(x & (1 << i))) x += (ll)d << (i - k);
cout << x << '\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;
}
方法二
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int qpow(int a, int k, int P) {
int ans = 1;
while (k) {
if (k & 1) ans = 1LL * ans * a % P;
k >>= 1;
a = 1LL * a * a % P;
}
return ans;
}
bool solve() {
int a, b, d;
cin >> a >> b >> d;
int k = __builtin_ctz(d);
if (k > __builtin_ctz(a) || k > __builtin_ctz(b)) return false;
d >>= k;
ll x = (qpow((d + 1) / 2, 30 - k, d) - 1 + d) % d * (1LL << 30) + (1 << 30) - (1 << k);
cout << x << '\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;
}
