Public Round #14 A 安顿 题解
Description 对于一个数组 AAA 和数字 XXX，让我们定义 f(A,X)f(A,X)f(A,X) 如下： 如果不能将 AAA 拆分为几个子段使得每个子数组中所有元素的异或不等于 XXX，则 f(A,X)=0f(A,X)=0f(A,X)=0。 否则，f(A,X)f(A,X)f(A,X) 等于这种拆分中最大可能的子段数。 给定整数 N,KN,KN,K 和 XXX，其中 0≤X<2
P11647 【MX-X8-T6】「TAOI-3」俄罗斯蓝猫 题解
Description 有 nnn 个 [0,1018][0, 10^{18}][0,1018] 之间随机的整数。可以提出两次询问，每次询问给出不超过 n−1n-1n−1 个二元组 (xi,yi)(x_i,y_i)(xi,yi)。返回 axi+ayia_{x_i}+a_{y_i}axi+ayi 从小到大排序的结果。 不能询问 (i,i)(i,i)(i,i) 或者重复的无序对 (i,j
模拟费用流学习笔记
首先模拟费用流有两种不同的方法： 如果不要求动态加入或者删除，只需要求全局的费用流或者流量小于等于某个数的费用流，可以用 EK 增广的方法，每次选当前图上费用最优的增广路增广。 如果要求动态加入并且只要求费用最优，可以每次选择费用最小的源汇路径或者一个经过新加的点的费用最小的负环进行增广。 注：EK 增广的时候一定不会出现环，并且第一个方法与源点或者汇点相连的边也一定不会发生退流。
P8291 [省选联考 2022] 学术社区 题解
Description 以下涉及的所有字符串判等操作都对大小写敏感，例如 1oushang、Loushang、LOUSHANG 是互不相同的字符串。 小 I 正在整理学术社区中的一个帖子。帖子中一共有 NNN 个网友发过消息，他们的网名分别为 n1,n2,…,nNn_1, n_2, \ldots, n_Nn1,n2,…,nN。帖子中总共有 MMM 条消息，对于第 iii 条消息，我们用三个
LOJ #3273. 「JOISC 2020 Day1」扫除 题解
Description 平面直角坐标系上一个等腰直角三角形，维护 444 种操作： 加入 (x,y)(x,y)(x,y)。 把 y≤ly\leq ly≤l 的点横坐标变成 max(x,n−l)\max(x,n-l)max(x,n−l)。 把 x≤lx\leq lx≤l 的点纵坐标变成 max(y,n−l)\max(y,n-l)max(y,n−l)。 查询第 iii 个点现在的位置。
P6779 [Ynoi2009] rla1rmdq 题解
Description 给定一棵 nnn 个节点的树，树有边权，与一个长为 nnn 的序列 aaa。 定义节点 xxx 的父亲为 fa(x)fa(x)fa(x)，根 rtrtrt 满足 fa(rt)=rtfa(rt)=rtfa(rt)=rt。 定义节点 xxx 的深度 dep(x)dep(x)dep(x) 为其到根简单路径上所有边权和。 有 mmm 次操作： 1 l r：对于 l≤i≤rl
CF1477D Nezzar and Hidden Permutations 题解
Description 给定一张 nnn 个点 mmm 条边的简单无向图，构造两个排列 p,qp,qp,q，使得： 对任意 (u,v)∈E(u,v)\in E(u,v)∈E，(pu−pv)(qu−qv)>0(p_u-p_v)(q_u-q_v)>0(pu−pv)(qu−qv)>0. 在此基础上，最大化 ∣{i ∣ pi≠qi}∣\left|\left\{i\ |\ p_
CF1017G The Tree 题解
Description 给定一棵树，维护以下 333 个操作： 1 x 表示如果节点 xxx 为白色，则将其染黑。否则对这个节点的所有儿子递归进行相同操作。 2 x 表示将以节点 xxx 为根的子树染白。 3 x 表示查询节点 xxx 的颜色。 n,q≤105n,q\leq 10^5n,q≤105。 Solution 首先考虑没有操作二怎么做。 容易发现在点 xxx 进行的操作