网站及app开发招聘,wordpress 局域网,河南海华工程建设监理公司网站,旅游网站 功能建造城市 题解 先思考一个简单问题 10个$toot$ 放进5间房屋#xff0c;每个房屋至少有1个$toot$#xff0c;方案数 思考#xff1a;插板法#xff0c;$10$个$toot$有$9$个缝隙#xff0c;$5$间房屋转化为$4$个挡板#xff0c;放在toot缝隙之间得到$C_{9}^{4}$ 10个$toot$… 建造城市 题解 先思考一个简单问题 10个$toot$ 放进5间房屋每个房屋至少有1个$toot$方案数 思考插板法$10$个$toot$有$9$个缝隙$5$间房屋转化为$4$个挡板放在toot缝隙之间得到$C_{9}^{4}$ 10个$toot$ 放进$5$间房屋每个房屋里可以没有$toot$方案数 思考插板法使用条件必须是每组至少有1个那么我们事先在每个房屋中放一个$toot$变成$15$个$toot$放进$5$个房屋可以插板法与上一题类似$C_{14}^{4}$ 那么应用到这个题上呢 这个题$toot$加了一个上界非常棒对不对我们可以考虑容斥 怎么算$\sum\limits_{i0}^{in} {-1}^i *C_{n}^{i}*C_{m-i*k-1}^{n-1}$ 前面是枚举的多的城市后面枚举的是多的怎么理解呢 首先我们让$i$个城市提前选出$i*k$ 个 $toot$假设我们当前是$i0$那么我们选出的包含0个不符合情况的1个不符合情况的2个不符合情况的3个不符合情况的------n个 我们只需要简单容斥一下就完了 代码 #includebits/stdc.h
using namespace std;
#define ll long long
#define A 10101010
#define mod 998244353
ll ni[A],jie[A];
ll n,m,k;
ll meng(ll x,ll k){ll ans1;for(;k;k1,xx*x%mod)if(k1)ansans*x%mod;return ans;
}
ll C(ll n,ll m){return jie[n]*ni[n-m]%mod*ni[m]%mod;
}
int main(){jie[0]1;for(ll i1;i10000000;i)jie[i]jie[i-1]*i%mod;ni[10000000]meng(jie[10000000],mod-2);for(ll i9999999;i1;i--)ni[i]ni[i1]*(i1)%mod;ni[0]1;
/* while(1){ll a,b;scanf(%lld%lld,a,b);coutC(a,b)endl;}
*/ scanf(%lld%lld%lld,n,m,k);ll ans0,tmp1;for(ll i0;in;i){if(n-1m-i*k-1) break;ans(anstmp*C(n,i)*C(m-i*k-1,n-1)%mod)%mod;tmp-tmp;}cout(ansmod)%modendl;
} 轰炸 语文不好被坑了 一句话题解 tarjan缩点最长链 代码不放了 石头剪刀布 很奇妙的思路但觉的现在还是似懂非懂的。 首先这个题是先计算所有概率最后再统计贡献 和以往做的期望题不太一样 这个题没有顺序很恶心思考换一种方法避免无序带来影响 我们发现如果只开三维最后根本无法统计答案统计起来会像一坨 尝试开四维 $f[i][j][k][4]$ $f[i][j][k][1]$表示已经有$i$个人出石头$j$个人出剪刀$k$个人出布下一轮出石头 $f[i][j][k][2]$表示已经有$i$个人出石头$j$个人出剪刀$k$个人出布下一轮出剪刀 $f[i][j][k][3]$表示已经有$i$个人出石头$j$个人出剪刀$k$个人出布下一轮出布 这样答案转移起来就很好转移了 $ans\sum\limits _{i1}^{in} max(f[i][j][k][1]f[i][j][k][2]*3,f[i][j][k][2]f[i][j][k][3]*3,f[i][j][k][3]f[i][j][k][1]*3)$ 思考状态转移 直接转移肯定难以转移开辅助数组$g[i][j][k]$表示出$i$个石头$j$个剪刀$k$个布的概率 显然我们可以得到 $f[i][j][k][u]f[i-1][j][k][u]*x[o][1]f[i][j-1][k][u]*x[o][2]f[i][j][k-1][u]*x[o][3](x[o][1]x[o][2]x[o][3])*g[i][j][k]$ 思考这是什么意思 拿1举例你当前状态已经这样你又往里面放了一个人他出了石头那么当前概率就等于之前的概率*转移过来的概率 下面是迪哥解释 //当u0时就不太一样了计算的是接下来出1的概率 //它由上一轮对方出1的概率乘对方真的出了1的概率累加而来此时ijks //因为你把这玩意当成一个背包不断往里面放对手来更新其概率 //意思大概就是“目前的状态已经是那样了而且下一轮你遇到了s”然后s对你的概率产生的贡献 //所以就是你走到原状态的概率乘上s出1的概率就是s对目前状态的概率贡献 //所以ijks时不能枚举到3,因为相当于你的原状态里面已经有s个人了可是你现在刚刚开始考虑第s个人啊 细节 你最后统计答案时不能枚举到n因为n没有下一个人了 吴迪带注释代码 #includebits/stdc.h
using namespace std;
//首先题意可能还有人理解错了。题目的意思是你要根据对手分别出了几个石头几个剪刀来决策
//而并不是一场战斗结束后你就能知道对方具体是谁从而直接推断剩下的人
#define d(x,k) for(int xk;x0;--x)//压行字少
int n;double x[51][4],f[51][51][51][4],ans,c[51][51];
//f数组的含义当最后一维为13时表示第ijk1个人在前面的人出了i个1,j个2k个3的情况下出13的概率
//当最后一维为0时表示前ijk个人出了i个1,j个2k个3的概率即那个题解里的g数组
int main(){ scanf(%d,n); f[0][0][0][0]1;//初始化for(int i1;in;i) scanf(%lf%lf%lf,x[i][1],x[i][3],x[i][2]),x[i][1]/300,x[i][2]/300,x[i][3]/300;//读入概率注意顺序是132。把石头剪刀步分别抽象为123,故1胜2,2胜3,3胜1for(int i0;i50;i) c[i][0]1;for(int i1;i50;i) for(int j1;ji;j) c[i][j]c[i-1][j-1]c[i-1][j];//杨辉三角。注意要用到50级别的而没有取模所以要开long long或doublefor(int s1;sn;s) d(i,s) d(j,s-i) d(k,s-i-j) d(u,(ijks?0:3)){//有点像个背包//你可以把s单独再开一维的数组来表示目前考虑到第几个人更好理解但貌似会炸内存//u为13时分别枚举第几个人前面的人出过几个1,2,3这个人要出u//注意u的枚举是当ijks时才更新对方下一次出123的概率否则只更新到达某状态的概率//u为0时计算到达这个状态的总概率即题解中的g数组if(i)f[i][j][k][u]f[i-1][j][k][u]*x[s][1];//这个人s出了1,累加概率//当u0时,f[i][j][k][0]由f[i-1][j][k][0]转移而来u0并不考虑下一个人会出什么//在原状态出一个1即为新状态后者的概率为x[s][1]。计算g数组就不必考虑其他f值的影响//因为根据含义就有f[i][j][k][0]f[i][j][k][1]f[i][j][k][2]f[i][j][k][3]//当u0时就不太一样了计算的是接下来出1的概率//它由上一轮对方出1的概率乘对方真的出了1的概率累加而来此时ijks//因为你把这玩意当成一个背包不断往里面放对手来更新其概率//意思大概就是“目前的状态已经是那样了而且下一轮你遇到了s”然后s对你的概率产生的贡献//所以就是你走到原状态的概率乘上s出1的概率就是s对目前状态的概率贡献//所以ijks时不能枚举到3,因为相当于你的原状态里面已经有s个人了可是你现在刚刚开始考虑第s个人啊if(j)f[i][j][k][u]f[i][j-1][k][u]*x[s][2];//出2同上if(k)f[i][j][k][u]f[i][j][k-1][u]*x[s][3];//出3同if(u)f[i][j][k][u]f[i][j][k][0]*x[s][u];//这个就是弥补了上面的缺陷。本层转移。不管目前的状态是什么反正第s个人就是出u了//与上面的并不重复。一个是在说s对以前的状态的贡献这个是在说s对当前状态的贡献}d(i,n-1) d(j,n-1-i) d(k,n-i-j-1)//ijk不要枚举到n因为已经进行过n轮后下一次再出什么已经不重要不记分了ansmax(max(f[i][j][k][1]3*f[i][j][k][2],f[i][j][k][2]3*f[i][j][k][3]),f[i][j][k][3]3*f[i][j][k][1])/c[n][ijk]/(n-i-j-k);//在每一种状态下即确定对手已经出了i个1,j个2,k个3时你都有唯一确定的最优决策来进行下一轮//每一次决策时都会累加分数3种决策分别对应出1,2,3.f[i][j][k][1]即为与1打平3*f[i][j][k][2]即为战胜2//你所说的最优决策就是根据已有信息每个对手出了什么通过猜测对手下一步会出什么来权衡3中决策//至于为什么用到了组合数因为你所算的概率只是到达这一步的概率但是你是从n个人里随便选出了c[n][ijk]个人//然而其实在同一场游戏中对于同样的ijk你只会选1次,在计算的时候你把概率累加在一起了现在要求一个平均值//再除一个(n-i-j-k)的原因也差不多因为你是要从剩下的(n-i-j-k)个人里选出一个去挑战//这一步的概率是1/(n-i-j-k)然而你在上面5层循环的时候并没有考虑所以在这里统一除去printf(%.12lf\n,ans);//给的std里是用%.12f输出double的真是惊奇
}//把注释全删掉你就会发现这个代码只有21行811B View Code 我这个菜鸡的代码 #includebits/stdc.h
using namespace std;
#define A 52
#define ll long long
double f[A][A][A][5],x[A][5];
double ans0;
ll C[A][A],n;
int main(){f[0][0][0][0]1;scanf(%lld,n);for(ll i0;in;i)C[i][0]1;for(ll i1;in;i)for(ll j1;ji;j)C[i][j]C[i-1][j]C[i-1][j-1];for(ll i1;in;i)scanf(%lf%lf%lf,x[i][1],x[i][3],x[i][2]),x[i][1]/300,x[i][3]/300,x[i][2]/300;for(ll o1;on;o){for(ll io;i0;i--){for(ll jo-i;j0;j--){for(ll ko-i-j;k0;k--){for(ll u(((ijk)o)?0:3);u0;u--){if(i)f[i][j][k][u]f[i-1][j][k][u]*x[o][1];if(j)f[i][j][k][u]f[i][j-1][k][u]*x[o][2];if(k)f[i][j][k][u]f[i][j][k-1][u]*x[o][3];if(u)f[i][j][k][u]f[i][j][k][0]*x[o][u];}}}}}for(ll in-1;i0;i--)for(ll jn-1-i;j0;j--)for(ll kn-1-i-j;k0;k--){ansmax(max(f[i][j][k][1]f[i][j][k][2]*3,f[i][j][k][2]f[i][j][k][3]*3),f[i][j][k][3]f[i][j][k][1]*3)/C[n][ijk]/(n-i-k-j);}printf(%.12lf\n,ans);
} View Code 转载于:https://www.cnblogs.com/znsbc-13/p/11327441.html
