前言

得分:$100+90+100+10+0=300$

排名 $\text{rk9}$

只能说把我这个月的 $rp$ 都用光了……

(话说要是我 T2 不是因为没特判丢了 $10$ 分我就可以 $\text{rk6}$ 了 qwq

考试过程

$00:00$

考试开始电脑出毛病了,收不到试卷(

稳了下心态,告诉了 mjl,然后他用他的 U 盘给我拷到电脑上了……

$00:05$

开始看试卷。看到 T1 先推了一下发现了规律,但是看了一下数据以为循环会超时(最多就 $60^+$次循环怎么会超呢我又被降智了真的是),然后跑过去看 T2。

$00:10$

看到 T2 挺适合记忆化暴搜的就写了,然后过了样例之后手造了一个极限数据看时间也没超限就跑了(然鹅并没有加特判 qwq。

$00:25$

回头看 T1,心想着就先打一个 log2 试试有没有这个函数吧……(顺便加了个 cmath)结果发现真的有?太好了,然后测了一下样例发现没过,经过手动分析和手动打表发现要加向上取整(虽然不知道为啥)然后把 T1 写出来了。

$00:35$

看了一下后面 $3$ 道,等等,T5 我好像见过,是区间 dp……但是想不起来了,再加上我记得它是道蓝题(应该是吧),然后 T4 又看得我自闭,就去切 T3 了(本来看到树不想做的……)

$00:40$

惊奇发现需要建树(其实并不需要),然而我又不会根据两个遍历的序列建树……考前问了 mjl 的,他也给我讲了,可是我没理解。

没办法只能硬着头皮上了……

$01:10$

程序弄好了,然后,递归层数超限了。

$01:30$

bug 没改过来,然后突然发现建树要用 bfs。当时脑子 what 一心只想建树没想到 bfs 直接输出就行了 qwq 心灰意冷把 dfs 全删了之后开始写 bfs……

$01:45$

rnm bfs 还是错的!(核心代码没改……)

$02:00$

草……原来我分析的时候把中序和后序搞混了吗……改过来就好了。

$02:30$

分析完了怎么把孩子求出来,写好了结果发现没用,又不想删掉,就注释掉了(喜提 $\text{3k}$ 代码……)。

$02:45$

添加了层数的条件并修好了几个小 bug,过了样例。

$02:50$

自己造了几组数据,都没有问题,准备去看后面骗分啦

$03:00$

草草草没多少时间了!赶紧看了看 T4,没思路,于是开始写 T5 $O(n^3)$ 暴力……并且过了两个样例。

$03:20$

开始养老,直至结束。


题解

T1

想到思路应该是不难的,但是要证明……emm……

首先观察可得每个小白鼠都有死和活两种情况,所以,$k$ 只小白鼠可以找出最多 $2^k$ 瓶酒中的毒药。

进一步,有 $n$ 瓶毒酒,当且仅当 $k$ 满足 $2^{k-1}<n\le 2^k$ 时,$k$ 为 $n$ 的正确答案。

那怎么证明呢?用二进制。

假如说有 $6$ 瓶酒,我们把它们编号为 $0,1,2,3,4,5$。

二进制:

酒的编号的二进制的 $1/0$ 其实代表了这一位代表的老鼠(最高位代表第一只老鼠,后面以此类推)喝/不喝这瓶酒。

那么就推出了方案:

第一只喝 $4,5$

第二只喝 $2,3$

第三只喝 $1,3,5$

所以也可以看出有些情况有多种解是因为 $0\sim 2^k-1$ 中选 $n$ 个不同的数字可以任意选,可能有多种选法。

关于代码的实现,异常简单,异常暴力,可以用 cmath 头文件里的 log2 函数。记得向上取整和开 long long

Code

1
2
3
4
5
6
7
8
9
10
11
#include<cstdio>
#include<cmath>
#define ll long long
ll bottle,ans;
int main(){
freopen("wine.in","r",stdin);
freopen("wine.out","w",stdout);
scanf("%lld",&bottle);
printf("%lld",(ll)ceil(log2(bottle)));
return 0;
}

T2

记忆化暴搜。记得特判 $-1$。

$dp_{i,j}$ 代表前 $i$ 首曲子弹完音量为 $j$ 的情况是否存在,如果存在直接存 $j$ 更加方便。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<cstdio>
#include<cstring>
#define max(a,b) (a)>(b)?(a):(b)
int begin,MAX,n,c[55],dp[55][1005];
int dfs(int t,int v){
if(t==n+1) return v;
if(dp[t][v]!=-1) return dp[t][v];
int a=0,b=0;
if(v-c[t]>=0) a=dfs(t+1,v-c[t]);
if(v+c[t]<=MAX) b=dfs(t+1,v+c[t]);
return dp[t][v]=max(a,b);
}
int main(){
freopen("volume.in","r",stdin);
freopen("volume.out","w",stdout);
memset(dp,-1,sizeof(dp));
scanf("%d %d %d",&n,&begin,&MAX);
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
int t=dfs(1,begin);
if(!t) printf("-1");
else printf("%d",t);
return 0;
}

T3

bfs 每层遍历,需要记录层数。

那如何根据后序遍历和中序遍历来确定一棵树呢?

首先我们知道后序遍历是按照“左——右——根”的顺序遍历的,所以每一个部分的根节点都必然在那个区域的最后。在中序遍历里找到这个根节点,把左右两边分为左子树和右子树,然后再在后序遍历里面找到这两个子树的节点所在的区域(它们一定是连续的)。然后再继续求解两个子树……(注意因为是 bfs 所以这一层的会先求解完再求解子树)。

我打得很麻烦,相当于把树建出来了,删掉注释部分就差不多可以了 qwq。

Code

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<cstdio>
#include<queue>
#include<vector>
#define max(a,b) (a)>(b)?(a):(b)
using namespace std;
struct jd{
int data,l,r,f;
}tree[305];
struct node{
int L,R,root,midr,f;
}t1,t2;
int n,t;
int m[305],l[305];
void find_tree(int a,int b,int c,int d,int e){
queue<node> q;
t1.root=a,t1.L=b,t1.R=c,t1.midr=d,t1.f=e;
q.push(t1);
while(!q.empty()){
t1=q.front();
q.pop();
int mid;
for(int i=1;i<=n;i++){
if(l[t1.root]==m[i]){
mid=i;
break;
}
}
//存结点
tree[++t].data=l[t1.root];
tree[t].f=t1.f;
int long_r=t1.midr-mid;
//左子树入队
if(t1.R-long_r-t1.L){
t2.L=t1.L,t2.R=t1.R-long_r-1,t2.root=t1.R-long_r-1,t2.midr=mid-1,t2.f=t1.f+1;
//tree[t].l=l[t2.R];
q.push(t2);
}else tree[t].l=-1;
//右子树入队
if(long_r){
t2.L=t1.root-long_r,t2.R=t1.root-1,t2.root=t1.root-1,t2.midr=t1.midr,t2.f=t1.f+1;
//tree[t].r=l[t2.R];
q.push(t2);
}else tree[t].r=-1;
}
return;
}
int main(){
freopen("z.in","r",stdin);
freopen("z.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&m[i]);
for(int i=1;i<=n;i++) scanf("%d",&l[i]);
find_tree(n,1,n,n,1);
//根据 l 和 r 的 data 值对应其下标
/*for(int i=1;i<=n;i++){
//左孩子
if(tree[i].l!=-1){
int s=0;
for(int j=1;j<=n;j++){
if(tree[i].l==tree[j].data){
s=j;
break;
}
}
tree[i].l=s;
}
//右孩子
if(tree[i].r!=-1){
int s=0;
for(int j=1;j<=n;j++){
if(tree[i].r==tree[j].data){
s=j;
break;
}
}
tree[i].r=s;
}
}*/
//test
//for(int i=1;i<=n;i++) printf("%d %d %d %d %d\n",i,tree[i].data,tree[i].l,tree[i].r,tree[i].f);
//输出
int maxf=0;
for(int i=1;i<=n;i++) maxf=max(maxf,tree[i].f);
printf("%d ",tree[1].data);
int l=2,r=1;
for(int i=2;i<=maxf;i++){
vector<int> print;
l=r+1,r=l;
while(tree[r].f==i) r++;
r--;
//printf("%d %d %d\n",i,l,r);
if(i&1){ // <-
for(int j=r;j>=l;j--) printf("%d ",tree[j].data);
}else{ // ->
for(int j=l;j<=r;j++) printf("%d ",tree[j].data);
}
}
return 0;
}
/*
7
4 2 5 1 6 3 7
4 5 2 6 7 3 1
*/

T4

Click here!


T5

二分 + $\text{check}$ 函数。

二分需要的金币数量,这个没啥好说的。

$\text{check}$ 函数的话,我没用单调队列的优化,而是 dp。我的想法是用 $dp_i$ 代表跳到第 $i$ 个格子能获得的最大数字之和。于是用两层循环,第一层 $i$ 从 $1$ 到 $n$,代表走到第几个格子了,第二层 $j$ 把走过的都扫一遍,然后求最大值:dp[i]=max(dp[i],dp[j]+a[i]位置的数字大小)

注意如果目前枚举到的地方比较靠近边缘,有可能是没有办法跳到的,所以可以加一个关于是否能跳到的优化,如果跳不到可以直接 break 掉第二层循环。

Code

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
#include<cstdio>
#include<cstring>
#define int long long
#define max(a,b) (a)>(b)?(a):(b)
const int MAXN=(int)5e5+5;
int n,k,d,sum,l,r;
int dp[MAXN];
struct square{
int x,s;
}a[MAXN];
//check函数
bool check(int mid){
memset(dp,128,sizeof(dp));
l=k-mid;
r=k+mid;
dp[0]=0;
for(int i=1;i<=n;i++){
for(int j=i-1;j>=0;j--){
if(a[i].x-a[j].x>r) break;
if(a[i].x-a[j].x<l) continue;
dp[i]=max(dp[i],dp[j]+a[i].s);
if(dp[i]>=d) return 1;
}
}
return 0;
}
//二分函数
int f(int l,int r){
if(l>r) return 0;
if(l==r) return l;
int mid=(l+r)>>1;
if(check(mid)) return f(l,mid);
else return f(mid+1,r);
}
signed main(){
freopen("jump.in","r",stdin);
freopen("jump.out","w",stdout);
scanf("%lld %lld %lld",&n,&k,&d);
for(int i=1;i<=n;i++){
scanf("%lld %lld",&a[i].x,&a[i].s);
sum+=(a[i].s>0ll)?a[i].s:0ll;
}
//printf("%lld %lld\n",sum,d);
if(sum<d){
printf("-1");
return 0;
}
int t=f(0ll,1000ll);
printf("%lld",t);
return 0;
}

总结

感觉还行?就是 T2 没特判,T5 暴力没骗到分……

去学 whk 了,拜拜ヾ(•ω•`)o~