Codeforces Round #848 (Div. 2)（B,C,D）
哎呀，最近不知道怎么回事，题目老是没看懂，还是心不在此，太烦了，好几天都只是一道题了
B
这道题到看答案才发现我理解错了，我怎么说越想越复杂，我就说第二道题怎么会这么复杂
其实题目的意思是要求我们每一个都满足条件才是\(no good\),我以为是只有一个就是\(no good\),看得不仔细
现在我看完了题解，发现我的题都读错了，真离谱
这道题大意是
给你一个长度为\(n\)的排序，还有一个长度为\(m\)的数组，还有一个\(d\),我们对于这个数组是\(no good\)有以下的条件
即 对于\(1\)到\(m-1\)都需要满足\(pos(a_i)<pos(a_{i+1})<=pos(a_i)+d\)
我们要求的是要这个数组变成\(good\)，的最小移动数量
移动是什么？
移动可以改变排序\(p\)里面相邻的两个数（注意是改变\(p\)里面的数的位置，而不是\(a\)里面的数的位置）
所以我们只有一个不满足以上\(no good\)的条件，那么这个就是\(good\)的，那么我们不需要移动，所以答案就是\(0\)
如果每一个都满足\(no good\)的条件，那么我们要怎么让这一个数不满足$ no good$的条件
对于此时\(pos(a_i)<pos(a_{i+1})<=pos(a_i)+d\)，我们要让这一对不满足这个条件，有两种移动方法
第一种，让\(pos(a_i)>pos(a_{i+1})\),此时，我们需要移动的是把\(a_i\)和\(a_{i+1}\)的位置转换一下
第二种，是让\(pos(a_{i+1})>pos(a_i)+d\),我们要让这两个数的位置差大于\(d\),我们还要考虑我们可不可以存在这两个数之间的距离大于\(d\),我们知道对于长度为\(n\)的排序，两个数之间的最大差为\(n-1\),所以，要想进行第二种移动，我们要满足\(n-1>d\)
然后我们取较小的那一个移动次数
#include <iostream>
#include <string>
using namespace std;
const int maxn=1e5+10;
int t,n,d,m;
int pos[maxn],k;
int a[maxn];
void solve()
{
cin>>n>>m>>d;
for (int i=1;i<=n;i++)
{
int x;
cin>>x;
pos[x]=i;
}
int ans=1e9;
for (int i=1;i<=m;i++)
{
cin>>a[i];
}
for (int i=1;i<m;i++)
{
if (pos[a[i]]<pos[a[i+1]]&&pos[a[i+1]]<=pos[a[i]]+d)
{
int c1=pos[a[i+1]]-pos[a[i]];//交换两个位置，让pos[a[i]]>pos[a[i+1]]
int c2=1e9;
if (d<n-1)//n-1是这两个数的最远距离，n-1,只有两点距离大于d才可以满足这第二个情况，pos[a[i+1]]>pos[a[i]]+d,那么这个d只能小于n-1才可
{
c2=pos[a[i]]+d+1-pos[a[i+1]];
}
int c=min(c1,c2);
ans=min(ans,c);
}
else
{
cout<<0<<'\n';
return ;
}
}
cout<<ans<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
C
这个题大意是给你两个字符串\(a\)和\(b\),我们需要尽量的让\(l,r\)的对数尽量多
\(l,r\)需要满足\(a\)的\(l\)和\(r\)这一个区间的字符和\(b\)同样位置的字符一样的
我们可以实行任意次操作
把\(a\)的\(pos\)位置的\(x\)变成\(y\),把\(x\)加进去一个集合，我们要保证这个集合里面的字符最多有\(k\)种，也就说说对于每次改变，我们一定要改变\(k\)个位置\(pos\),但是我们要保证这\(k\)个位置的字符的种类不可以大于\(k\)种
对于这个限制，我们首先可以把所有需要改变的字符\(a_i\)不等于\(b_i\)的\(a_i\)的种类记下来,\(cnt\)记录下来
然后我们可以看到题目中那个加粗字,\(a\)和\(b\)的不同字符种类不会超过\(10\)个，那么对于这些对于我们可以取的数量\(min(cnt,k)\),我们可以用二进制的形式把状态压缩，列举每一个状态
每一个状态都代表着其中的一类字符的改变还是保留的情况
对于这一类的字符，如果需要是改变成\(b\)里面的那一个字符，那么所有需要改变的都要改变，只有这样，才可以让\(l,r\)的数量最大
那么怎么求\(l,r\)的数量
对于如果有一段长度为\(tot\)的字符和\(b\)是一样的，那么我们可以有\(tot*(tot+1)/2\)种不同的\(l,r\),这里面的不同\(l,r\),里面的\(l\)都是这一段字符的第一个字符的位置，\(r\)就是后面的\(l,l+1,l+2,...,l+tot-1\),有\(tot\)个，对于\(l\)取这一段字符的第二个位置，\(r\)取值可为\(l+1,l+2,...l+tot-1\),有\(cnt-1\)个，由此可以得出
对于不同的\(l\),有\(tot,tot-1,tot-2...1\)个，那么这个数量和我们可以用前缀和求
然后对于不同的状态，我们选取那个可以得到最大的对数的那一个状态
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define int long long
int t,n,k;
string a,b;
void solve()
{
cin>>n>>k;
cin>>a>>b;
vector<int>vis(30,0);
vector<int>code(30,0);
int cnt=0;
for (int i=0;i<n;i++)
{
vis[a[i]-'a']=1;
}
for (int i=0;i<26;i++)
{
if (vis[i])
{
code[cnt++]=i;
}
}
k=min(k,cnt);
int M=1<<cnt;
int ans=0;
for (int i=0;i<M;i++)
{
vector<bool>use(26,false);
int tot=0;
for (int j=0;j<cnt;j++)
{
if ((i>>j)&1)
{
use[code[j]]=true;
tot++;
}
}
if (tot==k)
{
string tmp=a;
for (int j=0;j<n;j++)
{
if (use[tmp[j]-'a'])
{
tmp[j]=b[j];
}
}
int tot=0;
int sum=0;
for (int j=0;j<n;j++)
{
if (tmp[j]==b[j])
{
tot++;
}
else
{
sum+=tot*(tot+1ll)/2;
tot=0;
}
if (j==n-1)
{
sum+=tot*(tot+1ll)/2;
}
}
ans=max(ans,sum);
}
}
cout<<ans<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
D
这个题大意是我们有两种\(01\)字符串，我们最后要把\(a\)字符变成\(b\)字符，对于每一个位置的，都有平等的概率可以把\(a\)里面的这一个位置的字符翻转，\(0\)变成\(1\),\(1\)变成\(0\)
问最后把\(a\)变成\(b\)的概率
我们可以定义\(f[i]\)为此时由\(i-1\)个相同的位置，变成\(i\)个相同的位置的概率
状态转移是怎么转移的
\[f[i+1]=\frac{n-i}{n}+\frac{i}{n}\times(1+f[i]+f[i+1]) \]这个是怎么来的呢
对于此时已经有\(i\)个相同的位置，
如果这一次我们直接选择那些不相同的位置进行翻转，那么已经有\(i+1\)个相同的位置
如果这一次我们选择那些相同的位置的字符翻转，那么此时相同的位置就变成了了\(i-1\)个，那么我们要把\(i-1\)变成\(i\)个，这一步的概率应该为\(f[i]\),然后再又要把此时已经有的\(i\)个相同位置变成\(i+1\)个相同位置，这一步的概率为\(f[i+1]\)
但是我们最好是把未知数放在同一边，所以我们可以在纸上进行变换
可以得到以下这个方程
\[f[i+1]=(1+\frac{i}{n-i})\times(f[i]+1) \]然后我们从原来有\(cnt\)个相同的变成\(n\)个相同的，需要在这一系列的变化的概率相加
#include <iostream>
#include <string>
using namespace std;
#define int long long
const int mod=998244353;
const int maxn=1e6+10;
int t,n;
string a,b;
int f[maxn];
int ksm(int x,int p)
{
int res=1;
while (p)
{
if (p&1)
{
res=(res*x)%mod;
}
x=(x*x)%mod;
p>>=1;
}
return res%mod;
}
int inv(int x)
{
return ksm(x,mod-2);
}
void solve()
{
cin>>n;
cin>>a>>b;
int cnt=0;
for (int i=0;i<n;i++)
{
if (a[i]==b[i])
{
cnt++;
}
}
f[1]=1;
for (int i=1;i<n;i++)
{
f[i+1]=(1+i*inv(n-i)%mod*(f[i]+1))%mod;
}
int ans=0;
for (int i=cnt+1;i<=n;i++)
{
ans=(ans+f[i])%mod;
}
ans%=mod;
cout<<ans<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}