前言
最近几个月在做逻辑思维僵化的康复训练，刚好大学的教练说能争取到一个比赛的名额，于是兴致勃勃找了原来的队友和一个老学长，愉快的报名参加比赛。
于是开始组队做做练习赛，这次的练习题目是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题是树形背包+贪心。
