Codeforces Round #614 (Div. 1) NEKO's Maze Game 动态维护有多少对格子可以阻碍 $(1,1)$ 和 $(2,n)$ 相连,如果存在则意味着 No,否则为 Yes,模拟即可。 const int N = 1e5 + 7; int n, q, a[2][N], an...
题解
CF587D Duff in Mafia 题解
CF587D Duff in Mafia 题意 给定一张 $n$ 个点 $m$ 条边的无向图,每条边有一个颜色 $c$ 和权值 $t$。 你要选出一些边,使得它们是一个匹配,同时剩下的边每种颜色也是一个匹配。 同时,你要最小化选出的...
CF575I Robots protection 题解
CF575I Robots protection 题意 你需要在平面直角坐标系上进行 $q$ 次操作。 每次操作有两种,要么放置一个两条直角边平行于坐标轴的等腰直角三角形,要么查询某一个点被多少个三角形覆盖。 每个等腰直角...
CF504E Misha and LCP on Tree 题解
CF504E Misha and LCP on Tree 题意 给定一棵 $n$ 个节点的树,每个节点有一个小写字母。 有 $m$ 组询问,每组询问为树上 $a \to b$ 和 $c \to d$ 组成的字符串的最长公共前缀。 $n \le 3 \times 10^5$,$...
CF521D Shop 题解
CF521D Shop 题意 有 $k$ 个正整数 $a_{1\dots k}$。 有 $n$ 个操作,每个操作给定正整数 $b$,有三种可能:将 $a_i$ 赋值为 $b$,将 $a_i$ 加上 $b$,将 $a_i$ 乘以 $b$。 你可以从 $n$ 个操作中选择最多...
Educational Codeforces Round 80 (Rated for Div. 2) 题解
Educational Codeforces Round 80 (Rated for Div. 2) Deadline 在 $\sqrt d$ 附近枚举。 inline void solve() { int n, d; rd(n), rd(d); int x = sqrt(d); for (int i = max(0, x - 10)...
CF568E Longest Increasing Subsequence 题解
CF568E Longest Increasing Subsequence 题意 给定一个长度为 $n$ 的有 $k$ 个空缺的序列。 你有 $m$ 个数可以用于填补空缺。 要求最大化最长上升子序列的长度。 $n, m \le 10^5$,$k \le 10^3$。 题解 ...
CF538H Summer Dichotomy 题解
CF538H Summer Dichotomy 题意 有 $T$ 名学生,你要从中选出至少 $t$ 人,并将选出的人分成两组,可以有某一组是空的。 有 $n$ 名老师,每名老师要被分配到两个小组之一,对于第 $i$ 名老师,要求所在的小...
Codeforces Round #613 (Div. 2) 题解
Codeforces Round #613 (Div. 2) Mezo Playing Zoma 贪心。 int main() { int n; string s; cin >> n >> s; int l = 0, r = 0; for (int i = 0; i < n; i++) ...
CF526F Pudding Monsters 题解
CF526F Pudding Monsters 题意 给定一个 $n \times n$ 的棋盘,其中有 $n$ 个棋子,每行每列恰好有一个棋子。 求有多少个 $k \times k$ 的子棋盘中恰好有 $k$ 个棋子。 $n \le 3 \times 10^5$。 题解 ...