【cf549X】Looksery Cup 2015

2015年6月8日1,4728

A. Face Detection

模拟

B. Looksery Party

如果当前每个人还需要的信息数都非0,则已构造完

否则,找出为0的那个人,让其发一次信息(这个人之后一定<0)

C.The Game Of Parity

如果奇数和偶数城市都足够多,那么最后一个操作的人一定能将局面变成他想要的

否则就考虑某一方想将奇数或偶数的城市先取完

还要特判一下n=K的情况

D. Haar Features

考虑(n,m),它只能做(n,m)变换得到

所以从右下角开始,贪心+暴力即可

G. Happy Line

将所有人按照其钱数+所处位置进行排序

得出的序列就是最终序列

再依次计算每个人最终钱数

H. Degenerate Matrix

二分答案,就能得出a*d,b*c的区间,判区间是否重合

 

 

  • De℃,.: )2015年6月8日 下午2:34 回复

    黄学长怎么看H题的O(1)方法?

    #1  
    • hzwer2015年6月8日 下午5:17 回复
      admin

      请问是什么方法

      #11
      • De℃,.: )2015年6月8日 下午9:41 回复

        实在是不知道应该如何证明……
        最早出现在这:http://codeforces.com/blog/entry/18363?#comment-233514
        现在已经遍地了吧……

        #12
      • NanoApe2015年6月9日 上午9:12 回复

        O(1)方法貌似真的有。。。

        #12
      • 伪日常系LordNanoApe2015年6月9日 上午9:14 回复

        貌似可以证明最优解的A-B矩阵中,四个元素的绝对值一定相等。

        #12
        • De℃,.: )2015年6月9日 下午12:49 回复

          是呀评论区有证出来的可是然后呢……

          #13
          • zld37949552015年6月9日 下午1:55

            每个数要是修改的话,那么一定是加或减,一共16种情况,每种情况解个方程就行了。

            #14
          • De℃,.: )2015年6月9日 下午11:28

            由于有绝对值……就没有那么多种情况了……
            不过我好像是明白了:)谢啦

            #14