程序员进阶之算法练习（五）
前言
这次的题目质量非常高，除了第一道签到题之外都是很不错的想法题，值得学习。
- 几乎所有的程序员都能做A题；
- 思维缜密的程序员可以做B题；
- 数学还没还给老师的能做C题；
- 接受过算法训练的能过D,E题；
看完题目大意，先思考，再看解析；觉得题目大意不清晰，点击题目链接看原文。
文集：
程序员进阶之算法练习（一）
程序员进阶之算法练习（二）
程序员进阶之算法练习（三）
程序员进阶之算法练习（四）
代码地址
A
题目链接
题目大意：Mishka和Chris投掷n次骰子，每次数字大的赢；
每行输入m[i]和c[i]，表示两人投掷的数字大小，m[i] and c[i] (1 ≤ m[i], c[i] ≤ 6)
如果最后Mishka赢的次数多则输出"Mishka"，如果Chris赢的次数多则输出"Chris"，平局输出"Friendship is magic!^^"。
Examples
input
3
3 5
2 1
4 2
output
Mishka
题目解析：
如题，照着写即可。
B
题目链接
题目大意：n个城市，第i和i+1之间有一条边，第n个和第1个有边。
n个城市中有k个特殊城市，与n个城市之间都存在边。每个城市有一个权重c[i]，边(i, j)的值为c[i] * c[j]。
求所有边的值的和。
第一行输入： n and k (3 ≤ n ≤ 100 000, 1 ≤ k ≤ n)
第二行输入：每个城市的权重，c[1], c[2], ..., c[n] (1 ≤ c[i] ≤ 10 000)
第三行输入：k个城市的序号， id[1], id[2], ..., id[k] (1 ≤ id[i] ≤ n)
Examples
input
4 1
2 3 1 2
3
output
17
样例如图，所有边的值的和是2+2+3+4+6=17。
代码实现：
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个特殊城市a[1]，新增n条边，其中2条边和环重叠;
第i个特殊城市a[i]，新增n条边，其中2条边和环重叠，i-1条边和之前特殊城市形成的边重叠；
为了便于计算，先不考虑环。
第1个特殊城市a[1]，新增n条边；
第i个特殊城市a[i]，新增n条边，i-1条边和之前特殊城市形成的边重叠；
先计算出所有特殊城市产生的边；
对于环上的边，如果两点都不是特殊城市，那么是还没计算过的边；
可以求出总和。
C
题目链接
题目大意：n个点形成的多边形，整体以v的速度向x轴负方向移动；点P从（0，0）向（0，w）以最大u的速度前进。问，不撞到多边形的最短到达时间。（相交不算碰撞）
第一行 n, w, v, u (3 ≤ n ≤ 10 000, 1 ≤ w ≤ 1e9, 1 ≤ v, u ≤ 1000)
接下来n行 x[i] and y[i] ( - 1e9 ≤ x[i] ≤ 1e9, 0 ≤ y[i] ≤ w)
Example
input
5 5 1 2
1 2
3 1
4 3
3 4
1 4
output
5.0000000000
代码实现：
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[i], 有m个询问。 (1 ≤ n ≤ 1 000 000)（1 ≤ a[i] ≤ 10e9) (1 ≤ m ≤ 1 000 000)
询问给出两个数字l, r。(1 ≤ l ≤ r ≤ n)
在区间[l, r]中，把出现偶次的数字统计出来。对这些数字求异或，得到询问的值。
第一行是n，接下来是n个数字；
接下来是m，然后是m行询问，每行包括数字l，r表示询问区间(l, r)；
Example
input
7
1 2 1 3 3 2 3
5
4 7
4 5
1 3
1 7
1 5
output
0
3
1
3
2
代码实现：（树状数组）
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> 来维护a[i]上一次出现的位置，如果a[i]已经出现，那么在原来的位置进行异或即可。
于是变成区间[l, r]求和。
这个是树状数组最擅长的事情了。
E
题目链接
题目大意：n个数字，从中选取m个数字，使得乘积S被k整除。如果有多个组合，m最小；还有多个，S最小。(1 ≤ n ≤ 1 000, 1 ≤ k ≤ 1e12).
输入
第一行：n and k (1 ≤ n ≤ 1 000, 1 ≤ k ≤ 1e12).
第二行：n个数字a[i]，(1 ≤ a[i] ≤ 1e12) ；
输出：
第一行，数字m；
第二行，m个选中的数字的序号；
如果没有解则只输出-1，不用第二行；
Example
input
5 60
2 4 6 5 2
output
3
4 3 1
代码实现：
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，那么对于数字a[i]，不为T的因子没有用。
那么题目变成：
一堆物品，每个物品都有相应的cost（数量，大小），要把背包背满（可以超过），使得总数量最小，并且总数字和最小。
题目非常明显的是DP。
d[i][j][k] 表示前i个数字，第j个因子有k个的最小总数和最小数字和。
最后在所有 d[n][j][k] 中第j个因子中，k大于题目要求中，寻找最小值即可。
d[i][j][k] 根据第i个数的因子，有：
d[i][j][k] = min(d[i - 1][j][k], d[i-1][j-s][k-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。
于是，一个数的状态可以表示成从左到右的移动。
dp[i][j]表示前i个数字，能前进到第j个的最优解。
dp[i][j] = min(dp[i-1][j], dp[i-1][j/gcd(k, x)] + 1);
题目可解。复杂度O(N * K). K为因子个数
卡在某个地方很久：
b[i] = gcd(a[i], k);
可以优化，减少gcd的复杂度。
总结
任务和娱乐全在一念之间。
同样的Codeforces，在训练期间是任务，毕业之后却是娱乐。
任务重要是完成，娱乐却是要让自己满意。
如今很愿意花时间在Codeforces上，即使如今的选择比以前更多。
