2017 Multi-University Training Contest - Team 1

acm 2017年7月 hdu 多校 组队训练

入口：2017 Multi-University Training Contest - Team 1

1001. Add More Zero

• 因为$2^k不会是10的倍数，所以直接取个以10为底的对数即可。
  
  
  

1002. Balala Power!

• 求出每个字母的贡献，从大到小分配，注意一下前导零的情况。
  
  
  

1003. Colorful Tree

• 单独考虑每一种颜色，答案就是对于每种颜色至少经过一次这种的路径条数之和
• 反过来思考只需要求有多少条路径没有经过这种颜色即可。
• 直接做可以采用虚树的思想（不用真正建出来），对每种颜色的点按照 dfs 序列排个序，就能求出这些点把原来的树划分成的块的大小。【undo】
• 这个过程实际上可以直接一次 dfs 求出。【done】【参考blog】
  
  
  

1006. Function

• 首先，稍微手写一下可以发现，$a$数组的对应关系和$b$数组的对应关系都是一个环（或者说循环节）
• 那么若a的循环节的大小为$l$，则$f(i)$的值在置换$b$中所在的循环节的长度必须为$l$的因数。
  
  
  

1008. Hints of sd0061

• 注意题面中，$b_i+b_j \leq b_k$
• 最慢的情况是$b$的取值为$0,1,2,3,5,8,\cdots$ 的情况，但事实上也只有$\mathcal{O}(\log_{1.618}{n})$
• 考虑这个性质，我们可以从大到小做，那么每次至少能减掉一半
• 直接使用nth_element()
  
  
  

1009. I Curse Myself

由于图是一个仙人掌，所以显然对于图上的每一个环都需要从环上取出一条边删掉。所以问题就变为有$M$个集合，每个集合里面都有一堆数字，要从每个集合中选择一个恰好一个数加起来。求所有的这样的和中，前$K$大的是哪些。这就是一个经典问题了。

对所有集合两个两个进行合并，设当前合并的集合是$A$和$B$，合并的过程中用堆来求出当前$A_{i}+B_{j}$的前$K$大值是哪些。这样的复杂度看起来为$\mathcal{O}(MK \log K)$，但如果合并的时候保证堆内的元素个数是新集合里的元素个数，设每个集合的大小分别为$m_{0}, m_{1}, \cdots, m_{M-1}$，则复杂度为$\mathcal{O}(\sum{K \log{m_{i}}}) = \mathcal{O}(K \log{\prod{m_i}})$。当$m_{i}$都相等时取得最大值$\mathcal{O}\left(MK \log{\frac{\sum{m_i}}{M}}\right)$，所以实际复杂度为$\mathcal{O}(MK)$。

1011. KazaQ's Socks

• 找规律题。
  
  
  

1012. Limited Permutation

• 划重点：注意到题面中 if and only if
• 你可以把所有区间的id放到对应的区间长度的桶里面，因为是 for(int i = 0; i < n; i++) 所以每个桶里面的id是递增的。
• 针对id递增，我们可以递归构造这个排列，先构造右子树，在构造左子树
• 由于题面中 if and only if 的存在，所以如果能构造出排列，那么递归的每一步都应该能满足。
• 递归的时候，假设$u$有两个儿子$v_1$和$v_2$，左子树和右子树的方案数分别为$f(v_1)$和$f(v_2)$，对应的大小为$s(v_1)$和$s(v_2)$，那么$u$的子树对应的方案数为$\displaystyle f(u) = {s(v_1) + s(v_2) \choose s(v_1)} \cdot f(v_1) \cdot f(v_2)$
• 由于使用基数排序，故处理的时间复杂度为$\mathcal{O}(n)$，主要时间还是花在了读入上面。我们可以加一些读入优化使得复杂度变成$\mathcal{O}(n \log_{10}{n})$，其中$\log_{10}{n} \leq 6$
• 最后mark一下fastIO和预处理阶乘和逆元的组合数

namespace IO {  
    const int MX = 4e7;
    char buf[MX]; int c, sz;  
    void begin()
    {  
        c = 0;  
        sz = fread(buf, 1, MX, stdin);  
    }  
    inline bool read(int &t)
    {  
        while(c < sz && buf[c] != '-' && (buf[c] < '0' || buf[c] > '9')) c++;  
        if(c >= sz) return false;  
        bool flag = 0; if(buf[c] == '-') flag = 1, c++;  
        for(t = 0; c < sz && '0' <= buf[c] && buf[c] <= '9'; c++) t = t * 10 + buf[c] - '0';  
        if(flag) t = -t;  
        return true;  
    }  
}

void init()
{
    fac[0] = 1;  rep(i, 1, N)  fac[i] = fac[i - 1] * i % p;
    inv[0] = inv[1] = 1;
    rep(i, 2, N)  inv[i] = inv[p % i] * (p - p / i) % p;
    rep(i, 3, N)  inv[i] = inv[i - 1] * inv[i] % p;
}
LL C(int x, int y){ return fac[x] * inv[x - y] % p * inv[y] % p; }