1450
P1450 [HAOI2008] 硬币购物 题解
原题链接:P1450 这道题被教练放到了状压 \(DP\) 的题单里面,但是正解却不是状压 \(DP\),而是背包 \(+\) 神奇容斥,只不过是用到了一些二进制状压的思想。 思路 首先看到题目立马就想到了多重背包,但是时间复杂度肯定接受不了,于是考虑优化背包。我们可以想到一个很神奇的性质:假设只有 ......
CF1450C2 Errich-Tac-Toe (Hard Version)
思路 实际上,如果你会简单版本,那么困难版本也没有那么难了。 同样考虑构造一种通解,如下, 红色的格子改为 X,绿色的格子改为 O,就是一种通解,同样的,这样改可能会超过棋子总数的 \(\frac 1 3\)。 将方案整体向上挪一格和两格可以得到一共三种通解,这三种通解需要改的棋子总数就是棋盘上的棋 ......
CF1450C1 Errich-Tac-Toe (Easy Version)
思路 如果去考虑 O 的摆放,再考虑那些改为 X,这样不好思考,实现也很不好写,所以我们可以考虑构造一种通解。 如果将上图所有标红的位置都放上 X,那么无论 O 如何放,都不可能胜利,而 X 因为原本就没有,所以摆上后也不可能胜利。 不过,因为更改的次数不能超过棋子总数的 \(\frac 1 3\) ......
P1450 [HAOI2008] 硬币购物 题解
# P1450 [HAOI2008] 硬币购物 题解 首先考虑只有一种硬币的情况。 如果取的数量没有限制,就是一个完全背包,$f_i$ 表示背包体积为 $i$ 的选择方案数,显然 $f_j = f_{j - v}$。 如果取的数量有限制,用多重背包做一遍会超时,考虑以下思路:所有方案数 - 不合法方 ......
CF1450C2 题解
[题目传送门](https://www.luogu.com.cn/problem/CF1450C2) 再不写题解社贡要掉到 $0$ 了。 ## 题目分析 显然如果 $3$ 个格子构成了满足获胜条件的情况,这 $3$ 个格子模 $3$ 的余数各不相同。 那么我们将格子按模 $3$ 的余数分为 $3$ ......
CF1450E Capitalism - 差分约束系统 - 最短路 -
题目链接:https://codeforces.com/contest/1450/problem/E 题解: 题目中的等式关系为 $a_u-a_v=1$ 和 $|a_u-a_v|=1$ 首先,等式关系不好处理,考虑化成不等式 第一种:$a_u-a_v\leq 1$ 且 $a_v-a_u\leq -1 ......
leetcode-1450-easy
Number of Students Doing Homework at Given Time Given two integer arrays startTime and endTime and given an integer queryTime. The ith student started ......