程序员进阶之算法练习（十）2016CCPC东北重现赛
前言
最近几个月在做逻辑思维僵化的康复训练，刚好大学的教练说能争取到一个比赛的名额，于是兴致勃勃找了原来的队友和一个老学长，愉快的报名参加比赛。
于是开始组队做做练习赛，这次的练习题目是2016CCPC东北地区大学生程序设计竞赛-重现赛
这次的题目
正文
看完题目大意，先思考，再看解析；觉得题目大意不清晰，点击题目链接看原文。
A
题目链接 题目大意：n个点，序号从1到n。任意两点之间都存在边，权值为两个点序号的最小公倍数，求：找出包括n个点的最小生成树的最小权值和。 n (2≤n≤1e9）
Sample Input
2 2 3
Sample Output
Case #1: 2 Case #2: 5
代码实现：
lld t;
cin >> t;
for (int i = 1; i <= t; ++i) {
lld n;
cin >> n;
printf("Case #%d: %lld\n", i, (n + 1) * n / 2 - 1);
}题目解析： 签到题。容易知道，和1连的边是最优解，那么选择1为中心，所有点连上1即可。
C
题目链接 题目大意： 给出A，B 2个整数，要求： 找到所有A≤C≤B, A≤D≤B ，且 A/B+B/A≤C/D+D/C的CD，并输出。
Sample Input
2 10 10 9 27
Sample Output
Case #1: 1 10 10 Case #2: 2 9 27 27 9
代码实现：
lld t;
cin >> t;
for (int i = 1; i <= t; ++i) {
lld a, b;
cin >> a >> b;
printf("Case #%d:\n", i);
if (a == b) {
puts("1");
cout << a << " " << b << endl;
}
else {
puts("2");
cout << a << " " << b << endl;
cout << b << " " << a << endl;
}
}题目解析： 签到题。只有两种可能，当A==B，那么1个解；如果A!=B，那么有AB和BA两个解。
E
题目链接 题目大意： 给出n*m的数据矩阵，按照连连看的规则（连线最多由三条直线组成），判断矩阵是否存在解；（不需要消除完毕，只需判断第一步是否有解即可） n and m (1≤n,m≤30)
Sample Input
2 3 3 1 2 1 2 1 2 1 2 1 3 3 1 2 3 2 1 2 3 2 1
Sample Output
Case #1: Yes Case #2: No
样例解释：
样例1可以消去[1, 3] 和 [3, 3]。
代码实现：
bool ok = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (i + 1 < n) {
ok = ok || a[i][j] == a[i+1][j];
}
if (j + 1 < m) {
ok = ok || a[i][j] == a[i][j+1];
}
if (i == 0 || i == n-1) {
for (int k = j + 1; k < m; ++k) {
ok = ok || a[i][j] == a[i][k];
}
}
if (j == 0 || j == m-1) {
for (int k = i + 1; k < n; ++k) {
ok = ok || a[i][j] == a[k][j];
}
}
}
}
if (ok) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}题目解析： 签到题。每个数字只能和上下左右相连，最左最右最上最下可以在同一列/行内相连。
H
题目链接 题目大意： 给出一个栈，现在进行下面四种操作： ∙ PUSH x：push x（x只能是0或者1）到栈顶； ∙ POP： 弹出栈顶； ∙REVERSE： 反转栈，top变成bottom，bottom变成top； ∙QUERY：对top,top-1,top-2, ... , bottom 进行NAND操作，并输出结果（栈内数字不变） NAND的操作如下： 0 nand 0 = 1∙ 0 nand 1 = 1∙ 1 nand 0 = 1∙ 1 nand 1 = 0. 如果没有元素，那么输出"Invalid."
Sample Input
2 8 PUSH 1 QUERY PUSH 0 REVERSE QUERY POP POP QUERY 3 PUSH 0 REVERSE QUERY
Sample Output
Case #1: 1 1 Invalid. Case #2: 0
代码实现：
struct Node {
int left, right, value;
Node(int l, int r, int v)
{
left = l;
right = r;
value = v;
}
Node()
{
}
}node[N * 2];
// 其余代码太长，见git题目解析：
对于现在的栈T，从bottom往上算 1、bottom=0，size>1则ans=1，否则为0； 2、bottom=1，size=1,ans=1； size>1，假设连续的1个数为t，如果size-t<2,则这部分可以忽略；（因为可能为1个0，或者没有，都没影响） size-t>=2,则t=t+1;（长度加1） 最后ans = (t+1)%2;
每个值存三个信息，left, right, value. left表示连续的最左下标； right表示连续的最右下标； 对于一段连续的1，只维护最左点的和最右点的信息即可；
J
题目链接 题目大意： 游戏中一个人穿着suit 穿越一个充满敌人的区域； 每秒会受到A的伤害，人有 H（血量）, V(速度），R（回复）；单位都是1，可以认为每秒先受到攻击，如果血量>=0，则可以回复，否则死亡； 区域的长度为D； @胡钧 人的初始H/V/R 都是0，现在可以increase H/V/R， 代价分为是 G1/G2/G3；（每次increase1，速度不能大于D） 问穿越的最小代价 1 <= D,A <= 500000, 1 <= G1, G2, G3 <= 200
代码实现：
lld t;
cin >> t;
for (lld k = 1; k <= t; ++k) {
lld ans = 0x7fffffff7fffffffll;
lld bug[3];
lld d, a, g1, g2, g3;
cin >> d >> a >> g1 >> g2 >> g3;
for (lld v = 1; v <= d; ++v) {
lld x, y = v, z;
lld rTime = d / v; // 能回复的次数
if (rTime * v == d) {
--rTime;
}
lld lose = round(1.0 * d * a / v); // 总共被攻击的血量
if (lose * v < d * a) {
++lose;
}
if (g1 * rTime >= g3) {
x = a;
}
else {
x = lose;
}
if (rTime == 0) {
z = 0;
}
else {
z = (lose - x) / rTime;
if (z * rTime < lose - x) {
++z;
}
}
if (x * g1 + y * g2 + z * g3 < ans) {
bug[0] = x, bug[1] = y, bug[2] = z;
}
ans = min(ans, x * g1 + y * g2 + z * g3);
ans = ans;
}
printf("Case #%lld: %lld\n", k, ans);题目解析： 要求G1/G2/G3的数量，假设是x/y/z。 枚举y，算出通过时间T=float(D/V)，T'=round(D/V)为回血次数； 根据题目有，x>=A 而且 x - T * A + T’ * z >= 0，这里我们可以做一次贪心，假设最后的结果为x - T * A + T’ * z = 0，推出 z表达式； 把z的表达式带入xG1 + yG2 + z*G3，求出关于x的一次函数。 然后根据x的系数的正反，我们可以直接求出x的最优解（一次函数的最优解要么最左，要么最右），然后根据z的表达式求出z。
总结
作为一个练习赛，并且三个人分别在上海、珠海、广州，只能通过打字和语音交流，然后其中两个还是要上班的猿，能把这套题做完全靠那个不上班的牛。 B题是并查集+DFS。 D题是矩阵压缩+BFS。 F题是DFS。 G题是极角排序+DP。 I题是线段树+预处理。 K题是树形背包+贪心。
最后的成果
腾讯云开发者
