2013 ACM-ICPC Chengdu Invitational

4716 やるだけ 4717 三分(ry 4718 虽然可以dp倍增 但是lct写起来实在不用动脑筋……(ry 4719 与其说是dp不如说是披着dp外衣的数据结构水题吧……(ry 用线段树然后在最底层套一排multiset……大概没有比窝更懒的写法了……(ry 4720 最小覆盖圆(ry 4721 考虑选择任意一个点build city的话,suma和sumb可以O(n*m)预处理之后O(1)容斥,这个不用说 这样我们就得到n*m对数a[i]和b[i] 问题就转化为每次给一个A和B,求max{min{A+ai,B+bi}} 不妨考虑h=B-A,讨论一下可以得到以下结论 Continue reading

2013 ACM-ICPC Hangzhou Invitational

4576 4000ms、n=2e2、m1e6 这玩意根本就是在唬人嘛…… 吓死胆小的撑死胆大的…… 这种问题在没有特殊性质情况下的下界就是O(n*m),不可能更快……(ry 4577 考虑放在最后一个盒子里的球的编号 它们必须都整除2k-1 所以拿到n之后可以直接先n/=2k-1 可以得到一个贪心的猜想 尽量先取小的和尽量先取大的都不会更坏 那么就尽量先取小的吧 如果我们取了1,那么对于所有2i, i∈[1,k],i∈Z+就都不能取了 那么分阶段地搞的话,对于每一个阶段,所有的偶数都不能取、我们把所有的奇数都取走(ans+=(n+1)/2) 有点说不清楚…… 大概就是这样…… 4578 赤果果的线段树……(ry 差分成a×xi+b的形式,想清楚就行了……(ry 4579 可以列出一个方程组 似乎只能高斯消元解 但是观察一下的话会发现 dp[n]=0 dp[n-1]只涉及dp[n-1-m]到dp[n-2] Continue reading

2013 ACM-ICPC Changsha Invitational

4565 [latex](a+\sqrt{b})^n , \forall n\in Z^+[/latex]一定可以表示成[latex]x+y\sqrt{b} , x\in Z^+ , y\in Z^+[/latex]的形式 [latex](a-\sqrt{b})^n , \forall n\in Z^+[/latex]一定可以表示成[latex]x-y\sqrt{b} , x\in Z^+ , y\in Z^+[/latex]的形式 而且这两个x和y分别是相等的……( 所以[latex](a+\sqrt{b})^n+(a-\sqrt{b})^n=2x[/latex] [latex]\because (a-1)^24566 偷个懒窝就不做了吧……( 4567 (懒死中…… 4568 脑中秒出一个上下界最小费用最小流……( Continue reading

2013 ACM-ICPC Nanjing Invitational

4586 [latex]ans=\frac{\sum a_i}{n-m}[/latex] watch out trick 4587 枚举一个点、剩下的算割点……( 4588 对于二进制进位来说,如果低位已经进位完毕的话,现在考虑的这一位的进位情况一定只跟所有这一位的1的数目有关( floor(sum/2) ) 所以如果可以算出每一位的1的总数,那么再从低位到高位“上推”一次就行了……( 4589 已吓尿……( Continue reading

2013 ACM-ICPC Tonghua Invitational

4493 やるだけ first blood is mine 4494 赤果果的上下界最小流啦…… 用费用流来解上下界最大/小流的话,如果给你一个负环你就跪了……( 而且比ISAP慢很多啊……( 不过这题不会有负环…… 4495 很容易想到一个O(n3)的dp 注意一下边界情况……( 4496 やるだけ 4497 用lcm除以gcd之后,剩下的一堆素因子就是不能被三个数共有的了 比划一下……( 4498 曲线积分……吓尿……( Continue reading

2012 Asia Chengdu Regional Contest

4464 やるだけ 4465 多分これで 4466 长度为n的线能构成的整数边长三角形的种数有个这么一个规律 但是这些三角形不都是“本源三角形” 那么只要简单的使用类似批量分解素因子的方式从小到大筛一遍,剩下的就是“本源三角形”的数目了……( 然后枚举约数然后以下省略……( 4467 被卡常数了真是喜大普奔……( 4468 维护一个DFA(在这个地方具体的来说就是morris-pratt啦………………) Continue reading

2012 Asia Hangzhou Regional Contest

4453 三个双端队列所有操作O(1)啦…… 脑子有毛病才去写spt……( 4454 枚举角度居然能行……( 4455 考虑由w=i时如何增量求得w=i+1时的答案 对于每一个以∈[i+1,n]为结尾的子串,如果扩展之后答案+1,那么那个位置的字符上一次出现的位置必须距离这个位置超过i+1 那么每一步的增量可以这么预处理一下 Continue reading