2024.09.14模拟赛总结

$ T1 $

似乎是签到题，但是没开 $ unsigned $ $ long $ $ long $ 挂成 $ 88 $ 分了。
直接模拟即可，从后往前考虑，将每个数放到离其最近的位置，不过不会证...

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long LL;

const int N = 1000010;

struct wasd
{
	int ct, v;
} unq[N];
int n, a[N], b[N];
LL res;
map<int, bool> m;
map<int, int> ctn;
vector<LL> ans;

bool cmp(LL a, LL b)
{
	return a > b;
}

int main()
{
	freopen("openhook.in", "r", stdin);
	freopen("openhook.out", "w", stdout);
	
//	cout << mod << '\n';
	scanf("%lld", &n);
	for (int i = 1; i <= n; i ++ ) scanf("%d", a + i);
	for (int i = 1; i <= n; i ++ ) scanf("%d", b + i);
	
	sort(b + 1, b + n + 1);
	sort(a + 1, a + 1 + n);
	int cnt = 0;
	for (int i = 1; i <= n; i ++ )
	{
		if (m.count(a[i])) 
		{
			unq[cnt].ct ++ ;
			continue;
		}
		unq[ ++ cnt].v = a[i];
		unq[cnt].ct = 1;
		m[a[i]] = 1;
	}
	
	int lst_pos = unq[cnt].v + 1;
	for (int j = 1; j < unq[cnt].ct; j ++ )
		ans.push_back(lst_pos - unq[cnt].v), lst_pos ++ ;
	for (int i = cnt; i > 1; i -- )
	{
		ctn[unq[i].v] = lst_pos;
//		cout << unq[i].v << ' ' << lst_pos << "wasn\n";
		lst_pos = unq[i - 1].v + 1;
		while (ctn.count(lst_pos)) lst_pos = ctn[lst_pos];
		for (int j = 1; j < unq[i - 1].ct; j ++ )
		{
//			cout << unq[i - 1].v << ' ' << lst_pos << '\n';
			ans.push_back(lst_pos - unq[i - 1].v);
			lst_pos ++ ;
			while (ctn.count(lst_pos)) lst_pos = ctn[lst_pos];
		}
	}
	int ct = 0;
	sort(ans.begin(), ans.end(), cmp);
	for (auto x : ans) res += x * (LL)b[ ++ ct];
	
	cout << res << '\n';
	
	return 0;
} 
/*
10
1 1 1 1 3 5 5 6 7 7 
1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 1919810 

1 4
3 1
5 2
6 1
7 2

1 + 3 + 1 + 3 + 9
*/

$ T2 $

赛时基本上没有想，毕竟有关 $ mex $ 的题做得还是太少了。
只想到了一个 $ O(n ^ 3) $ 的做法：设 $ f[i][mex] $ 表示前 $ i $ 个数划分时，每段 $ mex $ 为 $ mex $ 的方案数。
大概是因为没有发现性质。

注意到一个性质：
整个数组的 $ mex $ 应当是要等于每个划分段的 $ mex $ 的。
设划分段 $ mex $ 都为 $ X $，整个数组的 $ mex $ 为 $ Y $。
那么 $ 0 \sim Y - 1 $ 应该都在数组中出现过了。
所以可以得出 $ X \ge Y $，再考虑 $ X > Y $ 的情况。
因为整个数组的 $ mex $ 为 $ Y $，那么 $ Y $ 一定没有出现过，所以 $ X $ 只能是 $ Y $。
得到了这个性质，不难想到 DP。
设 $ f_i $ 表示将数组前 $ i $ 位划分的方案数。
状态转移方程即为

$ f_i = \sum_{j = 1}^{i - 1} f_{j - 1} (mex[j, i] = Y)$

然后发现在这个过程中，$ j $ 只会向右移，于是可以用双指针 $ + $ 前缀和优化，是时间复杂度降到 $ O(n) $。

由于是前缀和，所以答案为 $ f_n - f_{n - 1} $。

#include <bits/stdc++.h>
#define lbw 37000000
#define thr 300010

using namespace std;

const int N = 37000010, mod = 1e9 + 7;

int n, a[N], cnt[N];
int f[N], mex;

signed main()
{
	freopen("clods.in", "r", stdin);
	freopen("clods.out", "w", stdout);
	
	int T;
	cin >> T;
	while (T -- )
	{
		cin >> n;
		if (n != lbw)
			for (int i = 1; i <= n; i ++ ) cin >> a[i];
		else 
		{
			int x, y;
			cin >> x >> y;
			a[1] = 0;
			for (int i = 2; i <= n; i ++ )
				a[i] = (a[i - 1] * x + y + i) & 262143;
		}
		
		f[0] = 1;
		for (int i = 0; i <= min(thr, n); i ++ ) cnt[i] = 0;
		for (int i = 1; i <= n; i ++ )
			cnt[a[i]] ++ ;
		mex = 0;
		while (cnt[mex] > 0) mex ++ ;
		for (int i = 0; i <= min(thr, n); i ++ ) cnt[i] = 0;
		int nw = 0, pre = -1;
		for (int i = 1, j = 0; i <= n; i ++ )
		{
			pre = -1;
			cnt[a[i]] ++ ;
			while (cnt[nw] > 0) nw ++ ;
			while (nw >= mex && j <= i)
			{
				j = max(j, 1);
				cnt[a[j]] -- ;
				if (!cnt[a[j]] && a[j] < nw) pre = nw, nw = a[j];
				j ++ ;
			}
			if (~pre)
			{
				j -- ;
				cnt[a[j]] ++ ;
				nw = pre;
			}
			f[i] = f[i - 1];
			if (j > 0) (f[i] += f[j - 1]) %= mod;
		}
		
		cout << (f[n] - f[n - 1] + mod) % mod << '\n';
	}
	
	return 0;
}