月度归档: 2020年8月

19 篇文章

[Codeforces]1399F – Yet Another Segments Subset
Before the Beginning转载请将本段放在文章开头显眼处,如有二次创作请标明。原文链接:https://www.codein.icu/cf1399F/题意选出若干线段,使其两两不相交,求最多选多少。解法先离散化坐标。设 $f(l,r)$ 为区间 $[l,r]$ 中满足条件的最大选出线段数量。首先有 $f(l,r) = f(l,r-1)…
[Codeforces]1389E – Weight Division
Before the Beginning转载请将本段放在文章开头显眼处,如有二次创作请标明。原文链接:https://www.codein.icu/cf1399E/E1题意给一棵带边权的树,每次操作可以使 $w:=\lfloor \dfrac{w}{2} \rfloor$,定义 $i \in leaves,W(i)$ 为叶子节点 $i$ 到根节点 …
[Codeforces]Global Round 10
Before the Beginning转载请将本段放在文章开头显眼处,如有二次创作请标明。原文链接:https://www.codein.icu/cf1392/前言补题。C一次选择一段连续的单调不减的元素加一,问最少多少次操作后,整个数组单调不减。差分一下,$d(i) = a(i) - a(i-1)$,然后每个 $d(i) < 0$ 都加上…
[Atcoder]ABC175 题解(A-E)
Before the Beginning转载请将本段放在文章开头显眼处,如有二次创作请标明。原文链接:https://www.codein.icu/atcoderabc175/前言乱序开题。C移动到最小正数,然后到最大负数。最小正数和最大负数的绝对值都是 $< d$ 的,而如果剩余步数为偶数次,则一定回到正数,否则一定回到负数。没看到 $X$…
[Codeforces]1389F – Bicolored Segments
Before the Beginning转载请将本段放在文章开头显眼处,如有二次创作请标明。原文链接:https://www.codein.icu/cf1389f/题意定义坏对为:两个线段相交且颜色不同。求最多选出多少个线段,能保证没有坏对。解法虽然两个颜色让人很容易想到二分图之类的东西,但这题更易理解的应该是动态规划做法。先对坐标离散化一下方便处…
[Codeforces]1398D – Rearrange
Before the Beginning转载请将本段放在文章开头显眼处,如有二次创作请标明。原文链接:https://www.codein.icu/cf1398d/题意给一个矩阵,其中元素值遍历 $1,2,\ldots,n \times m$,定义 $X$ 为每行最大值构成的集合,$Y$ 为每列最大值构成的集合,要求构造一个矩阵,使得:$X$ 与原…