Codeforces Round 1069 (Div. 2) A-E2

A. Little Fairy's Painting

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii = pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;void solve(){int n;cin>>n;set<int> st;for(int i=1;i<=n;i++){int t;cin>>t;st.insert(t);}int now=st.size();while(1){if(!st.count(now)){now++;}else{cout<<now<<endl;return;}}}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;cin>>ct;while(ct--){solve();}return 0; 
}

B. XOR Array

考虑前缀异或和数组，\(f(l,r)==0\) 等价于 \(pre[l-1]==pre[r]\)

所以给前缀和数组赋上各不相同的值，再让 \(pre[l-1]=pre[r]\)，得到符合条件的前缀和数组

反推原数组即可

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii = pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;void solve(){int n,l,r;cin>>n>>l>>r;vector<ull> a(n+1),pre(n+1);for(int i=1;i<=n;i++){pre[i]=i;}pre[r]=pre[l-1];for(int i=1;i<=n;i++){cout<<(pre[i]^pre[i-1])<<" ";}cout<<endl;}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;cin>>ct;while(ct--){solve();}return 0; 
}

C. Needle in a Haystack

如果 \(t\) 中甚至凑不出 \(s\)，则 Impossible

否则可以先从 \(t\) 中拿出来一个 \(s\) 所需要的字符，对于剩下的字符从小到大排序。

双指针 \(i,j\) 同 时从小到大遍历 \(s\) 和 \(t\)

如果当前 \(s[i]>t[j]\)，则把 \(t[j]\) 放入答案中

如果当前 \(s[i]<t[j]\)，则把 \(s[i]\) 放入答案中

如果当前 \(s[i]==t[j]\)，因为 \(s[i]\) 后面可能有更小的字符，而 \(t[j]\) 后面没有更小的字符，所以此时把 \(s[i]\) 放入答案中

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii = pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;void solve(){string s,t;cin>>s>>t;map<char,int> mp;for(auto ch:t){mp[ch]++;}for(auto ch:s){mp[ch]--;if(mp[ch]<0){cout<<"Impossible"<<endl;return;}}t.clear();for(auto [ch,cnt]:mp){for(int i=1;i<=cnt;i++){t.push_back(ch);}}sort(t.begin(),t.end());reverse(t.begin(),t.end());for(auto ch:s){while(t.size() && t.back()<ch){cout<<t.back();t.pop_back();}cout<<ch;}while(t.size()){cout<<t.back();t.pop_back();}cout<<endl;}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;cin>>ct;while(ct--){solve();}return 0; 
}

D. Wishing Cards

\(pos[v]\) 表示：第一个可以把最大值更新为 \(v\) 的位置

\(dp[i][j]\) 表示：最大值刚好更新为 \(i\),且用了 \(j\) 张卡片时,在 \(pos[i]\) 之前能获得的最大值

为什么是在 \(pos[i]\) 之前能获得的最大值？因为对于状态 \(dp[i][j]\)， \(i\) 结束的位置不确定，但 \(i\) 开始的位置是确定的

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;void solve(){int n,k;cin>>n>>k;vector<int> a(n+1),pos(k+1,inf);pos[0]=0;int mx=0;for(int i=1;i<=n;i++){cin>>a[i];// 优化掉，n*k 优化为 n+k// for(int j=0;j<=a[i];j++){//     pos[j]=min(pos[j],i);// }while(a[i]>mx){pos[++mx]=i;}}vector f(k+1,vector<int>(k+1,-1));f[0][0]=0;int ans=0;//更新最大值为i时，一定是在pos[i]处更新for(int i=1;i<=k;i++){if(pos[i]==inf) continue;for(int j=i;j<=k;j++){//枚举上一个最大值for(int x=0;x<i;x++){if(f[x][j-i]==-1 || pos[x]==inf) continue;int t=f[x][j-i]+x*(pos[i]-pos[x]);f[i][j]=max(f[i][j],t);}ans=max(ans,f[i][j]+i*(n-pos[i]+1));}}cout<<ans<<endl;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int t=1;cin>>t; while(t--){solve(); }}

E1. Beautiful Patterns (Easy Version)

问题转化题目要求“美丽值”的期望，即 \(E[(\text{回文子串数})^2]\)。

设 \(X_{i,j}\) 是一个指示变量：如果子串 \(s[i \dots j]\) 是回文串，则 \(X_{i,j} = 1\)。否则 \(X_{i,j} = 0\)。我们需要求：

\[E[(\sum X_{i,j})^2] = E[\sum_{S1} X_{S1} \cdot \sum_{S2} X_{S2}] = \sum_{S1} \sum_{S2} E[X_{S1} \cdot X_{S2}] \]

其中 \(S1, S2\) 代表任意两个子串。\(E[X_{S1} \cdot X_{S2}]\) 等价于 \(P(S1 \text{ 和 } S2 \text{ 同时是回文串})\)。2. 概率计算对于长度为 \(L\) 的单个子串，它是回文串的概率是：

\[P(L) = \frac{m^{\lceil L/2 \rceil}}{m^L} = m^{-\lfloor L/2 \rfloor} \]

对于两个子串 \(S1, S2\)，我们需要分情况讨论：

情况 A：非同心

如果两个子串中心不同，它们是回文串的事件是独立的。\(P(S1 \land S2) = P(S1) \times P(S2)\)。

情况 B：同心

如果两个子串中心相同（例如 b 和 aba），如果较长的那个是回文串，较短的那个必然也是回文串。

所以事件只取决于较长的那个子串。\(P(S1 \land S2) = P(\text{Longer One})\)。

接下来就是计算答案

第一步，可以先不考虑情况 B， \(O(n^2)\) 的枚举 \(i,j\)，计算出所有子串是回文的期望之和 \(sum\)

此时答案为 \(ans=sum*sum\)

再枚举所有的同心字符串 \(s1,s2\)，令 \(ans-=p(s1)*p(s2)\)，再加上 \(P(\text{Longer One})\)

注意，此时若 \(s1!=s2\)，则在需要进行两次上面的操作，因为在第一步的 \(ans\) 中，有两个 \(p(s1)*p(s2)\)

E2. Beautiful Patterns (Hard Version)

需要优化到 \(O(n)\)

对于第一步，可以将枚举 \(i,j\) 改为枚举长度，对于某个长度 \(len\)，可以 \(O(1)\) 的计算出所有长度是 \(len\) 的期望之和

对于第二步，可以还是枚举大串的长度，然后再枚举小串的长度，实现后发现枚举小串的长度可以使用前缀和优化

点击查看代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
using ll=long long; 
using pii=pair<int,int>;
const ll inf = 1e18;
int mod;int qmi(int a,int b,int p){int res=1;while(b){if(b&1) res=res*a%p;b>>=1;a=a*a%p;}return res;
}void solve(){int n,m;cin>>n>>m>>mod;int sum=0,inv=qmi(m,mod-2,mod);vector<int> fact(n+1);fact[0]=1;for(int i=1;i<=n;i++){fact[i]=inv*fact[i-1]%mod;}vector<int> prefact(n+1);prefact[1]=fact[1];for(int i=2;i<=n;i++){prefact[i]=fact[i]+prefact[i-1];prefact[i]%=mod;}//此时 sum 是所有子串的 x 期望之和for(int len=1;len<=n;len++){sum+=(n-len+1)*fact[len/2];sum%=mod;}sum*=sum;sum%=mod;//对于同心字符串，概率只取决与大的串for(int len=1;len<=n;len++){int now=len,cnt=n-len+1;//处理两个串相同的情况//前缀和优化到 O(n)sum-=fact[now/2]*fact[now/2]%mod*cnt%mod;sum+=fact[now/2]*cnt%mod;sum=(sum%mod+mod)%mod;now-=2;if(now>0){sum-=prefact[now/2]*fact[len/2]%mod*cnt*2%mod;sum+=fact[len/2]*cnt*2%mod*(now/2)%mod;sum=(sum%mod+mod)%mod;}// n^2 的去除所有同心串的错误贡献，同时加上正确贡献//错误贡献: p1 * p2, 正确贡献: p2 (plen)// for(int j=now;j>0;j-=2){//     sum-=(fact[j/2]*fact[len/2]%mod)*cnt*(1+(len!=j));//     sum+=fact[len/2]*cnt*(1+(len!=j))%mod;//     sum=(sum%mod+mod)%mod;// }}cout<<sum<<endl;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;cin>>ct;while(ct--) solve();return 0;
}