题解：P10534 [Opoi 2024] 简谐振动

xyz105 · 2024-07-04 18:01:16 · 题解

题目描述

已知一个数字串 S，请你判断是否存在一种长度为 n 且 n 为奇数的整数序列 A_i，使得 A_1+A_2,A_2+A_3,\dots,A_{n-1}+A_n,A_n+A_1 的值按顺序依次拼接起来可以得到 S。

特别的，如果存在一种方案使得拼接的时候两项中间用 [0,\infty) 个 0 分隔仍然可以得到 S，该方案仍然合法。所有数据保证最前面没有前导 0。

解题思路

不妨设分解 S 所得出的数字分别为 B_{1\ldots n}。因为最前面是没有前导 0 的，并且“两项中间用 [0,\infty) 个 0 分隔”说明非开头的数字可以有前导 0，所以实际上 S 可以任意分解。

考虑用 A_1 表示 A_{2\ldots n}，有

首尾相加的特性使得 B_{n}-B_{n-1}+B_{n-2}-\cdots+B_1-A_1=A_1。

即 2A_1=B_{n}-B_{n-1}+B_{n-2}-\cdots+B_1，说明等号右边必须是偶数。

又因为对于任意正整数 k，都有 k 与 -k 奇偶性相同，所以转为判定 B_{n}+B_{n-1}+B_{n-2}+\cdots+B_1 是偶数即可。

判断一个数是否为偶数，只需判断其个位即可。因此问题转化为 在 S 中取 n 个数（S 的最后一位必须取）使得它们相加为偶数。

可以循环 S 中每一位，记录奇数个数 \text{odd}、偶数个数 \text{even}。因为要保证“相加为偶数”，所以选取的奇数个数必须是偶数。因此记 \text{odd}' 为不大于 \text{odd} 的最大偶数，判断是否有 \text{odd}'+\text{even}\ge n 即可。

注意细节：S 的最后一位必须取。当 S 的末位是奇数时，应有 \text{odd}'>0 且 n>1 才有可行方案。

参考代码

已经算较短了。

代码中 \text{odd} 用 i1 表示，\text{odd}' 体现为 i1 / 2 * 2。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 1e6 + 10;

int t, n, l, i1, i2; char s[MAXN];

int main()
{
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%s", &n, s + 1), i1 = i2 = 0;
        for (int i = l = strlen(s + 1); i; i--) if (s[i] & 1) i1++; else i2++;
        puts(max(0, max(1, n - i1 / 2 * 2) - i2) || ((s[l] & 1) && (i1 == 1 || n == 1)) ? "No" : "Yes");
    }

    return 0;
}