AtCoder Beginner Contest 225 (A,B,C,D,E,F)
A. Distinct Strings
三个字母的全排列得到的字符串的种类数
ACcode
#include
#include
#include
#include
#include
#include
#include
B. Star or Not
给 n-1 条边,询问是否为菊花图。
判断入度即可。
ACcode
#include
#include
#include
#include
#include
#include
#include
C. Calendar Validator
判断是否为合法的矩阵。
先判断第一行是否合法,第二行开始判断是否和上一行相差 7。
ACcode
#include
#include
#include
#include
#include
#include
#include
D. Play Train
模拟链表即可。
ACcode
#include
#include
#include
#include
#include
#include
#include
E. 7
几何题,偏思维。
由图可知:从x轴开始选取,当发生覆盖时,优先选取斜率较小的点比较优。
如图,1 和 2 发生覆盖,选择 1 的同时可以选择 3。
注意精度问题,用 long double。
ACcode
#include
#include
#include
#include
#include
#include
#include
F. String Cards
DP。
在 n 个字符串中选取 k 个任意连接,得到字典序最小的字符串。
按照 A+B > B+A 的顺序排序。
设
d
p
i
,
j
dp_{i,j}
dpi,j 表示前 i 个字符串取 j 个得到的最小字符。
d
p
i
+
1
,
j
=
d
p
i
,
j
dp_{i+1,j} = dp_{i, j}
dpi+1,j=dpi,j
d
p
i
+
1
,
j
=
m
i
n
(
d
p
i
+
1
,
j
,
s
+
d
p
i
,
j
−
1
)
,
s
表
示
可
选
择
的
字
符
串
dp_{i+1,j} = min(dp_{i+1,j} , s + dp_{i, j-1}),s 表示可选择的字符串
dpi+1,j=min(dpi+1,j,s+dpi,j−1),s表示可选择的字符串
ACcode
#include
#include
#include
#include
#include
#include
#include
评论列表(0条)