tyvj测试

很不爽啊。。。

day1 60 + 100 + 10 = 170

day2 100 + 40 + 80 = 220

总分390

update:然后吐槽一下:tyvj的测评姬大概烂破了天际。。。能测一个小时的代码我还是第一次见。。。莫名其妙的System Error真的是醉了

t1 天天去哪吃。

【问题描述】
吃饭是⾃古以来令⼈头疼的问题,最后天天决定写⼀个程序来替他做决
定。
现在已知有 n 个餐厅,编号从 0 到 n−1。记 ai 表⽰第 i 天决定吃什 么,令
ti0 = αai−1 + βai−2 mod n
tij = ti(j−1) + 1 mod n,j ≥ 1 天天不想连续⼏天吃⼀样的餐厅,所以如果在前⾯ ⌊n 2⌋ 天中吃过某个 餐厅,就不想再去这个餐厅。所以我们要找⼀个最⼩的 k,使得 tik 不为前 ⌊n 2⌋ 天去过的餐厅。那么天天第 i 天就想去 tik 餐厅。 现在已知 a1 和 a2,想让你输出 a3...am,即接下来 m−2 天天会去哪 ⾥吃饭。
【输入格式】 第⼀⾏两个整数 n 和 m。其中 2 ≤ n ≤ 100,000,3 ≤ m ≤ 200,000 第⼆⾏两个整数,分别为 α 和 β。其中 0 ≤ α,β ≤ 109 第三⾏两个整数,为 a1,a2。其中 0 ≤ a1,a2 < n,且 a1 ̸= a2
【输出格式】 ⼀⾏ m−2 个整数,表⽰接下来 m−2 天⾥,天天去哪⾥吃饭。
【样例输入】
3 4
2
7 11 2 0
【样例输出】
1 2
【样例解释】 t30 = 7a2 +11a1 mod n = 1,前⾯ ⌊n 2⌋ = 1 天没有出现,所以第三天去 1 号餐厅。 t40 = 1,前⾯ 1 天已经出现,所以第四天去 t41 = 2 号餐厅。
【数据规模和约定】 对于 60% 的数据,2 ≤ n,m ≤ 10,000。 对于 100% 的数据,2 ≤ n ≤ 100,000,3 ≤ m ≤ 200,000,且保证 α,β 为随机选择的两个素数,所以可以认为 ti0 为⼀个随机数。

跟着模拟就好了,死于没开long long

c++代码如下:

60 分代码

满分代码:

t2 天天和树

天天和树
tree.in/.out/.cpp
【问题描述】 ⼀个树由 n 个点,n−1 条边组成,结点编号为 1...n。树上任意两个点 之间路径唯⼀。 定义⼀个点到⼀条路径的距离为:该点到路径上最近的⼀个点需要经过 的边的数量。 现在想知道怎样选两个点确定⼀条路径,使得距离这个路径最远的点尽 量近。要求你输出距离路径最远的点距离路径的距离。
【输入格式】 第⼀⾏⼀个整数 n。其中 1 ≤ n ≤ 100,000 接下来 n−1 ⾏,每⾏两个整数 u 和 v,表⽰结点 u 和结点 v 之间有 ⼀条边。
【输出格式】
⼀⾏⼀个整数,为题⽬要求的答案。
【样例输入】
8 1 2 2 3 1 4 4 5 1 6 6 7 7 8
4
【样例输出】
2
【样例解释】 可以选择 3 到 7 作为⼀条链,那么此时距离这条链最远的点是 5,距离 为 2。可以发现不存在其他的⼀条链,使得最远点的距离更短。
【数据规模和约定】 对于 10% 的数据,保证 n = 99998,且树退化成⼀条链。 对于另外 30% 的数据,保证 n = 100。 对于另外 30% 的数据,保证 n = 99999,且最终答案⼩于等于 5。 对于剩余的 30% 的数据,保证 n = 100000。

明摆着找树的直径,然后在直径上跑一跑就好了。

c++代码如下:

t3

摆摊
stall.in/.out/.cpp
【问题描述】 在 T 校的校门⼜有⼀条路,这条路上有⼀些摊位,按照离校门的远近 关系标号为 1,2,3,...,N。 你突然发现在校门⼜卖煎饼是⼀件很好的差事,于是你打算暑假在校门 ⼜卖煎饼。 你发现这些摊位有⼀些是被占⽤的,有⼀些是没有被占⽤的。 你为了⽅便⽣意,需要占⽤两个连续的没有被占⽤的摊位来卖煎饼。 当然你希望你的煎饼摊离学校越近越好,所以你希望占⽤的两个连续摊 位的的编号越⼩越好。 现在给你⼀个长度为 M 的序列 a1,a2,...,am,表⽰已经占⽤的摊位信 息。 你需要回答Q个询问,每个询问有两个参数 L, R,表⽰问你当 aL,aL+1,...,aR 这些摊位被占⽤的时候你应该选择哪两个编号的摊位。
【输入格式】 第⼀⾏三个整数,N,M,Q,分别表⽰摊位的编号范围,a 序列的长度,询 问次数。 第⼆⾏ M 个整数表⽰ a 序列。 之后 Q ⾏,每⾏两个整数 L,R。
【输出格式】 输出⼀共 Q ⾏,每⾏两个空格隔开的两个整数,表⽰你占⽤的连续两 个摊位,如果没有找到合适摊位请输出-1 -1。
【样例输入】
10 5 15
6
3 1 6 7 5 1 1 1 2 1 3 1 4 1 5 2 2 2 3 2 4 2 5 3 3 3 4 3 5 4 4 4 5 5 5
【样例输出】
1 2 4 5 4 5 4 5 8 9 2 3 2 3 2 3 2 3 1 2 1 2 1 2
7
1 2 1 2 1 2
【数据规模和约定】 对于 10% 数据,保证 Q = 1。 对于其他 20% 数据,N,M,Q ≤ 100。 对于其他 20% 数据,N,M,Q ≤ 1000。 对于其他 20% 数据,N,M,Q ≤ 10000。 对于其他 20% 数据,N,M,Q ≤ 100000 。 对于 100% 的数据,1 ≤ N,M,Q ≤ 200000,1 ≤ ai ≤ N。

只拿了十分,你要问我为啥,我也不晓得。

莫队再怎么着也应该有个70 80.可惜我没有。。。

10分代码没有了。。。下次直接补满分代码。。。tyvj还没发测。

待更

--------update--------

建一颗主席树,对于一个点 x ,同时更新 x 与 x+1 于 i,操作详情见:http://tgotp.science/3585-mex/

c++代码如下:

 

day2

天天寄快递
express.in/.out/.cpp
【问题描述】
天天暑假时帮别⼈寄送快递,经历了⼀个暑假,天天积累了不少数据, 想对快递公司进⾏⼀下评分,得到快递公司的质量⽔平。 总共有 n 家快递公司,编号为 1..n。现在天天有 m 天的寄送快递数据, 其中第 i 天使⽤第 ei 家快递公司,快递在路上花了 ti 天时间。⼀开始每个 快递公司的评分都为 0,对于⼀家快递公司,如果⼀个包裹花了 ti 天寄到, 那么对这家快递公司的评分贡献为 2−ti,(如果花的时间超过两天得分就会 变成负的啦)。 然⽽事情没有这么简单,如果某⼀天的数据丢掉了,天天为了公平起见 就忽略掉这天的数据。于是快递公司联盟决定雇佣⼀个⼩偷,⼩偷可以偷⾛ 最多 s 天的数据,使得每个公司的信⽤得分⾄少增加 k,且所有快递公司的 信⽤总和尽量⼤。 若如果被偷以后,⽆法让每个公司的信⽤得分都⾄少增加 k,输出 −23333333,否则请你输出被偷后, 所有快递公司的信⽤得分的和最多增 加多少。
【输入格式】 第⼀⾏四个整数 n,m,s,k,其中 1 ≤ n,m ≤ 100,000,0 ≤ s ≤ m,0 ≤ k ≤ 109。 接下来 m ⾏,每⾏两个整数。接下来的第 i ⾏为 ei,ti,其中 1 ≤ ei ≤ n,0 ≤ ti ≤ 109。
【输出格式】
⼀个整数,为题⽬要求的答案。
2
【样例输入】
2 5 4 22 1 1 1 40 2 25 2 30 2 0
【样例输出】
89
【样例解释】
⼩偷可以偷 4 天的数据,但是⼩偷实际上只偷了第 2,3,4 天的数据,1 号公司获得了 38 分的提升,2 号公司获得了 23 + 28 分的提升,都满⾜了 最⼩提升 22 分的要求。
【数据规模和约定】 对于 30% 的数据,1 ≤ n,m ≤ 20。 对于 100% 的数据,1 ≤ n,m ≤ 200,000,。

明摆着sort一遍,然后把负权值删一遍。

c++代码如下:

t2 天天和不可描述
unknown.in/.out/.cpp
【问题描述】 天天和 () 是好朋友,然⽽总是唱反调。对于⼀个有 () 的字符串,天天 总是会把 () 内的所有东西都倒过来读。 ⽐如对于字符串 abc(def) ,天天看到的就是 abcfed 。 括号⾥⾯可能是空的,也有可能套有多个括号,⽐如说abc(hello)(world)lcy()x(owq(zrt)) ,天天看到的就是 abcollehdlrowlcyxzrtqwo 。 因为 (owq(zrt)) ⾸先变成了 (trz)qwo ,接下来变成了 zrtqwo ,zrt 被 反转了两次,所以天天看到的还是 zrt。 现在给你⼀个字符串,问你天天看到的是什么样⼦的?
【输入格式】 ⼀⾏⼀个字符串,表⽰原始的字符串。保证字符串内只有⼩写字母和 ( 以及) 组成。保证括号总是配对的。
【输出格式】
⼀⾏⼀个字符串,表⽰天天看到的字符串。
【样例输入 1】 abc(hello)(world)lcy()x(owq(zrt))
【样例输出 1】 abcollehdlrowlcyxzrtqwo
【样例输入 2】 (y(g(el)da)nis)
4
【样例输出 2】 singleday
【样例输入 3】 mian()
【样例输出 3】 mian
【数据规模和约定】 对于 10% 的数据,保证只出现⼀对括号,字符串长度⼩于 100,000。 对于另外 30% 的数据,保证字符串长度⼩于 100。 对于另外 40% 的数据,保证字符串长度⼩于 100,000。 对于剩余的 20% 的数据,保证字符串长度⼩于 500,000。

知道我的大暴力分肯定不高。。。

40分,直接暴力模拟。。。

100分:splay吧,区间翻转很容易实现的。。。

不想写,写了个暴力交了。。。

c++代码如下:

满分待更。。。

update:

递归处理,在此之前预处理 出每个 ‘(’ 对应的 ‘)’然后跑一边,

开内存蛇皮了40分

 

c++代码如下:

 

t3

罪犯分组
prison.in/.out/.cpp
【问题描述】 B 城有⼀座监狱,⼀共关押着 N 名罪犯,编号分别为 1-N。 他们的关系⼗分不和谐。很多罪犯之间甚⾄积怨已久,如果客观条件具 备则随时可能爆发冲突。 在详细考察了 N 名罪犯间的⽭盾关系后,警察局长发现罪犯之间的⽭ 盾关系可以⽤⼀个 N 个点 M 条边的⽆向图来表⽰:如果 x 到 y 有⼀条边, 表⽰罪犯 x 和罪犯 y 有⽭盾。 现在警察局长要把这些罪犯分成⼀些⼩组,每名罪犯属于且仅属于⼀个 ⼩组。 为了开展活动顺利,要求每个⼩组内最多有 K 对罪犯有⽭盾,同时为 了管理⽅便,警察局长希望最小化分成的⼩组数量。 那么,应如何分配罪犯,才能使分成的⼩组数量最少?这个最⼩值是多 少?
【输入格式】 第⼀⾏ 3 个整数,N,M,K,意义见上述。 接下来 M ⾏,每⾏两个数字 x,y。表⽰ x 和 y 之间有⽭盾。
【输出格式】
输出⼀⾏⼀个值,表⽰最少的分组数量。
【样例输入】
3 3 1 1 2 2 3 1 3
6
【样例输出】
2
【数据规模和约定】 对于每个测试点,N 分别等于 2,4,6,8,10,12,14,15,16,16。 0 ≤ M,K ≤ N(N−1) 2 保证是⼀个⽆⾃环、⽆重边的⽆向图。

显而易见是状压,可惜我沙茶,一开始在想搜索,后面才xjb写了个状压。。。

原本以为要么0要么100.。。。

结果80

c++代码如下:

满分代码如下:

事实告诉我们没事不要乱存。。。

 

回复

  1. 回复 tianbu

    :smile: :smile: :eek: :eek:

9 + 9 =