Codeforces Round 909 (Div. 3)
基本情况
- 第一次在
CF上AC了超过一道题。（毕竟是Div3） B题卡住了很久。D没有深入思考。
[B. 250 Thousand Tons of TNT](Problem - B - Codeforces)
一开始死活过不了的代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 150000 + 10;
long long s[N];
long long a[N];
long long ans = 0;
int n, t;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> t;
while (t--)
{
cin >> n;
ans = 0;
long long maxx = 0, minn = 0x7fffffff;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
maxx = max(a[i], maxx);
minn = min(a[i], minn);
}
if (n == 1)
{
cout << 0 << endl;
continue;
}
ans = max(ans, maxx - minn);
for (int t = 2; t < n; t++)
{
if (n % t == 0)
{
maxx = 0, minn = 0x7fffffff;
for (int i = t; i <= n; i += t)
{
ll temp = 0;
for (int k = i - t + 1; k <= i; k++)
{
temp += a[k];
}
maxx = max(maxx, temp);
minn = min(minn, temp);
}
ans = max(ans, maxx - minn);
}
}
cout << ans << endl;
}
return 0;
}
已经觉察到可能爆int 而改了 long long。
但一是因为基础不扎实，二是不会造数据。
导致我搞了快一个小时都没有发现问题所在：
minn = 0x7fffffff
我初始化的极大值只是int下的极大值，导致了数据范围超过 int 后就会出现正确性问题。
改成 minn = 0x7fffffffffffffff即可。
但凡我能直接意识到这个问题，或者手造数据时候能造大一点都能 hack 掉自己的代码。
[D. Yarik and Musical Notes](Problem - D - Codeforces)
这题我已经推到 \(2^{a - b} = \frac a b\)，然而没有继续推导下去，而是尝试用不严谨的写法来做。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int a[N];
bool check(int n, int m)
{
if (n == m)
return true;
if ((m / n) % 2)
return false;
return ((m / n) == (1 << (m - n)));
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t, n;
cin >> t;
while (t--)
{
long long ans = 0;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
sort(a + 1, a + n + 1);
for (int i = n; i >= 1; i--)
{
for (int j = i - 1; j >= 1; j--)
{
if (check(a[j], a[i]))
{
ans++;
}
}
}
cout << ans << endl;
}
return 0;
}
显然，1 << (m - n)会爆范围。。。
看了题解，发现继续推下去就轻松了。
\(suppose\space that\space b = a \cdot 2^k(k > 0)\)
\[\frac{a}{a \cdot 2^k} = \frac{2^a}{2^{a \cdot 2^k}} \Leftrightarrow \frac{1}{2^k} = \frac{1}{2^{(2^k - 1)a}} \Leftrightarrow 2^k = 2^{(2^k - 1)a}
\]
- \(k = 1\)
- \(a = 1, b = 2\)
- \(k > 1\)
- \(2^k - 1 > k\)
- can't be satisfied
Thus, the only possible cases where the equality is satisfied are if \(b_i = b_j\) or \(b_i = 1, b_j = 2\)，(and vice versa). The number of such pairs can be counted for \(\operatorname O(n \log n)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int& x : a) cin >> x;
ll ans = 0;
map<int, int> cnt;
for (int i = 0; i < n; i++) {
ans += cnt[a[i]];
if (a[i] == 1) ans += cnt[2];
else if (a[i] == 2) ans += cnt[1];
cnt[a[i]]++;
}
cout << ans << "\n";
}
signed main() {
int t;
cin >> t;
while (t--) solve();
}