over 2 years ago

完结撒花!!


NOIP滚粗...
NOI滚粗...
WC滚粗...

今年还有ZJOI CTSC APIO.. 以及..NOI 感觉压力好大啊..

以下是滚粗狗的自我修养。


NEERC2014练习

听孙大大说NEERC的题目好,于是打算来写写NEERC的题目。不知道OI生涯还能不能抢救抢救。




  • [NEERC2014] Burrito King

有n个物品,每种物品有g[i]克,每种物品每克的joy值为a[i], unhappiness值为b[i]。给你两个参数A,B, 要求每种物品选取若干克(可以为小数), 在unhappiness值不超过B的情况下,joy值尽可能大。

经典的背包问题,按b[i] / a[i] 排序,能取则取。

WARNING
要特别注意b[i] = 0的情况.. 一除就爆炸了


  • [NEERC2014] Cactus Generator

给你一个用上下文无关语言定义的仙人掌生成语言.. SCGL, 里面定义了链, 分叉, 环.. 以及循环的规则.. 让你写一个解释器, 读入一个源代码.. 生成一个仙人掌,并且用其最小链覆盖的形式输出。

以下是几个例子:

码农题啊.. 一看就斯巴达了。
慢着..最后那个最小链覆盖怎么求。
只要把所有奇度点任意连起来,然后跑个欧拉回路,再把这些边删掉,剩下的链就是最小链覆盖。
正确性? 显然答案的下界是奇度点数/2, 这样做就能得到一个奇度点数/2的答案。
然后就码呀码.. 就好了.

WARNING
不要把int赋值给char!!


  • [NEERC2014] Damage Assessment

给你个这样的几何体,让你算阴影部分体积。

积分..强上simpson.. 面积的计算比较麻烦..


  • [NEERC2014] Epic Win!

一个玩石头剪刀布的DFA, 每个状态上都有一个值(R/P/S), 每个状态也有三条转移边。两个DFA对抗的时候,分别从start开始,比较完一个状态的值之后分别走对手的出招对应的转移边。现在给你一个DFA,但是不知到它的start,让你构造一个DFA,使得对手的DFA不论start在何位置,你对它的胜率都能超过99%.

感觉是个非常好的idea.
首先如果已经知道start了,那么就可以针对性地构造一个DFA,记为W.
那么把这个DFA先构造出来,枚举对手每一种可能的start,在当前的DFA上跑,如果状态跑出了环,说明可以一直赢下去,跳出。如果发现一条转移边并不存在于DFA上,就把W复制一份加到当前DFA中,把当前节点和对手DFA目前的点在新建W中的点连一条边,这样就能保证对手的状态处于被完全针对的状态上。这样就得到了一个状态数为对手状态数O(n ^ 2)级别的DFA。

WARNING
寻找状态的环的时候,要把两个DFA的状态一起考虑进去

if (vis[i][j] == x) break;
vis[i][j] = x;

  • [NEERC2014] Filter

给你一个哈希函数,去找可能等于输入值的所有输出值

按照题意直接暴力做就可以了。


  • [NEERC2014] Gomoku

交互式五子棋题目,给你一个先手的AI策略,你要写一个AI去击败他!

真有趣..手算题
题解说只有一种胜利策略.. 如下


  • [NEERC2014] Hidden Maze

给你一棵随机生成的带权的树,求长度为奇数的链的中位数的期望值。

n < 30000

这题不算难吧..可是很奇怪现场没有一个队交。
其实就是暴力,只是复杂度比较玄学。
先把边的大小排序,一条一条插进去,对于每一条插进去的边,计算它为中位数的方案数。
插入的边权记为1,没插入的记为-1。
假设现在插入的边为x,方案数就是找到一条经过x的路径,边权和为1。
可以从x出发往根走,枚举路径的lca,计算方案数。
g[i][j]表示以i为根的子树中走到i的边权和为j的点数。
每次插入一条边,就枚举它的祖先,更新g[i][j],顺带更新一发答案。
这个复杂度看起来非常玄学.. 题解说这个复杂度是靠谱的..


  • [NEERC2014] Improvements

所有满足条件的排列,将它取逆之后,一定是个单峰的东西,就是先单调增 ,然后单调减。
脑补一下发现,将一个元素任意取值的操作等价于删掉这个元素。
那就是选择一个子序列,使得它先增后降,套上经典算法即可.. O(nlogn)


  • [NEERC2014] Jokewithpermutation

直接dfs即可。


  • [NEERC2014] Knockout Racing

直接暴力 O(nm)

← 滚粗狗的自我修养之NEERC2015练习 一些基础dp题 →
 
comments powered by Disqus