题解：P17116 [Algo Beat 009 & MROI-R1] Avoid K Prefix

· · 题解

思路

由于不知道正解所以打暴力，由于 TLE 所以优化，由于优化所以 AC。

显然可以枚举 l 和 r 将 l 到 r 反转。\ 用 flag 记下有没有答案（flag 初始化为 1），有的话直接输出，然后 break，否则继续循环，直到循环完了都没有答案（即 flag 的值仍为 1），就输出 No。

显然可以想到不需要真正的反转，只用对应反转后的下标就行。\ 在区间 l 到 r 内，反转过后的 a_i 对应的值是原来的 a_{r - i + l}。

显然又可以想到，反转不会影响 1 加到 l 的和，所以用前缀和数组记录下来，用 sum_i 表示 a_1 + \dots + a_i，每次就不用算 1 加到 l 了。\ 如果 sum_{l - 1} 等于 k 的话就退出，输出 No。\ 由于 l 递增，所以这样就不需要担心 l 前面有和是 k 的了，因为如果有就已经 break 了。

已经把 1 到 l - 1 优化掉了，而 l 到 r 不知道怎么优化，所以现在要优化 r + 1 到 n。\ 显然，l 到 r 怎么反转，都不会影响 r 之后的前缀和。\ 不妨用 f_i 记录从 i 到 n 的每一位的前缀和是否都不是 k。\ 从后往前遍历，如果 f_{i + 1} 已经是 0 了，那么 f_i 显然是 0，因为 i 到 n 显然经过 i + 1 到 n。\ 否则就看 sum_i 是不是等于 k，如果 sum_i 不等于 k，则 f_i 为 1，否则为 0。

其他细节见代码。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int t, n, k, x, flag, flag2, a[2010], sum[2010], f[2010];
signed main()
{
    scanf("%lld", &t);
    while (t--)
    {
        scanf("%lld%lld", &n, &k), memset(sum, 0, sizeof sum), memset(f, 0, sizeof f), flag = 1, f[n + 1] = 1;
        for (int i = 1; i <= n; i++)
            scanf("%lld", &a[i]), sum[i] = sum[i - 1] + a[i];
        for (int i = n; i >= 1; i--)
            if (sum[i] != k && f[i + 1])
                f[i] = 1;
        for (int l = 1; l <= n; l++)
        {
            for (int r = l; r <= n; r++)
            {
                x = sum[l - 1], flag2 = 1;
                for (int i = l; i < r; i++)
                    x += a[r - i + l], flag2 &= x != k;
                if (flag2 && f[r])
                {
                    printf("Yes %lld %lld\n", l, r), flag = 0;
                    break;
                }
            }
            if (!flag || sum[l] == k)
                break;
        }
        if (flag)
            printf("No\n");
    }
    return 0;
}

给个赞再走吧。