A - Sleeping pairs
- 很明显，能删的要立刻删，它们会阻碍交换。
- 一共要删除 \(n\) 列，这需要 \(n\) 点体力。
- 由于删除时总要保证两列字符一致，故两列
X的个数要相等。设两列X的个数原来相差 \(b\) 个，则交换一行XZ（或ZX）会使得某一列减少一个X，而另一列增加一个X，差值减少 \(2\)，故这需要 \(\dfrac{b}{2}\) 点体力。 - 由样例 \(1\) 可知，删除两行相邻的
XZ和ZX需要 \(1\) 点额外体力（删除所需的体力已经计算过了）。上一步完成后，ZX和XZ一定都存在（否则两列X的个数不可能相同），因此总会有两行相邻的XZ和ZX。设上一步结束后还剩下 \(c\) 列，则这需要 \(\dfrac{c}{2}\) 点体力。
#include <bits/stdc++.h>
using namespace std;
int n;
int a, b, c;
string s;
int main()
{
freopen("pairs.in", "r", stdin);
freopen("pairs.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
cin >> s;
if (s == "XZ")
{
b++;
c++;
}
if (s == "ZX")
{
b--;
c++;
}
}
a = n + abs(b) / 2 + c / 2;
printf("%d", a);
return 0;
}
B - Have a check
模拟即可。样例已经涵盖了所有注意事项。
#include <bits/stdc++.h>
using namespace std;
string check(string answer, string output)
{
if (answer == output)
{
return "Accepted.";
}
int line = 1, column = 1, al = answer.size(), ol = output.size();
stringstream conv;
string res;
conv << "Wrong Answer: ";
for (int i = 0; i < min(al, ol); i++)
{
if (answer[i] != output[i])
{
if (answer[i] == '\n')
{
conv << "Extra Character";
}
else if (output[i] == '\n')
{
conv << "Missing Character";
}
else
{
conv << "Wrong Answer";
}
conv << " on Line " << line << ", Column " << column << ".";
getline(conv, res);
return res;
}
if (answer[i] == '\n')
{
line++;
column = 1;
}
else
{
column++;
}
}
if (al > ol)
{
if (answer[ol] == '\n')
{
conv << "Missing Line on Line " << line + 1 << ".";
}
else
{
conv << "Missing Character on Line " << line << ", Column " << column << ".";
}
}
else
{
if (output[al] == '\n')
{
conv << "Extra Line on Line " << line + 1 << ".";
}
else
{
conv << "Extra Character on Line " << line << ", Column " << column << ".";
}
}
getline(conv, res);
return res;
}
int main()
{
freopen("check.in", "r", stdin);
freopen("check.out", "w", stdout);
string ansa, out;
stringstream s0, s1, s2;
bool sepa = false;
char c = getchar();
while (c != EOF)
{
s0 << (int)c << endl;
if (c == 127)
{
sepa = true;
}
else if (sepa)
{
s2 << '*';
}
else
{
s1 << '*';
}
c = getchar();
}
s1 >> ansa;
s2 >> out;
int tmp = 0, cnt = 0;
sepa = false;
while (s0 >> tmp)
{
if (tmp == 127)
{
sepa = true;
cnt = 0;
}
else
{
if (sepa)
{
out[cnt] = tmp;
}
else
{
ansa[cnt] = tmp;
}
cnt++;
}
}
cout << check(ansa, out);
return 0;
}
C - Moving like a spider
- 由于向上运动不花费体力，会合点的 \(y\) 坐标可以无限大，因此只需要考虑会合点的 \(x\) 坐标即可。
- 不难发现，每只蜘蛛最优移动路径只有两种：
- 在当前 \(y\) 坐标上改变 \(x\) 坐标（设改变量为 \(\Delta x\)），然后向上运动，花费 \(ry_0\Delta x\) 点体力（其中 \(y_0\) 是初始的 \(y\) 坐标）。
- 向下运动到中心点 \(O\)，然后向上运动，花费 \(dy_0\) 点体力。
- 由上可知，我们只需要关注 \(\Delta x\) 和 \(l=\dfrac{d}{r}\) 的大小关系，即可确定每只蜘蛛的最优移动路径。
- 因此，我们枚举会合点的 \(x\) 坐标，然后差分（结合斜率）维护花费的总体力即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 12;
int K[N], D[N], R[N], A[N];
int move(int f, int s, int n)
{
return (f + s + n) % n;
}
int dis(int f, int t, int n)
{
int ans = abs(t - f);
return min(ans, n - ans);
}
void build(int n, int d, int r, int l)
{
for (int i = 0; i <= n - 1; i++)
{
if (l >= n / 2 && n % 2 == 1)
{
// i = 1, n = 7
// pos: 0 1 2 3 4 5 6
// dis: 1 0 1 2 3 3 2
K[move(i, n / 2 + 1, n)] += -1 * A[i];
K[move(i, n / 2 + 2, n)] += -1 * A[i];
K[move(i, 1, n)] += 2 * A[i];
}
if (l >= n / 2 && n % 2 == 0)
{
// i = 1, n = 6
// pos: 0 1 2 3 4 5
// dis: 1 0 1 2 3 2
K[move(i, n / 2 + 1, n)] += -2 * A[i];
K[move(i, 1, n)] += 2 * A[i];
}
if (l < n / 2)
{
// i = 1, n = 8, l = 2
// pos: 0 1 2 3 4 5 6 7
// dis: 1 0 1 2 d d d 2
R[move(i, l + 1, n)] += -l * A[i];
K[move(i, l + 1, n)] += -1 * A[i];
D[move(i, l + 1, n)] += 1 * A[i];
R[move(i, -l, n)] += l * A[i] + A[i];
K[move(i, -l, n)] += -1 * A[i];
D[move(i, -l, n)] += -1 * A[i];
K[move(i, 1, n)] += 2 * A[i];
}
}
return;
}
signed main()
{
freopen("spider.in", "r", stdin);
freopen("spider.out", "w", stdout);
int m, n, d, r;
cin >> m >> n >> d >> r;
for (int i = 1; i <= m; i++)
{
int x, y;
cin >> x >> y;
A[x] += y;
}
int l = d / r;
long long a0 = 0, d0 = 0, r0 = 0;
for (int i = 0; i <= n - 1; i++)
{
if (dis(0, i, n) <= l)
{
a0 += dis(0, i, n) * r * A[i];
r0 += dis(0, i, n) * A[i];
}
else
{
a0 += d * A[i];
d0 += A[i];
}
}
long long a1 = 0, d1 = 0, r1 = 0;
for (int i = 0; i <= n - 1; i++)
{
if (dis(1, i, n) <= l)
{
a1 += dis(1, i, n) * r * A[i];
r1 += dis(1, i, n) * A[i];
}
else
{
a1 += d * A[i];
d1 += A[i];
}
}
build(n, d, r, l);
long long kk = r1 - r0 - R[1], dd = d1, rr = r1, aa = a1, ans = min(a0, a1);
for (int i = 2; i <= n - 1; i++)
{
kk += K[i], dd += D[i], rr += R[i];
rr += kk;
aa = rr * r + dd * d;
ans = min(ans, aa);
}
cout << ans << endl;
return 0;
}
D - Faster than expected
第一部分
上述代码的最坏时间复杂度是 \(O(nT \log n)\)。
第二部分
为了证明中间的小猪不会出现左右往复移动而使时间复杂度达到 \(O(n^2T)\) 的情况，我们考虑把场上所有的小猪从左向右平分成三分，分别记为 \(A,B,C\)。
根据题意，在 \(A,B,C\) 中都至少有一只小猪还没下桥的情况下，\(A\) 中的小猪总会向左移动，而 \(C\) 中的小猪总会向左移动。\(\dfrac{T}{2}\) 秒后，\(A\) 中任意一只小猪和 \(C\) 中任意一只小猪之间的距离将不小于 \(T\)，因此它们之间一定有一组全部下桥了。
由上可知，时间每过去 \(\dfrac{T}{2}\) 秒，桥上小猪的数量都将至少减少 \(\dfrac{1}{3}\)，即剩下原来的 \(\dfrac{2}{3}\) 或更少。因此，整个过程最多持续 \(\dfrac{T}{2} \cdot \log _{\frac{3}{2}} n=O(T \log n)\) 秒。
阅读程序可知，它 while 循环内程序的时间复杂度为 \(O(n)\)，而 while 循环每执行一次相当于时间流逝一秒，因此 while 循环最多会执行 \(O(T \log n)\) 次。
综上，上述代码的时间复杂度不高于 \(O(nT \log n)\)。
第三部分
只要让 \(T\) 远大于 \(n\)（此时可以忽略 \(n\) 对小猪位置的影响），且 \(T,n\) 足够大，将 \(n\) 只小猪都放在 \(\dfrac{T}{3}\) 位置（时间每过去 \(\dfrac{T}{3}\) 秒，桥上小猪的数量都将减少 \(\dfrac{1}{2}\)），即可使上述代码的时间复杂度退化到 \(O(nT \log n)\)。
例如：
- \(n=10^6\)。
- \(T=3 \times 10^{18}\)。
- \(a_i=10^{18}+i\)。