The 2024 CCPC Online Contest （D、E、J）
IR101
·
2024-09-09 23:37:43
·
个人记录
Problem D. 编码器-解码器
思路:区间DP，f[i][l][r] 代表i-1次操作后，s中形成的t串的[l,r]这个子串的子序列的个数。转移看代码：
diamond:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int mod=998244353;
int f[105][105][105];
////F[i][l][r]代表i-1次操作后，s中形成的t串的[l,r]这个子串的子序列的个数。
///考虑怎么转移：如下
void solve(){
string s,t;
cin>>s>>t;
int n=s.size();
int m=t.size();
s=" "+s;
t=" "+t;
for (int i = 1; i <=n ; ++i) {
f[i][0][0]=1;
f[i][0][0]%=mod;
{ ///我们先不考虑加的s[i]这个字符，那么枚举t的l,r,因为串拼接了，那么新一层的个数肯定
///是先由上一层个数×2。
for (int l = 1; l <= m; ++l) {
for (int r = l; r <= m; ++r) {
f[i + 1][l][r] = f[i][l][r] * 2 % mod;
f[i + 1][l][r] %= mod;
////然后再考虑拼接的枚举拼接点j,左边是l到j，右边是j+1到r,乘起来即可。
for (int j = l; j < r; ++j) {
f[i + 1][l][r] += f[i][l][j] * f[i][j + 1][r] % mod;
f[i + 1][l][r] %= mod;
}
}
}
}
///再把s[i]放到中间后，新形成的包括s[i]的l,r的t的子串算一下
for (int j = 1; j <=m ; ++j) {
///枚举s[i]作为t的第j位
if(s[i]==t[j]){
///首先就是计算一下从l到j的方案数。
for (int l = 1; l <j ; ++l) {
f[i+1][l][j]+=f[i][l][j-1]%mod;
f[i+1][l][j]%=mod;
}
///计算一下从j到r的方案数
for (int r = j+1; r <=m ; ++r) {
f[i+1][j][r]+=f[i][j+1][r];
f[i+1][j][r]%=mod;
}
///只算s[i]本身的方案也加1
f[i+1][j][j]+=1;
f[i+1][j][j]%=mod;
///再计算一下j作为某个l到r之间的值的方案数
///就是l到j-1的方案×j+1到r的方案，注意判边界，不然容易重复
for (int l = 1; l <j ; ++l) {
for (int r = j+1; r <=m ; ++r) {
f[i+1][l][r]+=f[i][l][j-1]*f[i][j+1][r]%mod;
f[i+1][l][r]%=mod;
}
}
}
}
}
cout<<f[n+1][1][m]<<endl;
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0);
int t=1;
// cin>>t;
while(t--){
solve();
}
}Problem E. 随机过程
思路:
首先我们求出最多有多少个节点，其实字典树的叶子节点，代表了有多少个不同的字符串，那么我们枚举层数，对于第i层的节点个数，其实就是如果长度为i，有多少个不同字符串，那么一共有i位，每一位有26种，所以有26^i 种不同节点数，那么我们最多选n个，所以与n取个min即可，累加一下1到m层的所有节点即可。
然后考虑如何求解期望，同样的，对于第i层一共有26^i 种不同性质的节点，这些节点的期望是相等的，那么我们先考虑如何求解一个，其实就是考虑一下出现这个节点的概率 x 就是每一位都固定：(1/26^i) ，那么不出现的概率 y 就是y=1-x ，那么有n个位置，n个位置都不出现的概率 w 那就是y^n ，然后1-w就是当前节点出现的概率，然后再乘上节点数26^i ，就是这一层的节点数的期望，枚举1到m累加即可。
注意第一问的时候，取min，可能%998244353之后会改变 n 与26^i 的大小关系，特判一下
diamond:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int mod=998244353;
int ksm(int a,int b){
int res=1;
while(b){
if(b&1){
res=res*a%mod;
}
a=a*a%mod;
b>>=1;
}
return res;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
cin>>n>>m;
int ans=0;
// for(int i=0;i<=10;i++){
// cout<<ksm(26,i)<<endl;
// }
for(int i=0;i<=m;i++){
if(i<=5)
ans+=min(n,ksm(26,i));
else{
ans+=n;
}
ans%=mod;
}
cout<<ans<<' ';
ans=1;
int d=ksm(26,mod-2);
for(int i=1;i<=m;i++){
int a=ksm(d,i);
int p=(1-a+mod)%mod;
int b=ksm(p,n);
ans+=(1-b+mod)%mod*ksm(26,i)%mod;
ans%=mod;
}
cout<<ans<<endl;
}Problem J. 找最小
思路：对于ai和bi交换操作，可以看做将ai和bi都异或(ai异或bi)，那么首先计算出a和b数组的异或和x和y，就是选择一些z=ai异或bi ，将x和y都异或上z，使得max(x,y)最小，对于数组选择某些进行异或，可以先求出这个数组的线性基进行解决，这样就可以把长度为n的数组缩小成32位的数组，对于这个数组线性基上每一位的数字，都是极大无关的，要想使得这一位为1，必须选择他才行。那么我们可以从高位向低位贪心。
如果x和y的这一位都是0，那么这一位肯定不需要选择，continue。
如果x和y的这一位都是1，那么这一位如果有，必选，更新x，y。
如果1个0，1个1，如果你的线性基这一位有的话，那么可以选择使用和不使用两种选择，你会发现，这样两种的话，无论哪种，x和y的绝对关系已经确定了，这一位上1个1，另一个是0，那么对于这一位是1的，你后面直接全部考虑如何把他变小即可，不需要考虑另一个数字，那么后续位就确定了，枚举一下这两种选择即可。
diamond:
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define int long long
#define PII pair<int,int>
#define endl '\n'
typedef long long ll;
const int MN=31,N=1e6+3;
ll w[33],tmp[33];
bool flag;
int n;
int a[N],b[N];
void ins(ll x){
for( int i=MN;~i;i--)
if(x&(1ll<<i))
if(!w[i]){w[i]=x;return;}
else x^=w[i];
flag=true;
}
ll qmax(ll res=0){
for( int i=MN;~i;i--)
res=max(res,res^w[i]);
return res;
}
ll qmin(){
if(flag)return 0;
for( int i=0;i<=MN;i++)
if(w[i])return w[i];
}
void solve() {
cin>>n;
flag=0;
for (int i = 0; i <32 ; ++i) {
w[i]=0;
}
int res1=0;
int res2=0;
for (int i = 0; i <n ; ++i) {
cin>>a[i];
}
for (int i = 0; i <n ; ++i) {
cin>>b[i];
res1^=a[i];
res2^=b[i];
ins(a[i]^b[i]);
}
string a1=bitset<32>(res1).to_string();
string a2=bitset<32>(res2).to_string();
// cout<<a1<<endl<<a2<<endl;
// cout<<endl;
// for (int i = MN; i >=0 ; --i) {
// // cout<<w[i]<<' ';
// string a1=bitset<32>(w[i]).to_string();
// // cout<<a1<<endl;
// }
// cout<<endl;
// cout<<res1<<' '<<res2<<endl;
int ans=max(res1,res2);
for (int i = 31; i >=0 ; --i) {
if(w[i]==0)continue;
int d1 = res1 >> i & 1ll;
int d2 = res2 >> i & 1ll;
if (d1 and d2) {
if (w[i]) {
res1 ^= w[i];
res2 ^= w[i];
ans=min(ans,max({res1,res2}));
} else {
continue;
}
}
else if (d1 == 0 and d2 == 0) {
continue;
}
else if(d1){
// cout<<i<<endl;
int tm2=res2;
int tm1=res1;
tm1^=w[i];
tm2^=w[i];
for (int j = i-1; j>=0 ; --j) {
int d2=tm2>>j&1;
if(d2){
if(w[j]){
tm2^=w[j];
tm1^=w[j];
}
}
}
ans=min(ans,max(tm1,tm2));
tm2=res2;
tm1=res1;
for (int j = i-1; j>=0 ; --j) {
int d1=tm1>>j&1;
if(d1){
if(w[j]){
tm1^=w[j];
tm2^=w[j];
}
}
}
ans=min(ans,max(tm1,tm2));
break;
}
else if(d2 ){
// cout<<i<<endl;
int tm2=res2;
int tm1=res1;
for (int j = i-1; j>=0 ; --j) {
int d2=tm2>>j&1;
if(d2){
if(w[j]){
tm2^=w[j];
tm1^=w[j];
}
}
}
ans=min(ans,max(tm1,tm2));
tm2=res2;
tm1=res1;
tm1^=w[i];
tm2^=w[i];
for (int j = i-1; j>=0 ; --j) {
int d1=tm1>>j&1;
if(d1){
if(w[j]){
tm1^=w[j];
tm2^=w[j];
}
}
}
ans=min(ans,max(tm1,tm2));
break;
}
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}