前言
得分：$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$
开始养老，直至结束。
题解
想到思路应该是不难的，但是要证明……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;
}
|
记忆化暴搜。记得特判 $-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;
}
|
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;
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;
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);
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--;
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;
}
|
Click here!
二分 + $\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];
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;
}
if(sum<d){
printf("-1");
return 0;
}
int t=f(0ll,1000ll);
printf("%lld",t);
return 0;
}
|
总结
感觉还行？就是 T2 没特判，T5 暴力没骗到分……
去学 whk 了，拜拜ヾ(•ω•`)o~
