AtCoder Beginner Contest 300(E,F)
E (概率dp)
这个题意大致就是一开始有一个初始数\(x\)为\(1\),然后我们有一个骰子，最后得到的点数概率一样，为\(\frac{1}{6}\),如果这一次得到的点数为\(i\),那么\(x\)会变成\(i\times x\),问最后得到数\(n\)的概率为多少
先感性的分析一波，对于这六个数，除了\(1\)之外都可以改变\(x\),那么我们可以不用考虑\(1\)得到的效果，毕竟不管得没得到\(1\)效果都是一样的，那么我们每一次投中的概率就是\(\frac{1}{5}\)
下面我给出证明
假设\(dp[i]\)是得到的数为\(i\)的概率，那么我们可以得到
\[dp[i]=\frac{1}{6}dp[i]+\sum_{j=1}^n\frac{1}{6}dp[\frac{i}{j}] \]我把\(1\)和后面的数分开了
然后可以移项，把\(dp[i]\)放在一边，毕竟这个才是我们需要的
\[\frac{5}{6}dp[i]=\sum_{j=1}^n\frac{1}{6}dp[\frac{i}{j}] \]然后把\(dp[i]\)的系数变成\(1\)，这样好看一点
\[dp[i]=\sum_{j=1}^n\frac{1}{5}dp[\frac{i}{j}] \]这样，对于后面的非\(1\)数，得到的概率可以看成\(\frac{1}{5}\)了
然后我看到一个很好的解法，很易懂，大佬博客
他是从\(1\)逐渐往后面找，每得到一个新的点，都会乘上这个概率，（然后还用上了记忆化）
只有找到了\(n\)才是正确的
幸好这些数都就算是最小的\(2\)最多也只有\(64\)多次，而且，每次找都不会往回找，而是一直找，而且不会进入死循环，但是这个想法真的好好，有点像\(dfs\)在不断的往前找，走了一步就加一的感觉，我自己最初的想法是把那个\(n\)分解成若干个\(2,3,5\)，但是这个也不太好些，因为还有\(4,6\)的情况，还不止，还要考虑顺序，感觉有点复杂
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long
#define LL long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=1e6+10;
const int mod=998244353;
int p;
int n;
unordered_map<int,int>f;
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);
}
int getf(int x)
{
if(x>n) return 0;
if(x==n) return 1;
if(f.count(x))return f[x];
int res=0;
for (int i=2;i<=6;i++)
{
res=(res+getf(i*x))%mod;
}
res=res*p%mod;
f[x]=res;
return f[x];
}
signed main ()
{
cin>>n;
p=inv(5);
int ans=getf(1);
cout<<ans<<"\n";
system ("pause");
return 0;
}
F (二分)
这个题的大意是给你一个长度为\(n\)的只由\(x,o\)两个字符组成的字符串\(s\)，我们可以得到一个\(T\)字符串，\(T=m\times s\),我们可以从这个\(T\)里面，选出\(k\)个\(x\)变成\(o\),问最后我们可以得到最大的连续\(o\)的长度，而且，这道题还提醒了我们\(T\)里面的\(x\)的数量一定是够的（所以不存在没有足够\(k\))
这个呢
我们可以先从第一个\(s\)看，对于\(l,r\)这一段，要把这一段都变成\(o\)的代价就是这一段里面\(x\)的数量，所以，我们可以预先把\(x\)的前缀数量记录下来
对于一个最长的\(o\)串，一定是有最左端点一定在第一个字符串上面，（这是最优的，后面的和它都是一样的，而且越前面越代表答案可能越大）
我们枚举最左端点
然后对于第一个字符串，找到一个有最右端点\(sum[r]-sum[l]\)小于等于\(k\)，那么此时我们就已经获得了\(r-l+1\)的\(o\)了，如果我们要继续往后找第二个字符串的话，只有\(r\)等于\(n\)时才可以（不然不就是连最后一个都到不了，根本不需要考虑后面的）
对于往后找，我们先看了剩余的操作次数可不可以把字符串全部都变成\(o\),这样把可以全部变成\(o\)的考虑
如果还有剩余，我们就去考虑，剩下的最远可以到哪一个位置
我之前一直在担心会不会操作不够，其实完全不用担心，如果我们对于这一次的最左端需要的操作数还不够，我们可以用到那些和这些没有关系的\(x\)上（毕竟题目已经告诉你了\(x\)的数量一定大于等于\(k\),我之前就是考虑到这儿，每次都判断一下是不是等于\(k\)，结果\(wa\)了
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long
#define LL long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=3e5+10;
const int mod=998244353;
int m,k,n;
string s;
int sum[maxn];
int find(int x,int last,int l,int r)
{
int ans=-1;
while (l<=r)
{
int mid=(l+r)>>1;
int now=sum[mid]-last;
if(now<=x)
{
ans=mid;
l=mid+1;
}
else r=mid-1;
}
return ans;
}
signed main ()
{
cin>>n>>m>>k;
cin>>s;
s=" "+s;
for (int i=1;i<=n;i++)
{
int val=0;
if(s[i]=='x') val=1;
sum[i]=sum[i-1]+val;
}
int ans=0;
for (int i=1;i<=n;i++)
{
int l=find(k,sum[i-1],i,n);
if(l==-1) continue;
int val=(l-i+1);
int cnt=sum[l]-sum[i-1];
if(l<n)
{
ans=max(ans,val);
}
else if(l==n)
{
int cha=(k-cnt)/sum[n];
val+=min(cha,m-1ll)*n;
if(cha<m-1ll)
{
int res=(k-cnt)-cha*sum[n];
int pp=find(res,0,1,n);
if(pp!=-1)
{
val+=pp;
}
}
ans=max(ans,val);
}
}
cout<<ans<<"\n";
system ("pause");
return 0;
}