如何快速做一个网站商标logo设计生成器免费

如何快速做一个网站,商标logo设计生成器免费,南昌做网站开发的公司有哪些,做微信公众号的网站题目描述 Alice\texttt{Alice}Alice 和 Bob\texttt{Bob}Bob 设计了一个双人猜数游戏。游戏开始前#xff0c;他们约定两个正整数#xff1a;范围 NNN 和 允许的失误次数上限 SSS。Alice\texttt{Alice}Alice 秘密选择一个整数 XXX#xff08;0≤XN0 \le X N0≤X…题目描述Alice \texttt{Alice}Alice和Bob \texttt{Bob}Bob设计了一个双人猜数游戏。游戏开始前他们约定两个正整数范围N NN和允许的失误次数上限S SS。Alice \texttt{Alice}Alice秘密选择一个整数X XX0 ≤ X N 0 \le X N0≤XN然后Bob \texttt{Bob}Bob轮流猜测整数。对于Bob \texttt{Bob}Bob的每次猜测Alice \texttt{Alice}Alice会给出以下三种回应之一strike \texttt{strike}strike如果猜测的数字大于X XXsmile \texttt{smile}smile如果猜测的数字小于X XXstop \texttt{stop}stop如果猜测的数字等于X XX此时游戏结束Bob \texttt{Bob}Bob获胜。如果Bob \texttt{Bob}Bob累计收到S SS次strike \texttt{strike}strike则游戏结束Alice \texttt{Alice}Alice获胜。Bob \texttt{Bob}Bob希望在正式比赛前进行训练。他需要知道对于给定的N NN和S SS在最坏情况下他需要多少次猜测才能确保猜中Alice \texttt{Alice}Alice选择的任意数字X XX并且在此过程中他最多收到S − 1 S-1S−1次strike \texttt{strike}strike否则他会输掉游戏。输入格式第一行包含一个整数C CC表示测试用例的数量。接下来C CC行每行包含两个整数N NN和S SS分别表示数字范围和允许的strike \texttt{strike}strike次数上限。保证1 ≤ N ≤ 1000 1 \le N \le 10001≤N≤10001 ≤ S ≤ 20 1 \le S \le 201≤S≤20。输出格式对于每个测试用例输出一行一个整数表示Bob \texttt{Bob}Bob在最坏情况下所需的最少猜测次数。题目分析这是一个典型的最坏情况下的最优策略问题类似于带有限制的二分搜索。我们可以从以下几个关键点理解题目游戏目标Bob \texttt{Bob}Bob需要保证无论Alice \texttt{Alice}Alice选择哪个数字X XX他都能在收到少于S SS次strike \texttt{strike}strike的情况下猜中。策略限制每次猜测如果得到strike \texttt{strike}strike会消耗一次“允许的失误机会”如果得到smile \texttt{smile}smile则不消耗。最坏情况我们需要考虑在所有可能的X XX下Bob \texttt{Bob}Bob所需猜测次数的最大值并最小化这个最大值。解题思路1. 问题建模设d p [ n ] [ s ] dp[n][s]dp[n][s]表示当数字范围为[ 0 , n − 1 ] [0, n-1][0,n−1]即共有n nn个可能的数字且Bob \texttt{Bob}Bob最多还能承受s ss次strike \texttt{strike}strike时在最坏情况下需要的最少猜测次数。初始条件如果没有数字需要猜n 0 n 0n0则不需要猜测d p [ 0 ] [ s ] 0 dp[0][s] 0dp[0][s]0。如果不能承受任何strike \texttt{strike}strikes 0 s 0s0那么Bob \texttt{Bob}Bob只能从最小的数字开始逐个猜测最坏情况需要猜n nn次当X n − 1 X n-1Xn−1时d p [ n ] [ 0 ] n dp[n][0] ndp[n][0]n。状态转移假设当前范围大小为n nn我们选择猜测位置k kk0 ≤ k n 0 \le k n0≤kn。猜测后有三种可能猜中游戏结束本次猜测计数为1 11。得到strike \texttt{strike}strike猜大了说明X k X kXk剩余范围大小为k kk剩余可承受strike \texttt{strike}strike次数为s − 1 s-1s−1后续需要的最少猜测次数为d p [ k ] [ s − 1 ] dp[k][s-1]dp[k][s−1]。得到smile \texttt{smile}smile猜小了说明X k X kXk剩余范围大小为n − k − 1 n-k-1n−k−1剩余可承受strike \texttt{strike}strike次数仍为s ss后续需要的最少猜测次数为d p [ n − k − 1 ] [ s ] dp[n-k-1][s]dp[n−k−1][s]。由于我们要保证最坏情况所以对于固定的k kk需要的猜测次数为guesses ( k ) 1 max ⁡ ( d p [ k ] [ s − 1 ] , d p [ n − k − 1 ] [ s ] ) \texttt{guesses}(k) 1 \max(dp[k][s-1],\ dp[n-k-1][s])guesses(k)1max(dp[k][s−1],dp[n−k−1][s])其中1 11表示当前这次猜测。为了最小化最坏情况我们选择最优的k kkd p [ n ] [ s ] min ⁡ k 0 n − 1 ( 1 max ⁡ ( d p [ k ] [ s − 1 ] , d p [ n − k − 1 ] [ s ] ) ) dp[n][s] \min_{k0}^{n-1} \left(1 \max(dp[k][s-1],\ dp[n-k-1][s])\right)dp[n][s]k0minn−1​(1max(dp[k][s−1],dp[n−k−1][s]))2. 算法实现由于N ≤ 1000 N \le 1000N≤1000S ≤ 20 S \le 20S≤20我们可以使用动态规划预先计算所有可能的d p [ n ] [ s ] dp[n][s]dp[n][s]值。对于每个测试用例直接查表输出结果即可。时间复杂度O ( N 2 ⋅ S ) O(N^2 \cdot S)O(N2⋅S)对于给定范围是可接受的。空间复杂度O ( N ⋅ S ) O(N \cdot S)O(N⋅S)。3. 注意事项题目中给出的S SS是Alice \texttt{Alice}Alice获胜所需的strike \texttt{strike}strike次数因此Bob \texttt{Bob}Bob最多能承受S − 1 S-1S−1次strike \texttt{strike}strike。我们在计算时实际使用的s S − 1 s S-1sS−1。当S 1 S 1S1时Bob \texttt{Bob}Bob不能承受任何strike \texttt{strike}strikes 0 s0s0此时只能顺序猜测需要N NN次。代码实现#includebits/stdc.husingnamespacestd;constintMAX_N1005;constintMAX_S25;constintINF0x3f3f3f3f;intdp[MAX_N][MAX_S];// 预处理所有 dp[n][s] 的值voidprecompute(){// 初始化没有数字需要猜的情况for(ints0;sMAX_S;s)dp[0][s]0;// 初始化不能承受任何 strike 的情况for(intn1;nMAX_N;n)dp[n][0]n;// 动态规划递推for(intn1;nMAX_N;n){for(ints1;sMAX_S;s){intbestINF;// 尝试所有可能的猜测位置 kfor(intk0;kn;k){intstrikePartdp[k][s-1];// 猜大后的情况intsmilePartdp[n-k-1][s];// 猜小后的情况intworst1max(strikePart,smilePart);if(worstbest)bestworst;}dp[n][s]best;}}}intmain(){precompute();// 预先计算intc,n,S;cinc;while(c--){cinnS;intsS-1;// Bob 最多能承受的 strike 次数if(s0)s0;// 安全处理边界coutdp[n][s]endl;}return0;}样例解析样例输入2 3 2 4 1样例输出2 4解释N 3 , S 2 N3,\ S2N3,S2Bob \texttt{Bob}Bob最多能承受1 11次strike \texttt{strike}strike。最优策略是先猜1 11若得strike \texttt{strike}strike则X 0 X0X0下一轮猜0 00共2 22次。若得smile \texttt{smile}smile则X 2 X2X2下一轮猜2 22共2 22次。若猜中则只需1 11次。最坏情况为2 22次。N 4 , S 1 N4,\ S1N4,S1Bob \texttt{Bob}Bob不能承受任何strike \texttt{strike}strikes 0 s0s0。只能从0 00开始顺序猜测最坏情况X 3 X3X3需要猜0 , 1 , 2 , 3 0,1,2,30,1,2,3共4 44次。总结本题通过动态规划巧妙地处理了带有strike \texttt{strike}strike限制的猜数策略问题。关键在于定义状态d p [ n ] [ s ] dp[n][s]dp[n][s]并找到正确的状态转移方程即每次猜测后根据反馈strike \texttt{strike}strike或smile \texttt{smile}smile进入不同的子问题。预处理所有状态后即可快速回答每个测试用例。该算法在给定数据范围内效率良好是解决此类“最坏情况最优策略”问题的典型方法。