UOJ Logo wym6912的博客

博客

西北工业大学多校题解

2017-04-19 11:27:59 By wym6912

恶魔包毁灭世界!:

    首先输出的第一个值是一个裸的二分匹配,设匹配值为num。
    假设左边有n-num个恶魔(包)还未匹配,右边有m-num座城市还未匹配,因此我们将左侧增加m-num个虚拟恶魔(包),
虚拟恶魔(包)与右边所有城市连边;右边增加n-num个虚拟城市,虚拟城市与左边所有恶魔(包)连边,这样我们就得到
一个两边各有M=n+m-num的二分图,且该二分图是一个完美匹配。也就是每个恶魔(包)都有一个匹配的城市。现在,我们
将每个恶魔(包)匹配的城市向该恶魔(包)进攻的城市连边(建一个新图g),然后求g的强连通分量。那么与每个恶魔
(包)之前匹配的城市在一个强连通分量里的城市都可以作为该恶魔(包)的匹配使得最大匹配不变。也就是说,设恶魔
(包)i之前的匹配为p[i],现在为恶魔(包)i选择一个新的城市j,那么我们若能为p[i]重新找到一个恶魔(包)k,那么
实质上就是找到另一个恶魔(包)互换两个两个恶魔(包)进攻的城市。因此两城市若在一个强连通分量里,那么恶魔(包)
由之前的匹配城市A选择城市B时,A也能找到另一个匹配,因为B能够通过某些路径到达A。
翻硬币:
    注意如下两个事实:
    1、对于每一行(列),翻转对于结果的影响只限于翻转次数奇偶的差别。
    2、对于每个硬币,有且仅有一行和一列的操作会影响它。
    那么对于每个硬币,如果它初始是正面朝上,那么它所在的行和列,要么都进行一次操作,要么都不进行操作;如果它初
始是反面朝上,那么它所在的行和列,有且仅有其中之一进行了一次操作。
    至此,这个问题就变成了一个2-sat的模板题了。
    特别鸣谢prOgrammer提供了一种更加简洁的思路。
    通过枚举第一行是否翻转,即可确定每一列是否翻转,此时每一行的状态也就确定了。
海豹的队列:
题意:给定数列${a_n}$,任意改动其中至多$k$项,求相邻两项差的绝对值的最大值的最小值。 思路:二分答案(二分的区间可以优化),对于某一个二分值$mid$,采用 DP 检验其可行性。 设$dp[i]$表示考虑前$i$个数,且第$i$个数不变,至少需要改多少个才能使得答案不大于$mid$。 那么考虑下一个不变的数是$a[j]$,则$a[i+1]~a[j-1]$这些数可以任意改变,前提是$abs(a[i]-a[j])<=(j-i)*mid$。 接下来枚举最后一个不变的数到底是哪个,$ans=min(ans,dp[i]+n-i)$。只要$ans<=k$就可行,否则不可行

积性函数:

    根据定义,f(n,0)恒等于1,对于n是积性函数。而f(n,m)=sigma (d|n)  f(d,m-1)*f(n/d,m-1) ,即 f(*,m)是f(*,m-1)与自身的卷积,由归纳法可证,对于所有的正整数m,f(n,m)是n的积性函数。因此只需计算当n是质数的幂时,f(n,m)的值,再由积性函数的性质,得到任意n的函数值。
    把n写作p^d,则f(p^d,m)=sigma (i=0:d) f(p^i,m-1)*f(p^(d-i),m-1),这是一个多项式卷积的形式。当m=0时,f(p^d,0)=1。
    对比生成函数的形式,f(*,0)可以表示成 1/(1-x)。而f(*,m)=f(*,m) * f(*,m),由归纳法可知f(*,m)的生成函数表示是1/(1-x)^(2^m)。所以f(p^d,m)是以上生成函数的第d项的系数,cmb(2^m + d-1,d)。本题要求取模后输出答案,模的质数不大,可以用Lucas定理计算组合数的模。
金角大王的葫芦:
    在同一个圆上的点的最短路径是这两个点所在大圆上的劣弧。那么设给定两点a,b,设两球相交形成的圆环上有一点c,确定c的坐标让ac+bc最短就可以了。那么三分c的位置即可。
    
这个游戏很休闲么:
    这个问题来自于《Winning Ways for Your Mathematical Plays》,在Matrix67的 http://www.matrix67.com/blog/archives/6333 这篇文章中也有一定的介绍。由于具体的细节可以从上述的书中及文中找到,故下面将不加证明地给出此题的解法。

将每一个 ‘*’ 的联通块单独考虑,对于每一个联通块,如果它仅可以由up-down玩家操作,那么将其对应的数值记为最多能够操作的次数;如果仅可以由left-right玩家操作,那么将其对应的数值记为最多能够操作的次数的相反数。特别地,空表格 = 0,  * = 0.
剩余的情况为:
                      *
               *      *
        *      *      *
 *      *      *      *
 *= 1;  *= 1;  *= 2;  *= 2;

** = -1; *** = -1; **** = -2; ***** = -2.
若对于一种局面,up-down玩家与left-right玩家均可操作,将up-down玩家操作一步后形成局面的最大值记为A,将left-right玩家操作一步后形成局面的最小值记为B。若 A < B,则该局面的价值定义为 (A + B) / 2;不然,该局面不能用一个实数简单地表示,不妨将其记为 {A | B}。
举几个例子:
   **             ***          ****               **
   * = {0 | 0},   *  = -1/2,   *    = {-1 | -1},  **= {1 | -1}, ...
将能够表示为实数的价值求和,记为S. 同时考虑将所有不能表示为实数的价值 {Ai | Bi} 排序,按照Ai-Bi 递减的顺序排序。设一共有m个不能表示为实数的价值,排序后依次写为 {A1 | B1}, {A2 | B2}, ..., {Am | Bm}。那么
记 UD = A1 + B2 + A3 + B4 + ..., LR = B1 + A2 + B3 + A4 + ...,
若 UD + S > 0, 则up-down先手必胜;若 LR + S > 0, 则left-right先手必胜;
若 UD + S < 0, 则up-down先手必败;若LR + S < 0, 则left-right先手必败;
若 UD + S = 0, 则 “若 m 为奇数,up-down先手必胜,否则先手必败”;
若 LR + S = 0, 则 “若m为奇数,left-right先手必胜,否则先手必败”。

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。