AtCoder Beginner Contest 082

AtCoder Beginner Contest #082 - Click Here

　　

Preface

　　毫无营养的一场，但为了证明今晚没颓，还是水篇Blog吧233。

　　P.S. ABC好水啊，打完下场ABC后就去打ARC和AGC了QwQ。

　　

Problem A

Solutions

　　四舍五入就+1后再整除就好了~

　　

CODE

CODE - Click Here

　　

Problem B

Solutions

　　既然可以随意排列，那就选取最优的策略。

　　将$a$字符串从小到大排列，$b$字符串从大到小排列，然后比较即可。

　　

CODE

CODE - Click Here

　　

Problem C

Solutions

　　每个数字都是独立的，因此分开考虑。

　　设数字$a$出现次数为$cnt$。如果$a \leq cnt$，那么只需要消去多余的即可；反正，则只能够全部消去。

　　

CODE

CODE - Click Here

　　

Problem D

Solutions

　　每个$F$只能够使得$x$坐标或者$y$坐标发生变化，因此可以对一段连续的$F$看做一个操作。

　　然后不难发现，每一个$T$只能够使得原本对某一轴的变化转换为对另外一轴的变化，且增加或减少是能够自己控制的。

　　

　　这样，问题就转换成，有一堆数字，你能够在这些数字之间添加$+$或者$-$，问答案能否为询问值。

　　显然DP。定义$f(i,j)$表示$1$至$i$数字能够凑出$j$。

　　则易得转移方程，$f(i,j)=f(i-1,j-a_i) \, | \, f(i-1,j+a_i)$。

　　

　　这个DP显然可以压位优化，直接上bitset就好了~

　　时间复杂度$O(\frac{|S|^2}{w})$，$w$表示压位的大小。对于bitset而言，$w=60$。

　　

CODE

CODE - Click Here