题解：CF2131B Alternating Series

yiming1123 · 2025-08-19 11:11:06 · 题解

题目大意

给你一个数 n，构造一个长度为 n 的满足以下条件的字符串：

相邻两个元素的积为负。
对于任意长度大于 1 的子串，其元素和为正。
构造出来的字符串的字典序最小。

解题思路

题目要求字典序最小。贪心地想，我们所选的数字的绝对值越小，其构成的字符串的字典序就越小。

手玩一下样例可以发现，奇数位应该为负，偶数位为正，否则就不能同时满足长度大于 1 的子串元素和为正和字典序最小，比如： :::align{center}

string={1,-4,1}

::: 接下来我们再观察样例，发现：

当 n 为偶数时，正数出现了 2。
当 n 为奇数时，正数出现了 3。

因为样例太小了，我们还看不出正真的规律。可举 n=4 的情况。 :::align{center}

string={-1,3,-1,2}

::: 这就是答案了，但怎么既出现了 2 又出现了 3 了呢？那就手玩一下。

若把 3 改成 2。则子串 string={-1,2,-1} 明显是不满足条件的。因为 2 的前后有两个负数，最小的负整数就是 -1（同时满足了字典序最小）。2-1-1=0。为了让它为正，就只能再加一。

将这个思路代入子串 string={-1,2}，2 的前后只有一个负数，因此 2 就足够。

总结

奇负偶正，负数选 -1，正数看其左右两边有几个负数，一个选 2，否则选 3（实则是看其是否在末尾）。

Code

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
#define lint long long
#define line inline
line lint read(){
    lint x=0;int f=1;char c=getchar();
    while(c<'0' or c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' and c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return x*f;
}

int T,n;

int main(){
    T=read();
    while(T--){
        n=read();
        int k=(n-1)/2+1;
        int m=!(n%2)?-1:0;
        for(int i=1;i<=n+m;++i){
            if(i&1) printf("-1 ");
            else printf("%d ",k+1>3?3:k+1);
        }
        if(m) printf("2 ");
        printf("\n");
    }
    return 0;
}

题解：CF2131B Alternating Series

题目大意

构造出来的字符串的字典序最小。

解题思路

总结

Code