A. 321-like Checker

直接模擬。

Code

B. Cutoff

直接暴力枚舉 \([0\sim100]\)，每次把第 \(n\) 個數當作當前枚舉的 \(i\)，然後看看條件是否滿足。

Code

C. 321-like Searcher

Description

給你一個 \(K\)，求出 \([1 \sim K]\) 區間內有多少個 321-like Number。

321-like Number 的定義：

• 每一位上的數字從左到右嚴格單調遞減。
• 或者說，若它有 \(d\) 位，對於 \(\forall i\in[1,d-1]\)，從左到右第 \(i\) 位上的數大於從左到右第 \(i+1\) 位上的數。

Solution

預處理出所有的 321-like Number，枚舉的時候類似枚舉集合的做法。

存到 vector 數組裡，排序後輸出第 \(K\) 大的。

本題需要開 \(\text{long long}\)。

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll; // 開long long
ll k;
int main() {
	scanf("%lld", &k);
	k--;
	vector<ll> v; // vector 存放枚舉的結果
	for (int i = 2; i < (1 << 10); i++) {
		ll t = 0;
		for (int j = 9; j >= 0; j--) {
			if ((i >> j) & 1) { // 這一位為不為0
				t *= 10, t += j; // 加到結果里
			}
		}
		v.push_back(t);
	}
	sort(v.begin(), v.end()); // 排序
	printf("%lld", v[k]); // 輸出結果
	return 0;
}

D. Set Menu

Description

有兩個數列 \(A, B\)，並給定一個常數 \(P\)，現在 \(A_i\) 和 \(B_j\) 的配對總花費為：\(\min(A_i + B_j, P)\)。

現在求：所有可能的配對方式的總和。

\(N, M \le 2 \times 10 ^ 5\)。

Solution

這道題顯然不能用暴力，\(O(4 \times 10 ^ {10})\)，嚴重超時。

考慮如何優化。

可以將 \(B\) 從小到大排序，則對於每一個 \(A_i\)，滿足 \(A_i + B_j \le P\) 的 \(j\) 是一段首碼。

設 \(B_t\) 為最後一個滿足 \(A_i + B_j \le P\) 的 \(B_j\)，則對應的貢獻為 \(tA_i + S_t + (n - t)P\)。其中 \(S_i\) 代表 \(B\) 數組前 \(i\) 個數的首碼和。

對於每一個 \(A_i\)，雙指針/二分都可求解。

註：在雙指針情況下必須先將 \(A\) 數列降序排序。

Code

// LUOGU_RID: 128285445
#include <bits/stdc++.h>

using namespace std;

const int N = 200005;
int a[N], b[N], m, n, p;
long long s[N];
int main() {
	cin >> n >> m >> p;
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1; i <= m; i++) scanf("%d", &b[i]);
	sort(a + 1, a + n + 1, greater<int>());
	sort(b + 1, b + m + 1);
	for (int i = 1; i <= m; i++) s[i] = s[i - 1] + b[i];
	int now = 0;
	long long ans = 0;
	for (int i = 1; i <= n; i++) {
		while (now + 1 <= m && a[i] + b[now + 1] <= p) now++;
		ans += s[now] + 1LL * now * a[i] + 1LL * (m - now) * p;
	}
	printf("%lld", ans);
	return 0;
}

其他的題都沒做出來，菜雞一個。