1998(965div2)

A. Find K Distinct Points with Fixed Center

给你三个整数 $x_c$ 、 $y_c$ 和 $k$ ( $-100\le x_c,y_c\le 100$ , $1\le k\le 1000$ )。

找到 $k$ 个点，$(x_i,y_i)$ 满足 ${\displaystyle \sum x_i=k\times x,\sum y_i=k\times y}$ $-{10}^9\le x_i,y_i\le {10}^9$ 。

做麻烦了...

void solve() {
    int x, y, k;cin >> x >> y >> k;

    if (k & 1) {
        cout << x * k << " " << y * k << '\n';k--;
    } else {
        cout << x * (k / 2) + 100000000 << " " << y * (k / 2) + 100000000 << '\n';
        cout << x * (k - k / 2) - 100000000 << " " << y * (k - k / 2) - 100000000 << '\n';
        k -= 2;
    }
    for (int i = 1;i <= k;i++) {
        if (i & 1)
            cout << - i - 1 + 10000000 << " " << - i - 1 + 10000000 << '\n';
        else
            cout << i - 10000000 << " " << i - 10000000 << '\n';
    }
}

void solve() {
	int x, y, k; cin >> x >> y >> k;
	for(int i = 0; i < k - k % 2; i++){
		cout << x - (i & 1 ? 1 : -1) * (i / 2 + 1) << " " << y << "\n";
	} 
	if(k & 1){
		cout << x << " " << y << "\n";
	}
}

B. Minimize Equal Sum Subarrays

给你一个长度为 $n$ 的排列组合 $p$ 。

求长度为 $n$ 的排列组合 $q$ 使 $p_i+p_{i+1}+\dots +p_j=q_i+q_{i+1}+\dots +q_j$ 的成对数 ( $i,j$ ) ( $1\le i\le j\le n$ ) 最小。

也就是说要让两个排列尽量不要出现在 $[l,r]$ 区间内区间和相等的情况。这个题就很简单了，直接移一位即可满足。

rotate(p.begin(), p.begin() + 1, p.end());

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i < n;i++)cout << a[i + 1];
    cout << a[1] << ' ';cout << '\n';
}

C. Perform Operations to Maximize Score

给你一个长度为 $n$ 的数组 $a$ 和一个整数 $k$ 。同时给你一个长度为 $n$ 的二进制数组 $b$ 。

您最多可以执行以下操作 $k$ 次：

• 选择一个索引 $i$ ( $1\le i\le n$ )，使得 $b_i=1$ .设置 $a_i=a_i+1$ （即将 $a_i$ 增加 $1$ ）。

您的分数定义为 $\underset{i=1}{\overset{n}{max}}(a_i+\mathrm{median}(c_i))$ ，其中 $c_i$ 表示从 $a$ 中删除 $a_i$ 后得到的长度为 $n-1$ 的数组。

找出如果以最佳方式进行运算，你能得到的最高分。

Solution

这个题目我赛时思路完全正确的，不知道哪里错误了。

思路：只有两种情况：

• 全部 $k$ 交给 $a_i$ 即 $a_i+k$ 使得这个值达到最大，则此时最大值就是 $a_i+k+\text{mid}(c_i)$
• 最大值就是不能操作的数，此时的 $k$ 全部去提升中位数，运用二分答案即可。

打完牛客周赛 55 继续补