A.Flip Flop Sum
算法本质
模拟
题目大意
给定一个由1 -1组成的数组a[]，现在必须选择相邻的两个元素取反。
求操作后a[]元素和的最大值。
思路推演
模拟
B.The Forbidden Permutation
算法本质
模拟
题目大意
给定长度为n的排列p[]，长度为m的数组a[]，整数d。
设pos[]，p[i]=val --> pos[val]=i。
a[]称作不好满足以下条件：
- 对于任意
i：pos[ai] < pos[a(i+1)] <= pos[ai]+d
现在可以对p[]进行操作：
- 交换2个相邻元素位置
求最少需要多少次操作使得a[]变好。
思路推演
分析题面，不好的条件很苛刻，只需要找到其中一组i i+1，破坏左边或者右边一个条件即可。
两种情况都可以O(1)计算，然后整体O(n)。
C.Flexible String
算法本质
模拟
题目大意
长度为n的a b字符串，a由至多有10个字符组成，现在可以至多对a选择k个字符，对这些字符可以任意改变为另一字符。
操作后，a b的[l r]区间一致，最大化r-l+1，输出最大值。
思路推演
暴力模拟即可。
D.Flexible String Revisit
算法本质
概率dp、数学
思路推演
概率dp，两种设计方式：
f[x]表示当前还有x个字符未对齐，达到还有0个字符没有对齐的期望次数。
dp[x]表示当前还有x个字符未对齐，达到还有x-1个字符没有对齐的期望次数。
f[x] = 1 + (x/n)*f[x+1] + (1-x/n)*f[x-1] //当前成本 + 成功概率*成功后的期望 + 失败概率*失败后的期望
dp[x] = 1 + (dp[x+1]+dp[x])*(1-x/n) //当前成本 + 失败概率*失败后的期望动脑一想，我们选择dp[]来做，然后就很轻易的做出来了——ac核心代码-1。
当然如果是用f[]来做也不要紧，因为已经f[0]=0，所以我们对公式进行改动：f[i] = n/(n-i+1) * (f[i-1] - 1 - (i-1)/n*f[i-2])。
这说明所有f[i]都可以用f[0] f[1]来表示，其中f[0]=0已知，设f[1]=x，因为公式都是线性的，所以所有的f[i]都可以用ax+b表示。
在边缘n可以得到一个式子：f[n] = 1+f[n-1]，用将表示出来的f[n] f[n-1]带入上式，可以解出f[1]的值————ac核心代码-2。
ac核心代码-1
头文件、宏定义、快读模板、常见变量、常见变量等略。
int dp[maxn];
string a, b;
inline void solve()
{
//init
cin>>n;
cin>>a>>b;
a=" "+a;
b=" "+b;
int cnt=0;
for (int i=1; i<=n; i++)
cnt += a[i]!=b[i];
//cal dp[x]表示当前有x个不同的，如果要提升到有x-1个不同所期望的次数
dp[n] = 1;
ans=0;
for (int i=n-1; i>0; i--)
{
dp[i] = n*qpow(i,mod-2,mod)%mod + (n-i)*qpow(i,mod-2,mod)%mod*dp[i+1]%mod;
dp[i] %= mod;
}
for (int i=1; i<=cnt; i++)
ans += dp[i];
ans %= mod;
cout<<ans<<endl;
return;
}ac核心代码-2
头文件、宏定义、快读模板、常见变量、常见变量等略。
string a, b;
int x[maxn], val[maxn], inv[maxn];
inline void solve()
{
//init
cin>>n;
cin>>a>>b;
a=" "+a;
b=" "+b;
//cal
int cnt=0;
for (int i=1; i<=n; i++)
cnt += a[i]!=b[i];
//f(x)表示当前还有x个不同位置，达到完全相同的位置的期望数
x[0]=val[0]=val[1]=0;
x[1]=1;
for (int i=2; i<=n; i++)
{
inv[n] = qpow(n, mod-2, mod);
inv[n-i+1] = qpow(n-i+1, mod-2, mod);
x[i] = n*inv[n-i+1]%mod * (x[i-1] - (i-1)*inv[n]%mod*x[i-2]%mod)%mod;
x[i] = (x[i]%mod+mod)%mod;
val[i] = n*inv[n-i+1]%mod * (val[i-1] - 1 - (i-1)*inv[n]%mod*val[i-2]%mod)%mod;
val[i] = (val[i]%mod+mod)%mod;
}
int num_x = (x[n]-x[n-1]+mod)%mod;
int num_val = (1+val[n-1]-val[n]+mod)%mod;
int val_x = num_val/num_x;
ans = x[cnt]*val_x + val[cnt];
ans %= mod;
cout<<ans<<endl;
return;
}
评论 (0)