首页 > 其他分享 >AtCoder Beginner Contest 266 一句话题解

AtCoder Beginner Contest 266 一句话题解

时间:2022-08-30 13:58:09浏览次数:104  
标签:AtCoder 期望 Beginner Contest 266 dp

A and B

sbt,不讲。

C

垃圾计算几何,问是不是一个凸包,搞份板子交就可以了。

D

简单 dp,令 \(f(i,j)\) 表示第 \(i\) 个时间在第 \(j\) 个位置的最大价值,从上一个时间转移,可以向左,向右或者不动,即:

\[f(i,j)=\max(f(i-1,j-1),f(i-1,j),f(i-1,j+1))+s(i,j) \]

\(s(i,j)\) 就是读入,注意其中有一些限制。
Code

E

期望 dp,\(f_i\) 表示第 \(i\) 轮的期望,可以枚举这一次掷到的值,如果小于上一次的期望,那就不如不掷,否则就掷。

for(int i=1;i<=n;i++)
{
	for(int j=1;j<=6;j++)
	{
		if(j>f[i-1])f[i]+=j;
		else f[i]+=f[i-1];
	}
	f[i]/=6;
}

F

给你一棵基环树,多次询问两点之间是否有唯一路径。
先找到这个环,对于环上的每一点,都有一棵对应的子树,对其分别染色,如果颜色不同,则必定有两条路径。

标签:AtCoder,期望,Beginner,Contest,266,dp
From: https://www.cnblogs.com/LAK666/p/16639011.html

相关文章

  • AtCoder Beginner Contest 266
    比赛链接:https://atcoder.jp/contests/abc266C-ConvexQuadrilateral题意:平面图上有一个四边形,按照逆时针顺序给定四个点的坐标,判断四边形是不是凸的。思路:求两条......
  • AtCoder Beginner Contest 179
    https://atcoder.jp/contests/abc179我的AC代码https://atcoder.jp/contests/abc179/submissions/me?f.Task=&f.LanguageName=&f.Status=AC&f.User=HinanawiTenshi这......
  • AtCoder Beginner Contest 265(D-E)
    D-IrohaandHaiku(NewABCEdition)题意:找一个最少含有三个点的区间,将区间分成三块,三块的和分别为p,q,r,问是否存在这样的区间题解:先预处理一遍前缀和,和每一个前缀......
  • The 2021 Shanghai Collegiate Programming Contest D. Zztrans 的班级合照
    计数dp好题用组合数想了一下,需要容斥,情况太复杂用计数dp,\(dp[i][j]\)表示前\(i\)个人有\(j\)个在第一排,并且按照身高遍历i,这样满足了第一个偏序关系(“排成人数相同的两排......
  • [Atcoder]ABC266题解
    C-ConvexQuadrilateral计算几何给定平面内四个点,要求判断它们组成的四边形是否是凸四边形法一:凸四边形的两条对角线将其分成两个三角形分成的两个三角形面积相加......
  • Educational DP Contest G - Longest Path
    目录题目思路代码题目给定一个有向无环图,叫你求图中的最长路径思路记忆化搜索,定义f[i]:表示从点i开始的最长路径长度,那么很容易得出转移方程为\(f_i=max(f_i,f_......
  • 【Virt.Contest】CF1155(div.2)
    CF传送门T1:ReverseaSubstring只有本身单调不减的字符串不能转换为字典序更小的字符串。否则肯定会出现\(s_i>s_{i+1}\)的情况。所以只要从头到尾扫一遍,找到\(s_i>......
  • AtCoder Beginner Contest 266 题解
    只有ABCDEFG的题解。A模拟。代码voidmian(){strings;cin>>s;intpos=int(s.size())/2;cout<<s[pos]<<endl;}B模拟,注意longlong。......
  • AtCoder Beginner Contest 266 D(DP)
    ……题面Takahashi要抓Snuke。好狠心的Takahashi呀(bushiSnuke有5个洞(,在$0m,1m,2m,3m,4m$处。Takahashi开始在$0m$处,每秒他能走$1m$。第$i......
  • AtCoder Beginner Contest 266 A-D
    AtCoderBeginnerContest266https://atcoder.jp/contests/abc266EF待补A-MiddleLetter输出字符串最中间的那个字母#include<bits/stdc++.h>usingnamespace......