前面的话
南大软院的推送 我方计软智 还有谁能闲过放寒假的大学生呢？闲着也是闲着，便玩了玩这几场赛
有趣的题
数字游戏
题意
给一串数,每次可以将其中相邻的两个数相减(结果正负均可)，将结果放回，问最后剩下的数最大是多少
题解
由于这题中间结果有对称性，所以可以认为每个数都可以取它或它的相反数，而由于第一次操作必然会一正一负。所以答案是$\sum |a_i|$的基础上，如果所有数正负性相同，便再减去$2\times \min |a_i|$
家园树
题意
给出一棵带整数权的树，问最少修改权值几次能使其变为二叉搜索树
题解
二叉搜索树的中序遍历是升序序列，我们只需将原二叉树的中序序列通过修改改成升序序列即可。剩下来的这个序列上的经典问题只要把数列中的数改为$a_i-i$求最长不下降序列即可。
烤鸡(CF936A)
题意
使用了$k$分钟的大火之后，锅炉就会自动转为小火。厨师每隔$d$分钟就会到厨房去看看，如果它发现锅炉已经变成了小火，则它会把大火重新打开。烤一只鸡如果全用大火需要$t$分钟，全用小火需要$2t$分钟
题解
可以看出其实先大火后小火的过程是有个周期的，即为$(d - k % d) % d$。然后只用计算周期外的用时，分为只用大火和也用小火列式子，解出即可 PS:这题数据好像精度上有些偏差
q = (d - k % d) % d;
x = 2 * t / (2 * k + q);
if (x * (2 * k + q) + 2 * k >= 2 * t)
printf("%lf\n", x * (k + q) + double(2 * t - x * (2 * k + q)) / 2.0);
else printf("%lf\n", x * (k + q) + k + double(2 * t - x * (2 * k + q) - 2 * k));
缆⻋观光
题意
对于位置$x_i,y_i$上有权值$a_i$，现在要从中取出一些位置排好，满足$y_{i-1}>y_i,x_{i-1}\ne x_i$并$(x_{i-2}-x_{i-1})(x_{i-1}-x_i)<0$，使权值和最大
题解
先按$y$排序，设$f(i,0/1)$表示分别由左和右而来的当前最大权值和。用数据结构维护即可
铺地砖
题意
要用五种颜色逆时针给六边形网格染色，要求相邻不重复，每次染选出现次数最少的中编号最小的，问第$N$块格子地颜色应该是什么
题解
当然有推式子的做法。可这题如果暴力地走网格也十分有趣。 可以参考这个网站，可交互设计做的非常好，我自己写采用的是Cube coordinates，当然可以省去一维变成Axial coordinates。
const int dq[] = {1, 1, 0, -1, -1, 0};
const int dr[] = {0, -1, -1, 0, 1, 1};
const int ds[] = {-1, 0, 1, 1, 0, -1};
bool ban_col[6];
int T, n, d = 2, c[6], a[100010], nq = 1, nr = 0, ns = -1, res, res_n;
std::unordered_map<int, int> cols;
inline int cubic_to_int(int q, int r, int s) {return q * 2e6 + r * 2e3 + s;}
int main() {
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
c[1]++; cols[cubic_to_int(0, 0, 0)] = 1; a[1] = 1;
c[2]++; cols[cubic_to_int(1, 0, -1)] = 2; a[2] = 2;
for (int i = 3; i <= 100000; i++) {
if (!cols.count(cubic_to_int(nq + dq[(d + 1) % 6], nr + dr[(d + 1) % 6], ns + ds[(d + 1) % 6]))) d = (d + 1) % 6;
nq += dq[d]; nr += dr[d]; ns += ds[d];
for (int j = 1; j <= 5; j++) ban_col[j] = false;
for (int j = 0; j < 6; j++)
if (cols.count(cubic_to_int(nq + dq[j], nr + dr[j], ns + ds[j])))
ban_col[cols[cubic_to_int(nq + dq[j], nr + dr[j], ns + ds[j])]] = true;
res = 0; res_n = 1e6;
for (int j = 1; j <= 5; j++)
if (!ban_col[j] && c[j] < res_n) {
res = j; res_n = c[j];
}
cols[cubic_to_int(nq, nr, ns)] = res;
c[res]++;
a[i] = res;
}
fead(T);
while (T--) {
fead(n);
printf("%d\n", a[n]);
}
return 0;
}
守护鸽(CF1016C)
题意
给出一个$2*n$的网格，每个格子中有一个数，要求从左上方开始不重不漏地走完所有格子，每个格子得分为 访问序数$\times$格子中的数 ，要使得分最小(原题为最大)
题意
区间和以及区间和点乘一个等差数列是可以用前缀和维护的，剩下的只有写式子了(可这是真的难写)
fead(n);
b[0][0] = 0; c[0][0] = 0;
for (int i = 1; i <= n; i++) {
fead(a[i][0]);
b[i][0] = a[i][0] + b[i - 1][0];
c[i][0] = a[i][0] * (long long)i + c[i - 1][0];
}
b[0][1] = 0; c[0][1] = 0;
for (int i = 1; i <= n; i++) {
fead(a[i][1]);
b[i][1] = a[i][1] + b[i - 1][1];
c[i][1] = a[i][1] * (long long)i + c[i - 1][1];
}
for (int i = 1; i <= n; i++)
if (i & 1) {
tmp = res + ((c[n][0] - c[i - 1][0]) + ((long long)i - 1ll) * (b[n][0] - b[i - 1][0]));
tmp += (2ll * n + (long long)i) * (b[n][1] - b[i - 1][1]) - (c[n][1] - c[i - 1][1]);
if (tmp < ans) ans = tmp;
res += (2ll * i - 1ll) * a[i][0] + (2ll * i) * a[i][1];
}
else {
tmp = res + ((c[n][1] - c[i - 1][1]) + ((long long)i - 1ll) * (b[n][1] - b[i - 1][1]));
tmp += (2ll * n + (long long)i) * (b[n][0] - b[i - 1][0]) - (c[n][0] - c[i - 1][0]);
if (tmp < ans) ans = tmp;
res += (2ll * i) * a[i][0] + (2ll * i - 1ll) * a[i][1];
}
printf("%lld\n", ans - b[n][0] - b[n][1]);
随机游走
题意
给出一个$n\times n$方阵和其中$k$个障碍物位置，求在无数次随机游走(留在此地和走向相邻空格子概率一致)后停在右下三角内的概率(包括副对角线)
题解
先考虑没有障碍的情况，对于$5\times 5$的矩阵，它每个格子的权值如果表示为随机游走能到达的格子则如下:
34443
45554
45554
45554
34443
而如果放置了一个障碍物后则变为
33443
3X454
44554
45554
34443
可以看出停在某个格子的概率就是这个格子的权值(类似于围棋中的气?)比上剩下的总权值
可爱的数列
题意
给出一个长度为$n \leq 10^6$的数列，其中的数$a_i\leq 10^9$，问是否能从中抽出一个长度$\geq \lceil\frac{n}{2}\rceil$的子序列，使子序列的最大公约数大于一
题解
这题被我水过去了，再次向出题人道歉😢 这种什么选一半的题一眼随机。 对于原题的想法很简单，多次随机抽一个数检验它质因数即可 而如果$a_i\leq 10^{18}$非常大，我是这样想的: 第一次多次随机选取两个数求gcd，再用这个gcd和数列中每个数求gcd得到新的数列,第二次可以多次选取新数列中的数进行检验 我没有仔细思考，但这估计可以无需Pollard rho降低数据规模。
最后的话
无论如何还是要感谢南京大学软院的学长无偿地组织了这场比赛并提供了奖品。感谢南京大学和东南大学的学长们出了这些有趣的题目