摘要:受骗消费者lbl

10152020机房赛

闲话

关于这套题:

题解里写了部分分题面上没部分分,T1数据范围可以拿图灵奖,T2数据脚造,T3傻逼人类智慧分类讨论题…

T1

题目分析

50mb的空间,最大2e9的读入量,不存在边读边做的做法,不知道这出题人怎么想的.

而且std空间都只开了1e7,因为数据随机造的就给过了.

于是考场想出正解,不敢开数组,开vector还是被卡了空间,拿了48分,看葛队思路和我一样但是用的数组就多mle了一个点.

先不管这莫名奇妙的数据范围和空间限制,可以发现的是货物出现的时间是可以固定的,算上走到那个位置上的时间,只要在这个时间之后出发,就可以装载这个货物.

那我们把这个时间算出来,把所有的货物排个序.

然后把车放入小根堆,每次取出时间上最优的车去取一个货物,然后弹掉它,加上绕行一圈的时间再次插入,统计答案即可.

代码

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
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
#define mp(x,y) std::make_pair(x,y)
typedef long long lxl;
const lxl big=1000010,small=2010;
int n,m,point,num;
lxl now,sum;
std::priority_queue<lxl>car;
lxl a[big*10];
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template<typename T>
inline void read(T &x)
{
char c;lxl f=1;
while(!isdigit(c=gc())) (c=='-')&&(f=-1);
x=c^48;
while(isdigit(c=gc())) x=x*10+(c^48);
x*=f;
}
int main(void)
{
read(n),read(m);
for(R int i(1);i<=n;++i)
{
lxl _,x;read(_),sum+=_;
for(R int j(1);j<=_;++j)read(x),a[++num]=x-i*1ll;
}
std::sort(a+1,a+1+num);
for(R int i(1);i<=m;++i)car.push(0);
for(R int i(1);i<=num;++i)
{
lxl next=a[i];;
lxl ncar=-car.top();car.pop();
if(ncar<next)ncar=next;
car.push(-(ncar+n+1));
now=std::max(now,ncar+n+1);
}
printf("%lld\n",now);
return 0;
}

T2

题目分析

上一题是造数据不带脑子,这一题是直接拿脚造数据.

考场写个暴力就去刚T3了,T3刚到一半回头测测T2大样例,发现2e6的范围,理论最差复杂度$O(n^2)$的暴力在本机跑了500ms.

以为是出题人钓鱼没想到还真这么快,获得了72分的好成绩.

然后正解是拿动态树做,每个点给一个$1$的权值,删除的点清空权值,插入随便维护.

查询$x$的$k$级祖先就把$x$给access再旋到根,每个点维护了当前splay集合里的子树size,那么这样旋转之后$x$的祖先就都在它的左子树上,其中权值为$size_{root}-k$的点就是$x$的$k$级祖先了.

代码

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
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl big=200010;
lxl m,online,NodeCnt=1,LastAns;
lxl c[2][big],fa[big],size[big],val[big];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
inline void PushUp(lxl x){size[x]=size[c[0][x]]+size[c[1][x]]+val[x];}
inline bool IsRoot(lxl x){return c[0][fa[x]]!=x&&c[1][fa[x]]!=x;}
inline void rotate(lxl x)
{
lxl y=fa[x],z=fa[y],d=c[1][y]==x;
if(!IsRoot(y))c[c[1][z]==y][z]=x;
fa[x]=z,fa[y]=x,fa[c[d^1][x]]=y;
c[d][y]=c[d^1][x],c[d^1][x]=y;
PushUp(y),PushUp(x);
}
inline void splay(lxl x)
{
while(!IsRoot(x))
{
lxl y=fa[x],z=fa[y];
if(!IsRoot(y))rotate((c[0][y]==x)^(c[0][z]==y)?x:y);
rotate(x);
}
}
inline void access(lxl x){for(R int t(0);x;t=x,x=fa[x])splay(x),c[1][x]=t,PushUp(x);}
inline void link(lxl x)
{
fa[++NodeCnt]=x;
val[NodeCnt]=size[NodeCnt]=1;
access(NodeCnt),splay(NodeCnt);
}
inline void erase(lxl x)
{
access(x),splay(x);
val[x]=0,PushUp(x);
}
inline lxl find(lxl x,lxl k)
{
lxl cnt(0);
while(x)
{
if(size[c[0][x]]>=k)x=c[0][x];
else if(size[c[0][x]]+val[x]==k)return x;
else k-=size[c[0][x]]+val[x],x=c[1][x];
++cnt;
}
return 0;
}
inline lxl query(lxl x,lxl k)
{
access(x),splay(x);
return find(x,size[x]-k);
}
int main(void)
{
m=read(),online=read();
val[1]=size[1]=1;
while(m--)
{
lxl opt=read();
if(opt==1)
{
lxl x=read()^LastAns;
if(!x||x>NodeCnt||!val[x])continue;
link(x);
if(online)LastAns=x;
}
if(opt==2)
{
lxl x=read()^LastAns;
if(!x||x>NodeCnt||!val[x])continue;
if(online)LastAns=query(x,1);
erase(x);
}
if(opt==3)
{
lxl x=read()^LastAns,y=read()^LastAns,ans;
if(!x||x>NodeCnt||!val[x])continue;
printf("%lld\n",ans=query(x,y));
if(online)LastAns=ans;
}
}
return 0;
}

T3

题目分析

人类智慧分类讨论解三角形,不会.

总结

先做的T1,发现数据范围大得不可能存得下以为得边读边做,但是想了一会不知道怎么搞,于是去想了个和正解一样的用小根堆的做法,但其实数据点和std的数据范围比题面上的小得多,按题面开就mle了,拿了48.

然后去看了T2和T3,发现T3是个大模拟感觉比T2要好拿分,T2写了个暴力就没管了,测了测大样例发现跑得很快,拿了72.

最后两个小时都在写T3,分类讨论的情况太多了写了200多行,最后测大样例发现没判直角三角形和等腰三角形的情况,写上之后判等腰的条件写漏了于是把所有三角形都处理了,就只拿了24,非常不划算.

自己写大模拟的经验实在是不足,在情况很多的时候会写得很冗长浪费时间,而且在其他的题目上也经常出现做法想出来了但是写法太烂的情况,以后可以去多看看别人写得快的代码锻炼代码的实现能力.