DDOSvoid's Blog

发表于 更新于 分类于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/contest/1398/problem/F

简要题意：给定一个包含 $0,1,?$ 的长度为 $n$ 的字符串 $S$，需要对 $k\in[1,n]$，求每次将 $S$ 中的 $?$ 变成 $0$ 或 $1$ 后的最多操作次数，对于某一个 $k$，字符串 $S$ 的一次操作为每次删掉连续 $k$ 个相同字符

$|S|\le 10^6$

阅读全文 »

发表于 更新于 分类于
本文字数： 2.1k 阅读时长 ≈ 2 分钟

题目描述

https://codeforces.com/gym/102798/problem/B

简要题意：给定一个 $n\times m$ 的四连通网格图，现在有 $k$ 个点不能走，另外还有 $q$ 次询问，每次询问给定起点 $(sx,sy)$ 和中终点 $(tx,ty)$，求起点到终点的最短路

$n\times m \le 2\times 10^5,k\le 42,q\le 10^5$

阅读全文 »

发表于 更新于 分类于
本文字数： 677 阅读时长 ≈ 1 分钟

利用多种操作进行构造为指定状态

  1. 操作可以交换顺序的情况下，考虑先进行某种操作，再进行其它操作

    CF 1443D Extreme Subtraction

    CF 1400E Clear the Multiset

利用一种或多种操作将两个状态变成一个状态

  1. 利用中间状态 $t$，构造 $a\rightarrow t\rightarrow b$

    CF 1382C2 Prefix Flip (Hard Version)

    2018-2019 ACM-ICPC, Asia Nanjing Regional Contest E Eva and Euro coins

二分图构造

  1. 简要题意：给定一张 $n$ 个点 $m$ 条边的无向连通图，每个点有一个权值 $a_i$，每次操作可以使一条边相连的两个点同时增加任意一个整数值，求是否能使所有点的权值都为 $0$​

    $n,m\le 2\times 10^5$

    简要题解：首先注意到我们的操作不能改变权值总和的奇偶性，所以如果和为奇数则一定不行

    然后我们注意到我们可以将距离为奇数的两个点同时增加相同的数值，距离为偶数的点一个增加另一个减少相同的数值

    这启示我们考虑二分图的性质，首先我们将这张图分成两种情况考虑，二分图和不是二分图

    如果该图是二分图，那么我们只需要看一下两边点的总和是否相等，相等则一定有解，不相等则一定无解

    如果该图不是二分图，那么就一定存在奇环，对于一个存在奇环的图，任意两个点都存在一条长度为奇数的路径，所以一定有解

    CF 1537F Figure Fixing

例题

2020 China Collegiate Programming Contest Changchun Onsite L. Coordinate Paper