分类： 数学

发布于

[几何][数学][思维] CF 1030D Vasya and Triangle

题意：给定n,m,k,要求在横坐标小于n纵坐标小于m的整点中找到一个三角形使得三角形面积为 n*m/k。一开始一直纠结于存在性。首先可以证明如果2*n*m%k!=0那么一定是NO。当满足这一条件的时候，可以把n*m/k上下拆分，把k拆成gcd(n,k)*(k/gcd(n,k))，然后上下约分就可得到一组ab，这时候如果后者和m不能完全约分说明分母里会剩下一个2（因为分子上*2是可以完全约分的），这时候ab就是答案的两条边因为不需要除2了。如果能完全约分则还需要在分子的a或者b上乘一个2，哪个小乘哪个就好了。为什么乘2不会超过原来的n或者m？因为我们这时候一定是n*m%k==0，而且题中k>=2，所以n和m至少有一个可以除一个2。
感觉做的时候问题主要在于无法验证正确性，但是后来发现k>=2这个条件是极其重要的。。。。没有这个条件就可能无解了 继续阅读“[几何][数学][思维] CF 1030D Vasya and Triangle”

发布于

[比赛][暴力][循环][复杂度分析] 2018 icpc 青岛网络赛 J Press the Button

还好没有鸽这场比赛，当时是做数模的最后几小时，我和lyq没办法只能让iSika单挑，期间顶着40小时没休息的脑袋帮他过了一个水题和一个计数递推形的dp，然后看看J过的人挺多，准备去看却发现脑子实在太疼根本读不完题，然后iSika说他大概能过那个B，然后我就不管了去瞎编数模论文。。。

没想到的是晚上肝完数模去打印论文的时候，掏出手机发现代哥给我发消息问去沈阳赛区不去。。当时其实本来已经累得要死了但是看到这个瞬间高潮了，简直哭了，真的好不容易得到的icpc现场赛机会。。。

然后我在队里小群兴高采烈地发消息结果半天没人回我，嗯友尽系列（都在睡觉吗朋友们？？

然后后来一直在忙微软俱乐部的面试，到现在在高铁上才有空去看这几场区域赛攒的题，先把这个J补了，当时以为复杂度不可取，实际上就是一lcm循环，而lcm里a或c的倍数的数量最多1e6，所以不会超时。需要分成三段处理，第一段是[0,lcm)，第二段是[lcm,k*lcm)，第三段是[k*lcm,t]，其中第二段的计算只需要算(k-1)*[lcm,2*lcm)就可以了，也就是说三段复杂度都是1e6。当然有几段还得根据t与lcm的相对大小来具体判断。之所以第一段和中间循环段分别考虑，就是因为一开始的条件是灯都是灭的，但是在第一个lcm循环结束之后灯光却有可能是亮的，所以需要特别考虑这种情况。最后把三段的答案加起来就得到了最后的答案。

继续阅读“[比赛][暴力][循环][复杂度分析] 2018 icpc 青岛网络赛 J Press the Button”

发布于

[比赛][博弈论][SG表] 2018 ICPC徐州网络赛 B BE, GE or NE

赛后过题，心塞。

这题搞明白以后就是一个暴力打SG表的过程，-1表示bad，0表示normal，1表示good，从最后一轮开始，分奇偶轮，如果是奇数轮也就是先手轮，那就尽可能往1，也就是往大了转移，如果是偶数轮，也就是后手轮，那就往小了转移。真的是服了，这么简单当时就是没想到，唉。

因为n只有1000，每次的状态也最多只有200，（妈的限制上下界不就是为了可以暴力打表或者暴搜吗。。这么明显的特征没看出来我也是呵呵）想到这儿的时候直接明白了，为什么比赛时候那么多人过还那么高的通过率，呵呵呵呵呵，当时脑子真是短路。心情复杂。思考。 继续阅读“[比赛][博弈论][SG表] 2018 ICPC徐州网络赛 B BE, GE or NE”

发布于

[比赛][单调栈][histogram] 2018ICPC 南京网络赛 B The writing on the wall 求柱状图中有多少个矩形

比赛时候万人题，呵呵，没想到转换成histogram来做。貌似转化之后暴力都可以，n*m^2，气哭aaaaaaaaaaaaaaaaaaa

然后自己写了单调栈n*m做法，需要注意的是要同时保存一段height的左端点和右端点，因为要求数量的话，用单调栈只保存一个的话会忽略掉中间的“高点”，只保存一个端点就无法正确计算了。。。emm，代码写得时候脑子也很乱，还是需要多写写单调数据结构的题目。

继续阅读“[比赛][单调栈][histogram] 2018ICPC 南京网络赛 B The writing on the wall 求柱状图中有多少个矩形”