首页 > 其他分享 >ABC 326

ABC 326

时间:2024-02-08 18:55:36浏览次数:29  
标签:le leftarrow sum 机器人 ABC 326 操作

E

题意:

给定一个 \(n\) 面骰,长度 \(n\) 的数组 \(a\) 和一个初始为 \(0\) 的变量 \(x\)。

每次投掷骰子,等概率获得 \(1 \sim n\) 中的一个数 \(p\)。若 \(p\le x\),结束;否则 \(x\leftarrow p\) 且总收获 \(S\leftarrow S+a_p\)。

求期望值。

其实期望 \(S=\sum a_i\times p_i\),其中 \(p_i\) 是投掷过程中出现 \(i\) 的概率。

初值 \(p_0=1\)。\(p_i=\displaystyle\dfrac{1}{n}\sum_{j=0}^{i-1} p_j\)。

F

有一个机器人,初始在坐标原点,面向右侧。现在给定序列 \(a\),按顺序执行操作:第 \(i\) 次操作时令机器人向某侧转 \(90\degree\) 后再前进 \(a_i\) 个单位长度。

操作个数 \(n\le 80\)。

你可以任意安排每次操作前机器人是向左转还是向右转。问最后能否使机器人到达 \((X,Y)\)?判断可行,并且输出方案。

发现奇数编号的操作和偶数编号的操作可以分开考虑。原问题等价于:\(n\le 40\) 个数,可以任意改变符号,使得这些数的和为 \(X\)。

可以用 meet-in-middle。

G

经典最小割模型。

标签:le,leftarrow,sum,机器人,ABC,326,操作
From: https://www.cnblogs.com/FLY-lai/p/18012027

相关文章

  • ABC 304
    T4在一个平面上有一块面积无限的蛋糕,给出\(n\)颗草莓的所在位置和\(a\,(b)\)条平行与\(x\,(y)\)轴的切刀位置。切刀会把蛋糕沿\(x\,(y)\)轴切开。因此一共会切出\((a+1)(b+1)\)块蛋糕。问:现在蛋糕上草莓数量最少的一块蛋糕,草莓数量是多少?最多的,又是多少?用lower_bo......
  • ABC 306
    前三题过水。D\(dp[i][j]\)表示吃完前\(i\)个菜,胃的状况为\(j\)(\(0\)是健康,\(1\)是不好)所获得的最大美味值。E暴力的平衡树。用multiset也行,一个记录前\(k\)大的,一个记录除了前\(k\)大之后的所有数。每次修改看看是从哪边修改的,改完再考虑要不要更新前\(k\)大......
  • ABC 305
    题目列表前三题过水,第四题分类讨论两个端点之间的距离和所在位置是清醒或睡眠即可。E题意:一张图上有一些结点有保安,每个保安有不同的警戒度\(h_i\),定义一个结点是安全的为这个结点可以到达一个保安\(x\),且距离\(\leqx\)。问有多少个安全的结点。痛失第五题很简单的......
  • ABC 310
    E\(dp[i][j]\)表示前\(i\)个里有多少个后缀答案为\(j\)。\(if(c[i]=='0')\{\)\(dp[i][0]=1;\)\(dp[i][1]=dp[i-1][0]+dp[i-1][1];\)\(\}\)\(else\{\)\(dp[i][0]=dp[i-1][1];\)\(dp[i][1]=1+dp[i-1][0];\)\(\}\)F......
  • ABC 309
    直接从F开。F三维偏序。把盒子按\(h_i\)排序,离散化,正常跑三维偏序(注意不能相等)。还要处理\(h_i\)相等的情况,可以再把\(h_i\)从大到小排序,然后\(w_i,d_i\)都要求严格大于,如果发现有一种情况是无论\(h_i\)咋排序都可以的,就删掉这种情况。G错排问题的推广。tjtj2......
  • ABC 312
    前三题氵D给定一个由(,?,)组成的字符串。每个?可以设定为任意括号。求有几种设定方法使得整个是合法括号序列。套路,dpE给定\(n\)个两两不相交的长方体,对每个长方体,求有多少个长方体与其有公共面。有一个可以大幅度优化代码麻烦程度的小技巧:因为坐标范围很小,我们直接把......
  • ABC 311
    前四题过水E枚举正方形的上边界所在行。对于第\(i\)行一个没洞的位置\((i,j)\),我们尝试求出以它为右上角的无洞正方形个数。结论:设以\((i,j-1)\)为右上角的无洞正方形边长最大为\(len\),那以\((i,j)\)为右上角的无洞正方形边长最大为\(len+1\)。以\((i,j)\)为右上......
  • [ABC327G] Many Good Tuple Problems 题解
    Description对于一对长度均为\(M\)且元素值在\(\left[1,N\right]\)之间的序列\((S,T)\),定义其为好的当且仅当:存在一个长度为\(N\)的\(01\)序列\(X\),使得其满足如下条件:对于任意\(i\in\left[1,M\right]\),有\(X_{S_i}\neqX_{T_i}\)。给定\(N,M\),求在......
  • AT_abc270_g [ABC270G] Sequence in mod P 题解
    题目传送门前置知识大步小步算法解法递推式为\(x_{n}=(ax_{n-1}+b)\bmodp\),发现可以统一消去\(\bmodp\),只在最后参与计算。以下过程省去模运算。当\(x_{0}=t\)时,则\(n=0\)即为所求。当\(a=0,x_{0}\net\)时,递推式转化为\(x_{n}=b\bmodp\)。若\(b=t\),则......
  • AtCoder-ABC-Ex乱写
    ABC233ExManhattanChristmasTree先将\((x,y)\)变成\((x+y,x-y)\),也就是曼哈顿转切比雪夫,之后曼哈顿距离\(\lek\)的在切比雪夫坐标系下就是一个正方形。用主席树做矩形和,外层套一个二分即可,时间复杂度\(\mathcal{O}(n\log^2n)\)。ABC233Ex#include<bits/stdc++.h......