本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-08 18:35:41
符合条件的 $x$ 肯定是 $b_1$ 的因数，暴力枚举并检查合法性就可以了。
__vector__ 的博客
博客
标签
暂无
P1072 题解
Educational Codeforces Round 9 题解
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-08 19:53:02
A
考虑倒推一开始的苹果总数，记为 $ans$。从最后一个顾客倒序枚举，如果没有赠送，那么 $ans \leftarrow 2ans$，如果赠送了，$ans \leftarrow 2ans+1$。
这样，计算出了一开始的苹果总数，然后再根据购买情况计算收益就可以了。
B
将原序列中原本属于 A 的设计为正值，原本属于 B 的值取反。
然后 Bob 显然会选择权值最大的前缀或后缀。
C
结论：字符串 $a,b$，$a$ 在 $b$ 前面当且仅当 $a+b$ 的字典序小于 $b+a$ 的字典序。
反证法易证。
D
设 $f_x$ 为数组中 $x$ 的因子个数。
答案显然是 $\max\limits_{x \in [1,l]}f(x)$。
E
本题正解为 FFT，但是暴力也可以通过，考虑暴力怎么写。
恰好 $k$ 个的限制很烦人，如果是小于等于 $k$ 个就简单多了。
实际上，只要有一个权值为 $0$ 的物品就可以满足这个要求。
没有怎么办？
那就将所有物品的权值减去最小值。
然后 dp 就非常简单了。
F
本题我被卡死，主要原因在于我对 MST 的性质不是很熟悉。
很像是一个邻接矩阵，考虑以此解题。
$a_{i,j} \le \max(a_{i,k},a_{k,j})$ 的限制，可以理解为一条边的权值不能是任意一个包含它的环的严格次大值。
刚好 MST 的树边也有这个性质，那么如何检测非树边？
假设存在一个不合法的非树边，考虑枚举这个非树边的其中一个端点作为树的根节点，若某个点与根的边权大于它通过树边到根的路径最大值，那么不合法。
CF449D
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-08 20:20:17
设 $f(s)$ 为最终 and 的的结果包含 $s$ 中所有的 $1$ 的方案数。
若 $popcount(x)$ 是偶数，那么答案加上这个 $f(x)$，否则减去 $f(x)$。
$f(s)$ 如何计算呢？
考虑求出所有满足 $x$ and $s = x$ 的 $x$，然后这些数可以任意选择，只是至少需要选择一个。
但是这些 $x$ 的数量如何求呢？
可以将这个过程视为一个 20 维的后缀和，每一维大小为 $2$，使用 sosdp 搞定。
DarkBZOJ3309 DZY Loves Math I 题解
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-08 21:57:32
这次又没能自己做出来，卡死在了线性筛那一步，参照的这篇题解。
$f(n)$ 代表 $n$ 的质因子的最大幂指数。
假设 $a \le b$。
求 $\sum\limits_{i=1}^a\sum\limits_{j=1}^b f(\gcd(i,j))$。
转化：
$\sum\limits_{d=1}^a\sum\limits_{i=1}^{\lfloor \frac{a}{d}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{b}{d} \rfloor} [(i,j)=1]f((i,j))$
$= \sum\limits_{d=1}^a f(d)\sum\limits_{i=1}^{\lfloor \frac{a}{d}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{b}{d} \rfloor} \sum\limits_{k|(i,j)}\mu(k) $
$=\sum\limits_{d=1}^a f(d)\sum\limits_{k=1}^{\lfloor \frac{a}{d}\rfloor}\mu(k) \lfloor\frac{a}{dk}\rfloor\lfloor\frac{b}{dk}\rfloor$。
为了方便求解，可以将其转化为 Dirchlet 卷积的形式，令 $T =dk$。
原式转化为：$\sum\limits_{T=1}^a \sum\limits_{d|T}f(d)\mu(\frac{T}{d})\lfloor\frac{a}{T}\rfloor\lfloor\frac{b}{T}\rfloor$。
设 $g(i) = \sum\limits_{d|i}f(d)\mu(\frac{i}{d})$，现在只需要找到一个方法快速求出 $g(1),g(2),\cdots,g(a)$，就可以使用整除分块解决本题。
假设线性筛当前筛到了 $x = a_1^{p_1}\cdot a_2^{p_2}\cdot \cdots \cdot a_kp^k$，$\frac{x}{d} = a_1^{q_1}\cdot a_2^{q_2}\cdot \cdots \cdot a_k^{q_k}$。
此时的背景是正在计算 $f(d)\mu(\frac{T}{d})$。
需要注意的是，由于莫比乌斯函数的性质，值若不为 $0$，那么 $q_i$ 只能为 $0$ 或 $1$。
考虑一件事情，如果 $x$ 的某个质数的幂次不等于 $f(x)$，那么这个质数归类于 $d$ 还是 $f(d)$ 不会导致 $f(d)$ 的变化，但是 $\mu(\frac{T}{d})$ 的值却会因此翻转，导致答案变为 $0$。
下面考虑 $x$ 的每个质因数的幂次相同的情况。
对于 "普通" 的情况，还是按照上一种。
特殊情况，就是 $1 \le \forall i \le k, q_i=p_i-1$，不难注意到这种情况不会被抵消掉。
经过上述分类讨论发现，只有这种特殊情况不会被抵消掉，得出结论：
- 若 $x$ 的质因子的幂次不全相同，那么 $g(x)=0$。
- 否则，令 $m$ 为 $x$ 的质因子个数，$g(x)=(-1)^{m+1}$。
然后就可以快乐的线性筛了。
BZOJ3512 DZY Loves Math IV 题解
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-09 11:02:14
这题难点子啊与拆开之后怎么整合到一个可以求解的式子。
参考题解 1
参考题解 2
求 $\sum\limits_{i=1}^n\sum\limits_{j=1}^m \ arphi(ij)$。
注意到 $n$ 比较小。
设 $s(n,m) = \sum\limits_{i=1}^m \ arphi(ni)$。
令 $n$ 的质因数分解为 $\prod\limits_{i=1}^kd_i^{p_i}$。
令 $a=\prod\limits_{i=1}^kd_i^{p_i-1},b=\frac{n}{a}$。
$S(n,m) = \sum\limits_{i=1}^m \ arphi(iab)$
$=a\sum\limits_{i=1}^m\ arphi(ib)$
$=a\sum\limits_{i=1}^m\ arphi(i\frac{b}{(i,b)}(i,b))$
$=a\sum\limits_{i=1}^m\ arphi(i\frac{b}{(i,b)})(i,b)$
$=a\sum\limits_{i=1}^m\ arphi(i)\ arphi(\frac{b}{(i,b)})(i,b)$
$=a\sum\limits_{i=1}^m\ arphi(i)\ arphi(\frac{b}{(i,b)})\sum\limits_{d|(i,b)}\ arphi(d)$
$=a\sum\limits_{i=1}^m\ arphi(i)\sum\limits_{d|(i,b)}\ arphi(d)\ arphi(\frac{b}{(i,b)})$
$=a\sum\limits_{i=1}^m\ arphi(i)\sum\limits_{d|(i,b)}\ arphi(\frac{b}{\frac{(i,b)}{d}})$
$=a\sum\limits_{i=1}^m\ arphi(i)\sum\limits_{d|(i,b)}\ arphi(\frac{b}{d})$
$=a\sum\limits_{d |b}\ arphi(\frac{b}{d})\sum\limits_{i=1}^{\lfloor\frac{m}{d}\rfloor}\ arphi(di)$
$=a\sum\limits_{d|b}\ arphi(\frac{b}{d})S(d,\lfloor \frac{m}{d}\rfloor)$。
我不会证明复杂度，递归到 $n=1$ 就杜教筛，$m=0$ 就返回 $0$。
积性函数前缀和科技 - 杜教筛
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-09 11:37:09
我不知道发明者是怎么想到这些的。
假设存在一个积性函数 $f$，给定一个 $n$，要求 $\sum\limits_{i=1}^nf(i)$。
设 $S(n) = \sum\limits_{i=1}^nf(i)$。
考虑另一个积性函数 $g$，它们的 Dirchlet 卷积的前缀和：
$\sum\limits_{i=1}^n (f*g)(i)$
$= \sum\limits_{i=1}^n \sum\limits_{d|i}f(d)g(\frac{i}{d})$
$=\sum\limits_{d=1}^ng(d)\sum\limits_{i=1}^{\lfloor \frac{n}{d}\rfloor}f(\frac{di}{d})$
$=\sum\limits_{d=1}^ng(d)\sum\limits_{i=1}^{\lfloor \frac{n}{d}\rfloor}f(i)$
$=\sum\limits_{d=1}^n f(d)S(\lfloor \frac{n}{d}\rfloor)$。
由此可得，$f(1)S(n) =\sum\limits_{i=1}^n(f*g)(i)- \sum\limits_{d=2}^nf(d)S(\lfloor\frac{n}{d}\rfloor)$。
现在的主要任务在于找到一个函数 $g$，使得 $f*g$ 的前缀和可以快速求出。另外，$\sum\limits_{d=2}^nf(d)S(\lfloor\frac{n}{d}\rfloor)$ 可以使用整除分块计算。
假设 $f*g$ 的前缀和可以 $O(1)$ 计算，那么最后整个算法的复杂度是 $O(n^{\frac{2}{3}})$ 的，前提是使用线性筛预处理出 $f$ 的前 $n^{\frac{2}{3}}$ 的值的前缀和。
Master 定理可以证明复杂度，不写了。
How to AK ABC388
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-12 10:04:30
耻辱啊，E 题贪心假掉吃 3 发，F 题没处理跳过区间的 cases，最后 wa 3 个测试点，G 题简单题结果没看，掉大分了。
感觉每道题都弱于 CF 1900，但赛时确实因为各种原因没过 F,G。
E
我写了 3 种直接贪心的方式，都是错的。
- 倒序枚举，遇到一个数，如果待匹配的集合内部存在一个数可以与之匹配，那么匹配最小的这个数。
- 正序枚举，其余和上述一致。
- 正序枚举，每次找到这个位置之后第一个能与自己匹配的，与之匹配。
考虑二分答案，设答案为 $k$。
显然选择前 $k$ 个和后 $k$ 个。
较为明显的，$1 \le \forall i \le k$，$i$ 个匹配 $n-(k-i)$ 个。
可以用类似于归纳法证明，第 $1$ 个元素需要匹配第 $n-k+1$ 个元素，如果不能匹配，则第 $[2,k]$ 个元素也不能与其匹配，而即使可以，第 $[2,k]$ 个元素匹配 $n-k+1$ 显然也不优。
随后问题就简化到了 $k-1$ 个元素的，得到证明。
F
只需要判断能否到达。
首先预处理出每个好区间 $[l,r]$，由于题目保证坏区间两两不相交，这个还是很容易的。
事实上，对于每个好区间 $[l,r]$ ，我们只关心 $[l,l+b]$ 和 $[r-b,r]$ 这个范围的位置能否到达。
如果 $a\neq b$，那么想要行走的距离 $len$ 足够大，就一定能走出这个距离。
那这个阈值如何计算呢？这个阈值小于等于使得 $xa+yb = len$ 无解的最大的 $len$，这刚好在 CCF 原题里面出现过，答案是 $ab-a-b$，代入 $a=19,b=20$ 得到这个无解的 $len$ 最大是 $341$，所以只需要处理 $len$ 在 $[0,341]$ 之间能否走出这个距离就可以。
对于 $a=b$ 的情况，只需要满足想要走的距离 $len$ 是 $a$ 的倍数就可以。
现在，设 $dp_{i,j}$ 代表第 $i$ 个好区间，左端点开始算第 $j$ 个位置能否被到达。设第 $i$ 个好区间是 $[l_i,r_i]$。
转移的话，先计算出 $[r_i-b,r_i]$ 区间哪些点可以到达。
随后，从 $[r_i-b,r_i]$ 区间的可以到达的点出发，枚举单次走的距离，更新后面区间的 $dp$ 值。
需要注意的是，这个过程可能会跳过一些区间。
比如，$3$ 个好区间 $[1,5],[7,10],[12,15]$，$a=b=8$，此时从 $5$ 出发将到达 $13$，跳过第一个区间直接到第 $3$ 个区间。
所以，不能简单的仅仅更新 $i+1$ 区间。
G
仍然沿用 E 题的 check 方法，仍然二分答案 $k$。
注意到对于第 $i$ 个位置，其作为较大值时，能匹配的位置是数组的一个前缀。
而合法的条件是对于 $(r-k+1) \le \forall i \le r$，第 $i$ 个位置向左最远的不可匹配的距离小于 $r-l+1-k$。
双指针预处理出每个位置作为较大值时，左边最远的不可匹配的距离，每次询问 ST 表就可以了。
CF529B 题解
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-17 21:27:23
模拟赛数据范围看成了 $10^5$，苦战 2h 得以战胜，好像爆标了官方 std？
正文
考虑要维护哪些信息。
首先按照套路，升序枚举每个可能的最大的 $h$，设当前枚举的最大 $h$ 为 $lim$。
现在，需要知道的是，有哪些展板必须翻转，使得不超过最大的 $h$。
如果存在一个展板无论如何，都不能靠翻转使得 $h \le lim$，那么当前无解，判定条件是 $\min(h,w)\gt lim$。
所以，维护一个 set 存储所有尚不合法的展板，第一关键字是 $\min(h_i,w_i)$，每次枚举 $lim$ 都更新这个 set。
当不合法的展板全部清空之后，考虑如何翻转这些展板。
对于一个满足 $w \gt h$ 的展板，如果能将 $w,h$ 交换之后满足 $h \le lim$，那么交换之后，$w$ 将减少 $w-h$，使得当前情况的答案减少 $(w-h)lim$。
但是，很多个展板都可能交换 $h,w$，得考虑哪些是真正需要交换的。
注意到，对于满足 $w \le lim \lt h$ 的展板，属于必须翻转。
对于剩下的名额，则优先给 $w-h$ 更大的展板。
考虑维护一个 set 存储所有可能交换 $h,w$ 的展板（不含强制交换），第一关键字是 $w-h$；再用一个 set 维护所有强制交换的展板，第一关键字是 $h$；再用一个 set 维护所有不允许交换的展板，第一关键字是 $w$。
考虑如何更新这些 set。
每次更新 $lim$ 时，由于对 $h$ 的限制变宽，依次执行下列操作：
- 强制交换的展板有一部分不再需要强制交换，原因是 $h \le lim$ 了，此时将它们从强制交换的 set 删除，当然，根据之前的定义，它们交换 $h,w$ 一定不优。
- 另外，一些展板不允许交换 $h,w$，原因是 $w \gt lim$，此时它们变得可能交换，将他们加入允许交换的集合。
- 一些不合法的集合变得合法，原因是此时 $\min(h,w) \le lim$ 了，分类讨论将它们归入允许交换或不允许交换的集合。
- 在允许交换 $h,w$ 的集合里面选择前 $\lfloor \frac{n}{2} \rfloor$ 大的，前提是 $h-w \le 0$，事实上前面加集合的时候就可以判断这点。另外，考虑用两个 set 维护允许交换 $h,w$ 的集合，小的那个的大小维持在 $\lfloor \frac{n}{2} \rfloor$ 及以下。
注意到，总共出现过 5 个 set，单个元素不可能被加入同一个 set 两次（除了允许交换的集合内部的两个 set，但是新加入一个元素最多造成 $1$ 的影响），所以复杂度 $O(n \log n)$。
#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
a=min(a,b);
}
template<class T>
T gcd(T a,T b){
return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
return a\/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
template<class T>
void wrint(T x){
if(x<0){
x=-x;
pc('-');
}
if(x>=10){
wrint(x\/10);
}
pc(x%10^48);
}
template<class T>
void wrintln(T x){
wrint(x);
pln
}
template<class T>
void read(T& x){
x=0;
int f=1;
char ch=gc;
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=gc;
}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);
ch=gc;
}
x*=f;
}
const int maxn=1005;
int n;
pll nd[maxn];
set<pll> notok;
set<pll> waitswp;\/\/ 交换之后更优，但是不可以交换，关键字 w
multiset<ll> canswp;\/\/ 可以交换，关键字 h-w
multiset<ll> canswp2;
set<pll> noswp;\/\/ 可能不需要交换，但强制交换，关键字 h
int k=n\/2;
ll w=0;
void solve(int id_of_test){
read(n);
vi ableh;
FOR(i,1,n){
read(nd[i].fi);
read(nd[i].se);
ableh.eb(nd[i].fi);
ableh.eb(nd[i].se);
notok.insert(mkpr(min(nd[i].fi,nd[i].se),i));
}
sort(ableh.begin(),ableh.end());
ll ans=1e18;
for(int h:ableh){
while(!noswp.empty()){
if(noswp.begin()->fi<=h){
int id=noswp.begin()->se;
if(nd[id].se>=nd[id].fi){
w-=nd[id].se;
w+=nd[id].fi;
}else{
canswp.insert(nd[id].se-nd[id].fi);
}
noswp.erase(noswp.begin());
}else break;
}
\/\/ puts("???1");
while(!waitswp.empty()){
if(waitswp.begin()->fi<=h){
int id=waitswp.begin()->se;
canswp.insert(nd[id].se-nd[id].fi);
w+=(nd[id].se-nd[id].fi);
waitswp.erase(waitswp.begin());
}else break;
}
\/\/ puts("???2");
while(!notok.empty()){
\/\/ puts("wtf");
if(notok.begin()->fi<=h){
int id=notok.begin()->se;
if(nd[id].se<=h){
w+=nd[id].fi;
if(nd[id].fi>nd[id].se){
if(nd[id].fi>h){
waitswp.insert(mkpr(nd[id].fi,id));
}else{
w+=(nd[id].se-nd[id].fi);
canswp.insert(nd[id].se-nd[id].fi);
}
}
}else{
if(nd[id].fi<=h){
w+=nd[id].se;
noswp.insert(mkpr(nd[id].se,id));
}else{
break;
}
}
notok.erase(notok.begin());
}else break;
}
if(!notok.empty())continue;
while(!canswp.empty()&&canswp.size()+noswp.size()>n\/2){
w-=*prev(canswp.end());
canswp2.insert(*prev(canswp.end()));
canswp.erase(prev(canswp.end()));
}
while(!canswp2.empty()&&canswp.size()+noswp.size()<n\/2){
w+=*canswp2.begin();
canswp.insert(*canswp2.begin());
canswp2.erase(canswp2.begin());
}
\/\/ printf("w %lld\n",w);
if(canswp.size()+noswp.size()>n\/2)continue;
ckmn(ans,w*h);
}
printf("%lld\n",ans);
}
int main()
{
int T;
T=1;
FOR(_,1,T){
solve(_);
}
return 0;
}
CF1109F 题解
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-02-02 18:18:05
第一道自己想出做法的 CF Div.1 F，记录一下它的两种维护方式。
问题转化
$n$ 个点，每个点的度数最多是 $4$。
求有多少个点对 $(l,r)$ 满足 $1 \le l \le r \le n$，使得 $[l,r]$ 中的点构成的导出子图是一棵树。
考虑合法条件。
- 不能存在环。
- 边数等于点数减一。
考虑编号升序枚举右端点，想一想哪些左端点是符合要求的。
- 仅考虑条件一
注意到，如果 $[l,r]$ 合法，那么 $r \ge \forall l' \gt l$，$[l',r]$ 是合法的。在右端点递增的情况下，最小的符合要求的左端点是单调不降的。
基于此性质，可以双指针。右端每新增一个点，就需要从左端弹出若干个点，使得加上新的边后不会形成环，此过程可以 LCT 维护。
整体二分同样可以完成任务。
至此，求出了每个右端点对应哪些符合条件一的左端点。 - 考虑条件二
考虑对每个点维护一个权值，代表其作为左端点时，总点数减去边数是多少。
枚举右端点的时候使用线段树动态更新就可以。 注意到对于符合条件一的左端点，其权值必然大于等于 $1$，问题可以转化为求最小值及其出现次数。
虽然 LCT 常数巨大，但是在这道题可以吊打普通的整体二分。
其中 LCT 维护的时间复杂度是 $O(nm \log nm)$，整体二分多一个并查集的复杂度。
CF2042C 题解
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-04 01:27:55
考虑将一个完整的区间拆成两段的贡献是什么。
假设 $[l,r]$ 拆为 $[l,mid],[mid+1,r]$。
那么 $[mid,n]$ 所有鱼的价值加 $1$。
注意到，此时本质上是从 $mid+1$ 开始，每个点的编号加了 $1$。
也就是说，问题转化为：$[2,n]$ 共 $n-1$ 个点，对于每个点，都可以选择是否将从这个点开始的所有点的价值加 $1$。
假设一条鱼如果是 Bob 获得，那么是 $1$，反之 $-1$，设 $p_i$ 代表前 $i$ 个鱼的前缀和。
假设第 $i$ 个点选择将其开始的所有点价值加 $1$，那么 Bob 领先 Alice 的分数将会增加 $p_n-p_{i-1}$。
接下来排序贪心就可以。
共 320 篇博客
鲁ICP备2025150228号