基本情况
脑子最卡的一集。
A题读假题，卡了快一小时。
B题代码太复杂，出错不好修改，一直调。
虽然最后都出来了，但是没有剩下任何时间看后面题目了。
A. Forked!
一开始不知道犯得什么病，觉得可以斜着走一格算作一步，然后情况就太多了，非常不好处理。
后面突然想着有没有一种可能不能斜着走，然后问题就很简单了。
枚举皇后、国王各自身边的八个位置，看看八个位置中重合的数量即可。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<set>
int move[4][2] = {{1,1},{1,-1},{-1,1},{-1,-1}};
void solve()
{
int a, b, x1, x2, y1, y2, ans = 0;
std::cin >> a >> b >> x1 >> y1 >> x2 >> y2;
std::set<std::pair<int, int> > st1, st2;
for (int i = 0; i < 4; i++)
{
st1.insert({x1 + move[i][0] * a, y1 + move[i][1] * b});st1.insert({x1 + move[i][0] * b, y1 + move[i][1] * a});
st2.insert({x2 + move[i][0] * a, y2 + move[i][1] * b});st2.insert({x2 + move[i][0] * b, y2 + move[i][1] * a});
}
for (auto x : st1) if (st2.find(x) != st2.end()) ans++;
std::cout << ans << std::endl;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int _; std::cin >> _;
while(_--) solve();
return 0;
}
B. Collecting Game
最初
显然要用前缀和，但是仅限于此了，再加了几个比较无脑的剪枝，然后T了。
#include <bits/stdc++.h>
int n;
int a[N];
int b[N];
int c[N];
long long s[N];
int ans[N];
bool cmp(int x, int y)
{
return a[x] < a[y];
}
void solve()
{
std::cin >> n;
std::map<int, int> tag;
std::map<int, long long> sum;
std::iota(c + 1, c + n + 1, 1);
s[0] = 0;
for (int i = 1; i <= n; i++)
std::cin >> a[i], b[i] = a[i];
std::sort(c + 1, c + n + 1, cmp);
std::sort(b + 1, b + n + 1);
for (int i = 1; i <= n; i++)
s[i] = s[i - 1] + b[i];
for (int i = n; i >= 1; i--)
{
if (!sum[b[i]])
sum[b[i]] = s[i] - s[0];//剪枝
}
for (int i = n; i >= 1; i--)
{
long long tot = sum[b[i]];
int cnt = i - 1;
if (tag[b[i]])//剪枝
{
ans[c[i]] = tag[b[i]];
continue;
}
for (int j = i + 1; j <= n; j++)
{
if (tot >= b[j])
{
tot += b[j], cnt++;
}
}
if (!tag[b[i]]) {tag[b[i]] = cnt;ans[c[i]] = cnt;}//剪枝
}
for (int i = 1; i <= n; i++)
{
std::cout << ans[i] << " ";
}
std::cout << std::endl;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int _;
std::cin >> _;
while (_--)
solve();
return 0;
}
优化
观察了一番，感觉这一段有很大的优化空间：
for (int j = i + 1; j <= n; j++)
{
if (tot >= b[j])
{
tot += b[j], cnt++;
}
}
这一段的目的是找到所有的能被删除的数，但是我很朴素地删一个，加一个。
完全可以用二分查找先快速找到最后一个小于等于当前和 \(tot\) 的数，然后直接把当前 \(tot\) 赋成这个数下标的前缀和，然后迭代这个过程，直到无法找到小于等于当前的和 \(tot\) 的数为止即可。
复杂度从 \(\operatorname O(n^2)\) 降到了 \(\operatorname O(n\log_2n)\)。
int t, last_t = i;
while(true)
{
t = std::upper_bound(b + 1, b + n + 1, tot) - b - 1;
tot = s[t - 1]; cnt += t - last_t;
if (last_t == t) break;
last_t = t;
}
改错
话虽如此，但是这个代码是错的！导致我调了半天。
t = std::upper_bound(b + 1, b + n + 1, tot) - b - 1;
这玩意求得是第一个大于 \(tot\) 的值的下标。
这是我的第一反应。然后顺着这个思路，自然而然，最后一个小于等于当前 \(tot\) 的元素的下标为 \(t-1\)，\(tot = s_{t-1}\)。
然而真正第一个大于 \(tot\) 的下标是 std::upper_bound(b + 1, b + n + 1, tot) 啊喂。
又因为我从 \(1\) 开始存，减去 b+1 这个数组下标一地址之后，实际上返回的是它们之间的差值，说白了，也就是已经是真正第一个大于 \(tot\) 的下标减一了。
所以直接 tot = s[t] 就行了。
但是这样不够优雅。
直接直来直去最明白：
-
先求第一个大于 \(tot\) 的下标：
t =std::upper_bound(b + 1, b + n + 1, tot) - b;
-
再转成最后一个小于等于 \(tot\) 的下标：
t--;
-
然后直接用就行：
-
while(true) { t = std::upper_bound(b + 1, b + n + 1, tot) - b; t--; tot = s[t]; cnt += t - last_t; if (last_t == t) break; last_t = t; }
-
代码
最后再把之前口胡的剪枝都删掉，搞得简洁一点。
#include <bits/stdc++.h>
int n;
int a[N];
int b[N];
int c[N];
long long s[N];
int ans[N];
bool cmp(int x, int y)
{
return a[x] < a[y];
}
void solve()
{
std::cin >> n;
std::iota(c + 1, c + n + 1, 1);
s[0] = 0;
for (int i = 1; i <= n; i++)
std::cin >> a[i], b[i] = a[i];
std::sort(c + 1, c + n + 1, cmp);
std::sort(b + 1, b + n + 1);
for (int i = 1; i <= n; i++)
s[i] = s[i - 1] + b[i];
for (int i = 1; i <= n; i++)
{
long long tot = s[i];
int cnt = i - 1;
int t, last_t = i;
while(true)
{
t = std::upper_bound(b + 1, b + n + 1, tot) - b;
t--;
tot = s[t]; cnt += t - last_t;
if (last_t == t) break;
last_t = t;
}
ans[c[i]] = cnt;
}
for (int i = 1; i <= n; i++)
{
std::cout << ans[i] << " ";
}
std::cout << std::endl;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int _;
std::cin >> _;
while (_--)solve();
return 0;
}