比赛地址

B（贪心+期望）

题目链接
⭐⭐⭐

题目：
有\(n\)个盒子，他们的颜色未知，把第\(i\)个盒子打开所要付出的代价为\(w_i\)，现在可以花费\(C\)进行若干次询问，可以告诉当前剩余盒子中黑白各多少个，现在需要知晓每一个盒子的颜色，所需要花费的最小代价是多少

解析：
两种策略
第一种将所有盒子打开不进行询问，\(cost=\sum\limits_{i=1}^nw[i]\)
第二种开始前询问一次（后续多次询问没有意义，可以根据已经打开的盒子颜色推算出来），而后按代价从小到大打开盒子，在后续盒子不为同色时都应加上对应的代价。若当前为第\(i\)个盒子，后续不同色的概率为\(1-2\times\frac{1}{2^{n-i+1}}\)，对应的\(cost=C+w[i]\times(1-\frac{1}{2^{n-i}})\)

注意：

1. 使用long double才可以符合精度要求

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;
long double w[maxn];

int main() {
	int n;
	long double ans[2] = { 0 };
	scanf("%d%Lf", &n, &ans[1]);
	for (int i = 0; i < n; ++i)
		scanf("%Lf", &w[i]), ans[0] += w[i];
	long double t = 0.5;
	sort(w, w + n);
	for (int i = n - 2; i >= 0; --i)
		ans[1] += w[i] * (1 - t), t /= 2;
	printf("%Lf", min(ans[0], ans[1]));
}

D（线性dp）

题目链接
⭐⭐⭐

题目：
给出字符串A,B，从中找出子序列a,b，如果这对个子序列是好的，则满足\(|a|=|b|,\exists i\in\{1,2,\dots,|a|\},A_{a_i}<B_{b_i},\forall j\in\{1,2,\dots,i-1\},A_{a_j}=B_{b_j}\)，求对数（答案模取\(10^9+7\)）

解析：
对于每个符合\(A_i<B_j\)的\((i,j)\)，用\(dp[i][j]\)代表\(A\)中前\(i\)个，\(B\)中前\(j\)个所能够得到的相同子序列数量，\(c[i][j]\)代表长度为\(i,j\)的字符串中长度相同子序列数量，那此时贡献无疑为\(dp[i-1][j-1]\times c[n-i][m-j]\)
对于第一个\(dp\)，用容斥原理可以得到\(dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]\)代表仅\(A_i\)或\(B_j\)参与在子序列的构造中的情况，如果\(A_i=B_j\)则需要再加上\(dp[i-1][j-1]\)
同理也不难得到\(c[i][j]=c[i-1][j]+c[i][j-1]-c[i-1][j-1]+c[i-1][j-1]\)

#include<bits/stdc++.h>

using namespace std;

const int maxn = 5e3 + 5;
char a[maxn], b[maxn];
int dp[maxn][maxn], c[maxn][maxn];
const long long mod = 1e9 + 7;

int main() {
	int n, m;
	scanf("%s%s", a + 1, b + 1);
	n = strlen(a + 1), m = strlen(b + 1);
	for (int i = 0; i <= n; ++i)
		dp[i][0] = c[i][0] = 1;
	for (int i = 0; i <= m; ++i)
		dp[0][i] = c[0][i] = 1;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			c[i][j] = (1ll * c[i - 1][j] + c[i][j - 1]) % mod, dp[i][j] = (1ll * dp[i - 1][j] + dp[i][j - 1] - (a[i] != b[j]) * dp[i - 1][j - 1]) % mod;
	long long ans = 0;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			if (a[i] < b[j])
				ans = (ans + dp[i - 1][j - 1] * c[n - i][m - j]) % mod;
	printf("%lld", (ans + mod) % mod);
}

H（水题）

题目链接
⭐⭐

题目：
构建一个\(n\times m\)的矩阵，保证不存在三个不一样的点满足\(A_{i_1,j_1}=A_{i_2,j_2}=A_{i_3,j_3},-1\le i_1-i_2=i_2-i_3\le 1,-1\le j_1-j_2=j_2-j_3\le1\)

解析：
不难发现形如（下图）的矩阵满足要求

#include<bits/stdc++.h>
 
using namespace std;
int n, m;
int a[1005][1005];
 
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        int start = i & 1 ? 2 : -1;
        for (int i = 0; i < m; ++i) {
            if (start > 0) {
                printf("0"), --start;
                if (start == 0) --start;
            }
            else {
                printf("1"), ++start;
                if (start == 1) ++start;
            }
        }
        printf("\n");
    }
}

J（最小权匹配）

题目链接
⭐⭐⭐

题目：
现有宝石分布在\((x_i,y_i,z_i)\)，且在时间\(t\)时，宝石会下落\(v_it\)的距离，打捞每个宝石的花费为\(d^2\)，\(d\)代表宝石的距离\(x_i^2+y_i^2+z_i^2\)，现求打捞所有宝石所需要的最小花费

解析：
以时间点与宝石建点，求最小权匹配即可，边权为\(x_i^2+y_i^2+(z_i+tv_i)^2\)

#include<bits/stdc++.h>
using namespace std;


namespace KM {
	const int maxn = 305;
	const long long inf = 0x3f3f3f3f3f3f3f3f;
	long long w[maxn][maxn], lx[maxn], ly[maxn], slack[maxn];
	int match[maxn], pre[maxn], n; //linker[i]:右边第i个点的匹配对象
	bool visy[maxn];

	void bfs(int k)
	{
		int x, y = 0, yy = 0;
		long long delta;
		memset(pre, 0, sizeof(pre));
		for (int i = 1; i <= n; i++)
			slack[i] = inf;
		match[y] = k;
		while (1)
		{
			x = match[y];
			delta = inf;
			visy[y] = true;
			for (int i = 1; i <= n; i++) {
				if (!visy[i]) {
					if (slack[i] > lx[x] + ly[i] - w[x][i]) {
						slack[i] = lx[x] + ly[i] - w[x][i];
						pre[i] = y;
					}
					if (slack[i] < delta)
						delta = slack[i], yy = i;
				}
			}
			for (int i = 0; i <= n; i++) {
				if (visy[i])
					lx[match[i]] -= delta, ly[i] += delta;
				else
					slack[i] -= delta;
			}
			y = yy;
			if (match[y] == -1)
				break;
		}
		while (y)
			match[y] = match[pre[y]], y = pre[y];
	}

	long long km()
	{
		memset(lx, 0, sizeof(lx));
		memset(ly, 0, sizeof(ly));
		memset(match, -1, sizeof(match));
		for (int i = 1; i <= n; i++)
		{
			memset(visy, false, sizeof(visy));
			bfs(i);
		}
		long long ans = 0;
		for (int i = 1; i <= n; i++)
			ans += w[match[i]][i];
		return ans;
	}
}

int main()
{
	scanf("%d", &KM::n);
	long long ans = 0;
	for (int i = 0; i < KM::n; i++)
	{
		int x, y, z, v;
		scanf("%d%d%d%d", &x, &y, &z, &v);
		for (int j = 0; j < KM::n; j++)
			KM::w[i + 1][j + 1] = -(x * x + y * y + 1ll * (z + v * j) * (z + v * j));
	}
	printf("%lld\n", ans - KM::km());
	return 0;
}

K（单调队列）

题目链接
⭐⭐⭐

题目：
给出\(a\)数组，有\(m\)次询问，回答子连续数组中极差大于\(k\)的数量

解析：
对于每个点\(i\)来说，满足条件的最小\(r_i\)无疑是非严格递增的，所以可以维护一个单调递增与单调递减的队列，不断判断队首元素是否差值大于\(k\)，在均摊时间\(O(1)\)的情况下，计算出每个点对应的\(r_i\)

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
int a[maxn];

int main() {
	int n, m;
	int t;
	deque<int> mx, mn;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	while (m--) {
		long long ans = 0;
		scanf("%d", &t);
		mx.clear();
		mn.clear();
		int now = 1;
		for (int i = 1; i <= n; ++i) {
			while (!mx.empty() && a[mx.back()] <= a[i]) mx.pop_back();
			mx.push_back(i);
			while (!mn.empty() && a[mn.back()] >= a[i]) mn.pop_back();
			mn.push_back(i);
			while (a[mx.front()] - a[mn.front()] > t) {
				++now;
				ans += n - i + 1;
				if (mx.front() < now) mx.pop_front();
				if (mn.front() < now) mn.pop_front();
			}
		}
		printf("%lld\n", ans);
	}
}