首页 > 代码库 > 07 09&10
07 09&10
0709:
排名还是不高,毕竟没切出来题。
第一题dalao:
要求你做一个三维数点,只回答最终有多少个点对的状态是完全小于(可比?)的。(n<=2000000)
特殊限制是三维都是随机排列。
陈立杰在APIO讲过,当时我翘了......
在考场上努力卡常,结果卡常失败,应该拿到60,评测炸了,中间奇怪的RE,所以只有40。
正解是考虑一对点对(X,Y),由于有三维的对应大小,所以对应的大小关系只有 (2,1)(1,2)(3,0)(0,3)这几种,
我们要求的是所有(3,0)(0,3)的点对数目。分别对第一维第二维,第一维第三维,第二维第三维做二维数点。
然后我们发现(3,0)(0,3)的结果会在三次中都出现,(2,1)(1,2)的结果只会出现一次。
两种情况的并集是C(n,2),然后就是小学数学了。卡常。
第二题:
某回文自动机相关。
但我不准备学,因为应用范围比较小,而且普及度不高,NOI应该不会考吧.......虽说不要立FLAG,但还是想立一个......
第三题:
简单说就是带放缩的树上阶梯博弈。
每次从儿子拿走k个,然后在父亲放bi*k个,问是否一定会出现先手必胜。
放缩并没有什么卵用,除了bi等于0的情况,出现了这种情况可以将这两颗数拆开。
可以从树上阶梯博弈的解法思考。
想到了这种写法,但是忘记考虑bi等于0的情况需要特殊处理了,一看没过样例,就没有沿着这种思路继续。
0710:
第一题:
带权的最大密度子图。
板子题。
但不会优化建图,用前几天学到的二元费用模型现推,推出来了被卡了常。
非得用SAP吗?!怎么莫名其妙又开始卡常了。(数据又出锅什么鬼)。
第二题:
一个N*3的网格放m个点,一个点有一个给出的3*3的势力范围,要求方案数。
反正我写的状压DP。
题面怎么这么简洁,出题人N*3的网格是啥不能说清楚吗?多少人写的是3行N列啊!!
反正我写的是对的,尽管被出题人的这个方格放置坑了。卡常。
第三题:
设f[i]表示i的不同的质因子个数。
要求从1到N的2^(f[i])之和。
思路从开始就错了...
第一步应该是转化成对每个i计数有多少个(i,j)==1&&ij==n。
走出第一步之后后面的就是一个反演的套公式。卡常。
莫名其妙上午持续卡常....
这两天的题怎么这么喜欢卡常啊,出点正常的题目不好吗?!!?!
07 09&10