div1初中组，div2高中组。

老板：你既是初中生，也是高中生。

~~然而我只是个无辜的小六生。~~

赛时过程：

其实Div1和Div2都做得烂爆了qwq。

Div1前三道一看签到题，爆切了直接过。

然后后面的题卡死了……

比赛最后十分钟发现E看错题了，瞬间想到正解，可是有什么用呢，于是比赛就这样结束了。

于是我除了签到题就是爆零了。/kk

比赛后评讲是只用了一半时间就AK的银牌爷deaf，stO deaf Orz,deafAKIOI是我们的神，deaf太强了，deafAKIOIeveryday

赛后题解：

A题：$n$ 个球，每个球标有一个数字，问你最少修改多少个小球上的数字能使得最多有 $k$ 个不同数字出现在小球上。

纯签到送分。直接放代码。

#include <cstdio>
#include <algorithm>
#include <queue>

int a[200002];
std::priority_queue<int> q;

int main() {
int n, k, t(0), len(1);
scanf("%d%d", &n, &k);
for (int i(1); i <= n; ++ i) scanf("%d", a + i);
std::sort(a + 1, a + n + 1);
a[0] = a[1] - 1;
for (int i = 2; i <= n; ++ i) if (a[i] != a[i - 1]) q.push(len), len = 1; else ++ len;
q.push(len);
int ans(n);
while (q.size() && k --) ans -= q.top(), q.pop();
printf("%d", ans);
}

B题：一个 $n$ 层的数字金字塔上有 $n(n+1)\div 2$ 个非负整数。当一个数字的左上方和右上方没有数字时就可以被取走。现在要取走恰好 $k$ 个数，并且使拿走的最小数最小。请你帮忙计算，可能取走的最小数是多少。

#include <cstdio>
#include <cstring>

int a[210][210], mark[210][210];

inline int dfs(int x, int y) {
if (mark[x][y]) return 0;
mark[x][y] = true;
if (x == 1 && y == 1) return 1;
if (y == 1) return dfs(x - 1, 1) + 1;
else if (x == y) return dfs(x - 1, y - 1) + 1;
else return dfs(x - 1, y - 1) + dfs(x - 1, y) + 1;
}

int main() {
int n, k, ans(0x7fffffff);
scanf("%d%d", &n, &k);
for (int i(1); i <= n; ++ i) for (int j(1); j <= i; ++ j) scanf("%d", &a[i][j]);
for (int i(1); i <= n; ++ i) for (int j(1); j <= i; ++ j) if (a[i][j] < ans) {
memset(mark, 0, sizeof mark);
if (dfs(i, j) <= k) ans = a[i][j];
}
printf("%d", ans);
}

C题，不想说题面了qwq：

#include <cstdio>
#include <queue>
#include <vector>
#define int long long

struct node {
int x, y;
inline bool operator < (const node X) const {return x < X.x;}
} a[500005];

inline int min(const int x, const int y) {return x < y ? x : y;}
bool mark[500005][7];
std::priority_queue<node> q;

signed main() {
int m, n, ans(0LL);
scanf("%lld%lld", &m, &n);
mark[1][0] = mark[1][1] = mark[1][2] = mark[1][3] = mark[1][4] = mark[1][5] = true;
for (int i(1); i <= n; ++ i) scanf("%lld%lld", &a[i].x, &a[i].y), q.push(a[i]);
for (int i(0); i <= m; ++ i) {
if (q.empty()) {
printf("%lld", ans);
return 0;
}
for (int j(0); j <= 5; ++ j) if (mark[i][j]) {
node t(q.top());
if (i + q.top().y - 1 <= m) mark[i + t.y][j] = true, ans += t.x * t.y, q.pop();
else ans += t.x * (m - i + 1), q.pop(), q.push(node {t.x, t.y - (m - i + 1)});
}
}
printf("%lld", ans);
}

D题：

将 $n$ 拆分为若干个分数 $\frac{a_i}{b_i}$ 的和，满足以下条件：

$a_i, b_i$ 都是正整数
$b_i$ 是 $n$ 的约数
$b_i$ 严格单调递增
求方案数 $mod 2^{31}$。

赛场上想到了正解的一半，讲完了觉得真的是个大水题。

就把每个因数看成背包乱搞。理论上有 $O(\sqrt{n})$ 个因数。然而众所周知这个上界完全是假的，实际情况也就 $O(logn)$ 的常数倍左右而已，所以可以轻松通过。

这题都没做出来，我真是个菜逼。

#include <cstdio>
#include <cmath>
#define int long long

int f[1000005], p[2005], cnt;

signed main() {
int n;
scanf("%lld", &n);
for (int i(n - 1); i >= 2; -- i) if (n % i == 0) p[++ cnt] = i;
f[0] = 1LL;
for (int i(1); i <= cnt; ++ i)
for (int j(p[i]); j < n; ++ j) f[j] += f[j - p[i]], f[j] %= (1 << 31);
printf("%lld", f[n - 1]);
}

E题：

不说了这题看题问题没搞出来题目都懒得说。

#include <cstdio>
#include <algorithm>
#define int long long

inline int max(const int x, const int y) {return x > y ? x : y;}
struct Line {
int l, r;
inline bool operator < (const Line x) const {return l < x.l;}
} a[300005], b[300005];

int cnta, cntb;

signed main() {
int n, m, ans(0LL), MaxR(0LL), len(0LL);
scanf("%lld%lld", &n, &m);
for (int i(1); i <= n; ++ i) {
int x, y;
scanf("%lld%lld", &x, &y);
x <= y ? a[++ cnta] = Line {x, y} : b[++ cntb] = Line {y, x};
}
std::sort(a + 1, a + cnta + 1), std::sort(b + 1, b + cntb + 1);
ans = m;
if (cntb == 0) return printf("%lld", ans), 0;
MaxR = b[1].r, len = b[1].r - b[1].l;
for (int i(2); i <= cntb; ++ i) if (b[i].r > MaxR)
len += b[i].r - max(MaxR, b[i].l), MaxR = b[i].r;
printf("%lld\n", ans + (len << 1));
return 0;
}

F题：

整场比赛唯一一道难题。

NKOJ上一共有 $n$ 道题，题目编号 $1$ 到 $n$，每道题都有一个难度系数，第 $i$ 题的难度系数为正整数 $p_i$。

NK信竞队总共有 $m$ 名同学，编号 $1$ 到 $m$。何老板给每个同学都安排了解题任务。其中第 $i$ 号同学的任务是在编号在 $a_i$ 到 $b_i$ 之间的题中，任选一道，并刷掉它。

不过，NK的同学们都很懒，他们总会选难度最低的题来做，每个同学都有一个解题能力值 $c_i$，同学们是不会去做难度系数超过其解题能力的题的。比如第 $i$ 号同学会从 $[a_i, b_i]$ 中选难度系数最低的题出来，如果这个题的难度系数大于 $c_i$，号同学就会放弃解题，进入自闭状态，并表示自己”太菜了”。
同学们的解题习性让何老板很是烦恼，何老板想给每道题都设定一个合适的难度系数，使得同学们完成的题目的难度系数总和尽量大。

请你帮助何老板设定每道题的难度系数，并计算出所有人完成题目的难度系数总和的最大值。

~~首先题目非常真实好评。~~

非常好也很妙的题，考试里就deafakioi一个人做出来。

先猜一猜复杂度（滑稽），$O(n^2m)$ or $O(n^3m)$

是一道关于线段覆盖的题目。首先应该想到区间DP，~~然而我太弱了没想到~~。

显然每道题的难度只为设为所有 $c_i$ 中的一个。

状态：$f[i][j]$ 表示做题区间完全包含在 $[i,j]$ 中的同学完成的题目难度系数最大的总和。

方程：$f[i][j] = max${$f[i][k - 1] + f[k + 1][j] + S$}$(i\le k\le j)$

$S$ 表示所有经过 $k$ 的线段的最大难度系数总和。

然而有问题，因为我们不知道 $[i,k-1],[k+1,j]$ 里是否有更简单的题。

所以修改状态：$f[i][j][x]$ 表示做题区间完全包含在 $[i,j]$ 中的同学完成的题目难度系数最大的总和，且最简单的一道题难度为 $x$。将每道题的难度（$c_i$）离散化一下。

方程：$f[i][j][x] = max${$g[i][k - 1][x] + g[k + 1][j][x] + S$}$(i\le k\le j)$

其中 $g[i][j][x]$ 表示所有 $f[i][j][k]$ 的最大值，$k\ge x$。

其中，$x$ 为完全包含在区间 $[i,j]$ 内的线段的难度系数。$S$ 为所有经过点 $k$ 并且被完全包含在 $[i,j]$ 内的线段的数量乘上 $x$。

现在只有一个问题，就是 $S$ 怎么算？

神爷deaf给我们讲了这东西的套路：$h[i][j]$ 表示完全包含在 $[i,j]$ 内的区间数量。则完全包含在 $[i,j]$ 中且经过点 $k$ 的线段数量为 $h[i][j]-h[i][k-1]-h[k+1][j]$。我们用区间数量乘上 $x$ 就行了。$h[i][j]$ 可以很简单地预处理出来。

时间复杂度 $O(n^3m)$

差不多完事了？

$Code:$

#include <cstdio>
#include <algorithm>

struct node {
int l, r, x, p;
inline bool operator < (const node X) {return x < X.x;}
} a[4001];
int f[51][51][4001], g[51][51][4001], h[51][51][4001], Key[4001];
inline int max(const int x, const int y) {return x > y ? x : y;}
inline int min(const int x, const int y) {return x < y ? x : y;}

int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i(1); i <= m; ++ i) scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].x);
std::sort(a + 1, a + m + 1);
Key[a[1].p = 1] = a[1].x;
for (int i(2); i <= m; ++ i)
Key[a[i].p = (a[i].x != a[i - 1].x) + a[i - 1].p] = a[i].x;

for (int k(1); k <= m; ++  k)
for (int i(1); i <= a[k].l; ++ i)
for (int j(a[k].r); j <= n; ++ j) ++ h[i][j][a[k].p];
for (int i(1); i <= n; ++ i)
for (int j(i); j <= n; ++ j)
for (int k(a[m].p - 1); k; -- k)
h[i][j][k] += h[i][j][k + 1];

for (int l(1); l <= n; ++ l)
for (int i(1); i <= n - l + 1; ++ i) {
int j(i + l - 1);
for (int x(1); x <= m; ++ x) if (a[x].l >= i && a[x].r <= j) {
for (int k(i); k <= j; ++ k)
g[i][j][a[x].p] = f[i][j][a[x].p] = max(f[i][j][a[x].p], g[i][k - 1][a[x].p]
+ g[k + 1][j][a[x].p] + (h[i][j][a[x].p] - h[i][k - 1][a[x].p] -
h[k + 1][j][a[x].p]) * Key[a[x].p]);
}
for (int x(a[m].p - 1); x; -- x) g[i][j][x] = max(g[i][j][x], g[i][j][x + 1]);
}
int ans(0);
for (int i(1); i <= a[m].p; ++ i) ans = max(ans, f[1][n][i]);
printf("%d", ans);
}

G题：

有点意思，但是不难，这题一眼看上去数论难题又排在最后一位，我没敢看，结果其实不难。

传送门

首先，让我们求平方和肯定是有原因的嘛QAQ（（（

可以看成两个装置同时取珠，两个装置输出了相同的序列则答案加一。
~~这个很好理解吧（（（~~

然后：$f[i][j][x][y]$ 表示第一个装置上管道取到了 $i$ 个珠子，下管道取到了 $j$ 个珠子，第二个装置同理。

因为 $i+j=x+y$，所以最后那一维可以不要。

最后滚动一下就好了。

#include <cstdio>
#include <algorithm>
#include <cstring>

const int MOD = 1024523;
inline int max(const int x, const int y) {return x > y ? x : y;}
inline int min(const int x, const int y) {return x < y ? x : y;}
inline void upd(int& x, const int y) {if ((x += y) >= MOD) x -= MOD;}
char a[501], b[501];
int dp[2][501][501];

int main() {
int n, m;
scanf("%d%d\n%s\n%s", &n, &m, a + 1, b + 1);
std::reverse(a + 1, a + n + 1), std::reverse(b + 1, b + m + 1);
dp[0][0][0] = 1;
for (register int i(0); i <= n; ++ i) {
int t(i & 1), t2(i - 1 & 1);
memset(dp[t], 0, sizeof dp[t]);
if (i == 0) dp[0][0][0] = 1;
for (register int j(0); j <= m; ++ j)
for (register int k(max(0, i + j - m)); k <= min(i + j, n); ++ k) {
int l(i + j - k), &f(dp[t][j][k]);
if (i && k && a[i] == a[k]) upd(f, dp[t2][j][k - 1]);
if (i && l && a[i] == b[l]) upd(f, dp[t2][j][k]);
if (j && k && b[j] == a[k]) upd(f, dp[t][j - 1][k - 1]);
if (j && l && b[j] == b[l]) upd(f, dp[t][j - 1][k]);
}
}
printf("%d", dp[n & 1][m][n]);
}

zqs`s blog

NKOJ元旦欢乐赛Div1总结

赛时过程：

赛后题解：

$Code:$