[ABC384D] Repeated Sequence 题解

· · 题解

原题跳转

[ABC384D] Repeated Sequence

题目简述

给定一个每 N 项为一个周期的无限序列 A，给定 A_{1} \sim A_{N}，判断是否存在一个 A 的子序列使这个子序列的和为 S。如果存在输出 Yes，否则输出 No。

主要思路

不难发现，和为 S 的子序列可以由三部分组成：

  1. 设 x 为第一部分元素的个数（0 \le x < N），第一部分为 A_{N-x+1} \sim A_{N}（x 为 0 则没有）。
  2. 若干个序列 A 拼成的序列。
  3. 设 y 为第三部分元素的个数（0 \le y < N），第三部分为 A_{1} \sim A _ {y}（y 为 0 则没有）。

虽然第一部分和第三部分不能确定是如何组成的，但是第二部分可以，总和一定是若干个 \sum _ {i=1} ^ {N} A _ {i} 的和且不超过 S 的最大数。于是就可以先将 S 取余 \sum _ {i=1} ^ {N} A_{i}，再判断是否可能存在第一部分和第三部分。

由于第二部分是若干个完整的序列，所以在去掉第二部分后，因为 A 是一个无限序列，A_{N} 的下一个元素可以理解为又是 A_{1}，所以第一部分和第三部分拼接起来也是连续的。

要判断是否存在这样一个序列，可以使用双指针的算法，由于第一部分和第三部分的元素数都 < N，所以拼接后的元素数一定不会 > 2N。 那么想要判断是否存在这个序列，就只需要对 A_{1} \sim A_{2N} 进行枚举就可以了。暂且称 A_{1} \sim A_{2N} 为 A'。

将序列 A' 进行一次前缀和，根据双指针算法思路进行即可。如果 \sum _ {i=l} ^ {r} A' _ {i} > S，就不断增加 l，直到不大于为止，如果在这途中总和等于了 S，那么立即输出 Yes 并终止程序；如果在双指针枚举结束后还是没有出现总和等于 S 的情况，输出 No 即可。

AC Code

#include<map>
#include<set>
#include<list>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
using namespace std;

#define endl '\n'
typedef long long ll;
const int N = 4e5 + 10;       // 注意要开N的两倍，因为序列A'
typedef unsigned int ui;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const double PI = acos(-1.0);
typedef unsigned long long ull;
// ----------------------------

// ----------------------------
ll a[N];           // 不开long long见祖宗
ll b[N];
// ----------------------------

int main() {
    ll s;
    int n;
    cin>>n>>s;
    ll sum = 0;
    for (int i=1;i<=n;i++) {
        cin>>a[i];
        sum += a[i];
    }
    // ------------------------
    s %= sum;   // 去除第二部分的总和
    for (int i=1;i<=n*2;i++) b[i] = b[i-1] + a[(i-1)%n+1];            // 构造序列A'
  // 双指针算法
    int l = 1;
    for (int r=1;r<=n*2;r++) {
        ll k = b[r] - b[l-1];
        while (k > s) {
            l++;
            k = b[r] - b[l-1];
        }
        if (k == s) {
            cout<<"Yes";
            return 0;
        }
    }
    // ------------------------
    cout<<"No";
    return 0;
}