题解：P10765 「CROI · R2」在相思树下 I

XoCeLHsL · 2024-07-17 16:09:55 · 题解

当序列是 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;
}