A QWQ

思路

简单构造。

显然，Q 与 W 交替使用最优。

代码

#include <cstdio>

int t, n;
int main(){
	scanf("%d", &t);
	while (t --){
		scanf("%d", &n);
		for (int i = 1;i <= n;i ++){ // 输出方案
			for (int j = 1;j <= n;j ++) putchar(i + j & 1 ? 'W' : 'Q');
			putchar('\n');
		}
	}
}

B 最小值

思路

排序 + 一点思维。

可以发现，每一种选择方式的贡献只和选到的最小值有关。

然后，我们就可以转换问题，转换为枚举每一个数 $x$，求有多少种方案使得选到的三个数里 $x$ 最小，每一种使得选到的三个数里它最小的方案都会对总答案造成 $x$ 贡献。

显然，使得选到的三个数里 $x$ 最小的方案里，选到的另外两个数都 $\ge x$。

我们就可以对 $a$ 由小到大排序，每次枚举的时候另外两个数只选择 $\ge a_i$ 的，也就是在 $a_i$ 后面的。

设有 $m$ 个数 $\ge a_i$，就有 $C^2_m$ 也就是 $\dfrac{m^2 - m}{2}$ 种选择方案。

代码

#include <algorithm>
#include <cstdio>
#define mod 1000000007

using namespace std;

long long n, w[100001], ans;
int main(){
	scanf("%d", &n);
	for (int i = 1;i <= n;i ++) scanf("%d", &w[i]);
	sort(w + 1, w + n + 1);
	for (long long i = 1;i <= n - 2;i ++) ans = (ans + w[i] * ((n - i) * (n - i - 1) / 2)) % mod;
	printf("%d", ans);
}

C 子段和

思路

前缀和 + 哈希。

如果使用前缀和 $s$ 表示区间 $[l, r]$ 的和等于 $k$，是这样的：

$s_r - s_{l - 1} = k$

移项，得：

$s_r - k = s_{l - 1}$

然后，我们就可以将每一个 $s_i$ 插进哈希表里，然后查一下 $s_i - k$ 之前有没有出现过，如果有，就代表有和为 $k$ 的区间，否则没有。

代码

#include <cstdio>
#include <vector>
#define mod 1000007
#define abs(x) (x < 0 ? -x : x)

using namespace std;

int n, a[10000001];
long long k, sum[10000001];
vector<long long> ha[mod]; // 哈希表
inline long long read(){
    long long x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9'){
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x * f;
}
inline void insert(long long x){ // 插入
	int p = abs(x) % mod;
	for (int i = 0;i < ha[p].size();i ++){
		if (ha[p][i] == x) return;
	}
	ha[p].push_back(x);
}
inline bool check(long long x){ // 查找
	int p = abs(x) % mod;
	for (int i = 0;i < ha[p].size();i ++){
		if (ha[p][i] == x) return 1;
	}
	return 0;
}
int main(){
	n = read(), k = read();
	for (int i = 1;i <= n;i ++) a[i] = read(), sum[i] = sum[i - 1] + a[i]; // 计算前缀和
	for (int i = 0;i <= n;i ++){
		insert(sum[i]); // 插入 s[r]
		if (check(sum[i] - k)){ // 查找 s[l] - k
			printf("YES");
			return 0;
		}
	}
	printf("NO");
}

D 求数组

思路

二分。

显然，确定一个正确的 $a_i$，就可以确定整个数组。

然后，我们就可以二分枚举 $a$ 的某一个数，范围为 $[1, s_i]$。

这里，我枚举的是 $a_1$。

代码

#include <cstdio>

using namespace std;

int s[1000001], n, l, r, mid;
bool check(int x){ // 检查
	int sx = x;
	for (int i = 1;i < n;i ++) x = s[i] - x;
	return x <= s[n] - sx;
}
int main(){
	scanf("%d", &n);
	for (int i = 1;i <= n;i ++) scanf("%d", &s[i]);
	l = 1, r = s[1] + 1; // 枚举范围
	while (r - l > 1){
		mid = l + r >> 1;
		if (check(mid)) l = mid;
		else r = mid;
	}
	for (int i = 1;i <= n;i ++) printf("%d ", l), l = s[i] - l; // 输出答案
}