题解：P10765 「CROI · R2」在相思树下 I
17 Jul, 2024 04:09 PM +08:00
当序列是 $ak-b,k>0$，
-
如果删去奇数项，剩下 $a(2k)-b$，即 $2ak-b$。
-
如果删去偶数项，剩下 $a(2k-1)-b$，即 $2ak-(b+a)$。
我们发现无论如何操作，新的序列仍可以写成 $Ak-B$ 的形式。
初始状态 $a=1, b=0$，每次操作维护 $a,b$，最后取 $k=1$ 即可。
#include <bits/stdc++.h>
#define u64 unsigned long long
long long qread()
{
long long w = 1, c, ret;
while ((c = getchar()) > '9' || c < '0')
w = (c == '-' ? -1 : 1);
ret = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
ret = ret * 10 + c - '0';
return ret * w;
}
u64 T, n, k, a, b, oper;
signed main()
{
T = qread();
while (T--)
{
n = qread(), k = qread(), a = 1, b = 0;
while (k--)
{
oper = qread();
if (oper == 1)
{
a <<= 1;
}
if (oper == 2)
{
b += a;
a <<= 1;
}
}
std::cout << a - b << std::endl;
}
return 0;
}
本文最初发表于 Luogu，于 2026-04-19 同步至本站。