首页 > 其他分享 >闲话 11.8

闲话 11.8

时间:2024-11-08 21:30:28浏览次数:1  
标签:11.8 int 闲话 dp 题真 5k Ratio 丁真

别问为啥这么晚才写,因为一天都不知道在干啥,要寄的节奏。


  • 11.7 晚

轮到 CTH 写字

Ratio:程立雪?啥意思,程门立雪?门呢?

CTH:让我创掉了。


  • 上午

把昨天晚上想到的题出了出来,见此

由于 5k 们要打 nfls,所以只能找团委了,过了 hack 之后直接拿 \(\mathcal{O(n^2)}\) 出到了 \(10^5\) 的点,但发现 \(n\le 10^3\) 的 TLE 了?

研究发现团委做法是值域挂 \(\log\) 的,测试组数一多就炸了。

中午问 5k 发现需要写 DFT?


  • 下午

信息课,没什么劲,还我每日一歌!

学考模拟直接大战 Excel 三百回合,然后动用人类智慧直接查找替换 + 公式填充 + 学号除以 1000 变为班级 + 排序 + 分类汇总做完了。

上午的题问了原作 jjdw 说只能值域带根号挂 \(\log\) 做,需要将值域缩到 \(5\times 10^4\) 左右,好吧这下真出了不可做题了。

打了到大家不知道为什么都在做的简单 Ynoi,一眼根号分治,加了个 getchar_unlocked() 就过了。

然后去打没打完的 AT_dp,感觉今天闲话没什么内容啊,那就塞几个题解:


Digit Sum

简单数位 dp,当复健了。

设 \(f_{i,j,0/1}\) 表示到第 \(i\) 位前面的数和对 \(d\) 取模的结果为 \(j\) 且有/无原数大小限制的方案数。然后记搜做完了。

要点是 dp 数组初始化;记搜从高位到低位;然后没了。

Permutation

一个智慧 dp。

考虑设 \(f_{i,j}\) 表示已经放了 \(i\) 位且最后一位排名为 \(j\) 的方案数,那么每次枚举 \(1\) ~ \(i\),根据符号关系转移,有:

\[\begin{cases} f_{i,j}=\sum_{k=1}^{j-1}\ f_{i-1,k}\quad s_i='<'\\ f_{i,j}=\sum_{k=j}^{i-1}\ f_{i-1,k}\quad s_i='>' \end{cases} \]

前缀和优化即可,复杂度 \(\mathcal{O(n^2)}\)。

Grouping

看范围识状压,确实忘了。

考虑预处理每个分组的得分,然后枚举每个状态和它的每个子集,转移即可。

trick 是如何一遍直接枚举出目标集合的子集,这样实现:

for(int t = T; t; t = (t - 1) & T)

然后就过了,预处理复杂度是 \(\mathcal{O(3^n)}\) 的,转移是 \(\mathcal{O(n^22^n)}\) 的。


  • 晚上
起因

丁真:晚上有牛客,我要打。

Ratio:那你把第三题给我吧。

丁真:你还要上了,不给。

int_R 来了,说了比赛有关

丁真:这比赛简单。

Ratio:那你把 T6 给我吧。

丁真:行,我上次调一晚上没调出来。

拿了题面,看,没思路,再看,没思路。

“第 F 题真困难啊!”我想着。

叫来 5k,jijidawang,int_R,Estelle_N 一起看,没思路。

“第 F 题真困难啊!”大家想着。

丁真过来了:“我把 A, B, C, E 过了,D 是模拟不想打。”

Ratio:“给我 D 吧,你去看 F。”

int_R 和丁真一起做 F 题。

看 D 题,题面很简单,但是分讨很多,还不能简写。

“第 D 题真复杂啊!”Ratio 想着。

不知道过了多久,Ratio 打完了,测了下样例,过了。

“第 D 题真简单啊!”Ratio 想着。

喊来丁真交了一发,TLE 了,真不爽。

不会造点,于是手动一点一点出,发现果然 TLE 了,怎么会是呢?

输出一下,发现是边界判错了。改完过了,Ratio 高兴地说:“这发必过,不过我把 5k 吃掉。”

交了发,居然 WA 了,真不爽。

再次自己手造 + 模样例,发现边界又判错了。改完过了,Ratio 高兴地说:“这发必过,不过我把 5k 吃掉。”

交了发,居然又 WA 了,真不爽。

手造不出来样例了,输出过程量。“怎么 RE 了?”

“哦,原来数组开小了。”

image

image

发现了错误,Ratio 高兴地说:“这发必过,不过我把 xrlong 吃掉。”

交了发,居然又又 WA 了,真不爽。

“第 D 题真困难啊!”Ratio 想。

然后经过很长时间的探索,发现又是边界错了,还有 5min 改完交了发,过了。

“第 D 题真简单啊!”Ratio 想。

最终结果是 AK Rank8,丁真贡献一发罚时共 20min,int_R 贡献 5 发 1.3h,Ratio 贡献 4 发 1.5h。

我度过了一次充实的牛客小白月赛。

总结:1h 吃了 4 发罚时和两个人。


完结撒花~

image

标签:11.8,int,闲话,dp,题真,5k,Ratio,丁真
From: https://www.cnblogs.com/Ratio-Yinyue1007/p/18535973

相关文章

  • 【闲话】全知
    大抵是有这么一位全知监视观察着这个世界的一草一木,他被教导不对蝼蚁般的生灵的名义施与怜悯,也不应插手凡人的命运,而是与世无争、退隐闲境。他应做的只有监视观察,品味亦或是玩弄创世神早已安排好的一切,亲眼见证着世界一次次新生后的毁灭降临。他自己也无法摆脱这......
  • 2024.11.8随笔
    做题今天主要是上午在做题,写了李超线段树优化dp以及斜率优化的题,顺手交了一发经验题。我感觉现在斜率优化的题目对我来说很板,就是直接上暴力的dp然后发现转移式子里面有二次项所以需要把一坨东西抽象成一次函数,然后去寻找一次函数的特性。如果k值具有单调性我就直接单调队......
  • 11.8
    学习了如何在Java中执行复杂的多表连接查询importjava.sql.Connection;importjava.sql.DriverManager;importjava.sql.ResultSet;importjava.sql.Statement;publicclassJavaMySQLMultiTableJoinExample{publicstaticvoidmain(String[]args){try{Connection......
  • 11.8模拟赛总结
    赛时T1想如果某一行和某一列的最大值相同的话,这个数的位置就可以确定了,但如果一个数只作为某一行的最大值出现了一次,那它所在的列就一定有一个比它大的,所以考虑从大到小往矩形里放数,记录有几列已经放过数字了,那这个数就可以在这几列中任选一列,即\(ans\)乘上放过数的列的个数,赛......
  • [2024.11.8]NOIP 模拟赛
    省流:若为IOI赛制,则全机房一定同分。赛时T1看上去不太会。首先发现最大的数字的位置是固定的,然后我大胆考虑将数字从大到小依次填充。对于当前数字,一共会有四种情况:\(a,b\)数组都有,此时显然位置固定。\(a\)有或\(b\)有,此时能填的位置显然是一行或一列,即这一行或一列上......
  • 2024.11.8 鲜花
    MoonHaloSomedesertsonthisplanetwereoceansonce这颗星球上的一些沙漠曾是海洋Somewhereshroudedbythenight,thesunwillshine被黑夜笼罩的地方,也会迎来光明SometimesIseeadyingbirdfalltotheground偶尔也会见到濒死的鸟跌落地面Butitusedtof......
  • 11.8 javaweb学习 day1 入门
    网页响应流程浏览器前端服务器后端服务器数据库1.浏览器请求前端2.前端响应浏览器3.浏览器请求后端4.后端请求数据库5.数据库响应后端6.后端响应浏览器网页的组成1.网页的文字,图片,音频,视频,超链接什么的,本质是前端代码2.前端代码通过浏览器的转化......
  • 2024.11.5 闲话
    别人的闲话都推图or歌,我的鲜花啥也没有。我也没啥可推的啊,求图or歌高维前缀和常见的柿子是\(s_{i,j}=s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}+a_{i,j}\)。但是还可以一维一维求。点此查看代码rep(i,1,n,1)rep(j,1,m,1)a[i][j]+=a[i-1][j];rep(i,1,n,1)rep(j,1,m,1)a[i]......
  • 11.8
    阅读教材第一章复习UML,回答下述问题:面向对象程序设计中类与类的关系都有哪几种?分别用类图实例说明。关联关系(1).单相关联学生可以选修课程,但课程不需要知道哪些学生选修了它。(2).双向关联(3).自关联关系以公司的组织结构为例,一个员工可以是另一个员工的管理者。(4).......
  • 【闲话 No.1】 求解??
    大概是在中考之前,做过一个奇怪的梦:(梦中)一觉醒来,至公楼前面的空地上突然长出(字面意思)一个非常高级的酒店,huge突发奇想带着我们去那里全天集训。每天大概:起床跑去操场进行神秘仪式,然后回到酒店的会议室刷题。一天,huge突然把我拽了起来,一把扔出会议室门,扔进了一个壁炉里。壁炉......