526互联

Codeforces Educational Codeforces Round 145 (Rated for Div. 2) C. Sum on Subarrays 题解

发布时间 2023-04-13 00:13:26作者: 1v7w

题意

Codeforces Educational Codeforces Round 145 (Rated for Div. 2) C. Sum on Subarrays

给你 \(n\) 和 \(k\) ，要求生成一个长度为 \(n\) 的数组 \(a\)，且他的非空正子数组的数量为 \(k\) ，非空负子数组的数量为 \(n-k\)，且 \(a\) 的元素取值范围为 \([-1000, 1000]\)。

思路

题目解法很多，而我一个都不会(

分类讨论n和k的关系：

  • n > k: 那么第k个为一个大整数，所有右端点为k的子数组都是正数组，而且右边的子数组不被第k个数给影响了。即前k-1个设置为-1，第k个设置为100(大于30就行)，第k+1个大于第k个，后面的继续-1.
  • n = k: 那么第k个为一个大整数，所有右端点为k的子数组都是正数组。即前k-1个设置为-1，第k个设置为100。
  • n < k: 那么第n个数设置为最大值，剩下左边的n-1个位置再整k-n个正子数组。即第n个位置为1000，递归处理(n-1, k-n)。

注意可能卡常(我用vector被卡了

代码

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
const int N = 500;
int res[N];
 
void getarray(int n, int k) {  
    if(k < n) {
        if(k >= 1) {
            for(int i=1; i<=k-1; i++) res[i] = -1;
            res[k] = 100;
            res[k+1] = -200;
            for(int i=k+2; i<=n; i++) res[i] = -1;
        }
        else {
            for(int i=1; i<=n; i++) res[i] = -1;
        }
        
    }
    else if(k == n) {
        for(int i=1; i<=k-1; i++) res[i] = -1;
        res[k] = 1000;
    }
    else {
        getarray(n-1, k-n);
        res[n] = 1000;
    }
}
 
void solve() {
    int n, k; scanf("%d%d", &n, &k);
 
    getarray(n, k);
 
    for(int i=1; i<=n; i++) printf("%d%c", res[i], " \n"[i==n]);
 
}
 
int main() {
    int t; scanf("%d", &t);
    while(t--) {
        solve();
    }
    return 0;
}