前行 - CSP2019全国排位 Day1

两道题想到正解然后都写炸了 不知道在干什么


Part1. 总结(不重要)

这几天的状态不算特别好(从打 AGC 打爆开始),后面的几场 OI 制的模拟赛都不是特别顺畅。还有一种以前的“习惯写不出正解”的奇怪心态。

这次 noi.ac 的模拟赛其实不算难 —— 赛后,前两道题修修补补就过了,第三题的正解也非常好理解,基本上赛后不到一个小时就把这些题补完了。总的说来,这次体现出来的主要缺漏有两个:

  1. 不会分析时间复杂度
  2. 不会推导数学性质(这是硬伤)
  3. (其实还有一小点别的)

第一点体现在 T2,其实考试时就想到了正解,然后误判成了一个 $O(n^2)$ 的算法,以为只是一个部分分,数组只开了部分分的范围……

第二点就是 T3,根本就没有往正解的 $\sum a_i\le a_t+b_t$ 这个式子去想。


Part2. 题面

T1. 序列

有一种生成数列的方式:

给定参数 $k,A=(a_0,a_1,\dots,a_k)$ ,生成一个无限长的数列,其中第 $i$ 项为 $\sum_{j=0}^ka_ji^j$

现给出 $m$ 组 $k_i,A_i=(a_{i,0},a_{i,1},\dots,a_{i,k})$ ,按上面的规则生成 $m$ 个无限长的序列。然后把这 $m$ 个序列合并起来再从小到大排序,求得到的新序列的第 $n$ 项。

保证答案不超过 $10^{18}$。

数据规模:$1\le n\le10^5$,$1\le m\le3\times10^4$,$1\le k\le7$,$0\le a_i\le1000$。

T2. 积木

一块积木长为 2 高为 1,用这样的积木搭起一面无限高、无限宽的墙,并定义坐标系(每块积木的左边部分的横纵坐标奇偶性相同),如下图:

png1

现在抽出 n 个积木,第 i 块积木是 $(x_i,y_i)$,保证 $x_i$ 和 $y_i$ 奇偶性相同。当 $(x-1,y-1)$ 和 $(x-1,y+1)$ 两块积木都消失时,积木 $(x,y)$ 会塌落(塌落后就消失)。

问抽出这 $n$ 个积木后,总共会掉落多少个积木(包括抽出的 $n$ 块积木)。

数据规模:$1\le n\le3\times10^5$,$-10^9\le x_i,y_i\le10^9$。保证 $x_i,y_i$ 奇偶性相同且抽出的 $n$ 个积木不相同。

T3. 保镖

一共有 n 个保镖等待聘用,第 i 个保镖可以连续工作 $a_i$ 个小时,接下来的 $b_i$ 个小时他必须休息。而且对于每一个保镖 i,他工作完成后,只有当聘用的其他所有保镖都工作了,他才会继续工作。

你需要聘用尽可能少的保镖,使得在任何时刻都有保镖工作。求最少需要聘用多少保镖;如果无法满足“任何时刻都有保镖工作”,输出 -1

数据规模:$1\le n\le5\times10^5$,$1\le a_i,b_i\le10^{12}$。


Part3. 个人细节(不重要)

T1. 序列

其实这道题一开始卡了很久,没记错的话应该是把 $k$ 看成 $m$ 了,误以为计算一次序列的第 $i$ 项会有 $O(m)$ 的复杂度(这样的话总复杂度应该是 $O(nm\log_2 m)$),然后之后很久才注意到计算应该是 $O(k)$ 的,然后就这样写了。

考虑到虽然答案不会超过 long long,但是计算过程中,得到的不是答案的数可能是超过 long long 的,就处理了一下计算乘法和加法时的数字大小……结果有个地方把变量名写错了,导致有一些不会爆 long long 的计算误判成会爆……(最后听说这道题也没有卡 long long 来着)

T2. 积木

推导了很久的性质,最后自己推导出来一个“碗”状的东西,但是没法维护……就放弃了,开始打部分分。

一开始做的是 $1\le x_i,y_i\le5000$ 的部分分,写的复杂度是 $O(5000^2)$,就是从最底下暴力判断每一层哪些积木会掉落。然后感觉 20pt 太少了,说不过去……然后就想要做 40pt 的第 1,2 个部分分。

想到 $1\le x_i,y_i\le5000$ 的计算方法中其实有很多层不会有抽出去的积木,因此可以预先知道是哪些积木掉下来。于是就初步精简成了 $O(n^2)$ ,又结合了之前推导的所谓”碗“形,想到了可以用链表维护(还可以用堆维护,当时没有想到)。

实际上,我那个算法的复杂度应该是常数较大的 $O(n)$……(后面再讲为什么是 $O(n)$ )但是我以为是 $O(n^2)$ ,链表就只开了部分分的规模。虽然还有一些细节写错了,赛后修修补补就 AC 了 QwQ

T3. 保镖

受 C题 影响(??) 以为这道题很难,再加上自己推导了一下,感觉没什么结果。然后就没什么思路。


Part4. 题解

T1. 序列

注意到 $k\le7$,所以计算某一个序列的第 $i$ 项的复杂度简直可以当作常数处理。而且还有一个非常显然的性质 —— 这 m 个序列,每个都是 单调递增 的。

因此可以贪心 —— 用堆(优先队列)维护当前最小的数。每次取出最小的数(堆顶),然后把它换成它所在的序列的下一个数,再塞进堆里……取出来的第 n 个数就是答案。

这样的话,堆里的元素始终只有 m 个,所以复杂度稳定 $O(\log_2m)$ ;取出 n 次;计算复杂度 $O(k)$;总共是 $O(nk\log_2m)$,可以接受。

小插曲:关于判断是否超过 $10^{18}$。

其实确实是可以判断的,而且我觉得应该要判断……不知道为什么不判断可以 AC……(因为我觉得当我们取出堆顶后,它的下一个数可能会变得很大,虽然堆顶在 $10^{18}$ 以内,但是下一个数可能会超过 $10^{18}$。它一定不会是答案,但是如果它爆了 long long 变成负数,就到堆顶去了。)

对于计算 $a\times b$ ,$a,b$ 都没有爆 long long,如果 $a\times b>10^{18}$,则 $a>\left\lfloor\frac {10^{18}}b\right\rfloor$;这样就可以判断了。

计算 $a+b$,如果 $a>10^{18}-b$ 就爆了。

T2. 积木

不难发现,如果只考虑抽出同一行的连续 k 块积木,会有 $\frac{(k+1)k}2$ 块积木消失,比如这样(抽出橙色积木,黄色积木也会消失):

png2

而且设抽出的积木是 $(x,y),(x,y+2),\cdots,(x,y+2k-2)$ 这 k 块连续的积木,第 $x+i$ 层($i< k$)会掉落 $(x+i,y+i),(x+i,y+i+2),\cdots,(x+i,y+2k-2-i)$ 这 $k-i$ 块积木。

只要第 i 行没有抽出其他的积木,我们就 可以直接知道 第 i 行的消失情况。

因此我们只需要处理有积木被抽出的行 —— 用链表维护第 i 行有 哪几段积木 消失了,从第 i 层转移到第 j 层($i<j$)就是下面这样的过程:

png3

j=i+2 的情况(红色是第 j 层要抽出的积木):

黄色段是第 i 层会消失的段。第 i+1 层没有抽出积木,因此我们可以直接计算出打了叉的这些积木会消失。还可以计算出第 j 层的橙色积木也会消失。橙色段与要抽出的红色积木连成了连续的一段区间,因此把它们合并成一段继续计算。

假如 j 离 i 太远,黄色段不会对第 j 层的积木造成影响,就直接计算出黄色段会造成多少个积木消失,然后删掉这一段。

假如第 j 层删除的积木没有与橙色段相连,就新建长度为 1 的一段新区间,然后按 从左到右 的顺序插入到链表里。

要处理元素(区间)的修改(合并)、依次访问、任意位置插入以及删除,链表还是非常好用的,尤其是手写链表的优势就非常明显。

关于时间复杂度:

由于只有额外抽出的 n 个积木可能会造成新建一个段。所以链表中维护的段最多只有 n 个,而每个段只会被删除一次(如果一个要抽出的积木合并到另一个段里了,视为这个要抽出的积木新建的段被删除),因此复杂度是 $O(n)$,但是由于有一些遍历的复杂度,会有较大的常数。但是还好不会卡常……

T3. 保镖

不妨把每个保镖的工作看成一个长度为 $a_i+b_i$ 的循环,在这段循环中,每个时刻都必须有人工作。那么如果我们选的保镖中 t 的 $a_t+b_t$ 最大,那么选的这些保镖的 $a_i$ 必须要能够 填满 这个 $a_t+b_t$。

可能表现成线段图更直观:

png4

(斜线段表示保镖工作的段 $a_i$)

这样的一个安排就是合法的,因为每个保镖的 $a_i+b_i\le\max\{a_i+b_i\}$ ,所以在这样一个长度 $\ge\max\{a_i+b_i\}$ 的循环中,每个保镖都会在他开始工作之前完成休息。

那么可以考虑 先确定 $\max\{a_i,b_i\}=t$ ,再用 $a_i+b_i\le t$ 的保镖的 $a_i$ 来填满 $t$ 。显然贪心地想,要取尽可能大的 $a_i$ 才能使聘用的保镖尽可能少。

根据这个思路 —— 我们可以先把所有保镖按 $a_i+b_i$ 从小到大排序,然后从小到大枚举 $t=a_i+b_i$,同时用 权值线段树 维护小于等于 $t$ 的 $a_i+b_i$ 的每个 $a_i$ 的数量(当然要离散化),然后在线段树上查询尽可能取大的 $a_i$,至少要取多少个才能使它们的和大于等于 $t$,比较像平衡树的查询,具体可见代码 。对于每个 $t$ 都 $O(\log_2 n)$ 的复杂度查询一下,取最小值即可。


Part5. 源代码

T1. 序列

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
/*Lucky_Glass*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int M=3e4,K=7;

int n,m,k;
int cA[M+3][K+3];
struct QNODE{
long long num;int id,pos;
QNODE(){}
QNODE(long long _n,int _i,int _p):num(_n),id(_i),pos(_p){}
};
bool operator <(QNODE A,QNODE B){return A.num>B.num;}
priority_queue< QNODE > que;

int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++){
int tot=0;
for(int j=0;j<=k;j++){
scanf("%d",&cA[i][j]);
tot+=cA[i][j];
}
que.push(QNODE(1ll*tot,i,1));
}
QNODE now;
const long long INF=(long long)(1e18);
for(int i=1;i<=n;i++){
now=que.top();que.pop();
int id=now.id,nxt=now.pos+1;
QNODE cop(0,id,nxt);
long long val=1;
bool Bb=false,Bc=true;
for(int j=0;j<=k;j++){
if(cA[id][j] && Bb) Bc=false;
if(cop.num>INF-val*cA[id][j]) Bc=false; //这里在判 1e18
cop.num+=val*cA[id][j];
if(val>INF/nxt) Bb=true; //这里也在判 1e18
val*=nxt;
}
if(Bc) que.push(cop);
}
printf("%lld\n",now.num);
return 0;
}

T2. 积木

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
/*Lucky_Glass*/
#include<stack>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=3e5;
#define fir first
#define sec second

int n;
struct POSI{
int x,y;
POSI(){}
POSI(int _x,int _y):x(_x),y(_y){}
int& operator [](int id){return id? y:x;}
}del[N+3];

bool cmpPOSI(const POSI &a,const POSI &b){return a.x!=b.x? a.x<b.x:a.y<b.y;}
struct TNODE{TNODE *lef,*rig;int cell,celr;};
struct TLIST{
TNODE pol[N+3],*head,*tail;stack<TNODE*> abl;
TNODE *NewNode(int l,int r){
TNODE *resu=abl.top();abl.pop();
resu->lef=resu->rig=NULL;
resu->cell=l;resu->celr=r;
return resu;
}
void Init(){
for(int i=0;i<=N;i++) abl.push(pol+i);
head=NewNode(-2e9,-2e9);
tail=NewNode(2e9,2e9);
head->rig=tail;tail->lef=head;
}
void Delete(TNODE *it){
abl.push(it);
it->lef->rig=it->rig;
it->rig->lef=it->lef;
}
}Llist;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&del[i][0],&del[i][1]);

sort(del+1,del+1+n,cmpPOSI); //先按 x 小,再按 y 小

Llist.Init(); //手写链表的初始化,带有哨兵节点 head,tail
long long ans=0;
for(int i=1;i<=n;){
int cel=del[i].x;
TNODE *it=Llist.head;
while(i<=n && del[i].x==cel){
while(it && it->cell<del[i].y) it=it->rig;
//如果要抽出的积木不是本身就要掉落的积木
if(it->lef->celr<del[i].y && del[i].y<it->cell){
TNODE *p=Llist.NewNode(del[i].y,del[i].y);
p->lef=it->lef;p->rig=it;
p->lef->rig=p->rig->lef=p;
}
i++;
}
it=Llist.head->rig;
while(it!=Llist.tail){
//如果可以向左边合并
if(it->lef->celr+2==it->cell){
it->lef->celr=it->celr;
Llist.Delete(it);
}
it=it->rig;
}
it=Llist.tail->lef;
while(it!=Llist.head){
//如果可以向右边合并
if(it->rig->cell==it->celr+2){
it->rig->cell=it->cell;
Llist.Delete(it);
}
it=it->lef;
}
it=Llist.head->rig;
int maxhg=del[i].x-cel;
//计算每一段的影响以及下一层的段
while(it!=Llist.tail){
int len=(it->celr-it->cell)/2+1;
if(len<=maxhg || i>n){ //对下一层没有影响(注意顶层)
ans+=(len+1ll)*len/2;
Llist.Delete(it);
}
else{ //有影响
ans+=(len-maxhg+1ll+len)*maxhg/2;
it->cell+=maxhg;it->celr-=maxhg;
//更新为下一层的段
}
it=it->rig;
}
}
printf("%lld\n",ans);
return 0;
}

T3. 保镖

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
/*Lucky_Glass*/
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=5e5;

int n;
vector<long long> uni;
struct NODE{long long a,b;}nod[N+3];

struct SEGTREE{
long long sum[N<<2];
int cnt[N<<2];
void PushUp(int u){
sum[u]=sum[u<<1]+sum[u<<1|1];
cnt[u]=cnt[u<<1]+cnt[u<<1|1];
}
void Modify(int u,int Cl,int Cr,int Dv){
if(Dv<Cl || Cr<Dv) return;
if(Cl==Cr){
sum[u]+=uni[Dv];
cnt[u]++;
return;
}
int Cm=(Cl+Cr)>>1;
Modify(u<<1,Cl,Cm,Dv);
Modify(u<<1|1,Cm+1,Cr,Dv);
PushUp(u);
}
int Query(int u,int Cl,int Cr,long long Dv){
if(Cl==Cr) return Dv/uni[Cl]+(bool)(Dv%uni[Cl]);
int Cm=(Cl+Cr)>>1;
if(sum[u<<1|1]>=Dv) return Query(u<<1|1,Cm+1,Cr,Dv);
else return Query(u<<1,Cl,Cm,Dv-sum[u<<1|1])+cnt[u<<1|1];
}
}Stre;

bool cmpNODE(const NODE &A,const NODE &B){return A.a+A.b<B.a+B.b;}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&nod[i].a,&nod[i].b);
uni.push_back(nod[i].a);
}
uni.push_back(-1);
sort(uni.begin(),uni.end());
uni.erase(unique(uni.begin(),uni.end()),uni.end());
sort(nod+1,nod+1+n,cmpNODE);
int Ssiz=uni.size()-1;
int ans=n+1;
//按 a+b 从小到大插入到权值线段树里,自然就得到需要的权值线段树
for(int i=1;i<=n;i++){
int id=lower_bound(uni.begin(),uni.end(),nod[i].a)-uni.begin(); //离散化
Stre.Modify(1,1,Ssiz,id);
if(Stre.sum[1]>=nod[i].a+nod[i].b)
ans=min(ans,Stre.Query(1,1,Ssiz,nod[i].a+nod[i].b));
}
if(ans==n+1) printf("-1\n");
else printf("%d\n",ans);
return 0;
}

The End

Thanks for reading!

0%