luogu初赛模拟题解
minstdfx
·
·
个人记录
题链
1.A ----------------------
-114的补码
114=57*2 =01110010
57=28*2+1=00111001
28=14*2 =00011100
14=7*2 =00001110
7=3*2+1 =00000111
3=1*2+1 =00000011
1 =00000001
反:10001101
补=反+1=10001110
另外提一嘴lowbit的x&-x是基于补码表示法的
2.B ----------------------
不解释
3.C ----------------------
a=1
b=2
c=3
z=26
aa=26*1+1
az=26*1+26
BYT=26*26*2+25*26+20=2022
4.B ----------------------
24bit*(0.125bit/1byte)*4096*2160=26542080 byte = 25.3125 Mb
5.A ----------------------
快排思想期望O(n)
int findkth(int a[],int k,int l,int r)
{
int mid=rand()%(r-l+1)+l;
int base=a[mid];
swap(a[mid],a[l]);
int i=l,j=r;
while(i<j)
{
while(i<j && a[j]>=base) --j;
if(a[j]<base) a[i++]=a[j];
while(i<j && a[i]<base) ++i;
if(a[i]>=base) a[j--]=a[i];
}
a[i]=base;
if(k-1<i) return findkth(a,k,l,i-1);
else if(k-1>i) return findkth(a,k-(i-l+1),i+1,r);
else return a[i];
}
6.C ----------------------
(1) X
5 4
1 2
2 3
3 1
1 4
(2) O
(3) O
(4) X
7.A ----------------------
合(chai)并(fen)果子，n=4，暴力手推
5 10 13 14
merge(5,10) = 15
13 14 15
merge(13,14)= 27
15 27
merge(15,27)= 42
15+27+42=84
8.B ----------------------
把树画出来
HGBDAFEC frontfirst
BGHFAEDC mid
H为根
BG|H|FAE D C
H|GB|D AFE C
H 1
/ \
G 2 D 3
/ / \
B4 A 6 C 7
/ \
F12 E 13
9.C ----------------------
a=1 b=0 c=1
a&&b || b&&c = (a&b) | (b&c) = (1&0) | (0&1) = 0
a+b>c || b = (1+0>1) || 0 = 0
!(!c&&(!a||b)) = ! ( 0 && ****** ) = 1
a+b+c=2
10.B 理想情况 = 你懂得
11.D 直接枚举 18 过程略 自证不难
12.B
13.A
首先 rand%k的值域为 [0,k) = [0,k-1]
[a,b) = a+[0,b-a) = a+rand()%(b-a)
[a,b]闭区间在上面找
14.C 7*6/2-(7-1)=21-6=15
15.D 我怎么知道，查百度吧（考试遇到这种狗题凭感觉瞎**猜
16-21.记忆化搜索 ----------------------
1.(16) F
2.(17) T
3.(18) T 去掉记忆化结果不变
4.(19) T 不解释
5.(20) B 手膜
6.(21) A
22-27 ----------------------
2遍Floyd 求合并两个点(虫洞连接)的时候最小的 所有点的距离的和
1.(22) F 你说呢
2.(23) F 这题我错了
#2.(23)T 我不知道这道题对于复杂度的定义是什么，如果是要精确求到这种地步的话就是要算的，
#复杂度=O(k1*n^3+k2*m+k3)
#感觉m相对于n^3可以忽略，事实上我们分析算法复杂度的时候基本上也是这么干的
3.(24) T 不加虫洞完全图 10000*4950=49500000合并两个点之后少了一个10000 49490000>1e7
4.(25) T 不干扰
5.(26) A 啊这
6.(27) A
28-33 膜数好评 ----------------------
杨辉三角+二维前缀和
1.(28) F i=j a[i][j]=1
2.(29) F 组合数
3.(30) F 取过%了
4.(31) T
5.(32) C 不解释 #upd:模数加两次不会爆，这样才能证明此题正确
6.(33) C 从1开始算
34-38
1.(34) C
2.(35) D 注意当某个点取的条件需要前驱全部废掉没有入度
3.(36) D w代表这个点能否取 显然下一个与目前的点相反，由于w∈{0,1} 所以 !w = 1-w
4.(37) A 每个没有前驱的点开始
5.(38) C 不解释
39-43
1.(39) C 后缀和，注意到后面从n-1开始
2.(40) B 不解释
3.(41) D 减去最小值再除以目前的个数(n-i+1)-1(即n-i)
4.(42) C 统计答案不解释
5.(43) B 统计答案不解释
UPD:完全图的边数计算错了，我太菜了qwq
UPD:稍微修改了一下细节
UPD:误用均摊一词，已修改为期望