目录

比赛信息

题解

A -

solved by

题意

数据范围

题解

B - Mask Allocation

solved by gyp

题意

给定n,m。将$n\times m$拆成若干个数,使得可以凑成n个m或m个n。输出字典序最大的一种方案

数据范围

$n,m\le 10^4$

题解

设$n\ge m$。先输出n/m*m个m,然后将问题转化为求$m\times (n%m)$

C - A National Pandemic

solved by lxh,tyx, written by tyx

题意

在树上,支持以下三种操作:

1、选定一个点 $i$,别的点 $j$ 的价值都加上 $w[i]-dis(i,j)$。

2、选定一个点,它的价值值为 $min(价值,0)$。

3、询问某点的价值。

数据范围

$1 \le n(点数)、m(询问数) \le 5e4$

题解

经过分析后我们可以发现,一次$1$操作,对于任何一个点来说,权值的变化都是 $w-dep[x]-dep[p]+2*dep[k]$ (k是对于任何一个点来说从选定点 $x$ 到根的路径上最近的祖先).对于 $w-dep[x]$ 来说,所有点都是一样的,用一个全局的 $sum$ 来记录就可以。对于 $dep[p]$ 这部分同理记录次数,$2*dep[k]$ 这部分则需要利用树链剖分每次从 $x$ 到根每个点都$+1$,最后查询点时查询到根路径上的和来得到,对于二操作,我们单开一个新数组来记录操作对原值的影响就可以了。

D -

solved by

题意

数据范围

题解

E -

solved by

题意

数据范围

题解

F -

solved by

题意

数据范围

题解

G -

solved by

题意

数据范围

题解

H - Dividing

solved by gyp

题意

定义传奇二元组。(1,k)是传奇二元组,若(n,k)是传奇二元组,则(n+k,k),(nk,k)是传奇二元组。给定n,k,求$1\le a\le n,1\le b\le k$的传奇二元组(a,b)个数。

数据范围

$1\le n,k\le 10^{12}$

题解

所有第一个数模第二个数为0或1的均满足要求。数论分块计算个数即可。

I -

solved by

题意

数据范围

题解

J - Pointer Analysis

solved by tyx

题意

给出26个Pointer用大写字母表示,26个object用小写字母表示,每个object还有26个field,然后给出四种指向关系的赋值方式,问最后每个Pointer指向了哪些object

数据范围

题解

模拟题,要注意给出的赋值语句是可以调换顺序的,所以不能只做一遍,我们按照最坏情况,处理一遍以后第一个赋值语句被增加了一个,所以只需要重复处理26遍即可

Replay

第一小时:gyp和tyx发现D题是签到题于是直接开写,但是发现用cin超时了,改成scanf后通过。gyp开始想H并通过,tyx和lxh开始想B

第二小时:tyx写的B一直WA,随后gyp和lxh发现方法有问题,修正后通过。tyx开始想J,gyp和lxh开始想C

第三小时:tyx写出J并通过,随后加入gyp和lxh开始想C

第四小时:三个人想出了C,但是写起来非常复杂,由于lxh临时有事所以tyx开始写

第五小时:tyx写完了C但是WA了两次,后来发现是因为多组数据有一小部分没有初始化,更改后通过

总结