2024 CCPC网络预选赛

Frodnx / 2024-09-17 / 原文

The 2024 CCPC Online Contest
补题连接：https://codeforces.com/gym/105336

D. 编码器-解码器

考虑dp，$dp(i,j,k)$表示 $T$ 的子串 $T[j,k]$（下标 $j$ 到下标 $k$ ）在 $S_{i}^{'}$ 中以子序列出现的次数
尝试列出状态转移方程：
已知 $S_{i}^{'} = S_{i-1}^{'} + a_{i} + S_{i-1}^{'}$

考虑前后 $S_{i-1}^{'}$ 包含的子序列：

\[dp(i+1,j,k) = dp(i,j,k) * 2 \]

考虑 $S_{i-1}^{'} + a_{i} + S_{i-1}^{'}$ 包含的子序列
考虑四种情况：
情况1，$a_{i}$ 不是字符串头，也不是字符串尾；
情况2，$a_{i}$ 是字符串头，且不是字符串尾；
情况3，$a_{i}$ 是字符串尾，且不是字符串头；
情况4，$a_{i}$ 是字符串尾，也是字符串头。
不妨设，字符 $a_{i}$ 在字符串 $T$ 中出现的位置的集合为 $A$。$A_{i}$ 表示第 $i$ 个 $a_{i}$ 的下标，集合 $A$ 的大小为 $n$。

对于情况1：

\[dp(i+1,j,k) = \sum_{x=1}^{n} dp(i,j,A_{x-1}) * dp(i,A_{x+1},k) \]

对于情况2：

\[dp(i+1,j,k) = \sum_{x=1}^{n} dp(i,A_{x+1},k) \]

对于情况3：

\[dp(i+1,j,k) = \sum_{x=1}^{n} dp(i,j,A_{x-1}) \]

对于情况4：

\[dp(i+1,j,k) = 1 \]

考虑 $S_{i-1}^{'} + S_{i-1}^{'}$ 包含的子序列：

\[dp(i+1,j,k) = \sum_{x=j}^{k-1} dp(i,j,x) + dp(i,x+1,k) \]

分析时间复杂度，约为 $O(n^3)$，不超时

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
const int N = 105;
int ss[N][N][N];
// aba ba
signed main()
{
	string s, t;
	cin >> s >> t;
	unordered_map<char,vector<int> > hash;
	for(int i = 0; i < t.size(); ++ i)
		hash[t[i]].push_back(i);
	for(int i = 1; i <= s.size(); ++ i)
		for(int j = 0; j < t.size(); ++ j)
			for(int k = 0; k < t.size(); ++ k)
			{
				(ss[i][j][k] += ((ss[i-1][j][k] % mod) * 2) % mod) %= mod;
				for(int alp = 0; alp < hash[s[i-1]].size(); ++ alp)
				{
					int a2 = hash[s[i-1]][alp];
					if(a2 > j && a2 < k)
						(ss[i][j][k] += ((ss[i-1][j][a2-1] % mod) * (ss[i-1][a2+1][k] % mod)) % mod) %= mod;
					else if(a2 == j && a2 != k)
						(ss[i][j][k] += (ss[i-1][a2+1][k] % mod)) %= mod;
					else if(a2 == k && a2 != j)
						(ss[i][j][k] += (ss[i-1][j][a2-1] % mod)) %= mod;
					else if(a2 == j && a2 == k) 
						(ss[i][j][k] += 1) %= mod;
				}
				for(int beta = j; beta < k; ++ beta)
					(ss[i][j][k] += ((ss[i-1][j][beta] % mod) * (ss[i-1][beta+1][k] % mod)) % mod) %= mod;
			}

	cout << ss[s.size()][0][t.size() - 1] % mod << endl;
	
	return 0;
}

B. 军训 II

#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
//const int N=1e5;
typedef long long ll;
const ll N = 1e6 + 10;
const ll mod = 998244353;
ll arr[N];
ll mmul(ll a,ll b)
{
	return ((a % mod) * (b % mod)) % mod;
}
ll jie(ll a)
{
	ll sum = 1;
	for(ll i = 2; i <= a; ++ i)
		(sum *= i) %= mod;
	return sum;
}
signed main()
{
	ll n;
	cin >> n;
	map<int,int> hash;
	for(int i = 0; i < n; ++ i)
	{
		scanf("%lld",&arr[i]);
		hash[arr[i]] ++;
	}
	sort(arr,arr+n);
	ll res1 = 0, res2 = 2;
	if(hash.size() == 1) res2 = 1;
	for(int i = 2; i <= n; ++ i)
		for(int j = 0; j <= n - i; ++ j)
			res1 += arr[j + i - 1] - arr[j];
			
	for(auto hi : hash)
		res2 = mmul(res2,jie(hi.second)); 
	cout << res1 << " " << (res2 % mod);
	return 0;
}

K. 取沙子游戏
博弈论

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
//const int N=1e5;
#define int long long
int gcd(int a, int b)
{
	return b ? gcd(b, a%b) : a;
}
int lcm(int a, int b)
{
	return (a * b) / gcd(a, b);
}
void solve()
{
	int n, k;
	scanf("%lld%lld",&n,&k);
	if(k >= n)
	{
		printf("Alice\n");
		return;
	}
	if(n % 2 == 1)
	{
		printf("Alice\n");
		return;
	}
	else
	{
		int t = 1;
		while(n % 2 == 0 && n)
		{
			t <<= 1;
			n >>= 1;
		}
		if(k >= t) printf("Alice\n");
		else printf("Bob\n");
	}
} 
signed main()
{
	int t;
	cin >> t;
	while(t --){
		solve();
	}
	return 0;
}