牛客网NOIP赛前集训营第五六周-解题报告

· · 个人记录

PJ5-D 游戏

这不科学，10^8

每个怪兽死亡的顺序一定是按照血量升序，所以先排序；一个怪兽死亡当且仅当h[i]<=k+sum[i-1]，sum为之前死亡的怪兽的总攻击力；于是就有f[i][j]表示前i个怪兽，总攻击力为j的方案数，暴力转移；注意最后答案-1；

TG5-C 串串

    int ans=0;
    for(ri i=0;i<=a-c;++i)
        for(ri j=0;j<=b-d;++j)
            ans=(ans+(LL)C[i+j][i]*(a-c-i==0?1:C[a-c-i+d-1][d-1])%md*(b-d-j==0?1:C[b-d-j+c-1][c-1])%md)%md;
    ans=(LL)ans*C[c+d][c]%md;

PJ6-C 疏远度

这个好，单独写一篇；

PJ6-D WIFI

市政府想在品罗路建一些基站，保证这条路上每个公司的员工都能享受到 Wi-Fi。 
为了简化问题，我们将品罗路理解成一条直线，一个 Wi-Fi 基站为直线上的一个点。 
基站的费用为 A + k*B，其中A为建立基站的固定费用，B 为覆盖每单位距离需要的费用，k 为覆盖半径。 
如果在坐标为 a 的点建立基站，覆盖半径为 k，那么位于 [a-k, a+k] 的公司都能享受到这个基站的服务。
现在有n个公司，市政府希望从中挑出m个公司，使得这m个公司都被覆盖需要的最小建设费用最大。

不错的题，但是懒得写了，咕咕咕

但是这道题对区间的分析非常棒：

将问题转化为连通性（生成树问题），将花费移动到边权

TG6-A 最长路

有一张 n 个点 m 条边的有向图，每条边上都带有一个字符，字符用一个数字表示。

求以每个点为起点的最长路，输出走过的边的字符构成的字符串的字典序最小的方案。如果最长路无限长，则输出Infinity。

一看就是拓扑排序，但是一想到具体的字典序就不会了，看了题解之后恍然大悟：

核心就是快速比较字典序的大小，我们可以一边拓扑排序，一边维护hash的倍增数组，当需要比较两个串的字典序时，我们借助hash倍增找到第一个不同的位置，然后直接比较；我觉得是数据水，一遍就过了

TG6-BC

有毒吧出这么难的题...