比赛链接（已结束）：戳我打开。
比赛时间：15:30~19:00。
估了好久的补偿赛，感觉题目质量还行吧。
第一题：
看到之后居然感觉无从下手？
有了最小的数据范围 $m\leq10$ 之后，想到枚举每个人是否 $Hack$。
打算写之前随便特判了几组数据，然后发现有人已经 $A$ 了？
想写的念头就没了，接着发现 $T \leq 10^7$，算法应该是 $T \log_m$ 的样子吧。
然后还是没什么思路，写了个动态规划。
$f[i]$ 表示花 $i$ 个时间做题能拿到的最大分数，就是个 $0/1$ 背包。
感觉写出来之后是否 $Hack$ 就出来了。
结果发现真的出来了，直接枚举花多长时间做题，剩下的时间 $Hack$ 就行。
但是花这么多时间 $Hack$ 能得到多少的排名呢？
还是需要一个动态规划， $f[i][j]$ 表示前 $i$ 名中 $Hack$ $j$ 名的最少时间花费。
状态转移方程为 $f[i][j]=min(f[i - 1][j], f[i - 1][j - 1] + t[i])$。
二分就行了，时间复杂度为 $O(t\times n + T\times log_m)$，直接提交发现 $A$ 了。
$A$ 了之后才知道会爆啊，洛谷机子是真的快，$n$ 方过百万。
考试结束后听同学说应该把分数作为维度算，反正过了就行了呗(\doge。
考场代码：
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, _t, ans = 0x3f3f3f3f;
int f[10000005], dp[505][505];//f[i]:花费i时间做题所能得到的最大分数
//dp[i][j]:前i个人中Hackj个人所需要花费的最少时间
struct problem {
int t, s;
}a[110];
struct people {
int t, s;
}b[510];
bool cmp (people p1, people p2) {
return p1.s > p2.s || p1.s == p2.s && p1.t < p2.t;
}
int main () {
scanf ("%d%d%d", &n, &m, &_t);
for (int i = 1; i <= n; i ++) scanf ("%d%d", &a[i].t, &a[i].s);
for (int i = 1; i <= m; i ++) scanf ("%d%d", &b[i].t, &b[i].s);
sort (b + 1, b + m + 1, cmp);
for (int i = 1; i <= n; i ++) for (int j = _t; j >= 0; j --) if (j >= a[i].t) f[j] = max(f[j], f[j - a[i].t] + a[i].s);
memset (dp, 0x3f, sizeof dp);
dp[1][0] = 0;
dp[1][1] = b[1].t;
for (int i = 2; i <= m; i ++) {
dp[i][0] = 0;
for (int j = 1; j <= i; j ++)
dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1] + b[i].t);
}
for (int i = 0; i <= _t; i ++) {//枚举花费多长的时间做题
int score = f[i], rank;//所能够得到的分数
int l = 1, r = m, mid;//二分查找该分数的排名
while (l <= r) {
mid = l + r >> 1;
if (b[mid].s > score) l = mid + 1;
else r = mid - 1;
}
rank = r + 1;//当前这个人的排名
int t_ = _t - i;//剩下的可以Hack别人的时间
l = 1;
r = rank - 1;//二分查找最多能Hack前rank名中的几名
while (l <= r) {
mid = l + r >> 1;
if (dp[rank - 1][mid] > t_) r = mid - 1;//需要更多的时间，无法Hack
else l = mid + 1;//可以Hack，扩大左边界
}
ans = min (ans, rank - r);//可以Hack r名，排名由rank名变为rank-r名
}
printf ("%d", ans);
return 0;
}
第二题：
方格路径加强版，考前没复习，打了 $n \leq 10^5$ 的 $40$ 分暴力就没管了。
状态转移方程：$f[1][i] = f[1][i - 1] + f[2][i - 1]$
$f[i][j] = f[i - 1][j - 1] + f[i][j - 1] + f[i + 1][j - 1] (2 \leq i \leq 5)$
$f[6][i] = f[5][i - 1] + f[6][i - 1]]$
如果有障碍物，$f[i][j]=0$
后来看到有些人拿了 $60$ 分，以为拿的是障碍物一格的那个。
仔细一看数据范围有个 $n \leq 10^{18}$，$m \leq 0$，就是个递推啊。
写了个矩阵乘法 $6^3\times log_n$ 考试结束前 $12$ 分钟拿了 $60$ 分。
考场 $60$ 分代码：
#include <iostream>
using namespace std;
const int mod = 1e9 + 7;
long long n, m;
long long x1, y1, x2, y2;
long long f[7][100005], ans[7][7], pre[7][7] = {0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1};
bool a[7][100010];
void time (long long a[7][7], long long b[7][7]) {
long long c[7][7] = {0};
for (int i = 1; i <= 6; i ++)
for (int k = 1; k <= 6; k ++)
for (int j = 1; j <= 6; j ++)
c[i][k] = (c[i][k] + a[i][j] * b[j][k] % mod) % mod;
for (int i = 1; i <= 6; i ++)
for (int j = 1; j <= 6; j ++) a[i][j] = c[i][j];
}
int main () {
cin >> n >> m;
if (m == 0) {
if (n == 1) {
cout << 6;
return 0;
}
else if (n == 2) {
cout << 16;
return 0;
}
for (int i = 1; i <= 6; i ++)
for (int j = 1; j <= 6; j ++) ans[i][j] = 1;
m = n - 2;
while (m) {
if (m & 1) time (ans, pre);
time (pre, pre);
m >>= 1;
}
cout << (ans[1][1] + ans[1][2] + ans[2][1] + ans[2][2] + ans[2][3] + ans[3][2] + ans[3][3] + ans[3][4] + ans[4][3] + ans[4][4] + ans[4][5] + ans[5][4] + ans[5][5] + ans[5][6] + ans[6][5] + ans[6][6]) % mod;
}
else {
for (int i = 1; i <= m; i ++) {
cin >> x1 >> y1 >> x2 >> y2;
for (long long j = x1; j <= x2; j ++)
for (long long k = y1; k <= y2; k ++)
a[j][k] = true;
}
f[1][1] = f[2][1] = f[3][1] = f[4][1] = f[5][1] = f[6][1] = 1;
for (int j = 2; j <= n; j ++) {
if (! a[1][j]) f[1][j] = (f[1][j - 1] + f[2][j - 1]) % 1000000007;
for (int i = 2; i <= 5; i ++)
if (! a[i][j]) f[i][j] = (f[i - 1][j - 1] + f[i][j - 1] + f[i + 1][j - 1]) % 1000000007;
if (! a[6][j]) f[6][j] = (f[5][j - 1] + f[6][j - 1]) % 1000000007;
}
cout << ( ( (f[1][n] + f[2][n]) % 1000000007 + (f[3][n] + f[4][n]) % 1000000007) % 1000000007 + (f[5][n] + f[6][n]) % 1000000007) % 1000000007;
}
return 0;
}
第三题：
毒瘤题，考试的时候以为是结论题，写了不对。
以为是二分题，写一大会儿不出。
然后写 $2^{20}$ 爆搜枚举每一次左拐还是右拐还 $WA$ 了。
发现 $check$ 没查完整地图，查了 $9^4$，改成 $10^4$ 之后 $T$ 了？
就加了一个”随机性剪枝“，反正合法方案肯定很多，如果 $rand() % 107 == 1$ 就 $return$ 掉。
有一个点正好 $999ms$ 卡过，于是就得了 $10$ 分。
第四题：
我打 $2$ 年 $OI$ 总结出来的规律，题目背景很简单的又很难打的就是难题。
于是打了 $5$ 分暴力，后来发现可以打 $O(m\times n) $ 的算法，就求个交集。
然后打出来就 $15$ 分了。
总共：$100+60+10+15=185$ 分，$rank$ $44$，还可以吧。
$wjh(Graygoo):100+100+0+10=210$ 分，$rank$ $29$，%%%
$mxt(Mr_Imposter):20+100+0+0=120$ 分，$rank$ $107$
$yzf(Yang818):60+40+0+15=115$ 分，$rank$ $111$
$wzy(UFO2007):60+40+0+5=105$ 分，$rank$ $117$
标签：中小学生,10,人工智能,dp,rank,int,long,Hack,复赛 From： https://www.cnblogs.com/Xy-top/p/17004445.html