本文选取题目源于此处。
CF2071C Trapmigiano Reggiano
以终点 $t$ 为树的根节点。
那么求排列等价于求一种移动顺序，使得老鼠最后停留在根节点。
移动可以分两种：向上和向下。显然向上是更优的。
设老鼠当前位于节点 $p$，如果在 $x$ 处生成一个奶酪：
- 若 $x$ 是 $p$ 的祖先节点，则这是优的。
- 若 $x$ 是 $p$ 的子树内节点，则这是劣的。
- 否则 $x$ 仍然是优的，因为 $p$ 会走向 $\operatorname{lca}(x,p)$，会向上。
考虑先将子树内的走完，因此可以贪心：先走深度大的节点。
参考代码
```cpp //#include<bits/stdc++.h> #include-
using namespace std;
constexpr const int N=1e5;
int n,s,t,depth[N+1];
vector
参考代码
```cpp //#include<bits/stdc++.h> #include-
using namespace std;
constexpr const int N=1e5;
struct segTree{
struct node{
int l,r;
int sum,tag;
int size(){
return r-l+1;
}
}t[N<<2|1];
void up(int p){
t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
void build(int p,int l,int r){
t[p]={l,r};
if(l==r){
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
void down(int p){
t[p<<1].sum+=t[p<<1].size()*t[p].tag;
t[p<<1].tag+=t[p].tag;
t[p<<1|1].sum+=t[p<<1|1].size()*t[p].tag;
t[p<<1|1].tag+=t[p].tag;
t[p].tag=0;
}
void add(int p,int l,int r,int k){
if(l<=t[p].l&&t[p].r<=r){
t[p].sum+=t[p].size()*k;
t[p].tag+=k;
return;
}
down(p);
if(l<=t[p<<1].r){
add(p<<1,l,r,k);
}
if(t[p<<1|1].l<=r){
add(p<<1|1,l,r,k);
}
up(p);
}
int query(int p,int x){
if(t[p].l==t[p].r){
return t[p].sum;
}
down(p);
if(x<=t[p<<1].r){
return query(p<<1,x);
}else{
return query(p<<1|1,x);
}
}
}t;
int n,a[N+1];
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
t.build(1,1,n);
while(m--){
int l,r;
cin>>l>>r;
t.add(1,l,r,1);
}
for(int i=1;i<=n;i++){
int f=t.query(1,i);
if(!__lg(a[i])){
continue;
}
while(f){
int x=ceil(1.0*((1<<__lg(a[i])+1)-a[i])/__lg(a[i]));
x=min(x,f);
f-=x;
a[i]+=x*__lg(a[i]);
}
}
for(int i=1;i<=n;i++){
cout<<a[i]<<' ';
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```
</details>
# [[ABC412E] LCM Sequence](https://www.luogu.com.cn/problem/AT_abc412_e)
记 $a_i=\operatorname*{lcm}\limits_{j=1}^ij$，求 $a_l,a_{l+1},a_{l+2},\cdots,a_r$ 中不同的数的个数。
显然 $a_{i-1},a_i$ 不同当且仅当 $a_i$ 的某一个质因子的指数大于 $1\sim i-1$ 的该质因子的最大指数。而 $a_i$ 又需要最小，因此这个 $a_i$ **一定是质数的幂**。
$a_l$ 单独算作一个不同的整数，因此找 $[l+1,r]$ 内的质数幂即可。
***
对于二次幂及以上，可以通过埃式筛筛出 $\left[2,\sqrt r\right]$ 内的质数 $\textit{prime}$ 之后暴力枚举 $\textit{prime}$ 的幂次判断是否在 $[l+1,r]$ 内。
这样的复杂度是 $\mathcal O\left(\sqrt r\log\log\sqrt r+\dfrac{\sqrt r}{\ln\sqrt r}\log r\right)$ 的，可以接受。
对于 $[l+1,r]$ 内的质数，可以在之前 $\left[2,\sqrt r\right]$ 的质数的基础上，使用埃式筛筛出 $[l+1,r]$ 内的合数，剩下即为质数。（当然，你使用 Miller-Rabin 素性测试也可以，但是我背不下来。）
***
时间复杂度 $\mathcal O\left(\sqrt r\log\log\sqrt r+\dfrac{\sqrt r}{\ln\sqrt r}\log r+(r-l)\ln\sqrt r\right)$。三项分别为埃式筛筛质数、暴力判断幂次、埃式筛筛合数。
参考代码
```cpp //#include<bits/stdc++.h> #include-
using namespace std;
#define int ll
typedef long long ll;
constexpr const int N=1e7;
int query(int l,int r){
static int prime[N+1],vis[N+1],size;
int ans=1;
l++;
int t=sqrt(r);
for(int i=2;i<=t;i++){
if(!vis[i]){
vis[i]=i;
prime[++size]=i;
for(ll j=i*i;j<=t;j+=i){
vis[j]=i;
}
}
}
static bool flag[N+1];
for(int i=1;i<=size;i++){
ll powPrime=prime[i];
for(int k=1;powPrime<=r;k++,powPrime*=prime[i]){
if(l<=powPrime){
ans++;
flag[powPrime-l]=true;
}
}
}
for(int i=1;i<=size;i++){
for(int j=(l+prime[i]-1)/prime[i]*prime[i];j<=r;j+=prime[i]){
flag[j-l]=true;
}
}
for(int i=l;i<=r;i++){
ans+=!flag[i-l];
}
return ans;
}
main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int l,r;
cin>>l>>r;
cout<<query(l,r)<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```
</details>
# [[FJCPC 2025] 构造大师贝贝](https://www.luogu.com.cn/problem/P13098)
注意到 $T\leq1000$，但是 $n\leq10^{12}$。那么从时间复杂度的角度考虑，应当为一个类似于 $\mathcal O(T\log n)$ 的复杂度。
但是这道题的思维难度也就在这里了，将 $n$ 变为完全平方数，每次加上约数 $x$，很不好想到有什么带 log 的做法。
本题为 Special Judge，只需要输出任意一种构造方案。经过一些~~胡乱尝试~~猜测，想到也许可以想办法将 $n$ 构造为形如 $x^{2k}$ 的完全平方数。
那么考虑将其构造为 $2^{2k}$，每次只需要加上 $\operatorname{lowbit}(n)$ 即可，$\operatorname{lowbit}(n)$ 定义同树状数组。
参考代码
```cpp //#include<bits/stdc++.h> #include-
using namespace std;
typedef long long ll;
ll lowbit(ll n){
return n&-n;
}
bool check(ll n){
ll x=sqrt(n);
return x*x==n;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--){
ll n;
cin>>n;
vector
参考代码
```cpp //#include<bits/stdc++.h> #include-
using namespace std;
typedef long long ll;
constexpr const int N=2e5,V=1e9;
int n,a[N+1];
ll pre[N+1];
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
pre[i]=pre[i-1]+a[i];
}
deque
参考代码
```cpp //#include<bits/stdc++.h> #include-
using namespace std;
constexpr const int N=5000;
int cnt[N*N+1];
int f(int n){
for(int a=1;a<=n;a++){
for(int b=a;b<=n&&a*a+b*b<=n*n;b++){
cnt[a*a+b*b]++;
}
}
int ans=0;
for(int h=1;h<=n;h++){
for(int k=h;k<=n;k++){
ans+=cnt[k*k-h*h];
}
}
return ans;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
cout<<f(n)<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```
</details>
# [[ARC198B] Rivalry](https://www.luogu.com.cn/problem/AT_arc198_b)
$x$ 个 $0$，$y$ 个 $1$，$z$ 个 $2$，排成一个环，要求 $2$ 旁边为两个 $1$ 或 $0$，$1$ 旁边一个 $0$。
容易发现，$0$ 是最好的，放在哪里都合法。
考虑插入所有 $0$，再考虑 $1,2$。则两个 $0$ 中间存在两个 $1$ 或一个 $2$。
考虑最终是一个环，因此若有解，则有有 $2x\geq y,x\geq z$。
并且，若 $y\bmod 2=1$ 且 $z=0$ 的时候无解；因为此时会有两个 $0$ 中间只有一个 $1$，放一个 $2$ 进去就好了。
参考代码
```cpp //#include<bits/stdc++.h> #include-
using namespace std;
bool check(int x,int y,int z){
return x*2>=y&&x>=z&&(y%2==0||z>0);
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--){
int x,y,z;
cin>>x>>y>>z;
cout<<(check(x,y,z)?"Yes":"No")<<'\n';
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```
</details>
# [[常州市赛 2023] ABC 字符串](https://www.luogu.com.cn/problem/B4218)
$s$ 仅包含 `A`、`B`、`C`，每次可以将子串 `ABC` 换为 `BCA`。不难发现就是将 `A` **移到了最后**。
那么考虑 `ABC` 两边是什么。`ABC` 后面是若干个 `BC`，则可以将 `A` 换到后面之后继续操作。同时 `ABC` 前面的若干个 `A`，在 `BC` 换到前面后也可以继续操作。记 `ABC` 前面（包含本身）**连续** `A` 的个数为 $\textit{cntA}$，后面**连续** `BC` 的个数为 $\textit{cntBC}$，则有这一个 `ABC` 子串的贡献为 $\textit{cntA}\cdot\textit{cntBC}$。
可以简单地 $\mathcal O(n)$ 维护这个过程。
参考代码
```cpp //#include<bits/stdc++.h> #include-
using namespace std;
typedef long long ll;
constexpr const int N=2e5;
int n,cntA[N+1],cntBC[N+1];
char s[N+1];
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>(s+1);
n=strlen(s+1);
ll ans=0;
int cntA=0;
for(int i=1;i<=n-1;){
if(s[i]=='A'){
cntA++;
i++;
}else if(s[i]=='B'&&s[i+1]=='C'){
int cntBC=0;
for(;i+1<=n;i+=2){
if(s[i]=='B'&&s[i+1]=='C'){
cntBC++;
}else{
break;
}
}
ans+=1ll*cntA*cntBC;
}else{
cntA=0;
i++;
}
}
cout<<ans<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```
</details>
# [[JSOI2015] 最大公约数](https://www.luogu.com.cn/problem/P5502)
给定长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，定义 $a_l,a_{l+1},\cdots,a_r$ 的权值为 $(r-l+1)\gcd(a_l,a_{l+1},\cdots,a_r)$。
求最大权值，$1\leq a_i\leq10^{12},1\leq n\leq10^5$。
若 $l<l'\leq r$，则有 $\gcd(a_l,a_{l+1},\cdots,a_r)\geq\gcd(a_{l'},a_{l'+1},\cdots,a_r)$。原因显然。
而当 $\gcd$ 一定的时候，显然区间长度越长越好。因此对于确定的左端点 $l$，不断通过二分找到当前 $\gcd$ 的右端点，更新答案即可。
这样的端点至多只有 $\mathcal O(\log V)$ 个，因为 $\gcd$ 减少至少会减少一半。
实现上可以通过 ST 表/线段树等数据结构来维护区间 $\gcd$。
时间复杂度：$\mathcal O(n\log n\log V)$。
参考代码
```cpp //#include<bits/stdc++.h> #include-
using namespace std;
#define int ll
typedef long long ll;
constexpr const int N=100000;
template
关于答案正确性
若 $s(x)=s(m-f_{k-1}(s(x)))$ 成立，则有且仅有一个合法的 $x$。
假设 $\exist x_1\neq x_2,s(x_1)=s(x_2)$ 满足上述条件。
那么，$m-f_{k-1}(s(x))$ 在 $x=x_1,x_2$ 时相同，然而 $x_1\neq x_2$，与此矛盾。
故，答案一一对应。
参考代码
```cpp //#include<bits/stdc++.h> #include-
using namespace std;
typedef long long ll;
constexpr const int V=162;
int k;
int s(ll x){
int ans=0;
while(x){
ans+=x%10;
x/=10;
}
return ans;
}
ll f[V+1];
void pre(){
if(!k){
return;
}
k--;
for(int i=1;i<=V;i++){
if(k==0){
f[i]=i;
}else if(k==1){
f[i]=i+s(i);
}else{
f[i]=i+s(i)+(k-1ll)*s(s(i));
}
}
k++;
}
int query(ll m){
if(!k){
return 1;
}
int ans=0;
for(int i=1;i<=V;i++){
if(i==s(m-f[i])){
ans++;
}
}
return ans;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T;
cin>>T>>k;
pre();
while(T--){
ll m;
cin>>m;
cout<<query(m)<<'\n';
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```
</details>
# [[ARC203B] Swap If Equal Sum](https://www.luogu.com.cn/problem/AT_arc203_b)
若 $a,b$ 总和不同，显然无解。
诈骗题。第一眼可能会想到神秘 DP，但是又无从下手。
操作等价于：
1. 交换 `0`、`00`。
2. 交换 `1`、`01`。
3. 交换 `1`、`10`。
对于其他所有的交换，都可以通过这 $3$ 种操作实现。
操作可逆，因此考虑一种方式，让 $a,b$ 均单调不降。
***
假设存在至少两个 `1`，和若干个 `0`，那么就可以使其**单调不降**。
因为操作 1 可以任意调整两个 `1` 左边、右边的 `0`；对于 `1` 中间的 `0`，可以通过操作 1 变成 `101`，此时通过操作 2 变为 `011` 即可。
不管最右边的 `1`，又可以将前面所有的 `1` 换到最后。
***
仅仅只有一个 `1` 是简单地，只要不在开头/结尾，就可以通过操作 1 **任意调动**。也正因此，当且仅当存在 `1` 在开头/结尾且不是同时在 $a,b$ 的开头/结尾时**无解**。
参考代码
```cpp //#include<bits/stdc++.h> #include-
using namespace std;
constexpr const int N=2e5;
int n,a[N+1],b[N+1];
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--){
cin>>n;
int cntA=0,cntB=0;
for(int i=1;i<=n;i++){
cin>>a[i];
cntA+=a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
cntB+=b[i];
}
if(cntA!=cntB||cntA==1&&(a[1]!=b[1]||a[n]!=b[n])){
cout<<"No\n";
}else{
cout<<"Yes\n";
}
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```
</details>
# [[GDCPC 2024] 图](https://www.luogu.com.cn/problem/P13356)
从原图中找出 $k=\left\lceil\dfrac m{n-1}\right\rceil$ 条两点之间的边不相交路径。
考虑将原图划分为 $k$ 张图 $T_1,T_2,\cdots,T_k$，每一张图维护一条路径。$k$ 的值可以启发我们维护一棵类似于树的图，实际上 $T_i$ 中有环是不优的，可以放到其他图上产生新的路径。
最终答案即找 $u\sim v$ 的路径，使得 $T_1,T_2,\cdots,T_k$ 中均连通。维护前缀连通，在 $T_k$ 中随便找两个连通的点，在 $T_1\sim T_{k-1}$ 中暴力 DFS 找即可。
但其实 $T_i$ 应当是一棵森林。
[详细题解参见此处](./-/P13356)。
参考代码
```cpp //#include<bits/stdc++.h> #include-
using namespace std;
constexpr const int N=2e5,M=2e5,K=M;
int n,m;
//vector
参考代码
```cpp //#include<bits/stdc++.h> #include-
using namespace std;
typedef long long ll;
constexpr const int N=2000,W=1e9;
constexpr const ll inf=0x3f3f3f3f3f3f3f3f;
int n,w[N+1][N+1];
ll dis[N+1];
void Dijkstra(int s){
static bool vis[N+1];
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
vis[s]=true;
for(int i=1;i<=n;i++){
dis[i]=w[s][i];
for(int j=1;j<=n;j++){
if(i==j){
continue;
}
dis[i]=min(dis[i],2ll*w[i][j]);
}
}
for(int i=1;i<n;i++){
ll Min=inf;
int x=-1;
for(int j=1;j<=n;j++){
if(vis[j]){
continue;
}
if(dis[j]<Min){
Min=dis[j];
x=j;
}
}
vis[x]=true;
for(int j=1;j<=n;j++){
if(vis[j]){
continue;
}
dis[j]=min(dis[j],dis[x]+w[x][j]);
}
}
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<n;i++){
for(int j=1;j<=n-i;j++){
cin>>w[i][i+j];
w[i+j][i]=w[i][i+j];
}
}
ll Min=inf,s=-1;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(w[i][j]<Min){
Min=w[i][j];
s=i;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j){
continue;
}
w[i][j]-=Min;
}
}
Dijkstra(s);
for(int i=1;i<=n;i++){
cout<<dis[i]+(n-1ll)*Min<<'\n';
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```
</details>
