DDOSvoid's Blog

题目描述

https://codeforces.com/gym/103438/problem/G

简要题意：给定 $2n$ 个数对 $(a_i,b_i)$，现在要求将这 $2n$ 个数对分成 $n$ 组，如果 $x$ 和 $y$ 分到一组，那么这一组的贡献是 $max\lbrace|a_i-a_j|,|a_i-b_j|,|b_i-a_j|,|b_i-b_j|\rbrace$，求最大分配

题目描述

https://codeforces.com/problemset/problem/1628/E

简要题意：给定一棵 $n$ 个点的树，现在有 $m$ 次操作，操作有三种，操作一给定一个区间 $[l,r]$，将编号在 $[l,r]$ 内的点都染成白色；操作二给定一个区间 $[l,r]$，将编号在 $[l,r]$ 内的点都染成黑色；操作三给定一个点 $x$，求 $x$ 到黑点的最大瓶颈距离，要求是简单路径，且不包括 $x$，不存在输出 $-1$，初始时所有点都是白色

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

题目描述

https://codeforces.com/problemset/problem/1638/E

简要题意：现在有一个长度为 $n$ 的数列 $a_i$，初始时，每个位置的值都是 $0$，颜色为 $1$，现在有 $m$ 个操作，操作有三种：给定区间 $[l,r]$ 和颜色 $c$，将区间 $[l,r]$ 染成 $c$；给定颜色 $c$ 和值 $x$，将所有颜色为 $c$ 的位置的值增加 $x$；给定位置 $i$，求 $a_i$

$n,m\le 10^6$

题目描述

https://www.luogu.com.cn/problem/P5490

简要题意：给定 $n$ 个矩形，求这些矩形的并集覆盖的总面积，注意这里面积是连续而不是离散的

$n\le 10^5$

题目描述

https://codeforces.com/problemset/problem/1637/F

简要题意：给定一棵 $n$ 个节点的树，每个点有一个权值 $h$，现在要选择若干个点将其染色并赋一个值 $w$，要求染色之后，对于每个点 $x$，都存在两个染过色的点 $u$ 和 $v$，满足 $min\lbrace w_u,w_v\rbrace\ge h_x$ 且 $x$ 位于 $u$ 和 $v$ 的最短路径上，注意 $u$ 不能等于 $v$，如果给一个染色点赋值为 $x$，那么将产生 $x$ 花费，求最小花费

$n\le 2\times 10^5$

题目描述

https://codeforces.com/problemset/problem/1634/F

简要题意：给定两个长度为 $n$ 的数列 $a_i,b_i$，现在有 $m$ 个操作，每次操作给定一个区间 $[l,r]$ 以及将要操作的数列是 $a$ 还是 $b$，然后将区间内的数按顺序加上 $f_i$，其中 $f$ 是斐波那契数列，求每次操作后 $a$ 数列是否和 $b$ 数列完全相同

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

题目描述

http://codeforces.com/contest/547/problem/D

简要题意：现在有 $n$ 个点 $(x_i,y_i)$，要求将每个点染成红色或者蓝色，且横坐标相同的点中蓝色和红色点的数量相差不超过 $1$，纵坐标同理

$n\le 2\times 10^5$

题目描述

https://codeforces.com/problemset/problem/1634/E

简要题意：给定 $n$ 个数列，第 $i$ 个数列的长度为 $m_i$，现在要求将这 $\sum_{i=1}^nm_i$ 个数划分进两个可重集合中，要求这两个可重集合完全相同，每个数只能进一个集合，同时必须保证每个数列都有恰好一半的数进入 $A$ 集合，另一半进入 $B$ 集合

$n\le 10^5,\sum_{i=1}^nm_i\le 2\times 10^5$

题目描述

https://codeforces.com/contest/1634/problem/B

简要题意：给定一个长度为 $n$ 的数列 $a_i$，现在 $Alice$ 手上有一个数 $x$，$Bob$ 手上的数是 $x+3$，对于这个数列，每个人都从 $a_1$ 开始到 $a_n$ 按顺序操作，对于当前数 $a_i$，可以选择将手上的数 $x$ 加上 $a_i$，或者将 $x$ 异或上 $a_i$，现在给定一个数 $y$，求 $y$ 是 $Alice$ 操作得到的还是 $Bob$ 操作得到的，题目保证 $y$ 一定是其中一个人操作得到的

$n\le 10^5$

题目描述

https://codeforces.com/contest/1633/problem/E

简要题意：给定一个 $n$ 个点 $m$ 条边的带权无向图，现在有 $k$ 次询问，每次询问给定一个常数 $x$，求如果将边权改为 $|w-x|$，$w$ 为改之前的边权，求最小生成树

$n\le 50,m\le 300,k\le 10^7$