Atcoder

Atcoder ABC 173

E 题目 从 $n \le 2e5$ 个数 $|a_i| \le 1e9$ 中选出 $k \le n$ 个数,使得乘积最大。输出答案对 $1e9+7$ 取模的结果 题解 首先考虑答案是否是正数。要想答案是正数那么一定是偶数个负数乘上剩下的...

Atcoder ABC 168

E 题意 给定$n \le 2e5$ 个二元组 $(a,b) -1e18\le a,b\le 1e18$ ,若两个二元组 $i,j$ 满足 $a_ia_j+b_ib_j=0$ ,则 $i,j$ 不能同时存在,问有多少种选择方法。 解法 这个形式可以看成是点乘的形式...

Atcoder ABC 160

E 题意 你有$a\leq 1e5$个红球,$b\leq 1e5$绿球,$c \leq 1e5$个白球,每个球都有自己的价值.你要从中选$d\leq a$红球,$e\leq b$绿球,把一个白球染成红球或者染成绿球.求你能得到的最大价值 解法 枚举...

Atcoder ABC 159

F 题意 求长度为$n \leq 3000$的序列的每一个子串中和为$s$的子序列个数和. 解法 我们反过来求,对于一个 第一个元素在$j$,最后一个元素在$i$的子序列,那么它做出的贡献就是$j*(n-i+1)$,那么对于所有...

Atcoder ABC158

E 题意 求长度为$n$的数字串中,被素数$p$整除的子数字串的个数 解法 如果$p|n*10^{x}$,切$p\neq 2,5$ 那么$p|n$,那么从后往前维护$mod\ p$ 的后缀数,如果当前的余数是$x$,那么减去后面余数是$x$的就...

Atcoder ABC157

D 解法 一个人的 friend candidate 就是无向关系图中联通的,切不是坏朋友的非相邻点。那么只要用并查集求联通块的大小,并且记录在连通块中相邻点和坏朋友点的个数即可。 E 解法 用树状数组维护...

Atcoder ABC156

E 题意 有$n$个房间,刚开始每个房间都有1个人,一次 move 操作为一个房间的一个人到其它另外的房间去。问经过 $k$ 次 move 后,房间里人数情况有多少种 解法 首先我们只考虑最后的结果,不用考虑到...

Atcoder ABC155

D 题意 $N$个元素的数组,两两相乘会有$\frac{N*(N-1)}{2}$个新元素,求这些元素中第$K$大的元素 解法 很容易想到是二分。求的是((小于等于这个数字)的个数)大于等于$K$的最小数字。需要注意一下细...