标签：int 909 Codeforces long cin ans Div include

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

标签：int,909,Codeforces,long,cin,ans,Div,include
From： https://www.cnblogs.com/kdlyh/p/17842675.html