2024 CCPC网络预选赛

标签：int ll CCPC 2024 ss a2 预选赛 dp mod

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}^{'}\)

1. 考虑前后 \(S_{i-1}^{'}\) 包含的子序列：

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

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 \]

3. 考虑 \(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;
} 

---

L. 网络预选赛
签到题，暴力即可

标签：int,ll,CCPC,2024,ss,a2,预选赛,dp,mod
From： https://www.cnblogs.com/Frodnx/p/18412720