发表于   |   分类于   |  

275

Description

给你一些百分比，四舍五入之后，问原来可不可能是百分之百

Solution

数据范围非常小，暴力枚举分子分母到$1000$即可，做法很多。。。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
struct ElectionFraudDiv1 {
    int MinimumVoters(vector <int> percentages) {
        int n = percentages.size();
        for (int i = 1; i <= 1000; ++i) {
            bool f = 1;
            int l = 0, r = 0;
            for (int j = 0; j < n; ++j) {
                int x = percentages[j];
                bool ok = 0;
                for (int k = 0; k <= i; ++k) {
                    if ((int)((100.0000 / i * k) + 0.500005) == x) {
                        ok = 1;
                        l += k;
                        break;
                    }
                }
                for (int k = i; k >= 0; --k) {
                    if ((int)((100.0000 / i * k) + 0.500005) == x) {
                        ok = 1;
                        r += k;
                        break;
                    }
                }
                if (!ok)    f = 0;
            }
            if (f && l <= i && i <= r)  return i;
        }
        return -1;
    }
};

500

Description

给你一个$N\times M的$0/1$矩阵，你每次可以选一条最短路线的路线，把路线左下部$0/1$取反。问全矩阵变成$0$最少操作次数。

Solution

容易发现，每次最边界的是早晚都要取的，而且，$1$的边界线会逐渐变小。每次从上到下，找最右边界，翻转即可，数据范围很小，暴力即可，复杂度$O(N^2\times M^2)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
struct FlipGame {
    int minOperations(vector <string> board) {
        int ans = -1;
        int n = board.size(), m = board[0].size();
        while (1) {
            ++ans;
            int last = -1;
            bool ok = 0;
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < m; ++j)
                    if (board[i][j] == '1') ok = 1;
            if (!ok)    break;
            for (int i = 0; i < n; ++i) {
                for (int j = last + 1; j < m; ++j)
                    if (board[i][j] == '1') {
                        last = j;
                    }
                for (int j = 0; j <= last; ++j) 
                    board[i][j] = (board[i][j] == '1') ? '0' : '1';
            }
        }
        return ans;
    }
};

发表于   |   分类于 ，   |  

题外话

第五套感觉难度适中，今天把它补掉了。。。

hdu 5343(1001) MZL’s Circle Zhou

Solution

这题深深的暴露了自己$SAM$水平只差，每次遇到$SAM$的题，都不太能做出来，说到底还是对$SAM$理解不够深刻吧= =。。
由于是把两个串拼起来，容易想到，对第一个串正着建立$SAM$，第二个串反过来建$SAM$，用$dp[i]$表示第二个串中以$i$这个字符开头的串有多少个。
然后在第一个串$SAM$节点上，如果不能转移到字母$c$，答案加上$dp[c]$就好了
仔细想想，其实这题并不难= =。。。自己太弱了

Code

hdu 5344(1002) MZL’s xor

Solution

水题，发现不同项都抵消掉了。。。

Code

hdu 5345(1003) MZL’s combat

Solution

貌似有点烦，先跳过= =过段时间补

hdu 5346(1004) MZL’s game

Solution

dp好题，状态设计非常高端，和前几天CC月赛一个题思想非常相似，很好的idea。
正常dp复杂度无法保证，不妨考虑，一个选人顺序的全排列，如果一个人挂了，就继续选下一个人。由于每个人在每个位置概率都是$\frac{1}{n}$，我们不妨考虑编号$1 \sim n$。
这样转化后我们就可以做了！
考虑$dp[j][i]$表示$i$这个人受到$j$次攻击的概率,分两种情况考虑

  • (1) 第$i-1$个人没挂，则第$j$次攻击是来自第$i-1$的人的，于是$dp[j][i] = dp[j-1][i-1]\times (1-p)^{j-1}$
  • (2) 第$i-1$个人挂掉了，则受到的攻击次数和第$i-1$个人相同，于是$dp[j][i] = dp[j][i-1]\times (1-(1-p)^j)$
    于是就做完了，考虑全排列的这种思想，学到了。。

Code

hdu 5347(1005) MZL’s chemistry

Solution

无聊题，随手打个表

Code

hdu 5348(1006) MZL’s endless loop

Solution

类似于一笔画，奇数度的两两连一下，跑欧拉回路就完了

Code

hdu 5349(1007) MZL’s simple problem

Solution

水题，直接用set或者维护一下都可以

Code

hdu 5350(1008) MZL’s munhaff function

Solution

其实这就是个huffman树的生成过程，想明白那个式子和它的转换关系即可

Code

hdu 5351(1009) MZL’s Border

Solution

水题，关于$Fibonacci$的一般打个表就看出规律了，找第一个$i,m+1<|fib[i]|$,答案就是$m-|fib[i-2]|$

Code

hdu 5352(1010) MZL’s City

Solution

很容易想到的做法是，把每个操作$1$拆成$k$个点，与能相连的城市连一条边，跑匹配即可，由于要求字典序最小，倒着跑匹配即可。也可用最大流，费用流来做

Code

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

发表于   |   分类于   |  

250


求$A, B(A,B\le 4\times 10^{12})$之间所有数的$XOR$

Solution

转换成$1\sim B$异或和异或$1\sim A$异或和，容易发现当$n\ge 2时，1~\sim 2^n-1异或和为0$，$0,1,2,3$特判即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
LL gao(LL x) {
    LL t = 0;
    for (int i = 40; i >= 0; --i) {
        LL p = 1ll << i;
        if (x == 3 || !x) return t;
        if (x == 2) return t + 3;
        if (x == 1) return t + 1;
        if (p <= x) {
            if ((x - p + 1) & 1)    t += p;
            x ^= p;
        }
    }
    return t;
}
struct EllysXors {
    long long getXor(long long L, long long R) {
        return gao(R) ^ gao(L - 1);
    }
};

500

Description

在一个横坐标轴上有若干个垂直的线段.每个线段之间的距离为$width[i]$,现在让你从最左线段的左下角运动到最右线段的右上角
线段之间的运行速度为speed[i],在线段上垂直运动的速度为$walk$线段之间只能从整数坐标点运动到整数坐标点, 每个线段的高度都是一个定值$length$
请问最快多久可以到达目的地
$length\le 100000$

Solution

很容易想到dp,$dp[i][j]$表示过了前$i$个线段，当前在$j$的答案，暴力转移复杂度爆炸，容易发现，在每个线段的答案沿高度是单调的，转移时维护上一次转移的位置即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
const double inf = 1e20;
double dp[2][100005];
struct EllysRivers {
    double getMin(int length, int walk, vector <int> width, vector <int> speed) {
        int n = width.size();
        for (int i = 0; i <= length; ++i)   dp[0][i] = (double)i / walk;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= length; ++j)   dp[i & 1][j] = inf;
            int last = 0;
            for (int j = 0; j <= length; ++j)
                for (int k = last; k <= j; ++k) {
                    double t =  dp[(i - 1) & 1][k] + hypot(width[i - 1], j - k) / speed[i - 1];
                    if (t > dp[i & 1][j])   break;
                    dp[i & 1][j] = t;
                    last = k;
                }
        }
        return dp[n & 1][length];
    }
};

发表于   |   分类于 ，   |  

题外话

思考了一下人生，快打regional了，功利一点说多校的题并不需要每道都补，一些比较丧病或者烦的题我暂时就跳过了吧QvQ，先把正常向的题补了。。

hdu 5327(1001) Olympiad

Solution

SB暴力题，暴力算就好

Code

hdu 5328(1002) Problem Killer

Solution

水题，等差等比$O(N)$扫的时候判断即可

Code

hdu 5329(1003) Question for the Leader

Solution

简化问题，考虑把一棵树分成$k$块,这时一个显然的结论是如果有$k$个子树大小为$
\frac{n}{k}$的倍数，即可以分成$k$块。
考虑原问题，原题是一个基环加外向树，考虑不在环上的点$i$的$sz[i]$，显然可以直接计算。在基环上的点，不妨考虑断掉一条边后每个点为根的子树的$sz$,容易发现是一个前缀和的形式。然后我们对枚举的$k$取模，每次$O(N)$枚举在环上断掉哪条边即可。
复杂度$O(N\times logN)$

Code

hdu 5330(1004) Route Statistics

Solution

dp题，考虑$dp[S][k]$表示与$S$这个点距离为$k$的个数。($S$是一个长度为维度的$0,1,2$串)我们最后求出所有的$dp[S][k]$即可。
我们发现可以枚举中间某位不同，把那位分别替换为$0,1,2$三种情况来转移，简单dp一下即可

Code

hdu 5331(1005) Simple Problem

Solution

这个题其实并不Simple = =模型转换比较神，代码比较长，暂时没补，以后再说QvQ

hdu 5332(1006) Test for Rikka

Solution

这个一道比较有趣的题，$B=A^m,B[1][n]=k$很容易想到，我们相当于从$1$开始走$m$步到达n的方案数是k。
这样至少有个方向了。然后我们考虑特殊的图，完全图。
一个$n$个点的完全图，且每个点都直接与自己相连，走$x$步到达每个点的方案数都是$n^{x-1}$，然后怎么做呢。
我们很容易想到进制拆分，把$k$写成$\sum a[i]\times n^i$的形式，我们只需要搞出$a[i]$就可以了，我们可以把终点n拉出一条链，分别表示成对应$n$的$i$次方，然后不妨考虑完全图上有$a[i]$个点和链上连，这不就是$a[i]\times n^i$了么！至此，问题解决

Code

hdu 5333(1007) Undirected Graph

Solution

LCT题，先跳过= =以后再补

hdu 5334(1008) Virtual Participation

Solution

$k\le 10^5$时，全输出$1$即可
否则，不妨枚举有$i个1，j个2，k个3$，则，$i + j + k + i\times j + i\times k + j\times k=x$,枚举$i,j$即可，看上去复杂度非常高，其实满足条件的$i,j,k$不会特别大的

Code

hdu 5335(1009) Walk Out

Solution

细节题，先一直沿着0走到距离终点最近的距离，把这些点加入队列。
之后显然可以贪心走，输出答案时要注意细节。我写的有点烦= =

Code

hdu 5336(1010) XYZ and Drops

Solution

没什么好说的，大暴力就行，大水滴小水滴个数都不多，暴力复杂度完全可以接受

Code

hdu 5337(1011) Yet Another XYZ Problem

Solution

大型讨论题，先跳过= =

hdu 5338(1002) ZZX and Permutations

Solution

这题题意非常蛋疼，读懂了以后并不难做。
由于字典序要求最大，很容易想到贪心，不妨按位贪心，考虑第$1$位，查询$1$这个数的下一个数，不妨设为$A$，看之前的区间最大值$B$，如果$A$更大的话，标记$A$值使用过了，说明这个循环节可以用后面的替换。如果$B$更大，说明当前位置到$B$之间是一段连续的区间，确定下来了，然后把区间位置插入一个set里，表示这段区间已确定。就搞定了

Code

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

发表于   |   分类于 ，   |  

题外话

尼玛颓废着颓废着就开学了= =无聊终于把第三场的题全补完了

hdu 5316(1001) Magician

Solution

线段树裸题，维护四个东西，以奇/偶开头奇/偶结尾的最大值，正常线段树合并即可。

Code

hdu 5317(1002) RGCDQ

Solution

水题，发现$2\times 3\times 5\times 7\times 9\times 11\times 13 \times17>1000000$，所以素因子种数最多为7个，前缀和统计一下即可

Code

hdu 5318(1003) The Goddess Of The Moon

Solution

水题，题目太长比赛没看= =，唯一的坑是要把数字去重，然后容易看出可以用矩阵乘法来递推

Code

hdu 5319(1004) Painter

Solution

简单模拟题，按题目要求一刷刷到底就可以了

Code

hdu 5320(1005) Fan Li

Solution

感觉这道题是个不错题，考虑以$i$为开头的序列，$gcd$如果发生变化一定至少除以$2$，所以不同的gcd区间最多也是log级的。可以预处理出所有的四元组$(g,i,l,r)$，表示以$i$为开头，结尾在$[l,r]$区间内$gcd$为$g$。
考虑$dp$，不妨考虑当前$gcd=x$的方案数以及区间数，假设该四元组开头为$i$,显然区间数是以结尾在$[1,i-1]$区间内的最大值$+1$，方案数也很好计算。容易发现用一个线段树就可以轻松维护了。

Code

hdu 5321(1006) Beautiful Set

Description

A的计算方法是：对于$n$个数的某个排列，此排列的美丽值为这个排列所有的区间最大公约数之和。然后这个集合的美丽值为$n$个数的所有排列的美丽值之和。
B的计算方法是：在$n$个数中选出$k(1 \le k \le n)$个数，对于某种选取方案，这种方案的美丽值为$k$个数的最大公约数乘上$k$。然后这个集合的美丽值为所有选数方案的美丽值之和。

Solution

很容易想到用$cnt[i]$表示集合中$i$的倍数个数

  • 考虑第一个人
    $F1[x]$表示$gcd$为$x$的倍数的区间的个数
    $f1[x]$表示$gcd$为$x$的区间的个数
    $F1[x]=\sum_{x|d}f1[d]$

且$F1[x]=\sum_{j=1}^{cnt[x]} \binom{cnt[x]}{j}\times j! \times (n-j+1)!$
从$cnt[x]$里选$j$个数，再把$n-j$个数和这$j$个数算做$n-j+1$的排列

  • 考虑第二个人
    $F2[x]$表示$gcd$为$x$的倍数的区间的个数
    $f2[x]$表示$gcd$为$x$的区间的个数
    易知$F2[x] = \sum_{x|d}f2[d]$

且$F2[x]= \sum_{j=1}^{cnt[x]} \binom{cnt[x]}{j}\times j = cnt[x]\times 2^{cnt[x]-1}$
这个稍微推推就能推出来

同样的$F2[x] = \sum_{x|d}f2[d]$

然后就是我们熟悉的莫比乌斯反演辣！

$F(n)=\sum_{n|d}f(d)$

可以得到

$f[n]=\sum_{n|d}\mu(d/n)\times F(d)$

于是可以计算出$f$，$\sum f[i]\times i$即是答案

Code

hdu 5322(1007) Hope

Solution

这题其实并不难，考虑$dp[i]$为长度为$i$的排列的答案，枚举这个排列最大值所在的位置，最大值左边和它都是联通的，于是我们可以得到转移方程
$dp[i]=\sum_{j=1}^i \binom{i-1}{j-1}\times (j-1)!\times dp[i-j]\times j^2$

稍加变换我们可以得到

$dp[i]=(i-1)!\times \sum_{j=1}^i \frac{j^2}{(i-j)!}\times dp[i-j]$

令$k=i-j$我们可以得到$dp[i]=(i-1)!\times \sum_{k=0}^{i-1}\frac{(i-k)^2}{k!}\times dp[k]$
展开得$dp[i]=(i-1)!\times (i^2-2ik+k^2)\times \frac{dp[k]}{k!}$
维护三个前缀和即可O(N)解决，当然你可以没思维难度得想到cdq分治+NTT得做法QAQ

Code

hdu 5323(1008) Solve this interesting problem

Solution

考虑$[l,r]$是做左儿子还是右儿子，具体有$4$种情况，暴力枚举即可，实际上的复杂度是$4^{11}$，完全可以接受

Code

hdu 5324(1009) Boring Class

Solution

三维最长不下降序列之类的题，很容易想到按$id$算答案，$r$这一维排序，$l$这一维用树状数组维护然后cdq分治的经典做法。
考虑$dp$由于要字典序最小，先cdq分治算右区间的答案，考虑对左区间的影响即可。
写了不到$80$行，轻松愉快，cdq分治真是个高大的姿势。。。爽

Code

hdu 5325(1010) Crazy Bobo

Solution

水题，按权值排序后，权值小的向大的连即可，dp一下就行了

Code

hdu 5326(1011) Work

Solution

水题，随便dfs就行了= =

Code

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

发表于   |   分类于 ，   |  

题外话

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

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

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

发表于   |   分类于 ，   |  

题外话

这个暑假以前就决定要把这次多校的所有题全补了，中间断断续续，总算把第一场的题补全了，鄙视一下颓废的自己。。。

hdu 5288(1001) OO’s Sequence

Solution

水题，定义两个数组$L[i], R[i]$示第i个数左侧和右侧最接近它且值是a[i]因子的数字的位置，统计贡献即可。由于a[i]范围很小，因子数很小，暴力统计更新l,r即可。

Code

hdu 5289(1002) Assignment

Solution

水题，很容易想到先用st表预处理区间最大最小值，然后枚举左端点，二分右端点检查是否满足即可。复杂度$O(NlogN)$，也可以用单调队列维护最值

Code

hdu 5290(1003) Bombing plan

Solution

这题比赛时候没时间看，其实赛后发现并不是很难。看数据范围很容易往O(NW)上去想。于是不难想到dp
定义两个数组
$f[i][j]$表示以i为根的子树全部破坏掉，还能向上破坏最多j的距离，需要的最少点数
$g[i][j]$表示以i为根的子树未被全部破坏掉，且未被破坏的点距离i最远为j，需要的最少点数

  • (1)不取i点,则
    $$f[i][j]=f[son][j+1]+\sum_{l是i的其他孩子} min(f[l][0],f[l][1],…,f[l][j+1],g[l][0],g[l][1],…,g[l][j-1])$$

    $$g[i][j]=g[son][j-1]+\sum_{l是i的其他孩子} min(f[l][0],f[l][1],…,f[l][j],g[l][0],g[l][1],…,g[l][j-1])$$

  • (2)取i点则
    $$f[i][w[i]]=1+\sum_{l是i的孩子} min(f[l][0],f[l][1],…,f[l][w[i]+1],g[l][0],g[l][1],…,g[l][w[i]-1])$$
    很容易想到用两个数组$ff,gg$分别维护$f,g$的最小值，复杂度$O(NW)$，具体实现的时候注意下边界$0$的情况即可。仔细想想，转移方程还是比较容易得到的

Code

hdu 5291(1004) Candy Distribution

Solution

考虑最暴力的dp,$dp[i][j]表示分配完第i种物品，A比B多j个的方案数$，然后dp转移的时候枚举分给A$x$个，B$y$个，则$dp[i][j+x-y]+=dp[i-1][j]$。考虑第$i$种物品有$s$个，$x+y\le s$时可转移，则$dp[i-1][j]$对$dp[i][j]$的贡献有$\frac{s}{2}+1$次($x=y=0…x=y=\frac{s}{2}$),下发现，j每变化2,贡献-1。奇偶两种情况考虑时，这个东西类似于等差数列，差分两次后我们就可以完成递推了。复杂度$O(n^3)$

Code

hdu 5292(1005) Pocket Cube

Solution

这个题就是个找规律的题，看了题解才会做QAQ。。。

Code

hdu 5293(1006) Tree chain problem

Solution

比赛时没看，赛后发现是个很裸的题= =。
考虑dp，$dp[i]$表示以$i$为根的子树的最优值，则
$sum[i]=\sum_{j\in son[i]} dp[j]$
容易想到有两种转移

  • (1) $dp[i]=sum[i]$
  • (2) $dp[i]=value[p]+\sum sum[k]-\sum dp[k]$ $(链p的lca是i,k是链上的节点)$
    链上求和很容易想到树链剖分，复杂度$O(Nlog^2N)$

Code

hdu 5294(1007) Tricks Device

Solution

水题，最短路寻找道路边数最少的最短路,总边数减去最少条数为第二个问答案。
把最短路图抽出来建流量为1的边，最小割即为第一问答案。

Code

hdu 5295(1008) Unstable

Solution


平几题，给出中点很容易想到倍长的事情。如图，倍长$AF$，做$BG$平行于$AD$且$|BG|=|AD|$，容易看出三角形$FDA$和三角形$FCA’全等$
不妨固定BC,$A’$可以通过以$C$圆心，半径长为$da$，和以$B$为圆心，半径长为$2ef$的圆交点得到。
由于$A’GBC$是平行四边形，可以得到G的坐标。于是$D$的坐标可以通过以$C$为圆心，半径长为$cd$，和以$G$为圆心，半径长为$DG$(即$ab$)的圆得到。于是可以得到$A$的坐标

Code

hdu 5296(1009) Annoying problem

Solution

比赛时自己蠢一直没想出来，想过dfs序但没细想= =
其实每次插入的时候找两个dfs序最接近的点$x,y$一个大于$u$一个小于$u$即可。每次增加的花费是$dis[u]-dis[lca(x,u)]-dis[lca(y,u)]+dis[lca(x,y)]$，即为$u$到$x-y$链上的距离。删除时类似。
找不到这样的点时直接取最大和最小dfs序的两个点即可
为什么这样呢，给定固定点把它们连通得到的树一定是固定的。这样选点的目的是为了不让边重复。

Code

hdu 5297(1010) Y sequence

Solution

这个题比赛时我写的二分，一直T，= =非常蛋疼。赛后看题解和问别人才知道，可以迭代，迭代次数不会太多。
首先考虑反函数$f(x)$表示前$x$个数中Y-sequence的数量。我们迭代来算这个值，不用二分。
我们要求第$n$个Y-sequence，开始令$x=n$，如果$f(x)=now$，那么前$x$个数中有$n-now$个不是Y-sequence的数，那么我们令$x=x+n-now$，看看新的$f(x)$是否等于n即可。
我们每次只加了缺少的答案数，所以不可能超过正确答案。
迭代还是玄学啊。。。。新姿势get

Code

hdu 5298(1011) Solid Geometry Homework

Solution

比赛时以为是大型计算几何看都没看，赛后发现这是个SB题，把点带到平面和球面方程中，确定点在哪一边把结果异或一下考虑染色即可。

Code

hdu 5299(1012) Circles Game

Solution

自己太弱，不会扫描线，赛后补了下姿势。。
很容易想到扫描线处理圆，把圆变成树，然后就变成了经典博弈问题树上删边问题，具体可以看09年国家集训队论文<<组合游戏略述——浅谈SG游戏的若干拓展及变形>>。
结论是叶子节点$sg值为0$其余节点$sg$值为所以孩子节点$sg$值$+1$的异或和。

Code

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

发表于   |   分类于   |  

250

Description

从矩形地图中选三个点，使得A-B,B-C,C-A的曼哈顿距离和在给定的一个范围内，求多少种选法。$X,Y\le 3000$

Solution

水题，很容易发现曼哈顿距离和是一个矩形的周长，枚举长和宽统计即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
const int M = 1e9 + 7;
const int N = 5000;
struct PatrolRoute {
    int countRoutes(int X, int Y, int minT, int maxT) {
		LL ans = 0;
  		for (int i = 2; i < X; ++i)
			for (int j = 2; j < Y; ++j) {
				if ((i + j) * 2 >= minT && (i + j) * 2 <= maxT) {
					ans += 1ll * (X - i) * (Y - j) % M * (i - 1) % M * (j - 1) % M;
				}
			}
		return ans * 6 % M;
    }
};

500

Description

给出$n$个长度都为$m$的字符串。$n\le 16, m\le 50$，任两个字符串之间的大小关系由一个随即产生的排列来决定。即，如果比较至第$i$位，则去比较$pa_i$和$pb_i$的大小关系，从而确定字符串的大小关系。问$words_i$排完序后是最小串的概率。

Solution

感觉这题很难QAQ，首先n=16可以想到状压Dp，但是状态很难想，看了别人的题解才会做。。
$dp[i][mask]$表示当前状态是$mask$，第$i$个人是最小串的概率，$mask$为i的位置表示该串已被选择。在统计第$i$个串的概率时同时记录每位字母对应比该串小的和相等的状态。分别用$small[j]$和$same[j]$存二进制状态。
当$small[j] \& mask > 0$时，显然不可以转移，当$same[j] \& mask=mask$时，转移没什么意义，否则$dp[i][mask] += dp[i][same[j] \& mask]$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//状压Dp
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
const int N = 16;
int small[51], same[51];
vector<double> ans; 
double dp[N][1 << N];
double gao(int x, int mask, int l) {
	if (dp[x][mask] != -1.0)	return dp[x][mask];
	double &t = dp[x][mask];
	if (mask == (1 << x))	return t = 1.0;
	t = 0.0;
	int cnt = 0;
	for (int i = 0; i < l; ++i) {
		if ((small[i] & mask) > 0)	++cnt;
		else if ((same[i] & mask) != mask)	++cnt, t += gao(x, mask & same[i], l);
	}
	t /= cnt;
	return t;
}
struct StrangeDictionary2 {
    vector <double> getProbabilities(vector <string> words) {
  		int n = words.size(), l = words[0].size();
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < 1 << n; ++j)
				dp[i][j] = -1.0;
		for (int i = 0; i < n; ++i) {
			memset(small, 0, sizeof(small));
			memset(same, 0, sizeof(same));
			for (int k = 0; k < l; ++k)
				for (int j = 0; j < n; ++j) {
					if (words[j][k] < words[i][k])	small[k] |= 1 << j;
					else if (words[j][k] == words[i][k])	same[k] |= 1 << j;
				}
			ans.pb(gao(i, (1 << n) - 1, l));
		}
		return ans;
    }
};

发表于   |   分类于   |  

250

Solution

水题，最暴力的方法枚举即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
map<char, int> s;
int dx[] = {0, 1, -1, 0};
int dy[] = {1, 0, 0, -1};
const int N = 55;
int f[N];
bool vis[N];
struct AntsMeet {
    int countAnts(vector <int> x, vector <int> y, string direction) {
        int n = x.size();
        s['N'] = 0, s['E'] = 1, s['W'] = 2, s['S'] = 3;
        for (int i = 0; i < n; ++i) x[i] <<= 1, y[i] <<= 1, f[i] = s[direction[i]], vis[i] = 1;
        for (int i = 1; i <= 4001; ++i) {
            for (int j = 0; j < n; ++j)
                if (vis[j]) {
                    for (int k = j + 1; k < n; ++k)
                        if (vis[k]) {
                            if (x[j] == x[k] && y[j] == y[k])   vis[j] = vis[k] = 0;
                        }
                }
            for (int j = 0; j < n; ++j)
                if (vis[j]) {
                    x[j] += dx[f[j]];
                    y[j] += dy[f[j]];
                }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) 
            if (vis[i]) ++ans;
        return ans;
    }
};

550

Description

给出串$A,B,C,S,F$和整数$k$。以及函数$f(x) = A+x+B+x+C$。求$f^k(x)$中以F为子串，出现了多少次。答案mod $10^{9}+7$。串的长度$\le 50$, $k\le 10^7$

Solution

注意到串长度$\le 50$,以及$k\le 10^7$，而且出现F的情况分为在A，B，C三个串中分别出现，以及在交界处出现。由于串的长度比较小，所以我们暴力50次以后，交界处包含F的次数就不再变化了（想一想，为什么）。于是后面的情况我们每次$ans = ans \times 2 + t$即可。。$t$是交界处的答案，$ans$是$A,B,C$中的答案。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
const int M = 1e9 + 7;
struct AkariDaisukiDiv1 {
    int gao(const string &s, const string &t, int l = 0, int r = 100000000) {
        int tmp = 0;
        for (int i = l; i < s.size() - t.size() + 1 && i < r; ++i)
            if (s.substr(i, t.size()) == t) ++tmp;
        return tmp;
    }
    int countF(string A, string B, string C, string S, string F, int k) {
        int cnt = 0;
        for (; cnt < k && S.size() < F.size(); ++cnt)   S = A + S + B + S + C;
        if (S.size() < F.size())    return 0;
        int ans = gao(S, F), t = 0; 
        string p = S.substr(0, F.size()), q = S.substr(S.size() - F.size(), F.size());
        for (int i = 0; cnt < k && i < 50; ++cnt, ++i) {
            t = gao(A + p, F, 0, A.size()) + gao(q + B + p, F, 1, F.size() + B.size()) + gao(q + C, F, 1);
            ans = (ans + ans + t) % M;
            p = (A + p).substr(0, F.size()), q = (q + C).substr((q + C).size() - F.size(), F.size());
        }
        for (; cnt < k; ++cnt)  ans = (ans + ans + t) % M;
        return ans;
    }
};