Codeforces Round #419 简要题解
Div1Div2Karen and Morning暴力枚举即可。代码Karen and Coffee差分求出每个点被覆盖的次数，再求一个被覆盖次数是否 $\geq k$ 的前缀和即可。代码Karen and Game先把行尽量删完，再把列尽量删完，如果最后剩下了则无解。但这不一定是最优的，还有可能先把列尽量删完，再把行尽量删完。两种情况比一下即可。代码Karen and Test$n$ 为偶...
分类 题解 下的文章
- 首页
- 题解
AtCoder Regular Contest 079 简要题解
比赛地址警告：下面没有任何的证明。Cat Snuke and a Voyage最短路即可判一下有没有 $1\to n$ 或者 $1\to u\to n$ 即可。后面那个可以把 $1\to u$ 和 $u\to n$ 的 $u$ 分别标记一下。代码Decrease (Contestant ver.)既然是构造，那肯定令 $n=50$。那么，我们可以令最后的序列是 $n$ 个 $n-1$，然后还...
AtCoder Regular Contest 078 简要题解
比赛地址Splitting Pile枚举即可。代码Fennec VS. Snuke双方显然是先把对方到自己这边来的路堵上。于是我们只要找到分界点，看看哪边的点多即可。需要注意的是，如果两边的点一样多，那么是后手胜。代码Awkward Response首先可以把 $N$ 的位数确定出来：依次问 $1,10,100,\cdots$ 直到回答是 N，则前一个数和 $N$ 的位数相同。那么可以考虑二...
AtCoder Regular Contest 077 简要题解
比赛地址pushpush双端队列模拟即可。代码11显然有恰好一个数出现了 $2$ 次，设其出现的两个位置为 $l,r(l<r)$。考虑容斥。长度为 $k$ 的子序列数显然为 ${n+1\choose k}$，但其中有重复的。冷静分析一下可以发现，重复的一定是在 $l-1+(n+1-r)$ 个元素中选了 $k-1$ 个，和某个重复的数组成了子序列。所以答案为 ${n+1\choose k...
AtCoder Regular Contest 076 简要题解
比赛地址Reconciled?如果 $\lvert n-m\rvert>1$ 一定无解。否则，如果 $n=m$ 则答案为 $2\times n!\times m!$，如果 $\lvert n-m\rvert =1$ 则答案为 $n!\times m!$。代码Built?和某个切比雪夫距离最短路的题很像。对于每个点 $(x,y)$，向 $x$、$y$ 各连一条 $0$ 边。然后再把相邻两...
AtCoder Regular Contest 075 简要题解
比赛地址Bugged如果所有数的和不是 $10$ 的倍数答案就是所有数的和，如果所有数都是 $10$ 的倍数答案是 $0$，否则答案为所有数的和减去最小的不是 $10$ 的倍数的数。代码Widespread二分答案 $mid$，那么相当于先把所有怪物的血量减去 $b\times mid$，再补 $mid$ 次伤害为 $a-b$ 的攻击。我们只要对减去 $b\times mid$ 血后仍然活着...
AtCoder Regular Contest 074 简要题解
比赛地址Chocolate Bar横着竖着是一样的，这里只考虑横着。那么要么是横切三刀，要么是先横切一刀再竖切一刀。前面只要看 $H$ 是不是 $3$ 的倍数，不是的话差最小是 $W$。后面可以直接枚举横切在哪，竖切一定切在 $\frac{W}{2}$ 的位置。代码3N Numbers显然存在一个分界线 $i\in[n,2n]$，满足在 $[1,i]$ 中选了最大的 $n$ 个、在 $[i+...
AtCoder Regular Contest 073 简要题解
比赛地址Sentou按题意算一下即可。代码Simple Knapsack这个 $w_1\leq w_i\leq w_i+3$ 非常的有趣。可以想到设 $dp_{i,j,k}$ 表示前 $i$ 个物品，已选的体积是 $j\times w_1+k$ 时的最大价值，转移和背包相同。最后算答案时枚举一下合法的 $j,k$ 即可。代码Ball Coloring不妨设 $x_i\leq y_i$，最小的...
AtCoder Regular Contest 072 简要题解
比赛地址Sequence枚举第一个是正的还是负的，那么后面的符号都确定了。那么如果有一个前缀和不满足的话直接改成 -1 或 1 即可。可以证明这是最优的。代码Alice&Brown如果 $(n,m)$ 是先手必胜的，则存在一个 $(n-2x,m+x)$ 或一个 $(n+x,m-2x)$ 是先手必败的。于是手动打一个表可以发现 $(n,m)$ 必败当且仅当 $\lvert n-m\rvert ...
CF528E Triangles 3000
CodeforcesLuogu分析考虑三角形的面积公式：$S_{\triangle ABC}=\frac{1}{2}\left(\vec{OA}\times\vec{OB}+\vec{OB}\times\vec{OC}+\vec{OC}\times\vec{OA}\right)$，其中 $ABC$ 是逆时针顺序。于是可以枚举一条直线 $l_i$，然后枚举另一条直线 $l_j$，计算它与之前枚...