程序员进阶之算法练习（五）
前言
这次的题目质量非常高，除了第一道签到题之外都是很不错的想法题，值得学习。
- 几乎所有的程序员都能做A题；
- 思维缜密的程序员可以做B题；
- 数学还没还给老师的能做C题；
- 接受过算法训练的能过D,E题；
看完题目大意，先思考，再看解析；觉得题目大意不清晰，点击题目链接看原文。
A
题目大意：2个人，投掷n次骰子，大的赢，问谁赢，平局输出"Friendship is magic!^^"。
题目解析：
如题，照着写即可。
B
题目大意：n个城市，第i和i+1之间有一条边，第n个和第1个有边。n个城市中有k个特殊城市，与n个城市之间都存在边。每个城市有一个权重ci，边(i, j)的值为ci * cj。 求所有边的值的和。
代码实现：
long long sum = 0, ans = 0, n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> c[i];
sum += c[i];
}
for (int i = 1; i <= m; ++i) {
long long k;
cin >> k;
flag[k] = 1;
sum -= c[k];
ans += c[k] * sum;
}
for (int i = 1; i <= n; ++i) {
int next;
if (i == n) {
next = 1;
}
else {
next = i + 1;
}
if (!flag[next] && !flag[i]) {
ans += c[i] * c[next];
}
}
cout << ans;题目解析：
首先n个城市形成一个环，其次每一个特殊城市都会新增若干条边。任意两个城市之间最多只有一条边。
第1个特殊城市a1，新增n条边，其中2条边和环重叠;
第i个特殊城市ai，新增n条边，其中2条边和环重叠，i-1条边和之前特殊城市形成的边重叠；
为了便于计算，先不考虑环。
第1个特殊城市a1，新增n条边；
第i个特殊城市ai，新增n条边，i-1条边和之前特殊城市形成的边重叠；
先计算出所有特殊城市产生的边；
对于环上的边，如果两点都不是特殊城市，那么是还没计算过的边；
可以求出总和。
C
题目大意：n个点形成的多边形，整体以v的速度向x轴负方向移动；点P从（0，0）向（0，w）以最大u的速度前进。问，不撞到多边形的最短到达时间。（相交不算碰撞）
代码实现：
long long sum = 0, ans = 0, n, w, v, u;
cin >> n >> w >> v >> u;
double k = u * 1.0 / v, ret = 0, l = w * 1.0 / u, minT = 10E9, maxT = -10E9;
while (n--) {
long long x, y;
cin >> x >> y;
double t = y - k * x;
minT = min(minT, -t / k);
maxT = max(maxT, -t / k);
}
if (minT >= 0) {
ret = l;
}
else if (maxT <= 0) {
ret = l;
}
else {
ret = l + maxT / v;
}
printf("%.6lf", ret);题目解析：
为了达到最短时间，并且点与多边形碰撞，可以知道会有如下结果：
1、点直接到（0，w）；
2、点在行进过程中等待若干时间，到达（0，w）；
核心：变换参考系，假设多边形不动，把v的速度叠加到点P上，那么变成点P以-v的速度在x轴运动。
求出每个点相对点P的速度斜率曲线在X轴上的距离，得到最大和最小的两个值minT和maxT。
如果minT>=0或者MaxT<=0，点P可以直接到达点w；（多边形太远和太近两种情况）
其他情况，点P要在x轴移动maxT的距离，再直线到达点w。（在x轴移动maxT的距离相当于等待maxT/v的时间）
D
题目大意：给出有n个数字的数组a, 有m个询问。 (1 ≤ n ≤ 1 000 000)（1 ≤ ai ≤ 10e9) (1 ≤ m ≤ 1 000 000)
询问给出两个数字l, r。(1 ≤ l ≤ r ≤ n)
在区间l, r中，把出现偶次的数字统计出来。对这些数字求异或，得到询问的值。
代码实现：（树状数组）
int low_bit(int x) {
return x & (-x);
}
void tree_add(int x, int v) {
while (x <= n) {
tree[x] ^= v;
x += low_bit(x);
}
}
int tree_sum(int x) {
int sum = 0;
while (x) {
sum ^= tree[x];
x -= low_bit(x);
}
return sum;
}题目解析：
区间求值，数据量极大，可以猜测是从区间相减来求子区间的值，从这里出发。
l, r区间的偶数次的数字的异或和为sumA；
l, r区间的奇数次的数字的异或和为sumB；
sumA ^ sumB的值为什么？
l, r区间段所有数字的异或和！
其中sumB直接对l, r所有的区间求异或和即可；（偶次的会为0）
重点就是l, r的不重复的异或和。
用map<int, int> 来维护ai上一次出现的位置，如果ai已经出现，那么在原来的位置进行异或即可。
于是变成区间l, r求和。
这个是树状数组最擅长的事情了。
E
题目大意：n个数字，从中选取m个数字，使得乘积S被k整除。如果有多个组合，m最小；还有多个，S最小。(1 ≤ n ≤ 1 000, 1 ≤ k ≤ 10e12).
代码实现：
int n;
long long k;
cin >> n >> k;
long long t = sqrt(k);
for (long long i = 1; i <= t; ++i) {
if (k % i == 0) {
vec.push_back(k / i);
vec.push_back(i);
}
}
int vecSize = vec.size();
sort(vec.begin(), vec.end());
for (int i = 0; i < vecSize; ++i) {
Hash[vec[i]] = i;
}
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
b[i] = gcd(a[i], k);
}
if (k == 1)
{
cout << 1 << endl;
cout << min_element(a + 1, a + 1 + n) - a << endl;
return 0;
}
for (int j = 1; j < vecSize; ++j) {
dp[0][j] = make_pair(n + 1, 0);
}
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < vecSize; ++j) {
long long gcdnum = gcd(b[i], vec[j]);
int pre = Hash[vec[j] / gcdnum];
dp[i][j] = min(dp[i - 1][j], make_pair(dp[i - 1][pre].first + 1, dp[i - 1][pre].second + a[i]));
}
}
if (dp[n][vecSize - 1].first > n) {
cout << -1 << endl;
return 0;
}
else {
cout << dp[n][vecSize - 1].first << endl;
int pre = vecSize - 1;
for (int i = n; i > 0; --i) {
if (dp[i][pre] == dp[i - 1][pre]) {
continue;
}
printf("%d ", i);
pre = Hash[vec[pre] / gcd(vec[pre], b[i])];
}
}题目解析：
求出k的所有非1因子集合T，那么对于数字ai，不为T的因子没有用。
那么题目变成：
一堆物品，每个物品都有相应的cost（数量，大小），要把背包背满（可以超过），使得总数量最小，并且总数字和最小。
题目非常明显的是DP。
dik 表示前i个数字，第j个因子有k个的最小总数和最小数字和。
最后在所有 dnk 中第j个因子中，k大于题目要求中，寻找最小值即可。
dik 根据第i个数的因子，有：
dik = min(di - 1k, di-1k-t) s、t取决于k的第j个因子的个数。
状态复杂度n*k的因子数K，10^12的因字数不会超过45个，按50个算。那么状态数最大为 50000个。
转移复杂度为O（1）。
那么总得复杂度O(N x K).
这种做法的难点在于，对于一个数字，转移的时候无法通过一个式子来表达。（一个数字有多个参数）
换一种dp的表示方式。
求出K的所有约数，15=1,2,3,5,15。
于是，一个数的状态可以表示成从左到右的移动。
dpi表示前i个数字，能前进到第j个的最优解。
dpi = min(dpi-1, dpi-1 + 1);
题目可解。复杂度O(N * K). K为因子个数
卡在某个地方很久：
bi = gcd(ai, k);
可以优化，减少gcd的复杂度。
总结
任务和娱乐全在一念之间。
同样的Codeforces，在训练期间是任务，毕业之后却是娱乐。
任务重要是完成，娱乐却是要让自己满意。
如今很愿意花时间在Codeforces上，即使如今的选择比以前更多。