AGC007


A Shik and Stone

我是沙比这都能蛙一发

https://agc007.contest.atcoder.jp/submissions/7946110

B Construct Sequences

造两个等差数列\(20000,40000,\ldots,20000n\)和反过来作为基础\(A,B\),然后在上面减一下就好了。

https://agc007.contest.atcoder.jp/submissions/7946428

C Pushing Balls

真tmd神仙题

每次操作后移除对应的石子和洞,并重标号

打表可证(真tmd是打表啊)若干次操作以后,可将一段长度的期望直接作为长度计算,然后这个tmd还是个等差数列= = = = = =

然后打表算算算(甚至tm可以手打

https://agc007.contest.atcoder.jp/submissions/7958580

D Shik and Game

简单打牌,不会可以谢罪= =

可以看出方案一定是每次选择一个前缀\(A[1-i]\),从\(1\)往返一次\(1,i\),然后等到\(1\)处金币出来,直接走到\(i+1\)(期间可以拿\(1-i\)所有金币)

设\(f_i\)表示后缀\(i-n\)的答案

dp式:\(f_i=\min\{f_{j+1}+x_{j+1}-x_i+\max\{T,2(x_j-x_i)\}\}\)

\(2(x_j-x_i)\)与\(T\)关系是单调的,\(<T\)单调队列维护,\(>T\)确定了直接记一个min

https://agc007.contest.atcoder.jp/submissions/7959461

E Shik and Travel

神仙题

(这场8个切C,2个切E,无数人切D,5人切F

先二分

设\(f[i][a][b]\)表示点\(i\),入边是\(a\)出边是\(b\)(\(a,b\)完全可以交换),然后\(a,b\)是没有限制的(因为直接连根的长度任意

然后就神仙优化了

对于相同的\(a\)留最小的\(b\)就行了,所以可以优化掉一维

对于相同的\(b\)留最小的\(a\)也行了,所以\(f[i]\)只用记\(O(siz)\)个二元组\((a_j,b_j)\),其中\(a\)严格递增\(b\)严格递减,剩下的都可以不要

然后转移的时候点\(i\)会有一条路径从\(ls\)子树到\(rs\)子树,我们要满足这一条\(\leq mid\)

很蠢(用原来dp方法)的办法是那么枚举\(a,b,c,d\),其中\(b+c\leq mid\),可以转移给\(a+d\)

优化以后只要枚举一个子树中的\(a\)可以得到最小的\(b\),然后根据\(b\)得到\(c\)的范围,再选一个最小的\(d\)

这个过程可以双指针优化

因为只需枚举三元组较少的儿子在另一个查询,复杂度同启发式合并

https://agc007.contest.atcoder.jp/submissions/7964497

F Shik and Copying String

题解好神啊懒得看题解了

先不考虑最优化步数,\(T\)串显然可以缩连续段,问题转化成:\(S\)串选一个子序列,使得子序列等于缩完后的\(T\),然后由于只能往右走要满足位置都在\(T\)对应左边

作完dp可以判-1了

然后是最优化步数,这里我sb了

dp完之后过程可以转化成由决策点扩展到整个区间,那么首先扩展到区间左端点,最后花一步全部扩展完毕,新的问题是,有\(m\)只鸡贼位置是\(a_i\),想到\(b_i\)去,只能向右走,满足\(a_i\leq b_i\),而且鸡贼相对位置不能改变。这个东西直接模拟是\(n^2\)的,不过可以用单调队列维护做到\(O(n)\)。

https://agc007.contest.atcoder.jp/submissions/7964196

最新文章

  1. Linux mkdir 创建文件夹命令
  2. WCF传输图片解决方案
  3. 组合or继承
  4. [转载]Windows 2012 R2安装SharePoint 2013 手动安装工具软件
  5. 关于offer选择
  6. zoj 2027 Travelling Fee
  7. MySQL 更改默认编码为 utf8 (转)
  8. ASDL + WN725N 配置无线AP
  9. 实现windows和linux互传文件
  10. 求奇数偶数的和,,利用while循环
  11. CSS选择器详解(伪类) 转 http://blog.csdn.net/Panda_m/article/details/50084699
  12. docker 容器开启ssh服务
  13. Amazon前技术副总裁解剖完美技术面试
  14. Hibernate(一)——采用Hibernate框架开发环境搭建
  15. SQL解决时间段重复合并问题
  16. Java中多线程服务中遇到的Redis并发问题?
  17. Jenkins二 安装gitlab及其使用
  18. linux_shell自定义命令
  19. airport 抓包
  20. Java学习第一周博客

热门文章

  1. C# - List.Sort()自定义排序方法
  2. CMU-Multimodal SDK Version 1.1 (mmsdk)使用方法总结
  3. JSP+SpringMVC框架使用WebUploader插件实现注册时候头像图片的异步上传功能
  4. JavaScript 之 offset 、client、scroll
  5. mysql 使用 MD5函数 校验账号密码
  6. Springboot+事务
  7. 让window10目录支持大小写
  8. workman即时推送
  9. golang http 服务器的接口梳理
  10. Win10 Microsoft Store 微软商店 Error 0x00000193 解决方法