5/5
好久没写博客了，难得有空写个题解，难得有空补不动~~
题A hdu5776 sum
题意：略
题解：dp[x]表示前缀modm的余数有没有出现，如果同一个结果出现两次，那么就说明中间的一段是可以整除m的，当然不要忘了本身前缀就能够整除。
1 /*zhen hao*/ 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <queue> 6 #include <vector> 7 #include <string> 8 #include <stack> 9 #include <set> 10 #include <map> 11 #include <iostream> 12 #include <algorithm> 13 using namespace std; 14 15 #define lson l, m, rt*2 16 #define rson m + 1, r, rt*2+1 17 #define xx first 18 #define yy second 19 20 typedef pair<int,int> pii; 21 typedef long long ll; 22 typedef unsigned long long ull; 23 24 const int N = 5e3 + 10; 25 int dp[N]; 26 27 int main() { 28 // freopen("case.in", "r", stdin); 29 30 int T; 31 cin >> T; 32 while (T--) { 33 memset(dp, 0, sizeof dp); 34 int n, m, now = 0, ok = 0; 35 scanf("%d%d", &n, &m); 36 for (int i = 0; i < n; i++) { 37 int x; 38 scanf("%d", &x); 39 now = (now + x) % m; 40 if (now == 0 || dp[now]) ok = 1; 41 dp[now] = 1; 42 } 43 if (ok) puts("YES"); else puts("NO"); 44 } 45 46 } 代码君
题B hdu5777 domino
题意：略
题解：仔细观察发现贪心可解，sort一下即可。
1 /*zhen hao*/ 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <queue> 6 #include <vector> 7 #include <string> 8 #include <stack> 9 #include <set> 10 #include <map> 11 #include <iostream> 12 #include <algorithm> 13 using namespace std; 14 15 #define lson l, m, rt*2 16 #define rson m + 1, r, rt*2+1 17 #define xx first 18 #define yy second 19 20 typedef pair<int,int> pii; 21 typedef long long ll; 22 typedef unsigned long long ull; 23 24 const int N = 1e5 + 10; 25 int d[N]; 26 27 int main() { 28 // freopen("case.in", "r", stdin); 29 30 int T; 31 cin >> T; 32 while (T--) { 33 int n, k; 34 scanf("%d%d", &n, &k); 35 for (int i = 0; i < n - 1; i++) { 36 scanf("%d", d + i); 37 } 38 sort(d, d + n - 1, greater<int>()); 39 ll sum = 0; 40 for (int i = k - 1; i < n - 1; i++) { 41 sum = sum + d[i]; 42 } 43 printf("%I64d\n", sum + n); 44 } 45 46 } 代码君
题C hdu5778 abs
题意：略
题解：质因子都是2说明这个数一定是平方数，然后对于x，我们先把它去个根的sx，然后我们枚举距离这个sx最近的距离d，然后判断d的质因子是不是都是一个。还有一个问题，我们取得这个sx可能sx+1更优，所以要先判断一下哪个距离x更近。
1 /*zhen hao*/ 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <queue> 6 #include <vector> 7 #include <string> 8 #include <stack> 9 #include <set> 10 #include <map> 11 #include <iostream> 12 #include <algorithm> 13 using namespace std; 14 15 #define lson l, m, rt*2 16 #define rson m + 1, r, rt*2+1 17 #define xx first 18 #define yy second 19 20 typedef pair<int,int> pii; 21 typedef long long ll; 22 typedef unsigned long long ull; 23 24 const int N = 1e5 + 10; 25 bool vis[N]; 26 vector<int> p; 27 28 void init() { 29 for (int i = 2; i < N; i++) if (!vis[i]) 30 for (int j = i + i; j < N; j += i) vis[j] = 1; 31 for (int i = 2; i < N; i++) if (!vis[i]) p.push_back(i); 32 } 33 34 bool check(ll n) { 35 if (n < 2) return false; 36 int m = (int)sqrt(n + 0.5); 37 for (int i = 0; i < (int)p.size() && p[i] <= m; i++) if (n % p[i] == 0) { 38 int c = 0; 39 while (n % p[i] == 0) { 40 n /= p[i]; 41 c++; 42 } 43 if (c > 1) return false; 44 } 45 return true; 46 } 47 48 int main() { 49 // freopen("case.in", "r", stdin); 50 51 init(); 52 int T; 53 cin >> T; 54 while (T--) { 55 ll x; 56 scanf("%I64d", &x); 57 ll sx = (ll)sqrt(x + 0.5); 58 if (abs(sx * sx - x) > abs((sx + 1) * (sx + 1) - x)) ++sx; 59 int d = 0; 60 while (true) { 61 if (check(sx + d)) break; 62 if (check(sx - d)) break; 63 d++; 64 } 65 ll res = 1e18; 66 if (check(sx + d)) res = min(res, abs(x - (sx + d) * (sx + d))); 67 if (check(sx - d)) res = min(res, abs(x - (sx - d) * (sx - d))); 68 cout << res << endl; 69 } 70 71 } 代码君
题D 5779 Tower Defence
题意：略
题解：太弱了，第一眼看不到题解的状态转移，实际上题解的状态转移描述得已经够专业了。但是我是结合代码才看得懂(/▽╲)！！这里详细地解释一下怎么转移的吧，毕竟都把代码看懂了。
题目说最短路不是k，很容易由反证法得到这个最短路是小于k的。
先定义一个状态数组，f(i,j,k)表示与1连接的那个连通块（包括1）的size，当前的最短路是j，得到这个最短路的点数是k。
我们发现如果想要最短路的长度加一，那么必须是从非连通块里面的点连到这k个点的其中x个(1 <= x <= k)，所以我们要枚举接下来的连通块以外的新点的个数x，目的是更新状态f(i+x,j+1,x)。
转移：（假设上一层是k个点，下一层是x个点）
（1）对于第二层的每个点x，从第一层的k个点里面人选1到k个连边，方法数是2 ^ k - 1。
（2）对于第二层的每个点x自己互相连边，方案数是2 ^ (x * (x - 1) / 2)，因为共有这么条边，可以连也可以不连
（3）这个最难想，因为我们增加了x个点，那么原来图中有多少个点是可以换位置的呢？答案就是非1和非最短路为j的点，所以由i - k - 1个点里面选x作为最短路为j+1的点。
这三步我们得到了f(i,j,k)。
给定n和k怎么得到答案呢？枚举与1连通的点，然后剩余的点可以乱排，同样要考虑排列组合。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 #define lson l, m, rt*2 6 #define rson m + 1, r, rt*2+1 7 #define xx first 8 #define yy second 9 10 typedef pair<int,int> pii; 11 typedef long long ll; 12 typedef unsigned long long ull; 13 14 const int N = 61, mod = 1e9 + 7; 15 ll f[N][N][N], C[N][N], p2[N * N], p2_1[N]; 16 17 void add(ll& a, ll b) { 18 a += b; 19 if (a >= mod) a -= mod; 20 } 21 22 void init() { 23 for (int i = 0; i < N; i++) { 24 C[i][0] = 1; 25 for (int j = 1; j <= i; j++) 26 add(C[i][j], (C[i - 1][j] + C[i - 1][j - 1]) % mod); 27 } 28 // cout << C[5][3] << endl; 29 p2[0] = p2_1[0] = 1; 30 for (int i = 1; i < N * N; i++) p2[i] = p2[i - 1] * 2 % mod; 31 for (int i = 1; i < N; i++) p2_1[i] = (p2[i] + mod - 1) % mod; 32 // cout << p2[5] << ' ' << p2_1[5] << endl; 33 f[1][0][1] = 1; 34 for (int i = 1; i < N; i++) 35 for (int j = 0; j < i; j++) 36 for (int k = 1; k <= i; k++) if (f[i][j][k]) { 37 ll tmp = f[i][j][k]; 38 for (int l = 1; l + i < N; l++) { 39 tmp = tmp * p2_1[k] % mod; 40 ll val = tmp; 41 val = val * p2[l * (l - 1) / 2] % mod; 42 val = val * C[i + l - 1][l] % mod; 43 add(f[i + l][j + 1][l], val); 44 } 45 } 46 } 47 48 ll get_ans(int n, int k) { 49 ll ans = 0; 50 for (int i = 1; i <= n; i++) 51 for (int j = 0; j < k; j++) 52 for (int l = 1; l <= i; l++) if (f[i][j][l]) { 53 ll tmp = f[i][j][l]; 54 tmp = tmp * C[n - 1][n - i] % mod; 55 tmp = tmp * p2[(n - i) * (n - i - 1) / 2] % mod; 56 add(ans, tmp); 57 } 58 return ans; 59 } 60 61 int main() { 62 // freopen("case.in", "r", stdin); 63 64 init(); 65 int T; 66 cin >> T; 67 while (T--) { 68 int n, k; 69 cin >> n >> k; 70 cout << get_ans(n, k) << '\n'; 71 } 72 73 return 0; 74 } 代码君
题E hdu5780 gcd
题意：略
题解：实际上官方题解已经写得很详细了，我再复述有点多余(/▽╲)改天有空补上这个公式证明吧，希望我不会忘记。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 #define lson l, m, rt*2 6 #define rson m + 1, r, rt*2+1 7 #define xx first 8 #define yy second 9 10 typedef pair<int,int> pii; 11 typedef long long ll; 12 typedef unsigned long long ull; 13 14 const int N = 1e6, mod = 1e9 + 7; 15 int phi[N + 10]; 16 ll s[N + 10]; 17 18 void phi_table() { 19 phi[1] = 1; 20 for (int i = 2; i <= N; i++) if (!phi[i]) 21 for (int j = i; j <= N; j += i) { 22 if (!phi[j]) phi[j] = j; 23 phi[j] = phi[j] / i * (i - 1); 24 } 25 for (int i = 1; i <= N; i++) 26 s[i] = (s[i - 1] + phi[i]) % mod; 27 } 28 29 ll quick(ll a, ll b, ll c) { 30 ll ret = 1; 31 while (b > 0) { 32 if (b & 1) ret = ret * a % c; 33 b = b / 2; 34 a = a * a % c; 35 } 36 return ret; 37 } 38 39 ll get_ans(int x, int n) { 40 if (x == 1) return 0ll; 41 ll ret = 0; 42 ll inv = quick(x - 1, mod - 2, mod); 43 for (int i = 1, j; i <= n; i = j + 1) { 44 j = n / (n / i); 45 ll sd = 2ll * s[n / i] - 1; 46 ll a0 = quick(x, i, mod), qn = quick(x, j - i + 1, mod) + mod - 1; 47 ll tmp = a0 * qn % mod; 48 tmp = tmp * inv % mod; 49 tmp = (tmp + mod - (j - i + 1)) % mod; 50 tmp = sd * tmp % mod; 51 ret += tmp; 52 if (ret >= mod) ret -= mod; 53 } 54 return ret; 55 } 56 57 int main() { 58 // freopen("case.in", "r", stdin); 59 60 phi_table(); 61 int T; 62 cin >> T; 63 while (T--) { 64 int x, n; 65 scanf("%d%d", &x, &n); 66 cout << get_ans(x, n) << endl; 67 } 68 69 return 0; 70 } 代码君
转载于:https://www.cnblogs.com/zhenhao1/p/5724177.html
