#512. 「LibreOJ NOI Round #1」春游
退火调调参能调到61分(A了5个点),退火还是强啊。
大力猜测#2是个二分图,dfs一遍又加了10分。
https://loj.ac/submission/774590
.#1,#2应该是暴力点,我写了个瞎退火跑久点能过。
.#3做个背包还原一下方案。
. #4、#5 一看a都一样,b都是a的倍数,明示费用流
.#6 一看a只有一点点不一样,所以令(a[i]=max(a)),继续费用流
.#7一看a[2..n]都一样,(a[1]=4a[2]),(w[1][...])又特别大,枚举(a[1])选什么,还是费用流,跑个1分钟。
. #8、#9、#10一看就是全范围退火了,很可惜,我的退火不如按边权排序后选。
网上看到一种退火是退火一个排列,然后每次插进最优,看上去有点道理,但和我的贪心一个分。
一个多小时能搞(10*7+4+2+1=77),很良心。
https://loj.ac/submission/779713
我怎么知道它什么时候跳出去啊,貌似是交点。
不管了,走完一条线段再走其他的退火有35分,血赚。
之后有想法了再补吧。
https://loj.ac/submission/780259
被精度干到自闭。
先考虑点到超平面的距离公式:
({|sum ai*xi+a0|over sqrt{sum ai^2}})
(=r)
假设(sqrt{sum ai^2}=1)
枚举绝对值下面的正负,整理一下方程,可以得到(ai=k*a0+b)
代入(sqrt{sum ai^2}=1)解出(a0),再解出其它的(ai)
然后就是求切点,(sum ai*xi+a0)的法向量貌似就是((a1,a2,…,an)),那就很简单了。
注意解方程时,x可能是0,导致出现奇怪的问题,考虑一开始把每一维的坐标随机平移一下,最后平移回去。
https://loj.ac/submission/782624(99分不卡了)
造计算机好题。
先讲讲我没看题解的思路,拿了73分,发现有很多人都是这个分数,这大概是不会绝对值那种构造的分数上限。
.#1:熟悉环境,
.#2:17=(1<<4)+1
.#3:
暴力就是直接调用P比较(x)和(-x),能获得6分
考虑(S(x))这个函数,
当(x->+∞)时,(s(x)=1)
(x=0,s(x)=0.5)
(x->-∞,s(x)=0)
发现(2*S((x<<inf))-1)就是#3要的那个东西。
这里(inf)取(1000)比较合适。
.#4:
不会,输出(max(-x,x))获得6分。
套用#3加个乘法一样是6分。
.#5:
题目怎么说你就怎么做,95次可以获得10分。
.#6:
考虑对x进行二进制逼近,需要用到小于号,#3稍作变形就可以(<)时(=1,>时=0)
等于的情况比较烦,所以一开始把(x+=0.1)。
但还是需要用到乘法,次数也比较多,只有3分。
upd:这里不用乘法,比如有(2^x*y),直接(y<<x)就好了。
.#7:
先求出每一位,然后(x~xor~y=x+y-2xy)
还是只有3分。
.#8:
(a/10≈a/2^x*{lfloor {2^xover10} floor})
需要用到快速加,x取60精度就够了。
可以获得9分。
.#9:
考虑枚举(i,j(i<j))
令(a[i]=min(a[i],a[j]),a[j]=max(a[i],a[j]))
(min(a[i],a[j])=a[i]+a[j]-max(a[i],a[j]))
要用到max,还剩6分。
.#10:
同#6还是二进制逼近。
因为用到了乘法,还剩6分。
代码:https://loj.ac/submission/782817
总结:
我花了三个小时才拿这73分,分数上来说到了大众水平,但正式比赛时间肯定不够,需要加快速度。
题答后面的点可能依赖前面的点,也可能比前面的点还简单许多,比如#8、#9比前面都好拿分,#10依赖前面的小于号。
做的时候应该全部看一看,从有思路的简单的做起。
订正:
代填。。。