概况
第二次完整考试模式复盘了。
这次比上次有进步的地方，但是更多是我对自己状态不满的地方。
比如明明写好了对拍程序，却没写srad(time(NULL))，赛后一交OJ就麻了…
比如明明是个模拟题，但是却往着数据结构优化啥的奇怪方向去想，于是这题也麻掉了…
比如明明是个状压$DP$板子题，然后我转移方程的时候考虑错了情况，于是就没了分…
考试时能不能避免好这些问题？能不能考到出线的成绩？能不能达到自己的预期？
写完这套决定告一段落，留着2020的那一套考前练一下手（好耶）。
题目
*表格来源于：https://blog.csdn.net/weixin_43914593/article/details/113520868
平方和
答案：2658417853
签到题。
只要写个拆位判断是否含有$2,0,1,9$就行了，没有特别注意的地方。
赛时代码（AC）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include <bits/stdc++.h>
using namespace std;
bool check(int num){
while(num)
{
int tmp = num % 10;
num /= 10;
if(tmp == 2 || tmp == 0 || tmp == 1 || tmp == 9)
return true;
}
return false;
}
int main(void)
{
long long sum = 0;
for(int i = 1; i <= 2019; i++)
if(check(i)) sum += 1LL * i * i;
printf("%lld\n", sum);
return 0;
}
|
数列求值
答案：4659
签到题。
只取后四位的话，对$10000$取模即可。
所求数列的项数并不大，而且不需要提交到OJ限时解决问题，因此不需要矩阵快速幂优化。
赛时代码（AC）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include <bits/stdc++.h>
using namespace std;
int main(void)
{
int l1 = 1, l2 = 1, l3 = 1;
for(int i = 4; i <= 20190324; i++)
{
printf("%d %d %d\n", l1, l2, l3);
system("Pause");
int now = l1 + l2 + l3;
l1 = l2; l2 = l3; l3 = now;
l1 %= 10000; l2 %= 10000; l3 %= 10000;
}
printf("%d\n", l3);
return 0;
}
|
最大降雨量
答案：34
思维题。
本来想写多个搜索验证一下的，但是没想到什么有效的搜索做法就作罢了。
既然题目是要求中位数，那么，我们可以简化一下问题，将最后用符咒的情况划分为$7*7$的表格。
并且，这个表格可以构造为有序的。
此时，可以确定$49$会在表格的右下方。那么，为了使最终的降雨量足够的大，可以如图构造。
迷宫
搜索题。
题目要求步数最小，且字典序最小。
因此，我们选用$BFS$，并人为规定每步搜索时，搜索顺序为$D,L,R,U$。
这样，如果一旦搜索到终点，则此时的答案一定为步数最小，且字典序最小的。
$BFS$还有个去重问题，由于我们要求步数最小，因此，先入队列的坐标一定能够达到更优的步数。只需要使用$set$判断坐标是否重复即可。
赛时代码（AC）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include <bits/stdc++.h>
#define maxn 55
using namespace std;
char board[maxn][maxn];
char qread(){
char ch = getchar();
while(ch != '0' && ch != '1') ch = getchar();
return ch;
}
struct Step{
int x, y;
int num;
string detail;
};
bool operator < (const Step &A, const Step &B){
return A.x == B.x ? A.y < B.y : A.x < B.x;
}
set<Step> s1;
queue<Step> q1;
int fx[] = {0, 1, 0, 0, -1};
int fy[] = {0, 0, -1, 1, 0};
char d[] = {'#', 'D', 'L', 'R', 'U'};
string bfs(){
q1.push((Step){1, 1, 0, ""});
s1.insert((Step){1, 1, 0, ""});
while(!q1.empty())
{
Step tmp = q1.front(); q1.pop();
if(tmp.x == 4 && tmp.y == 6)
{
return tmp.detail;
}
for(int i = 1; i <= 4; i++)
{
int nx = tmp.x + fx[i];
int ny = tmp.y + fy[i];
int ns = tmp.num + 1;
string nd = tmp.detail + d[i];
if(board[nx][ny] == '1') continue;
if(nx < 1 || ny < 1 || nx > 4 || ny > 6) continue;
if(!s1.count((Step){nx, ny, ns, nd}))
{
s1.insert((Step){nx, ny, ns, nd});
q1.push((Step){nx, ny, ns, nd});
}
}
}
return "NULL";
}
int main(void)
{
for(int i = 1; i <= 4; i++)
for(int j = 1; j <= 6; j++)
board[i][j] = qread();
cout << bfs() << endl;
return 0;
}
|
RSA解密
数论题。
这题差不多弄了我半个小时多。
首先，可以通过$O(\sqrt{n})$的算法枚举寻找$p,q$中的一个后，相除得到另一个数。
此时，已知：
1
| p = 891234941, q = 1123984201
|
数了一下数字位数，发现$long \ long$也只是勉强能够存下$n$。
于是，我采用了拓展欧几里得而不是快速幂，求解$d \cdot x - (p - 1)(q - 1) \cdot y = 1$来计算出$x$（也就是$e$）。
由$gcd { d, (p-1)(q-1) } = 1$，得方程一定有整数解。
求解得：
此时，似乎只能用快速幂来计算密文了。
但$long \ long$几乎肯定会溢出，由于不知道$C++$选手赛场上有没有$Python$用，我继续思考有没有方法可以避免溢出。
好在以前写过一些题，接触到了$__int128$这个类型，于是就套上来做了。
最后也顺利求得了结果。
这道题主要是各种地方我都不太熟练所以卡卡的，写了很久。
比如拓欧忘了怎么写，手推了一下。以及$__int128$的输出方式，研究了好一会。
最后得密文：
赛事代码（略混乱，AC）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include <bits/stdc++.h>
#define int unsigned long long
#define ull unsigned long long
using namespace std;
unsigned long long now = 1001733993063167141;
void exgcd(int a, int b, int &x, int &y){
if(b == 0)
{
x = 1; y = 0;
return;
}
exgcd(b, a % b, x, y);
int tmp = x;
x = y;
y = tmp - a / b * x;
}
__int128 a;
__int128 qpow(__int128 a, __int128 b, __int128 p){
if(b == 0)
{
return 1;
}
__int128 tmp = qpow(a, b / 2, p);
tmp = ((tmp % p) * (tmp % p)) % p;
if(b & 1) tmp = (tmp * a) % p;
return tmp;
}
void print(__int128 now){
if(now > 9) print(now / 10);
putchar(now % 10 + '0');
}
signed main(void)
{
__int128 ans = qpow(20190324, 823816093931522017, 1001733993063167141);
print(ans);
return 0;
}
|
完全二叉树的值
基本送分的编程题？
因为是完全二叉树，且节点不超过$1e5$，因此完全可以用$(x<<1)$和$(x<<1)+1$来表示$x$的左右节点。
如果是普通二叉树的值，且数据不随机，还要考虑斜树（专门用来卡上面那种表示方法），菊花树（偶尔在一些树的题目能拿来卡一些奇怪的做法）等等特殊情况。
要注意的一点就是$max(权值)$，这个值初值一定要赋的足够小，容易遗忘，在后面手造小数据的时候才发现。
赛时代码（AC）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include <bits/stdc++.h>
#define lson(x) (x << 1)
#define rson(x) (x << 1) + 1
#define int long long
#define maxn 1000005
using namespace std;
int n, maxx = -(1 << 30), pos, a[maxn], dep[maxn], vis[maxn];
void dfs(int x, int d){
if(x > n) return;
dep[d] += a[x];
dfs(lson(x), d + 1);
dfs(rson(x), d + 1);
}
signed main(void)
{
scanf("%lld", &n);
for(int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
dfs(1, 1);
for(int i = 1; i <= log2(n) + 1; i++)
if(maxx < dep[i])
{
maxx = dep[i];
pos = i;
}
printf("%lld\n", pos);
return 0;
}
|
外卖店优先级
简单模拟题。
我白给了。
想错了方向以为需要配套什么乱七八糟的数据结构来优化我枚举时间的过程。
实际上，只需要按照时间排序后枚举任务，就能很好完成这道题。
需要特别注意的一点是，置于优先队列内，添加由于当下点单增加的积分，置出优先队列内的顺序问题。
赛时代码（0 pts，TLE）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int n, m, t, ts[maxn], id[maxn];
int prio[maxn];
int main(void)
{
scanf("%d %d %d", &n, &m, &t);
for(int i = 1; i <= m; i++)
scanf("%d %d", &ts[i], &id[i]);
for(int i = 1; i <= t; i++)
{
for(int j = 1; j <= n; j++)
{
int flag = 0;
for(int k = 1; k <= m; k++)
{
if(ts[k] == i && id[k] == j)
{
flag++;
}
}
if(flag) prio[j] += 2 * flag;
else if(prio[j]) prio[j] --;
}
}
int cnt = 0;
for(int i = 1; i <= n; i++)
if(prio[i] > 3)
{
printf("%d %d\n", i, prio[i]);
cnt++;
}
printf("%d\n", cnt);
return 0;
}
|
赛后补题（AC）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int n, m, t, las[maxn], proi[maxn], can[maxn];
struct sta{
int ts;
int id;
} order[maxn];
bool cmp(const sta &A, const sta &B){
return A.ts < B.ts;
}
int main(void)
{
scanf("%d %d %d", &n, &m, &t);
for(int i = 1; i <= m; i++)
scanf("%d %d", &order[i].ts, &order[i].id);
sort(order + 1, order + m + 1, cmp);
for(int i = 1; i <= m; i++)
{
if(las[order[i].id] && las[order[i].id] != order[i].ts)
proi[order[i].id] = max(0, proi[order[i].id] - (order[i].ts - las[order[i].id] - 1));
if(proi[order[i].id] <= 3) can[order[i].id] = 0;
proi[order[i].id] += 2;
if(proi[order[i].id] > 5) can[order[i].id] = 1;
las[order[i].id] = order[i].ts;
}
int ans = 0;
for(int i = 1; i <= n; i++)
{
if(las[i] != t)
proi[i] = max(0, proi[i] - (t - las[i]));
if(proi[i] > 5) can[i] = 1;
else if(proi[i] <= 3) can[i] = 0;
ans += can[i];
}
printf("%d\n", ans);
return 0;
}
|
修改数组
数据结构题？
赛后在网上搜索才发现，大部分写法都是并查集。
赛时我读完题后发现，如果写暴力模拟的算法，最消耗时间的部分是$+1$的过程。
因此，需要优化这个过程，观察数据范围，考虑需要$log(n)$的算法。
此时观察权值，发现极限情况下权值也不会超过$1e6+1e5$。
于是，我使用$set$，并在其中插入了$1 \sim 1e6+1e5$。
若存在这个集合内，则是允许插入的数字（可以理解为集合内的数字为可用的位置）。
因此，每次只需要判断$a[i]$是否在集合内出现过。
若有，则直接插入，然后从集合中删除这个元素。
若无，则由$set$本身的有序性，使用$upper_{-}bound$查询集合内第一个大于等于$a[i]$的元素，即为可以插入的空缺。
坦白说不确定真正的赛场上能不能拿到这么多的分数，但是$NewOnlieJudge$上面$AC$了，还是很不错的。
赛时代码（AC）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include <bits/stdc++.h>
#define maxn 1100005
using namespace std;
set<int> s1;
int n, maxx, a[maxn], ans[maxn];
int main(void)
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]), maxx = max(maxx, a[i]);
for(int i = 1; i <= maxx + n + 5; i++) s1.insert(i);
for(int i = 1; i <= n; i++)
{
if(s1.count(a[i]))
{
ans[i] = a[i];
s1.erase(a[i]);
}
else
{
int now = *(s1.upper_bound(a[i]));
s1.erase(now);
ans[i] = now;
}
}
for(int i = 1; i <= n; i++)
printf(i == n ? "%d\n" : "%d ", ans[i]);
return 0;
}
|
赛后，学习了并查集的写法。
不得不说这个写法非常精妙。
以$1,2,1,2$为例：
这时我们发现，普通的并查集如果在$1,1,1,1,1,\dots,1$的输入数据下，使用并查集维护时会退化成一条链，最差的时间复杂度为$O(n)$。
因此，我们使用路径压缩，来达到既能够准确指向下一个空位，又能快速指向下一个空位。
赛后补题（AC）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include <bits/stdc++.h>
#define maxn 2000005
using namespace std;
int n, a[maxn], ans[maxn], uset[maxn];
int find(int x){
return x == uset[x] ? x : uset[x] = find(uset[x]);
}
int main(void)
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= maxn; i++) uset[i] = i;
for(int i = 1; i <= n; i++)
{
if(find(a[i]) == a[i])
{
ans[i] = a[i];
uset[a[i]] = find(a[i] + 1);
}
else
{
ans[i] = find(a[i]);
uset[ans[i]] = find(ans[i] + 1);
}
}
for(int i = 1; i <= n; i++)
printf(i == n ? "%d\n" : "%d ", ans[i]);
return 0;
}
|
糖果
状压$DP$板子题。
板子题！
虽然是个板子题，但仍应该先写一个保证正确性的搜索。
赛时代码（搜索）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include <bits/stdc++.h>
#define maxn 105
using namespace std;
int n, m, k, ans = 105, t[maxn], used[maxn];
void dfs(int sta, int cost){
if(sta == (1 << m) - 1)
{
ans = min(ans, cost);
return;
}
if(cost > ans) return;
for(int i = 1; i <= n; i++)
{
if(used[i]) continue;
used[i] = 1;
dfs(sta | t[i], cost + 1);
used[i] = 0;
}
}
int main(void)
{
scanf("%d %d %d", &n, &m, &k);
for(int i = 1; i <= n; i++)
{
int tmp, sta = 0;
for(int j = 1; j <= k; j++)
{
scanf("%d", &tmp);
sta |= (1 << (tmp - 1));
}
t[i] = sta;
}
dfs(0, 0);
printf("%d\n", ans == 105 ? -1 : ans);
return 0;
}
|
然后，开始考虑优化。
估算设计状态为$dp[sta]=购入糖果包数$，$sta$为压缩的目前吃到的糖果种类，直接状压$DP$，时间复杂度为$O(n*2^m)$，能够通过该题。
编写对拍程序后，验证方程正确性：
1
| dp[i] = min(dp[i], dp[i - t[j]] + 1);
|
很不幸的是，这个方程是存在很明显漏洞的。
因为吃不同包的糖果有可能吃到相同口味的糖果，因此，这里使用dp[i - t[j]]来实现只能做所有口味糖果都来自不同包且各包之间不重叠味道的情况。
然后很不幸的是，本来能够通过对拍程序发现的问题，由于忘了设srand(time(NULL))，就完全没有起到对拍应有的作用。
最后交上去的时候，$NewOnlineJudge$好像还是比较友情的给了$30$.
（不过如果是真的比赛应该已经爆零了）
真的是一步错步步错。
意识到这个问题之后，方程改为：
1
| dp[i | t[j]] = min(dp[i | t[j]], dp[i] + 1);
|
顺利通过该题。
赛后补题（AC）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <bits/stdc++.h>
#define maxn 105
using namespace std;
int n, m, k, t[maxn], dp[(1 << 22)];
void print(int x){
vector<int> v1;
while(x) v1.push_back(x % 2), x /= 2;
for(int i = v1.size() - 1; i >= 0; i--)
printf("%d", v1[i]);
putchar('\n');
}
int main(void)
{
scanf("%d %d %d", &n, &m, &k);
for(int i = 1; i <= n; i++)
{
int tmp, sta = 0;
for(int j = 1; j <= k; j++)
{
scanf("%d", &tmp);
sta |= (1 << (tmp - 1));
}
t[i] = sta;
}
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for(int i = 0; i <= (1 << m) - 1; i++)
{
for(int j = 1; j <= n; j++)
{
dp[i | t[j]] = min(dp[i | t[j]], dp[i] + 1);
}
}
printf("%d\n", dp[(1 << m) - 1] > 100 ? -1 : dp[(1 << m) - 1]);
return 0;
}
|
组合数问题
原题：【清华集训2016】组合数问题
这道题的题解准备战略性先放弃后面的$60$分，修为到家再学。
前$40$分还是比较容易的，是$NOIP$的一道签到题。利用杨辉三角的特性计算组合数（便于取模），再利用二维前缀和打表$2000*2000$以内的答案，就可以在$O(n^2)$预处理后$O(1)$回答询问。
写的时候时间很紧，因为前面那道饱了么还没怎么优化（事实证明是方向错了…），铁拿不了多少分。
然后就东拆西凑补出来了。
赛时代码（40 pts，较乱）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include <bits/stdc++.h>
#define maxn 2005
#define mod 1000000007
#define int long long
using namespace std;
int t, n, m, k, ca[maxn][maxn], sum[maxn][maxn];
signed main(void)
{
scanf("%lld %lld", &t, &k);
ca[0][0] = 1;
for(int i = 1; i <= 2000; i++)
{
ca[i][0] = 1;
for(int j = 1; j <= i; j++)
{
ca[i][j] = (ca[i - 1][j - 1] + ca[i - 1][j]) % k;
}
}
for(int i = 1; i <= 2000; i++)
{
for(int j = 1; j <= 2000; j++)
{
sum[i][j] = (sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]) % mod;
if(j <= i && ca[i][j] == 0)
sum[i][j]++;
}
}
while(t--)
{
scanf("%lld %lld", &n, &m);
printf("%lld\n", sum[n][m]);
}
return 0;
}
|
总结
这次对自己还是很不满意的。
很多地方明显生疏（拓展欧几里得现场推，__int128不太会用）。
并且在转移方程上面犯下了不可饶恕的错误。
$5+5+10+10+15+15+0+20+7.5+10$
$97.5/150$
出线感觉还是有点困难欸。
如果状压那题能$AC$，就是$110$了，应该会稳很多吧。
希望真正上场的时候能够给力一点U•ェ•*U。