Educational Codeforces Round 119 (Rated for Div. 2) 做题日志
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
A Equal or Not Equal
题意 给你一个字符串
s
i
=
=
E
si == E
si==E表示
a
(
i
)
=
=
a
(
i
+
1
)
a(i) == a(i+1)
a(i)==a(i+1)
s
i
=
=
N
si == N
si==N表示
a
(
i
)
!
=
a
(
i
+
1
)
a(i) != a(i +1)
a(i)!=a(i+1)
思路 vp时猜了一个长度为2出现
N
E
NE
NE或者
E
N
EN
EN为
N
o
No
No,交上去结果
w
a
wa
wa了冷静之后分析了一下该如何构造构造时发现不相等的个数只有一个的话就没法接上循环的链上然后猜了一下
N
N
N只出现一次答案是
N
o
No
No然后a了。
代码
B Triangles on a Rectangle
题意 给你一个矩形
(
w
,
h
)
(w , h)
(w,h)每条边有不少于两个的点问你在一条边选两个一条边选一个组成三角形面积最大为多少。
代码
C BA-String
题意 给你一个字符串
s
s
s当
s
i
=
=
′
∗
′
si == '*'
si==′∗′时表示
s
i
si
si可以被替换成
(
0
−
k
)
(0-k)
(0−k)的整数字符串只由
′
a
′
和
′
∗
′
'a'和'*'
′a′和′∗′组成输出本质不同的字典序第
k
k
k大字符串。
思路 观察样例我们发现连续的
∗
*
∗会影响本质不同我们考虑按块操作我们先预处理把其字符串分成
∗
*
∗相同的块序列然后每块的取值是
(
0
,
k
∗
l
)
(0 , k * l)
(0,k∗l),
l
l
l为块长然后我们按照贪心思路暴力贪心即可。这题的难点在于代码能力是一个不是很好写的贪心题。
n
<
=
5
e
3
n <= 5e3
n<=5e3。赛场
c
c
c过题量较少。
代码
D Exact Change
题意 给你数组
a
a
a,已经三种硬币
123
1 2 3
123问你最少需要多少个硬币满足可以组成所有的
a
i
ai
ai。
n
<
=
2
e
5
n <= 2e5
n<=2e5
s
a
m
p
l
e
sample
sample
input:
3
10 8 10
output:
4
I
n
t
h
e
s
e
c
o
n
d
t
e
s
t
c
a
s
e
,
y
o
u
s
h
o
u
l
d
,
f
o
r
e
x
a
m
p
l
e
,
t
a
k
e
2
c
o
i
n
s
o
f
v
a
l
u
e
3
a
n
d
2
c
o
i
n
s
o
f
v
a
l
u
e
2.
S
o
y
o
u
c
a
n
p
a
y
e
i
t
h
e
r
e
x
a
c
t
l
y
8
=
2
⋅
3
+
1
⋅
2
o
r
10
=
2
⋅
3
+
2
⋅
2
In the second test case, you should, for example, take 2 coins of value 3 and 2 coins of value 2 . So you can pay either exactly 8=2⋅3+1⋅2 or 10=2⋅3+2⋅2
Inthesecondtestcase,youshould,forexample,take2coinsofvalue3and2coinsofvalue2.Soyoucanpayeitherexactly8=2⋅3+1⋅2or10=2⋅3+2⋅2
思路 当时考虑用3对所有的
a
i
ai
ai取模我们发现模数只有
1
1
1,
2
2
2,然后我直觉感觉到
1
1
1,
2
2
2的个数不会很多我第一印象是感觉
1
1
1,
2
2
2的个数最多为1然后样例
h
a
c
k
hack
hack掉我的思路然后多次手完之后发现最多次数一定不会超过
2
2
2,然后暴力枚举
1
、
2
1 、2
1、2的个数即可我们可以用贪心的思路判断一个数能否组成。
代码
E Replace the Numbers
题意 模拟两个操作
1.将
x
x
x放到数组末尾。
2.将值为
x
x
x改为值为
y
y
y。
思路 一道比启发式合并典题还裸的一道题也是本场的最大诈骗题暴力启发式合并即可。
代码
.