64th 2023/7/15 UNR(UOJ NOI ROUND#7 Day1-2)总结

发布时间 2023-08-24 21:38:27作者: Far_delivery

本次情况

Day1

很认真去打的一场,但是我是真的菜,分根本不够看

T1是一道博弈论,开局很有信心地去看,推,一个半钟头砸出去,最后只拿了暴力分,因为实在推不出什么

T2是一道多项式题,这块的知识面尚未触及,因而不懂,然后有10分的贪心,打了

T3是一道DP,有贪心的思路和数据结构维护

难度完全在线,认真去打也不能得到什么,赛后发现有人能切T1,细想了一下,发现什么博弈思路必胜策略都是不太可行的,因此发现对博弈论而言,还有经过推理最优策略和游戏特殊性质而得到的贪心思路

如这题,每次取相邻的两个数,因此每次只能是一奇数位一偶数位,然后总共奇数位比偶数位多一,因此答案只可能在奇数位中出现,双方一个想要答案最大,一个想要最小,就会一个取最大奇数位,一个取最小奇数位,因而最后答案是奇数位中的中位数,若中位数不为整数,就取更大的

真是好思路,开了眼了

然后T2则有些数论化,因为比赛给了5h,所以认真看完题目了,能看懂,但就已经失去下一步了,打了很简单的数据(看懂题就应该会的)

T3是在对题目一次次推理后,将一个DP优化再优化,用到了单调队列和一些贪心,为了方便转移处理,转化了一下题目

Day2

T1赛时的25分很容易,然后因为其他题都不好打,就去思考T1的50分了,没什么结果,赛时想到了50分的思路,但因为没看到一个条件\(a_i≥b_i\)导致没想出来

因为这个条件,可以证明从L开始往后找和从L前几个数往后找,找到第一个可以弹出L的节点是一样的

因此可以倍增打出k=1的条件

正解很有意思

因为区间前k-1大肯定不会被弹出,所以可以用主席树维护前k大,然后最后的一用k=1的代码找即可

题外

emmm

发生了一件事

就是关于杭电(HDU)比赛,在共享里报了名,但账号却没get到

当时心灰意冷,毕竟自己实力的确有问题,就觉得是账号不够,分给了别人

嗯,然后有人去找了老师,后来又申请了账号,成功了,实属没想到

其实这是自己的问题,因为凡事中,想要的,都要又勇气去尝试,就好似在比赛中打一个不熟悉的算法,要有勇气去冒风险尝试,才有机会得更高的分,若只是因为所谓”成功率不高“,就放弃,那就没有机会去触碰到成功

这次与比赛的机会失之交臂,却也不能说坏,因为题目,只要我想还是能拿到的,这样不去真正参与比赛,反而增加了我的灵活性,让我有能力有机会去选择,

我也是初三的人了,时间已刻不容缓

学算法,数据结构,补坑

苏醒,行将集结