题目1

题目链接
题目大意：
有一个数组a，仅有整数1和-1组成，我们定义数组a的乘积为：
对于 1≤𝑖<𝑗≤𝑛, 𝑎[𝑖]⋅𝑎[𝑗]=1的数量。

现在给出数组长度n和乘积k，问是否可以构造一个满足要求的数组a；

输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤20000)
每个样例1行， n和𝑘，表示数组长度和乘积k （2≤𝑛≤100 ; 0≤𝑘≤(𝑛−1)*𝑛/2）

输出：
如果有解，则输出YES，然后第二行输出n个整数；
如果无解，则输出NO；

Examples
input
7
2 0
2 1
3 1
3 2
3 3
5 4
5 5

output
YES
1 -1
YES
1 1
YES
1 -1 1
NO
YES
1 1 1
YES
-1 1 -1 1 1
NO

题目解析：
题目给出的数据范围比较小，可以直接枚举；
遍历数组存在0个、1个、2个、、、到n个1的情况，剩下用-1填充；
然后再遍历整个数组，两两计算a[i]*a[j] = 1的数量；
如果满足要求则输出；

class Solution {
    static const int N = 201010;
    char s[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n, k;
            cin >> n >> k;
            int ans = 0;
            for (int i = 0; i <= n; ++i) //第i个开始都是1，前面都是-1
            {
                int sum = 0;
                for (int x = 0; x < n; ++x) {
                    for (int y = x + 1; y < n; ++y) {
                        if ((x < i && y < i) || (x >= i && y >= i)) {
                            ++sum;
                        }
                    }
                }
                if (sum == k) {
                    ans = 1;
                    int tmp = 0;
                    cout << "YES" << endl;
                    while (tmp < i) {
                        cout << "-1" << " ";
                        ++tmp;
                    }
                    while (tmp < n) {
                        cout << "1" << " ";
                        ++tmp;
                    }
                    cout << endl;
                    break;
                }
            }
            if (!ans) cout << "NO" << endl;
            
        }
    }
}

题目2

题目链接
题目大意：
给出1到n的整数排列所形成的数组p以及整数k，现在可以对数组进行下列操作形成从小到大的数组：
选择任意两个相差为k的位置，交换他们的位置上的元素；
比如说数组[3,2,1] 和 k=2，那么可以选择位置1和位置3进行交换，得到数组[1,2,3]，满足题目要求；

但是有些数组的无法满足要求，比如说[2,4,3,1]和k=2，此时无法通过交换得到数组[1,2,3,4]；
这种情况下，此时允许在最初的时候（进行交换操作之前），对选择任意数组两个位置，进行交换（该交换只允许一次），比如说：
数组[2,4,3,1]选择整数1和2交换得到[1,4,3,2]，然后再进行交换操作，可以得到从小到大的数组[1,2,3,4]；

现在的任务是给出数组p和整数k，问是否能得到从小到大的数组。

输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例2行
第一行 n和𝑘，表示数组长度和整数k (2≤𝑛≤2⋅1e5; 1≤𝑘≤𝑛−1)
第二行 n个整数 𝑝1,𝑝2,…,𝑝𝑛 （1≤𝑝𝑖≤n）

输出：
每个样例一行，输出0/1/-1，分别表示：
0，有解，并且不需要提前交换；
1，有解，但是必须要提交交换；
-1，无解；

Examples
input
6
4 1
3 1 2 4
4 2
3 4 1 2
4 2
3 1 4 2
10 3
4 5 9 1 8 6 10 2 3 7
10 3
4 6 9 1 8 5 10 2 3 7
10 3
4 6 9 1 8 5 10 3 2 7

output
0
0
1
0
1
-1

题目解析：
当k=1的时候，肯定有解，因为可以随意交换；
当k>1的时候，每个位置能和相距为k的位置交换，那么将距离为k的元素全部提取出来，这部分元素就能任意交换，比如说数组[1,2,3,4,5,6,7]
k=2时，数组可以拆分为[1,3,5,7]和[2,4,6]，这两个数组的元素就能任意交换；
k=3时，整数可以拆分为[1,4,7], [2,5], [3,6] 这样三个数组；
我们将数组p，拆分成k个数组，每个数组如果都按照上述的规律展示，那么不需要做提前交换，就可以有解；

通过不匹配当前数组的元素数量，如果为2，那么通过提前交换就有解；如果为其他值则无解；

举个例子，假设数组4 1 3 5 2 6 7，我们拆分得到
457
12
36

那么可以得到4应该在第二组，而不是第一组；
1不应该在第二组，而是应该在第一组；
此时提前交换1和4，有解；

class Solution {
    static const int N = 201010;
    int a[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n, k;
            cin >> n >> k;
            for (int i = 1; i <= n; ++i) cin >> a[i];
            if (k == 1) cout << 0 << endl;
            else {
                int cnt = 0;
                for (int i = 1; i <= k; ++i) {
                    int idx = i;
                    while (idx <= n) {
                        if ((a[idx] - i) % k) ++cnt;
                        idx += k;
                    }
                }
                if (cnt == 2) cnt = 1;
                cout << (cnt < 2 ? cnt : -1) << endl;
            }
        }
    }
}

题目3

题目链接
题目大意：
有n个整数的数组a，数组元素由1和-1组成；
现在可以对数组中的元素进行操作（最后一个元素无法操作），将这个元素与右边元素进行符号反转；
比如说数组[1, -1, -1]，如果我们选择[1, -1]进行符号反转，则得到[-1, 1, -1]；如果我们选择[-1, -1]进行符号反转，则可以得到[1, 1, 1]；
这个操作必须执行一次，问操作完数组最大的和是多少。（a1+a2+a3...+an)

输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤500)
每个样例2行，第一行整数𝑛 (2≤𝑛≤10e5）
第二行n个整数 𝑎1,𝑎2,…,𝑎𝑛 (𝑎𝑖=1 or 𝑎𝑖=−1)

输出：
每个样例一行，输出可能的最大数组和；

Examples
input
4
5
-1 1 1 -1 -1
5
1 1 -1 -1 -1
2
1 1
4
1 -1 -1 1

output
3
3
-2
4

题目解析：
直接累加数组的整数，得到整数和sum；
接着遍历数组：
如果能找到两个-1相邻，则直接反转着两个整数，sum=sum+4；
如果能有一个-1，则sum=sum;
如果都是1，则sum=sum - 4;

class Solution {
    static const int N = 201010;
    int a[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            int sum = 0, done = 0;
            for (int i = 0; i < n; ++i) {
                cin >> a[i];
                sum += a[i];
            }
            for (int i = 1; i < n && !done; ++i) {
                if (a[i] + a[i - 1] == -2) {
                    sum += 4;
                    done = 1;
                }
            }
            for (int i = 0; i < n && !done; ++i) {
                if (a[i] == -1) {
                    done = 1;
                }
            }
            if (!done) {
                sum -= 4;
            }
            cout << sum << endl;
        }
    }
}

题目4

题目链接
题目大意：
给出一个由 _ 和 ^ 两种字符组成的字符串，现在小明可以往字符串任意位置插入这两种字符，要求：
1、任何位置的字符，都可以和相邻连续字符组成^_^ 或者 ^^ 这样的字符串；
2、尽可能少的插入字符；

比如说字符串^^__^_^^__^，在第3,4,9,10,11个字符，就无法和相邻连续字符组成满足要求的字符串。

问最少需要插入多少个字符。

输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤100)
每个样例1行，字符串𝑠 (1≤|𝑠|≤100)

输出：
每个样例一行，输出最少插入数量；

Examples
input

 7
 ^______^
 ___^_^^^_^___^
 ^_
 ^
 ^_^^^^^_^_^^
 ___^^
 _

output

 5
 5
 1
 1
 0
 3
 2

题目解析：

字符串只包含两种字符，由于可以插入 ^ 字符，^字符可以和_组成^_^ ，也可以和^组成^_^，那么必然题目有解；
 对于题目来说，单个^，以及_左右不是^都是不合法的，需要插入^；
 那么就可以有简单的解决方案：
 从左到右遍历字符串，对于第i个字符串s[i]，假如：
 1、s[i]是^字符，只要i>0，^必然合法，因为s[i-1]是'^'，已经合法；如果s[i-1]是'_'，那么在处理s[i-1]的时候已经做了合法处理；
 2、s[i]是_字符，如果i==0，需要在前面插入^，否则只需要考虑后面是_的情况，需要插入一个^；

class Solution {
    static const int N = 201010;
    char s[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            cin >> s;
            int n = strlen(s);
        
            int ans = 0;
            for (int i = 0; i < n; ++i) {
                if (s[i] == '_') {
                    if (i == 0) {
                        ++ans;
                    }
                    if (i + 1 == n || s[i + 1] == '_') {
                        ++ans;
                    }
                }
                else {
                    if (n == 1) {
                        ++ans;
                    }
                }
            }
            cout << ans << endl;
            
        }
    }
}

题目5

题目链接
题目大意：
给出一个0/1字符组成的字符串，现在按照以下规则进行排序：
1、将字符串str作为矩阵第一行；
2、将字符串str所有字符右移1位（最后一位字符会移动到最左边的位置），将这个字符当做下一行；
重复以上规则，直到得到一个正方形矩阵。
以“101”字符串为例：
第一行是101；
第二行是110；
第三行是011；

问得到的正方形矩阵中，由1组成的连续字符矩阵最大面积是多少。

输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤2⋅1e4 )
每个样例1行，字符串𝑠 (1≤|𝑠|≤2⋅1e5),

输出：
每个样例一行，输出最大的面积，如果不存在则输出0；

Examples
input
5
0
1
101
011110
101010

output
0
1
2
6
1

题目解析：
由于字符串长度很大，暴力枚举计算的空间复杂度太高；
分析题目给出的构造规则，我们发现0会形成一条斜线，将矩形分割开来；

参考题目样例4，我们可以知道最终矩阵：
0 0 1 1 1 1 0
1 0 0 1 1 1 1
1 1 0 0 1 1 1
1 1 1 0 0 1 1
1 1 1 1 0 0 1
0 1 1 1 1 0 0
存在一个长为4，等边三角形；

同理，这样的字符串，一样在矩阵中存在长为4的等边三角形。
1 1 1 1 0 0 0
0 1 1 1 1 0 0
0 0 1 1 1 1 0
0 0 0 1 1 1 1
1 0 0 0 1 1 1
1 1 0 0 0 1 1

极端的情况，连续的1拆分在两边
1 1 0 0 0 1 1
1 1 1 0 0 0 1
1 1 1 1 0 0 0
0 1 1 1 1 0 0
0 0 1 1 1 1 0
0 0 0 1 1 1 1
1 0 0 0 1 1 1

1 1 1 0 0 0 1
1 1 1 1 0 0 0
0 1 1 1 1 0 0
0 0 1 1 1 1 0
0 0 0 1 1 1 1
1 0 0 0 1 1 1
1 1 0 0 0 1 1

可以得到一个规律，我们根据字符串中“连续”1的数量，就可以得到等边三角形的数量。
这个连续1的计算方式，可以用下面的规则：
将字符串1100011，复制一遍粘到末尾 1100011+1100011 = 11000111100011
这样去计算一遍连续的最长字符串即可。

注意：
1、如果全为1，答案为n * n；
2、如果全为0，答案为0；
3、结果有可能超int32，需要用long long。

class Solution {
    static const int N = 401010;
    char s[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            cin >> s;
            int n = strlen(s);
            for (int i = 1; i < n; ++i) {
                s[n + i - 1] = s[i - 1]; // 拼接
            }
            s[n * 2 - 1] = '0';
            int cur = 0, zero = 0, len = 0;
            for (int i = 0; i < 2 * n; ++i) {
                if (s[i] == '0') {
                    len = max(len, cur);
                    cur = 0;
                }
                else {
                    ++cur;
                }
            }
            for (int i = 0; i < n; ++i) zero |= (s[i] == '0');
            if (!zero) cout << n * 1LL * n << endl;
            else {
                if (len <= 2) cout << len << endl;
                else if (len % 2) cout << (len + 1) / 2LL * (len + 1) / 2 << endl;
                else cout << len / 2LL * (len + 2) / 2 << endl;
            }
            
        }
    }
}