• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

Codeforces Round #713 (Div. 3) VP

开发技术 开发技术 1周前 (05-04) 4次浏览

比赛链接


前言

心血来潮,这个憨憨居然打起 Div.3 来了。可惜人傻手慢,没有 AK。

总体来说题目还是很水的,我感觉 Div.3 难度没这么低?


A. Spy Detected!

题目大意

给你一个数组,输出不同数字的下标。

分析

反正我直接结构体排序,桶排其实也可。

反思

犹豫就会败北!一开始写了结构体就应该继续写下去,而不是嫌麻烦删掉再换一种!这种题目就是输在这种愚蠢的地方。

代码

https://codeforces.com/contest/1512/submission/114523907


B. Almost Rectangle

题目大意

告诉你两个点,让你补上另外两个,使它们四个分别是一个矩形的四个顶点。

分析

分类讨论呗。

设一个点为 ((a,b)),另一个为 ((c,d))

(a=c) 时,若 (a=n),剩下两个往上挪一行,否则往下挪,防止不合法。

(b=d) 时,同理即可。

剩余情况相当于已知对角两个点求剩下两个。

反思

手速不行,居然隔了 (6) 分钟。

代码

https://codeforces.com/contest/1512/submission/114524384


C. A-B Palindrome

题目大意

在给出 (01) 串的 ? 处填上 (0)(1),使得填后为一个有 (a)(0)(b)(1) 的回文 (01) 串。

分析

因为是回文,所以先检查给出字符串是否合法,不合法直接为 -1,否则就把一边 ? 一边有 (01) 的地方填上。顺便就算出剩下需要几个 (0) 和几个 (1) 了。对于长度为奇数的串,把中间那个字符处理掉。

我直接拿 (a)(b) 边填边减来算的,所以下文的 (a)(b) 都是处理过后的。

若处理完后 (a<0)(b<0),那么就是 -1

否则 (a)(b) 必然都为偶数,否则为 -1

然后把剩下留的空一对一对填,(0) 填完 (1) 填,然后就没了。

反思

看仔细一点!样例都没过还交!我真是憨死了!

代码

https://codeforces.com/contest/1512/submission/114525684


D. Corrupted Array

题目大意

有一个数组 (a),从 (a_1)(a_n)

有一个数组 (b),从 (b_1)(b_{n+2})

其中 (a) 数组已知,(b) 数组的构造方法如下:

  1. (a) 数组一一对应赋值给 (b) 数组。((i=1dots n))

  2. (b_{n+1}=sumlimits_{i=1}^n a_i)(b_{n+2}=x=text{RAND}(1,10^9))

  3. 随机打乱 (b) 数组。((i=1dots n-2))

现在给出 (b) 数组,输出任意可能的 (a) 数组,若不存在输出 -1

分析

分类讨论。

将得到的 (b) 数组排序,那么 (b_{n+2}) 要么是元素和,要么是 (x)

(b_{n+2}=x) 时,必然 (b_{n+1}) 为元素和,那么直接把 (b_1dots b_n) 输出即可。否则为 -1

(b_{n+2}) 为元素和时,那么 (x=sumlimits_{i=1}^{n+1}-b_{n+2})。由于 (x>0),当 (xle 0) 时直接返回 -1。由于此时 (b_1dots b_{n+1}) 已经是有序的了,直接二分查找 (x),若没找到直接返回 -1,否则就输出 (b_1dots b_{n+1}),输出时跳过 (x) 第一次出现的位置。(当然你选任意一个 (b_i=x) 的都可以。)

反思

手速太慢,居然写了 (17) 分钟!!

代码

https://codeforces.com/contest/1512/submission/114526984


E. Permutation by Sum

题目大意

(p)(1dots n)(n) 个数的一个排列,并满足 (sumlimits_{i=l}^r p_i=s)。给出 (n,l,r,s),求 (p)。若不存在输出 -1

分析

首先我们要得知 (x=sumlimits_{i=l}^r p_i) 的范围。

(t=r-l+1)(smle xle bi)

那么显然 (sm=dfrac{t(t+1)}{2})(bi=sm+t(n-t))

(s) 不满足这个条件,直接返回 -1,否则都是可构造的。

先给 (b_ldots b_r) 依次赋值为 (1dots t)。然后从 (r)(l) 加数,加满后换下一个加。对于位置 (i),为保证每个数不同,它的加满指加到 (i-r+n),来使得 (b_ldots b_r) 单调递增。

剩下的直接把没填的按顺序填即可。

反思

手速太慢,居然写了 (13) 分钟!!

代码

https://codeforces.com/contest/1512/submission/114528008


F. Education

题目大意

恶心死了,不想翻。

分析

递推就好了,有个坑注意。懒得详细写。

搞不懂在这题里 (c-1)/a+1(c-1+a)/a 有什么区别。

反思

题目要看清!每个数组的定义要弄清楚!白瞎了我 (35) 分钟。

代码

https://codeforces.com/contest/1512/submission/114530972


G. Short Task

题目大意

(d(n))(n) 的约数和。给定 (n),求满足 (d(i)=n) 的最小的 (i)(t) 组数据。

分析

先咕着。

反思

先咕着。

代码

https://codeforces.com/contest/1512/submission/114533772


总结

慎之又慎!千里之堤毁于蚁穴!

相信自己!犹豫就会败北!


程序员灯塔
转载请注明原文链接:Codeforces Round #713 (Div. 3) VP
喜欢 (0)