ww3113306

该文被密码保护。 阅读全文

该文被密码保护。 阅读全文

该文被密码保护。 阅读全文

该文被密码保护。 阅读全文

该文被密码保护。 阅读全文

摘要： 题意 一共有$n$个人，他们开始互不认识，而每天早上不认识的两个人会变成朋友。一共有$m$天，每天晚上有的人要去旅行，去旅行的人必须满足ta有至少$k$个朋友也去旅行 求每天去旅行的最大人数 题解 首先考虑一个朴素暴力： 对于每次询问，在原图上不断删点，直到没有点的度小于k。 复杂度O(nm) 然后 阅读全文

摘要： CF1088F Ehab and a weird weight formula 题意 给定一棵树，点有点权，其中这棵树满足除了权值最小的点外，每个点至少有一个点权小于它的相邻点。 要求你重新构建这棵树，使得代价最小。计算代价的方法如下： 点的代价： $deg_xv_x$,其中$deg_x$表示点$x 阅读全文

该文被密码保护。 阅读全文

摘要： 题面 "[USACO12NOV]同时平衡线Concurrently Balanced Strings" 题解 考虑DP。 $f[i]$表示以$i$为左端点的合法区间个数。令$pos[i]$表示以$i$为左端点，最靠左的合法右端点。 那么有如下转移： $f[i] = f[pos[i] + 1] + 1 阅读全文

摘要： 题面 "[BJOI2017]树的难题" 题解 考虑点分治。 对于每个点，将所有边按照颜色排序。 那么只需要考虑如何合并2条链。 有2种情况。 合并路径的接口处2条路径颜色不同 合并路径的接口处2条路径颜色相同 我们分别考虑这2种情况。 维护2棵线段树，分别表示与当前接口颜色不同和颜色相同。 如果我们 阅读全文