B / 简谐振动

· · 题解

思路

&=A_1+A_2+A_3+\dots+A_{n-1}+A_n\end{aligned}\\ \because n \bmod 2 = 1\\ \begin{aligned}&\therefore A_x=(A_1+A_2+A_3+\dots+A_{n-1}+A_n)-\\ &\begin{cases} [(A_1+A_2)+\dots+(A_{x-2}+A_{x-1})+(A_{x+1}+A_{x+2})+\dots+(A_{n-1}+A_n)]&x \bmod 2 = 1\\ [(A_2+A_3)+\dots+(A_{x-2}+A_{x-1})+(A_{x+1}+A_{x+2})+\dots+(A_{n-2}+A_{n-1})+(A_n+A_1)]&x \bmod 2 = 0\end{cases}\end{aligned}

只需要使 (A_1+A_2)+(A_2+A_3)+\dots+(A_{n-1}+A_n)+(A_n+A_1)\bmod 2 = 0 即可，考虑将数字串划分分成 n 个可以有前导 0 的数字，使得末尾数字的和为偶数。

最后一位数字必选为末尾数字，剩下 n-1 个自己选择，因此，只需要看是否有 n-1 个不同的数字和最后一位数字的和为偶数即可。

末尾为偶数：判断是否可以从前面选出 n-1 个数和为偶数即可。

末尾为奇数：先拿另一个奇数凑成偶数，再判断是否可以从其他数中选出 n-2 个数和为偶数即可。

code

写的有点复杂……

#include<bits/stdc++.h>
using namespace std;
void ask(int od,int ev,int cnt){//判断od个奇数、ev个偶数中能否选cnt个数使得和为偶数
    if(od+ev<cnt){//个数都不够
        printf("No\n");
        return;
    }
    if(cnt%2==1){//奇数个，需要先拿一个偶数，避免下面使用奇数时会选出半个一对奇数导致结果为奇数
        if(!ev){//没有偶数
            printf("No\n");
            return;
        }
        cnt--;
        ev--;
    }
    cnt-=od/2*2;//每两个一对奇数
    if(cnt<=0){
        printf("Yes\n");
        return;
    }
    cnt-=ev;
    if(cnt<=0){
        printf("Yes\n");
        return;
    }
    printf("No\n");
}
int main(){
    int tc,n,od,ev;
    string s;
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&n);
        cin>>s;
        od=0;
        ev=0;
        for(int i=0;i<s.size()-1;i++)//统计奇数和偶数的数量
            if((s[i]-'0')%2==0)
                ev++;
            else
                od++;
        if((s[s.size()-1]-'0')%2==0)
            ask(od,ev,n-1);//末尾为偶数
        else{//末尾为奇数
            if(n==1){//特判：一个数字，但是是奇数
                printf("No\n");
                continue;
            }
            if(od==0){//特判没有奇数
                printf("No\n");
                continue;
            }
            od--;//先用一个奇数
            ask(od,ev,n-2);
        }
    }
    return 0;
}