solve 5(A E F I L)
rank 77
水题总体没有很卡，但提升的题都没有思路，实力差距还是有的。
个人感觉出了的题都是铜牌及以下的难度。
<qj>
思路：
已知两堆的值，我求出它们的差，如果是正数，说明原始堆要挪走一部分；否则，则要从别的堆移一部分过来。
不难证明，为了使花费最小，直接从左到右扫一遍便可，这样一定最优。
两个优先队列，存下标和差值。扫一遍就过了。
B 合约数
预处理出$[2, 10000]$区间内所有数$x$的合约数，假设放在vector $vf[x]$中。这里把$1$当素数看就OK了。
然后，对树做一遍dfs。搜索过程中，统计每一个节点属性值$x$的个数。
进入某个节点$root$时，先记录好在以$root$为根的子树之外的$val_{root}$的合约数个数，再从该节点往下dfs，把搜索到$val_{root}$的合约数个数减去刚开始记录好的，就是以$root$为根的子树中，属性值是$val_{root}$的合约数的节点个数。
#include<bits/stdc++.h> using namespace std; #define MAXN 20010 #define MOD 1000000007LL typedef long long LL; typedef struct{ int to, next; }Edge; Edge tree[MAXN * 2]; int head[MAXN], ecnt, n, p, val[MAXN], cnt[MAXN]; bool is[MAXN]; vector<int> vf[MAXN]; LL ans = 0; void init(){ memset(head, -1, sizeof(head)); ecnt = 0; } void add(int from, int to){ tree[ecnt].to = to; tree[ecnt].next = head[from]; head[from] = ecnt++; } void init0(){ for(int i = 0;i < MAXN;++i)vf[i].clear(); fill(is, is + MAXN, 1); for(int i = 2;i < MAXN;++i){ if(is[i]){ for(int j = i + i;j < MAXN;j += i)is[j] = false; } } for(int i = 2;i < MAXN;++i){ for(int j = 1;j * j <= i;++j){ if(i % j == 0){ if(!is[j])vf[i].push_back(j); if(j * j != i && !is[i / j])vf[i].push_back(i / j); } } } } void dfs(int root, int par){ vector<int> tmp; int x = val[root]; for(int i = 0;i < vf[x].size();++i)tmp.push_back(cnt[vf[x][i]]); for(int i = head[root];~i;i = tree[i].next){ int to = tree[i].to; if(to != par){ dfs(to, root); } } cnt[x]++; for(int i = 0;i < vf[x].size();++i)ans = (ans + root * LL(cnt[vf[x][i]] - tmp[i])) % MOD; } int main(){ // freopen("input.txt", "r", stdin); int T, a, b; init0(); for(scanf("%d", &T);T--;){ init(); scanf("%d%d", &n, &p); for(int i = 1;i < n;++i){ scanf("%d%d", &a, &b); add(a, b), add(b, a); } for(int i = 1;i <= n;++i)scanf("%d", val + i); ans = 0; memset(cnt, 0, sizeof(cnt)); dfs(p, -1); cout << ans << endl; } return 0; }
C 序列变换
D 数字游戏
E 小Y吃苹果
<qj>
抢到了1血表示很开心。
猜个结论便可，要证明也不太难。
G 小Y做比赛
H 小Y与多米诺骨牌
I 二数
<qj>
思路：
对于数字s，我需要求出比s大的sa，比s小的sm
sa：
遍历串s，对于第一个奇数，把该位 +1 ，然后接下来所有位全部改成 '0' 便可。
若该位是9，需要考虑"89"这种情况，如果是9，要进位，下一位的8变成9，就需要继续进位。所以我们需要把9前面连在一起的8全都处理成0，然后在下一位添加一个2。
比如：2888889 就变成了 4000000 ， 88889123456 就变成了200000000000
sm：
遍历串s，对于第一个奇数，把该位 -1，然后接下来所有位全都改成'8'便可。
那么
如果sa - s >= s - sm 答案就是 sm
否则就是 sa
至于这个数字的大小比较，以及减法，需要手写或者套板子。
尝试过java大数，果断超时了。
贴一下模拟减法的板子
string BigInegerMinus(string s1, string s2, bool negative) // s1-s2; { if (s1.size() < s2.size()) { return BigInegerMinus(s2, s1, true); } if (s1.size() == s2.size()) { int i = 0; while(i < s1.size() && s1[i] == s2[i]) i++; if (s1[i] < s2[i]) { return BigInegerMinus(s2, s1, true); } } string res(s1.size(), '0'); int i = s1.size() -1, j = s2.size() - 1; int k = i; int borrow = 0; while(i >= 0 && j >= 0) { int sum = s1[i] - '0' - borrow - (s2[j] - '0'); //cout<<sum<<endl; if (sum < 0) { borrow = 1; sum += 10; res[k--] = sum + '0'; } else{ borrow = 0; res[k--] = sum + '0'; } i--;j--; } while(i >= 0) { int sum = s1[i--] - '0' - borrow; if (sum < 0) { borrow = 1; sum += 10; res[k--] = sum + '0'; } else{ borrow = 0; res[k--] = sum + '0'; } } if (res[0] == '0') { //ignore the prefix '0's int index = 1; while(index < res.size() && res[index] == '0') index++; if (negative) { return "-" + res.substr(index, res.size() - index); } else return res.substr(index, res.size() - index); } else { if (negative) { return "-" + res; } else return res; } }
J 小Y写文章
K 树上最大值
L K序列
一、思路
01背包dp。设，$dp[i][j]$表示在前$i$个数中模$k$累加和为$j$的最长长度。那么，有如下递推式：
$dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i]]+1)$。
需要注意的是：
（1）$j-a[i]$可能为负；
（2）初始状态$dp[0][0]=0$，$dp[0][i]$不存在$(0 < i < k)$。那么，$dp[i][j]$不能由不存在的状态转移过来。
（3）因为$n*k \le 10^7$，所以，直接开辟静态数组行不通，采用二维vector动态开数组即可解决。
二、代码
#include<bits/stdc++.h> using namespace std; #define MAXN 100010 typedef vector<int> vec1d; int n, k, a[MAXN]; int main(){ // freopen("input.txt", "r", stdin); scanf("%d%d", &n, &k); for(int i = 1;i <= n;++i)scanf("%d", a + i); vector<vec1d> dp(n + 5, vec1d(10000010 / n + 5)); for(int i = 0;i <= n;++i){ for(int j = 0;j <= k;++j)dp[i][j] = -1; } dp[0][0] = 0; for(int i = 1;i <= n;++i){ for(int j = 0;j < k;++j){ int t = (j - a[i] + k) % k; t = (t + k) % k; if(dp[i - 1][t] != -1)dp[i][j] = max(dp[i][j], dp[i - 1][t] + 1); if(dp[i - 1][j] != -1)dp[i][j] = max(dp[i][j], dp[i - 1][j]); } } cout << (dp[n][0] == -1 ? 0 : dp[n][0]) << endl; return 0; }