A
注意到除了血量为 \(1\) 的怪物，其余的怪物直接斩杀是更合理的。
所以只要统计血量为 \(1\) 的怪物的个数即可。
#include <cstdio>
void solve() {
int n; scanf("%d", &n);
int cnt = 0;
for (int i = 1, x; i <= n; i ++) scanf("%d", &x), cnt += (x == 1);
int k = 0;
if (cnt != 0) k = (cnt - 1) / 2 + 1;
printf("%d\n", k + (n - cnt));
}
int main() {
int T; scanf("%d", &T);
while (T --) solve();
return 0;
}
B
分讨题，注意到我们可以把一个 \(a_2\) 和一个 \(a_3\) 视为一个无影响到 joke。
然后我们只要讨论是否能撑到 \(a_4\) 就好了。
注意特判 \(a_1 = 0\) 时，这时是不能把 \(a_2\) 和 \(a_3\) 视为一个的。
#include <cstdio>
#include <algorithm>
using namespace std;
void solve() {
int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d);
int minbc = min(b, c);
int maxbc = max(b, c);
int need = maxbc - minbc;
if (a == 0) {
printf("%d\n", (b != 0 || c != 0 || d != 0));
return;
}
if (need > a) {
// puts("Case 1");
printf("%d\n", a + minbc * 2 + a + 1);
} else {
// puts("Case 2");
// printf("%d %d\n", a - need + 1, d);
printf("%d\n", a + b + c + min(a - need + 1, d));
}
}
int main() {
int T; scanf("%d", &T);
while (T --) solve();
return 0;
}
C
我们可以 dp。
设 \(f_i\) 表示以 \(i\) 结尾的最长的连续段 (\(x,x+1,x+2,\dots\))
因为 \(f_i\) 越小一定越优，然后我们可以前缀和优化一下转移，就可以 \(\mathcal{O}(n)\) 求出答案了。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
void solve() {
int n; scanf("%d", &n);
vector<int> a(n + 1);
for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
vector<int> f(n + 1, 0);
vector<int> g(n + 2, n + 1);
for (int i = 1; i <= n; i ++) {
f[i] = min(g[a[i]], i);
g[a[i] + 1] = f[i];
}
int ans = n;
for (int r = 1; r <= n; r ++) {
int l = f[r];
ans = min(ans, max(n - a[r], a[l] - 1));
}
printf("%d\n", ans);
}
int main() {
int T; scanf("%d", &T);
while (T --) solve();
return 0;
}
D
注意到题目中的乘积定义为 \(r_j = q_{p_j}\)。
所以实际上如果 \(r_1=1\)，那么就有 \(q_{p_1}=1\)。
所以实际上我们是可以通过 \(q\) 求出对应的 \(p\) 的。
这就转换成了 \(LCP\) 问题，由于值域很小，直接 hash 解决即可。
#include <cstdio>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll K = 11;
unordered_set<ll> s;
void solve() {
int n, m; scanf("%d%d", &n, &m);
s.clear();
vector<vector<int>> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i ++) {
a[i].resize(m + 1), b[i].resize(m + 1);
for (int j = 1; j <= m; j ++) scanf("%d", &a[i][j]);
for (int j = 1; j <= m; j ++) b[i][a[i][j]] = j;
ll hsh = 0 ;
for (int j = 1; j <= m; j ++) {
hsh = K * hsh + b[i][j];
s.insert(hsh);
}
}
// for (int i = 1; i <= n; i ++) {
// printf("permutation %d:\n", i);
// for (int j = 1; j <= m; j ++) printf("%d%c", a[i][j], " \n"[j == m]);
// for (int j = 1; j <= m; j ++) printf("%d%c", b[i][j], " \n"[j == m]);
// }
for (int i = 1; i <= n; i ++) {
ll hsh = 0; int ans = m;
for (int j = 1; j <= m; j ++) {
hsh = K * hsh + a[i][j];
if (s.find(hsh) == s.end()) {
ans = j - 1;
break;
}
}
printf("%d%c", ans, " \n"[i == n]);
}
}
int main() {
int T; scanf("%d", &T);
while (T --) solve();
return 0;
}
E
首先有一个比较重要的性质，就是当 \(x \leq 10^{18}\) 时，\(\max{\{d_x\}} \leq 103680\)，当 \(x \leq 10^9\) 时，\(\max{\{d_x\}} \leq 1344\)。
所以我们是可以直接通过分解 \(m_1, m_2\) 的因数来求出 \(m\) 的所有因数的。
然后考虑我们要怎么求出题目中所述的答案。
注意到如果我们直接取 \(x\) 的最小因数这时不对的，因为 \(\frac{x}{mind}\) 可能 \(> n\)。
所以实际上我们要找的是不大于 \(n\) 的 \(x\) 的最大因数。
所以我们记 \(m\) 的因数时，我们可以把它是由哪两个因数乘起来的记下来，对这两个因数进行因数分解，然后枚举一个因数，记为 \(x\)，在另一堆因数里二分第一个小于 \(\frac{n}{x}\) 的数，这就一定是由 \(x\) 组成的最大的不大于 \(n\) 的因数。
记 \(C_1 = 103680, C_2 = 1344\)。
这样的复杂度应该是 \(\mathcal{O}(\sqrt{m} + {C_2}^2 \log {{C_2}^2} + C_1 \times (\sqrt{m} + C_2 \times log{C_1}))\)。
然后你就得到了 TLE ON 5。
优化 1
注意到如果我们在求答案那一步，将两堆因数都排序后，第二堆因数的位置的选择实际上是单调的，所以我们就不用二分了。
优化 2
可以发现主要瓶颈在于求答案时的求出两堆因数。
但我们可以发现，其因数一定出现在 \(m_1,m_2\) 的所有因数中，所以我们就可以直接 \(\mathcal{O}({C_2}^2)\)，预处理出这两堆因数。
优化 3
尽管有了以上两个优化，我们还是难以通过，注意到 \(2e6\) 范围的数组排序是很耗时的，又因为实际上不同的因数很少，我们可以考虑使用 hash table 来去重。
总和以上三个优化，再卡卡常，应该就可以通过了，单次复杂度 \(\mathcal{O}(\sqrt{m} + {C^2}^2+{C_1}\times{C_2})\)。
#pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3)
#pragma GCC target("avx","sse2")
#include <cstdio>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <cassert>
#include <unordered_map>
#include <set>
using namespace std;
typedef long long ll;
void solve() {
ll n, m1, m2; scanf("%lld%lld%lld", &n, &m1, &m2);
vector<int> d1, d2;
vector<pair<ll, pair<int, int>>> d;
for (ll i = 1; i * i <= m1; i ++) if (m1 % i == 0) {
d1.push_back(i);
if (m1 / i != i) d1.push_back(m1 / i);
}
for (ll i = 1; i * i <= m2; i ++) if (m2 % i == 0) {
d2.push_back(i);
if (m2 / i != i) d2.push_back(m2 / i);
}
vector<vector<ll>> dd1(d1.size()), dd2(d2.size());
for (int i = 0; i < d1.size(); i ++) {
for (int j = 0; j < d1.size(); j ++) if (d1[j] % d1[i] == 0) {
dd1[j].push_back(d1[i]);
}
}
for (int i = 0; i < d2.size(); i ++) {
for (int j = 0; j < d2.size(); j ++) if (d2[j] % d2[i] == 0) {
dd2[j].push_back(d2[i]);
}
}
for (int i = 0; i < d1.size(); i ++) sort(dd1[i].begin(), dd1[i].end());
for (int i = 0; i < d2.size(); i ++) sort(dd2[i].begin(), dd2[i].end());
for (int i = 0; i < d1.size(); i ++) for (int j = 0; j < d2.size(); j ++) d.push_back({1ll * d1[i] * d2[j], { i, j } });
// sort(d.begin(), d.end());
unordered_set<ll> s;
// ll lst = 0;
// vector<pair<ll, pair<int, int>>> res;
// for (auto [mul, p] : d) {
// if (mul != lst) {
// lst = mul;
// res.push_back({ mul, { p.first, p.second }});
// }
// }
vector<ll> ans; int cnt = 0;
for (auto [mul, p] : d) {
if (s.count(mul)) continue;
s.insert(mul);
// printf("has div: %lld\n", mul);
ll x = d1[p.first], y = d2[p.second];
int i = p.first, j = p.second;
ll finalDiv = 0;
int tp = dd2[j].size() - 1;
for (auto div : dd1[i]) {
auto k = n / div;
while (tp && dd2[j][tp] > k) -- tp;
if (dd2[j][tp] <= k) {
finalDiv = max(finalDiv, dd2[j][tp] * div);
} else {
break;
}
}
assert(finalDiv <= n && mul % finalDiv == 0);
ll anotherDiv = mul / finalDiv;
if (anotherDiv <= n) {
ans.push_back(min(finalDiv, anotherDiv));
++ cnt;
} else {
ans.push_back(0);
}
}
printf("%d ", cnt);
ll final = 0;
for (auto tmp : ans) final ^= tmp;
printf("%lld\n", final);
}
int main() {
int T; scanf("%d", &T);
while (T --) solve();
return 0;
}