2015 ACM多校训练第二场

发表于   |   分类于 ，   |  

题外话

颓废了一万年终于把第二场的题补完了，除了丧病的第一题。。

hdu 5301(1002) Buildings

Solution

水题，仔细讨论各种情况即可

Code

hdu 5302(1003) Connect the Graph

Solution

构造题，比赛时没看，赛后发现挺水的。由于连接黑边白边只有$0,1,2$三种情况，0我们就不管了。
不妨想考虑白色边，$1,2$的情况我们只需要先构造一个长链，解决$2个1和所有2$，然后再把1的搞出来。然后为了防止重边，做黑色边的时候有同样的方法，连边时隔着一个点连即可。

Code

hdu 5303(1004) Delicious Apples

Solution

贪心的好题，有两种情况，一种是都从两个半边取，另外一种是从一边开始取回去后，绕后另外一个半边取。但是注意到环最多肯定是只绕一次的，如果绕两次我们明显可以只绕一次，然后再走一个半边。显然更优。
预处理的时候把所有苹果按位置排序，dp一下即可。

Code

hdu 5304(1005) Eastest Magical Day Seep Group’s Summer

Solution

好题，删掉$m-n$条边后剩下$n$条边，可以看出是一个树上有一个环，看到数据范围很容易想到枚举环上点的集合。然后剩下的便是生成树计数问题，可以用Matrix-tree定理解决。
那么如何求点集为$S$的环的个数呢，考虑状压Dp，枚举环上最小点的标号，令$dp[i][j]$为当前点集为$i$，终点为$j$的方案数，简单dp即可。最后答案要除以$2$，因为每个环两个方向都算了一遍。而且注意到长度为1的环是不算的。
复杂度$O(2^n \times n^3)$

Code

hdu 5305(1006) Friends

Solution

水题，随便搜搜就过了= =

Code

hdu 5306(1007) Gorgeous Sequence

Solution

神题，主要考察复杂度的分析= =然而我并没怎么理解QAQ。。。
打了和正常线段树一样的标记tag，另外记录了一个cov标记，表示该节点下多少个叶子节点被控制，还维护了mx,表示最大值。每次修改的时候，不直接修改，先dfs到叶子节点，清一下之前的标记，然后再返回来修改该节点。sum更改时只要增加tag值控制的节点的sum即可。
感觉非常的玄幻= =太神了。。。蒟蒻不太理解QAQ

Code

hdu 5307(1008) He is Flying

Solution

比赛时没怎么想，赛后发现并不难。
首先容易想到用$s[i]$表示前$i$段的和，答案是$\sum (j-i+1)x^{s[j]-s[i-1]}$，最后$x$的次数为$k$的就是对于长度为$k$的答案。
变化一下形式得$\sum j\times x^{s[j]}- \sum (i-1)\times x^{s[j]-s[i-1]}$，再拆一下得到$\sum j\times x^{s[j]}\times \sum x^{s[i-1]}-\sum x^{s[j]}\times \sum (i-1)\times x^{s[i-1]}$。
这样熟悉FFT的同学马上就会发现这是个卷积的形式，FFT直接搞就可以了。由于精度问题，可以选择大质数的NTT，或者两个int型的NTT再中国剩余定理合并。实测选取大质数NTT会更快一些。

Code

hdu 5308(1009) I Wanna Become A 24-Point Master

Solution

24点= =水题，就是麻烦。。。
我的做法是分为$n是否大于等于12$，如果$n\ge 12$，那么显然可以搞出$2\times 3\times 4$这种形式，分奇偶不同处理一下即可。比如多的一些数是$4$，那就不停的乘4除以4即可。
$n<12$时，手算即可。

Code

hdu 5309(1010) JRY is Fighting

Solution

这题看了鸟神的题解一直没看懂= =。。最后问了他才搞明白。。感谢鸟神。
很容易想到二分答案，如何验证是个问题。首先预处理出一个数组$r$，$r[i]$表示在第$i$秒嗑药后能挺到第几秒。然后我们二分答案再验证，如何验证是核心。
考虑下面check长度为x的代码，建议和输出答案的$nxt$数组一起考虑。
我们将点转换为区间考虑，$d[i]$表示$i$到终点的嗑药次数，如果$d[i]>d[i+1]$表示$i$这一时刻要嗑药，然后我们分了三种情况考虑

  • (1)$r[i]>n$表示这个点可以直接到终点，显然我们可以再这点嗑药
  • (2)$r[i]-i<x$，这个点显然不能嗑药，因为间隔$<x$
  • (3)否则$r[i]+1>i+x$,如果最近的间隔到了$i+l$这一时刻可以到达最后的终点($d[i+x]>d[r[i]+1]$)，显然我们这第$i$时刻可以嗑药。

同时由于我们要求字典序最小，显然如果能取前面的就尽量取前面的,这个$d$数组挺难理解的，不知道我自己理解的是否透彻QAQ，可以把$d$数组看做后面整个区间的一个最值，从后往前推时$d$值不降，呈阶梯状，变化时表示可以嗑药。注意到第一次嗑药时没限制的，最后特殊判断一下即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool check(int x) {
    d[n] = 0;
    for (int i = n - 1; i >= 1; --i) {
        if (r[i] > n)   d[i] = d[i + 1] + 1;
        else if (r[i] - i < x)  d[i] = d[i + 1];
        else    d[i] = d[i + 1] + (d[i + x] > d[r[i] + 1]);
    }
    return d[1] > d[r[0] + 1];
}
void print() {
        for (int i = n - 1; i >= 0; --i) 
            nxt[i] = d[i] > d[i + 1] ? i : nxt[i + 1];
        int top = 0;
        int x = nxt[1];
        while (x) {
            s[top++] = x;
            if (r[x] > n)   break;
            x = nxt[x + ans];
        }
}

Code

完结撒花！
继续补题！>_<