「一题」
codesonic
2020-08-23 14:07:51
每天~~6:00~13:00左右更新一道大约NOIP pj C~D，tg Day1 B题。~~
~~第二天的同一时间更新一句话题解和代码 大概到初赛时停止更新~~。
## 8.23 [P1338 末日的传说](https://www.luogu.com.cn/problem/solution/P1338)
8.24 6:23 更新了题解。
很容易发现每个数对逆序对个数的贡献仅仅与他前面的数和后面的数有关，而与这些数之间的相对位置无关。那么我们每次可以只确定一个数的位置。
考虑令$f(n,m)$表示n个数，逆序对个数为$m$的方案。由于字典序要最小，我们试图先确定最小的数的位置，为了使得最终答案字典序最小（日子是一天天过的，第一个到$m$的字典序最小），第$1$个数要尽量放在前面，所以若除了第一个数，剩下的数能产生$m$个逆序对，那么第一个数就可以放在第一位。
另外可以发现，长度为$n$的排列最多形成$\sum_{i=1}^{n}i=\frac{n(n+1)}{2}$个逆序对。
也就是说，$n-1$个数能产生$\frac{n(n-1)}{2}$个逆序对，所以若$\frac{n(n-1)}{2}>m$，那么数字1放在第一位。
若$\frac{n(n-1)}{2}\leq m$，则数字1必须对答案产生贡献，考虑到数字1是原序列最小的数，那么数字1每前进一位，就会产生一对逆序对。故数字1的位置为$m-\frac{n(n-1)}{2}+1$。
接下来我们可以把$1$无视，将剩余数字从$2$到$n$依次考虑。
大概口胡了一下，因为是很久以前写的题....某些式子可能相差$1$或$2$。建议对照其他题解。
一万年前写的代码：
```cpp
#include<cstdio>
using namespace std;
#define int long long
int n,m,a[100010];
int head,tail;
signed main()
{
scanf("%d%d",&n,&m);
for(register int i=1,head=1,tail=n;i<=n;i++){
int tmp=((n-i)*(n-i-1))>>1;
if(m<=tmp)
a[head++]=i;
else a[tail--]=i,m-=tail-head+1;
}
for(register int i=1;i<=n;i++)
printf("%d ",a[i]);
return 0;
}
```
中午更新下一题。
## 8.24 [UVA10271 佳佳的筷子 Chopsticks](https://www.luogu.com.cn/problem/UVA10271)
8.25 6:17 更新了题解。
发现三元组的贡献仅与较小的两个数无关，考虑先选出这两个数，再找一个比他们都大的数字作为一个三元组。
另外，为了使得状态无后效性，我们应当从大到小选而不是从小到大选。
因为输入已经单调递增，那么我们可以将输入倒过来处理。
令$f_{i,j}$表示最大的前$i$个数，选出$j$个三元组的最小权值之和。
考虑选与不选第$i$个数，若不选，则$f_{i,j}=f_{i-1,j}$，若不选，则有$f_{i,j}=f_{i-2,j-1}+(a_i-a_{i-1})^2$。
注意，以上式子都是在$3\times j\leq i$下讨论的。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5010;
int Task,n,k,a[maxn],f[maxn][maxn];
inline int Min(int a,int b){
return a<b?a:b;
}
int main(){
scanf("%d",&Task);
while(Task--){
scanf("%d%d",&k,&n);
k+=8;
for(int i=n;i;i--)
scanf("%d",&a[i]);
memset(f,0x3f3f3f3f,sizeof f);
for(int i=0;i<=n;i++) f[i][0]=0;
for(int i=3;i<=n;i++){
for(int j=1;j<=k;j++)
if(i>=j*3) f[i][j]=Min(f[i-1][j],f[i-2][j-1]+(a[i-1]-a[i])*(a[i-1]-a[i]));
}
printf("%d\n",f[n][k]);
}
return 0;
}
```
我个人认为难度应当为`普及/提高-`。
中午更新下一题。
## 8.25 [P3609 [USACO17JAN]Hoof, Paper, Scissor G](https://www.luogu.com.cn/problem/P3609)
可以先做P6120。
8.26 6:21 吹水：这几天都抢着宿舍开门第一个粗来 困死了
首先考虑P6120，因为只能变换一次，所以实际上要求找出变换的的那个点$k$，使得$[1,k-1]$的众数出现次数加上$[k,n]$的众数出现次数最大。
那么$\Theta(n)$扫一遍求出$[1,i]$的众数出现次数$a_i$，再倒着扫一遍$[i,n]$的众数出现次数$b_i$，然后再找$max(a_i+b_i)$即可。
我认为P6120会误导你，让你更难想出P3609= =。因为P3609实际上是找$k+1$个区间的众数之和。
这里我们采用DP，设$f_{i,j,0/1/2}$表示已经到第$i$轮，之前变换次数为$j$，当前手势是0/1/2的最多胜利次数。状态转移很显然。时间复杂度$\Theta(nk)$
当然也可以记忆化搜索写，DP不太熟练确实写成记忆化搜索比较舒服（就是代码长）。
有一个显然的trick，我们不要看成剪刀石头布~~黑吃黑~~互相吃的形式，可以看成自己吃自己，即当John选石头，你选石头赢。
（本来没想加这句话，翻题解区的时候看到一堆人写成了互相吃的形式导致代码量剧增）
还没写代码。
我正在撕烤$k$更大怎么做，如果有人想到做法可以和我说一下（）
中午写代码然后更新下一题。
```cpp
//P3609
#include<bits/stdc++.h>
using namespace std;
int n,k;
int f[200010][30][4];
int a[200010];
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
char opt[3];
scanf("%s",opt);
if(opt[0]=='P') a[i]=1;
if(opt[0]=='H') a[i]=2;
if(opt[0]=='S') a[i]=3;
}
for(int i=1;i<=n;i++){
f[i][0][1]=f[i-1][0][1]+(a[i]==1);
f[i][0][2]=f[i-1][0][2]+(a[i]==2);
f[i][0][3]=f[i-1][0][3]+(a[i]==3);
for(int j=1;j<=k;j++){
f[i][j][1]=max(f[i][j][1],f[i-1][j][1]);
f[i][j][2]=max(f[i][j][2],f[i-1][j][2]);
f[i][j][3]=max(f[i][j][3],f[i-1][j][3]);
f[i][j][1]=max(f[i][j][1],max(f[i-1][j-1][2],f[i-1][j-1][3]))+(a[i]==1);
f[i][j][2]=max(f[i][j][2],max(f[i-1][j-1][1],f[i-1][j-1][3]))+(a[i]==2);
f[i][j][3]=max(f[i][j][3],max(f[i-1][j-1][1],f[i-1][j-1][2]))+(a[i]==3);
}
}/*
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++)cout<<f[i][j][1]<<' '<<f[i][j][2]<<' '<<f[i][j][3]<<" | ";
puts("");
}*/
int ans=0;
for(int i=0;i<=k;i++)
ans=max(ans,max(f[n][i][1],max(f[n][i][2],f[n][i][3])));
printf("%d",ans);
}
```
## 8.26 [P5159 WD与矩阵](https://www.luogu.com.cn/problem/P5159)
8.27 6:16更新了题解 考虑到，无论我们前$m-1$列怎么放，最后一列总是存在一种方法使得每一行的异或和为0。
那么前$m-1$列每列的异或和为$0$就行了。问题改变为“$m-1$列，让每一列异或和都为$0$的方案数”。每一列异或和为$0$的方案数之间互不干扰，只需要把每一列异或和为$0$的方案数取$m-1$次方。
考虑一列数异或和为$0$的方案数，很容易发现前$n-1$个数无论怎么放，第$n$个数都能使得该列异或和为$0$。所以问题改变为随便放$n-1$个数，答案显然为$2^{n-1}$，再取上$m-1$次方，答案为$2^{(n-1)(m-1)}$。
快速幂做一下就行了。
```cpp
#include<bits/stdc++.h>
using namespace std;
const long long Mod=998244353;
long long n,m;
inline long long fpw(long long x,long long y){
long long ans=1;
while(y){
if(y&1) (ans*=x)%=Mod;
(x*=x)%=Mod;
y>>=1;
}
return ans%Mod;
}
int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%lld%lld",&n,&m);
printf("%lld\n",fpw(fpw(2,n-1),m-1));
}
return 0;
}
```
## 8.27 [P2650 弹幕考察](https://www.luogu.com.cn/problem/P2650)
经典的离线树状数组题。如果强制在线，则需要用主席树完成。
>一道更加经典的题目是[SPOJ DQUERY D-query](https://www.luogu.com.cn/problem/SP3267)（[HH的项链](https://www.luogu.com.cn/problem/P1972)），这道题除了树状数组和主席树，还可以用莫队完成。这里限于篇幅仅仅稍微提一下做法，本题非常经典，到处都有题解：）。
>首先考虑SPOJ这个题。一个数字$a_i$对答案的贡献区间为$[lst_i,i]$，$lst_i$表示$a_i$上次出现的位置。
>将询问按照右端点排序，然后每次从上一次询问的右端点扫描到当前询问的右端点。对于这中间的每一个数，对答案有贡献的区间仍然为$[lst_i,i]$，即如果询问的区间包含$[lst_i,i]$，那么答案中只计入一次。例如询问的区间为$\{1,1,5,4,1,4\}$，前几个数其实没有用，询问的区间实质等同于$\{\times,\times,5,\times,1,4\}$。
>维护一个树状数组，$tr_i$表示前$i$个数有多少个不相同的数。每次根据当前询问的$r$，加入位置$\leq r$的所有贝壳（将树状数组中的对应位置标为$1$），并删去前面相同的数字（将树状数组中的对应位置标为$0$）。对于每个询问的答案则为$tr_r-tr_{l-1}$。
将询问离线并且按照左端点排序，对弹幕则按右端点排序。依次考虑各个询问，对于可能会有影响的所有弹幕加入。（如果一个弹幕的右端点大于当前询问的左端点），则该弹幕有可能影响。设该弹幕的区间为$[l,r]$，加入时，对$tr_l$加一，假设询问区间$[ql,qr]$，答案则为$\sum_{i=1}^{qr}tr_i$，很容易用树状数组维护。至于该做法的合理性，可以自行画图理解。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000010;
int n,m,ans[maxn],tot=0;
struct node{
int l,r;
}x[maxn];
inline bool cmp1(node a,node b){
return a.r>b.r;
}
struct query{
int l,r,id;
}q[maxn];
inline bool cmp2(query a,query b){
return a.l>b.l;
}
int a[maxn<<2],tr[maxn];
inline int lowbit(int x){
return x&(-x);
}
inline void add(int x){
while(x<=maxn-1) tr[x]++,x+=lowbit(x);
}
inline int que(int x){
int ans=0;
while(x)ans+=tr[x],x-=lowbit(x);
return ans;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d%d",&x[i].l,&x[i].r);
x[i].l++;x[i].r+=x[i].l;
a[++tot]=x[i].l;a[++tot]=x[i].r;
}
sort(x+1,x+1+n,cmp1);
for(int i=1;i<=m;i++){
scanf("%d%d",&q[i].l,&q[i].r);q[i].id=i;
q[i].l++;q[i].r+=q[i].l;
a[++tot]=q[i].l;a[++tot]=q[i].r;
}
sort(q+1,q+m+1,cmp2);
sort(a+1,a+1+tot);tot=unique(a+1,a+tot+1)-a-1;
for(int i=1;i<=n;i++){
x[i].l=lower_bound(a+1,a+tot+1,x[i].l)-a;
x[i].r=lower_bound(a+1,a+tot+1,x[i].r)-a;
}
for(int i=1;i<=m;i++){
q[i].l=lower_bound(a+1,a+tot+1,q[i].l)-a;
q[i].r=lower_bound(a+1,a+tot+1,q[i].r)-a;
}
int j=1;
for(int i=1;i<=m;i++){
while(x[j].r>q[i].l) add(x[j++].l);
ans[q[i].id]=que(q[i].r-1);
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}
```
## 8.28 [ [LnOI2019SP]快速多项式变换(FPT)](https://www.luogu.com.cn/problem/P5248)
发现你要构造的$\{a_i\}$相当于$m$进制下的每一位，那么输出$f(m)$在$m$进制下每一位的值即可。
```cpp
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
inline ll read(){
ll res=0,fh=1;char ch=getchar();
while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
if(ch=='-')fh=-1,ch=getchar();
while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
return fh*res;
}
ll ans[10010];
int main()
{
ll cnt=0;
ll m=read(),fm=read();
while(fm)
ans[++cnt]=fm%m,fm/=m;
printf("%lld\n",cnt);
for(int i=1;i<=cnt;i++)
printf("%lld ",ans[i]);
return 0;
}
```
## 8.29 [AT4827 [ABC165D] Floor Function](https://www.luogu.com.cn/problem/AT4827)
洛谷remotejudge挂了 可以去原网站提交：https://atcoder.jp/contests/abc165/tasks/abc165_d
$$\left\lfloor \frac{ax}{b} \right\rfloor -a\left\lfloor \frac{x}{b} \right\rfloor$$
$$=\left\lfloor a(\frac{x}{b}-\left\lfloor \frac{x}{b} \right\rfloor) \right\rfloor +a\left\lfloor \frac{x}{b} \right\rfloor -a\left\lfloor \frac{x}{b} \right\rfloor$$
所以最大化$\left\lfloor \frac{x}{b}- \left\lfloor\frac{x}{b}\right\rfloor \right\rfloor$即可，即最大化$x$
那么$x$若能取到$b-1$，则取$b-1$，否则取$n$。
这还要代码？
## 8.30 [P2187 小Z的笔记](https://www.luogu.com.cn/problem/P2187)
8.31 6:13
经典$\text{dp}$题，感觉写过好多次类似的了= =
设$f_i$表示前$i$个字母合法需要删掉多少个字母，得出一个$n^2$的做法。
$f_i=min(f_j+i-j-1)$，$i,j$可以相邻且$j\le i$。表示删掉j到i之间所有字符。
但是$n^2$做法不足以通过本题，因为$i$的值与选取无关，原式可以变为$f_i=min(f_j-j)+i-1$。那么我们对于每种字母维护$f_j-j$的最小值，每次只需要枚举字母即可。
时间复杂度$\Theta(26n)$。（以上这个提出$min(f_j-j)$的步骤有斜率优化那味了）。
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxn=1000010;
int f[maxn];
bool gg[30][30];
int p[maxn];
char s[maxn];
inline int Min(int a,int b){
return a<b?a:b;
}
int main(){
scanf("%d",&n);
scanf("%s",s+1);
scanf("%d",&m);
memset(gg,0,sizeof gg);
for(int i=1;i<=m;i++){
char c[3];scanf("%s",c);
gg[c[0]-'a'][c[1]-'a']=gg[c[1]-'a'][c[0]-'a']=1;
}
memset(f,127,sizeof f);
f[0]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<26;j++)
if(!gg[s[i]-'a'][j])
f[i]=Min(f[i],p[j]+i-1);
p[s[i]-'a']=Min(p[s[i]-'a'],f[i]-i);
}
printf("%d",f[n]);
return 0;
}
```
9月开始可能会加大码量(
## 8.31 [CF1304C Air Conditioner](https://www.luogu.com.cn/problem/CF1304C)
考虑到，每个时间点合法的温度是一个区间（时间点$0$是$[m,m]$），在这之后$t$秒，则变为$[m-t,m+t]$，并且与顾客的要求取交集。如果某个交集为空，则不合法。
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,Tas;
const int maxn=114;
struct node{
int t,l,r;
}s[maxn];
inline bool cmp(node a,node b){
return a.t<b.t;
}
inline int Max(int a,int b){
return a>b?a:b;
}
inline int Min(int a,int b){
return a<b?a:b;
}
int main(){
scanf("%d",&Tas);
while(Tas--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&s[i].t,&s[i].l,&s[i].r);
sort(s+1,s+1+n,cmp);
int L=m,R=m,T=0;
for(int i=1;i<=n;i++){
//printf("now:%d t:%d l:%d r:%d\n",i,s[i].t,s[i].l,s[i].r);
int t=s[i].t-T;
if(L-t>s[i].r||R+t<s[i].l){
puts("NO");
goto a;
}
L=Max(L-t,s[i].l);
R=Min(R+t,s[i].r);
T=s[i].t;
}
puts("YES");
a:;
}
}
```
## 9.1 [P3606 [USACO17JAN]Building a Tall Barn P](https://www.luogu.com.cn/problem/P3606)
难题。大概能做TG D2 B了，因为当时放题的时候误估了题目难度，dbq。
可以不做。因为我也不会（
转化为形式化的表述。
已知$\sum_{i=1}^{n}c_i$ 和 $a_i$，求$\sum_{i=1}^{n}\frac{a_i}{c_i}$的最小值。
给定一个数组 $a$ 和另一个数组 $c$ 的和，求$\sum_{i=1}^{n}\frac{a_i}{c_i}$的最小值。
考虑对于每一层表示出如果增加一个人将减少的时间 $t_i=\frac{a_i}{c_i}-\frac{a_i}{c_i+1}$ （也可以改为$t_i=\frac{a_i}{c_i-1}-\frac{a_i}{c_i}$）。可以看出，最后的$t_i$之间肯定相差不大，因为如果相差较大，就可以挪动一个人使得
去分母，变成$t_ic_i(c_i+1)=a_i(c_i+1)-a_ic_i$。
试图表示$c_i$，$c_i=\frac{-1+\sqrt{1+\frac{4a_i}{t_i}}}{2}$
放大点。
$$\large{c_i=\frac{-1+\sqrt{1+\frac{4a_i}{t_i}}}{2}}$$
由于最后的$t_i$基本相同，二分$t_i$并求值即可。
注意精度。
```cpp
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-9;
#define int long long
int n,k;
const int maxn=114514;
double a[maxn];
typedef long long ll;
inline bool check(double t){
long long sum=0;
for(int i=1;i<=n;i++){
double c=(sqrt(1+4*a[i]/t)-1)/2;
ll v=ceil(c);
sum+=v;
if(sum>k) return 0;
}
return 1;
}
signed main(){
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++)
scanf("%lf",&a[i]);
double l=1e-9,r=20;
while(r-l>=eps){
double mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid;
}
double sum=0,ans=0;
for(int i=1;i<=n;i++){
double c=(sqrt(1+4*a[i]/r)-1)/2;
int v=ceil(c);
sum+=v;
ans+=a[i]/v;
}
printf("%.0lf",ans-(k-sum)*r);
return 0;
}
```
似乎有贪心做法？
## 9.2 [P2585 [ZJOI2006]三色二叉树](https://www.luogu.com.cn/problem/P2585)
简单DP，因为每个节点的状态转移只和其子节点有关，具有无后效性，设$f_{i,j,0/1}$表示第$i$个节点颜色为$j$的贡献最大/最小值，直接做即可。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000010;
int n,son[maxn][2],tot=0,f[maxn][3][2];
string a;
int build(){
int now=++tot;
if(a[now-1]=='2'){
son[now][0]=build();
son[now][1]=build();
}
else if(a[now-1]=='1') son[now][0]=build();
return now;
}
void dfs(int x){
if(!x) return ;
int ls=son[x][0],rs=son[x][1];
dfs(ls);dfs(rs);
if(!ls&&!rs){
f[x][0][0]=f[x][0][1]=1,f[x][1][0]=f[x][2][0]=f[x][1][1]=f[x][2][1]=0;
return ;
}
f[x][0][0]=max(f[ls][1][0]+f[rs][2][0],f[ls][2][0]+f[rs][1][0])+1;
f[x][1][0]=max(f[ls][0][0]+f[rs][2][0],f[ls][2][0]+f[rs][0][0]);
f[x][2][0]=max(f[ls][1][0]+f[rs][0][0],f[ls][0][0]+f[rs][1][0]);
f[x][0][1]=min(f[ls][1][1]+f[rs][2][1],f[ls][2][1]+f[rs][1][1])+1;
f[x][1][1]=min(f[ls][0][1]+f[rs][2][1],f[ls][2][1]+f[rs][0][1]);
f[x][2][1]=min(f[ls][1][1]+f[rs][0][1],f[ls][0][1]+f[rs][1][1]);
}
int main(){
cin>>a;
dfs(build());
printf("%d %d\n",max(f[1][0][0],max(f[1][1][0],f[1][2][0])),
min(f[1][0][1],min(f[1][1][1],f[1][2][1])));
}
```
## 9.3 [CF1343E Weights Distributing](https://www.luogu.com.cn/problem/CF1343E)
考虑到，最后我们走的路径会是最小的前几个数，而且该路径越短越好。
所以其实可以每条边的边权为1来跑最短路（BFS），求出A到B再到C的最短距离。
很遗憾的是，因为A到B和B到C的路径可能重复，所以需要枚举一个$i$，表示开始重复的点。那么路径就变为$A\rightarrow i\rightarrow B\rightarrow i\rightarrow C$。求出$A,B,C$到每个点的距离，然后枚举$i$，路径长度就是$dis(A,i)+dis(i,B)+dis(B,i)+dis(i,C)$，这时把最小的几个给$i$到$B$便是最划算的。其余的贪心选择剩下的前$dis(A,i)+dis(i,C)$个分配
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int T;
const int maxn=1000010;
int n,m,a,b,c;
int dis[maxn],disa[maxn],disb[maxn],disc[maxn];
int w[maxn],s[maxn];
struct node{
int to,nxt;
}G[maxn];int tot=0,head[maxn];
inline void addedge(int u,int v){
G[++tot].to=v;
G[tot].nxt=head[u];
head[u]=tot;
}
inline void bfs(int cur){
queue<int> q;
for(int i=1;i<=n;i++) dis[i]=(1ll<<50);
dis[cur]=0;q.push(cur);
while(!q.empty()){
int u=q.front();q.pop();
//cerr<<"now:"<<u<<endl;
for(int i=head[u];i;i=G[i].nxt){
int to=G[i].to;
if(dis[to]==(1ll<<50)) {
dis[to]=dis[u]+1;
q.push(to);
}
}
}
//for(int i=1;i<=n;i++) cerr<<dis[i]<<' ';puts("");
}
signed main(){
scanf("%lld",&T);
while(T--){
scanf("%lld%lld%lld%lld%lld",&n,&m,&a,&b,&c);
for(int i=1;i<=n;i++) head[i]=0;tot=0;
for(int i=1;i<=m;i++) scanf("%lld",&w[i]);
sort(w,w+m+1);
for(int i=1;i<=m;i++) s[i]=s[i-1]+w[i];
for(int i=1;i<=m;i++){
int u,v;scanf("%lld%lld",&u,&v);
addedge(u,v);addedge(v,u);
}
bfs(a);for(int i=1;i<=n;i++) disa[i]=dis[i];
bfs(b);for(int i=1;i<=n;i++) disb[i]=dis[i];
bfs(c);for(int i=1;i<=n;i++) disc[i]=dis[i];
int ans=(1ll<<50);
for(int i=1;i<=n;i++){
int a=disa[i],b=disb[i],c=disc[i];
if(a+b+c<=m) ans=min(ans,s[a+b+c]+s[b]);
}
printf("%lld\n",ans);
}
}
```
## 9.4 [P1131 [ZJOI2007]时态同步](https://www.luogu.com.cn/problem/P1131)
感觉是个模拟题..?
因为只有一个子树的叶节点同步，他上面才能同步
于是只需要对子树单独考虑。对于每个子树先平衡（这一点无论上面怎么调都没用），再将根节点平衡即可。
这题简单了。
```cpp
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#include<set>
using namespace std;
inline int read() {
int res=0,fh=1;
char ch=getchar();
while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
if(ch=='-')fh=-1,ch=getchar();
while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
return fh*res;
}
typedef long long ll;
const int maxn=500010;
int n,m,rt,val[maxn];
ll ans;
struct node{
int to,w,nxt;
}t[maxn<<1]; int head[maxn],tot=0;
inline void addedge(int u,int v,int w){
t[++tot].to=v;
t[tot].w=w;
t[tot].nxt=head[u];
head[u]=tot;
}
void dfs(int u,int fa){
int cnt=0;
for(int i=head[u];i;i=t[i].nxt){
int to=t[i].to;
if(to!=fa){
dfs(to,u);
if(val[to]+t[i].w>val[u]){
ans+=(val[to]+t[i].w-val[u])*(cnt++);
val[u]=val[to]+t[i].w;
}
else ans+=val[u]-val[to]-t[i].w,++cnt;
}
}
}
int main(){
n=read(),rt=read();
for(int i=1;i<n;i++){
int u=read(),v=read(),w=read();
addedge(u,v,w);
addedge(v,u,w);
}
dfs(rt,0);
printf("%lld",ans);
return 0;
}
```
## 9.5 [P5514 [MtOI2019]永夜的报应](https://www.luogu.com.cn/problem/P5514)
考虑到，两个数之和大于等于其异或和，故全部异或起来就是答案。
这还要代码？
## 9.6 [P2127 序列排序](https://www.luogu.com.cn/problem/P2127)
先二分确定每个元素的最终位置。把一个元素和它的最终位置之间连边，这两个位置之间**必须直接或间接做交换**，那么我们得到了一个有$n$个点$n$条边的图，且每个点的度数要么为$0$，要么为$2$（如果当前元素的最终位置就是这个位置就是0，否则是2）。
考虑到，这样会在图中形成若干个环。环与环之间互相分离，如果不考虑元素的权值，每次交换的代价都是$1$的话，显然环与环之间元素的交换是多余的。
那么在一个环内，最小交换的代价是多少呢？
很容易想到，在一个环内以最小元素为起点，让该元素把整个环走一遍是最优的。这样的代价是$\sum w_i+(siz-2)\times w_i$。$siz$表示环的大小。
↑这一点如果不能理解应该多撕烤几遍。
当然由于序列不止这个环中的元素，你也可以讲环中最小的元素和序列中最小的元素做交换，再重复以上过程，最后再把刚刚环内的最小元素换回来。这样的代价是$\sum w_i + min(w_i)+min(a_i)*(siz+1)$，$w_i$表示环内元素，$a_i$表示整个序列元素，$siz$表示环大小。
对于每个环从这两个方案中选取最优方案即可。
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=(1<<30);
const int maxn=114514;
ll a[maxn],b[maxn];
ll Allmin=INF;
ll sum,siz,mnx;
bool vis[maxn];
int nxt[maxn];
ll ans=0;
void dfs(int x){
if(vis[x]) return ;
vis[x]=1;
sum+=a[x],siz++,mnx=min(mnx,a[x]);
dfs(nxt[x]);
}
int n;
int main(){
scanf("%d",&n);
Allmin=INF;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
b[i]=a[i];Allmin=min(Allmin,a[i]);
}
sort(b+1,b+1+n);
for(int i=1;i<=n;i++) nxt[i]=lower_bound(b+1,b+n+1,a[i])-b;
for(int i=1;i<=n;i++){
if(!vis[i]){
sum=0,siz=0,mnx=INF;
dfs(i);
ans+=min(sum+Allmin*(siz+1)+mnx,sum+mnx*(siz-2));
}
}
return printf("%lld\n",ans),0;
}
```
## 9.7 [P2707 Facer帮父亲](https://www.luogu.com.cn/problem/P2707)
维护一个元素数为$n$的大根堆表示将$n$个票价+1元后的收益增量。
原始票价定0，然后循环k次每次取出堆顶，将那个票价+1并且计算收益，然后将下次的增量塞回去即可。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k;
struct node{
int val,b;
bool operator <(const node& rhs) const{
return val<rhs.val;
}
};
priority_queue<node> q;
int ans=0;
signed main(){
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++){
int a,b;
scanf("%lld%lld",&a,&b);
if(a-b>0)q.push((node){a-b,b});
}
while(k--&&!q.empty()){
node tmp=q.top();q.pop();
ans+=tmp.val;
tmp.val-=2*tmp.b;
if(tmp.val>0) q.push(tmp);
}
return printf("%lld",ans),0;
}
```
## 9.8 [P5340 [TJOI2019]大中锋的游乐场](https://www.luogu.com.cn/problem/P5340)
分层图最短路的~~板子~~题，设$f_{i,j}$表示在第$i$个点，汉堡比可乐多$j$次的最短路。为了防止出现$\text{ub}$，将$j$随便加个数再存进去。
```cpp
#include<bits/stdc++.h>
#define fst first
#define scd second
using namespace std;
const int maxn=10010;
struct node{
int nxt,to,w;
}tr[maxn<<5];int tot=0,head[maxn];
int n,m,k;
int d[maxn][41],vis[maxn][41],p[maxn];
inline void addedge(int u,int v,int w){
tr[++tot].nxt=head[u];
tr[tot].to=v;
tr[tot].w=w;
head[u]=tot;
}
queue<pair<int,int> > q;
int T;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&k);
memset(d,127,sizeof d);
memset(head,0,sizeof head);
memset(vis,0,sizeof vis);
tot=0;
for(int i=1;i<=n;i++){
scanf("%d",&p[i]);
if(p[i]==1) p[i]=-1;
else p[i]=1;
}
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);addedge(v,u,w);
}
int x,y;
scanf("%d%d",&x,&y);
d[x][p[x]+20]=0,vis[x][p[x]+20]=1;
q.push(make_pair(x,p[x]+20));
while(!q.empty()){
pair<int,int> u=q.front();q.pop();
vis[u.fst][u.scd]=0;
for(int i=head[u.fst];i;i=tr[i].nxt){
int to=tr[i].to;
if((abs(u.scd+p[to]-20)<=k)&&(d[to][u.scd+p[to]]>d[u.fst][u.scd]+tr[i].w)){
d[to][u.scd+p[to]]=d[u.fst][u.scd]+tr[i].w;
if(!vis[to][u.scd+p[to]]){
q.push(make_pair(to,u.scd+p[to]));
vis[to][u.scd+p[to]]=1;
}
}
}
}
int ans=(1<<30);
for(int i=20-k;i<=k+20;i++)
ans=min(ans,d[y][i]);
printf("%d\n",ans==(1<<30)?-1:ans);
}
}
```
## 9.9 [CF442C Artem and Array](https://www.luogu.com.cn/problem/CF442C)
考虑到，如果一个数的左右都比这个数大，那么删除它肯定是正确选择。
所以先把这些数删除，然后成为一个单调序列。这个时候按顺序删除最小的几个数即可。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
const int maxn=500010;
int stk[maxn],top=0;
signed main(){
scanf("%lld",&n);
int ans=0;
for(int i=1;i<=n;i++){
int x;scanf("%lld",&x);
while(top>=2){
int a=stk[top],b=stk[top-1];
if(b>=a&&a<=x) ans+=min(x,b),top--;
else break;
}
stk[++top]=x;
}
sort(stk,stk+1+top);
for(int i=1;i<=top-2;i++)
ans+=stk[i];
return printf("%lld\n",ans),0;
}
```
## 9.10 今天放假补题
教师节快乐！
## 9.11 [P2679 子串](https://www.luogu.com.cn/problem/P2679)
很容易看出是DP。
设 $f_{i,j,k}$ 为从 $A$ 的前 $i$ 个字符中，取了 $k$ 个子串，与 $B$ 的前 $j$ 个字符相同的方案数。
很容易得出状态转移方程。可以对该方程进行优化滚掉一维。
## 9.12 补作业没写 咕咕咕
## 9.13 [CF1184E3 Daleks' Invasion](https://www.luogu.com.cn/problem/CF1184E3)
## 9.14 [P4965 薇尔莉特的打字机](https://www.luogu.com.cn/problem/P4965)
较难题。
假装有一棵字典树，包含的是所有字符串。
即根节点有 $\texttt{A}$ 到 $\texttt{Z}$ ，每个节点都有 $\texttt{A}$ 到 $\texttt{Z}$ 的儿子。
先不考虑删除，把我们当前能到达的节点打上标记，考虑添加一个字符$c$，意味着我们所有有标记的节点的儿子$c$都打上标记。
这个过程，如果每个有标记的节点的 $c$ 儿子都没有标记，显然意味着答案翻了个倍。
但是不可能。为了消除这个影响，我们计一个标记$s_i$，$s_i$表示当前有多少个标记了的节点的儿子$i$已经被标记。那么每次输入一个字符$c$，当前被标记的节点个数$ans$就是翻倍再减去$s_c$。
考虑如何维护$s_c$，输入字符$c$时，所有的标记节点的儿子$c$都获得了标记，所以$s_c$更新为上一次操作后的被标记节点数量。
被标记的节点总数就是当前答案。
那么现在考虑删除操作，是让所有被标记节点的父亲获得标记，在没有原始字符串的情况下，这是白费功夫。
因为我们输入过原始字符串，我们把原始字符串搞成一条链接到刚刚那个trie上。画个图（原始字符串是violet）。
那么第一次删除操作，会让答案+1，因为节点 $\texttt{T}$ 被标记了。
所以每删除一次都让答案+1，这是顺便更新 $s$ 数组（多了一个标记的节点），最多更新$n$次，如果退格超过 $n$ 次就是真正的白费功夫。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=19260817;
const int maxn=10000010;
char a[maxn],b[maxn];
int s[maxn];
int n,m,ans=1;
signed main(){
scanf("%lld%lld%s%s",&n,&m,a+1,b+1);
for(int i=1;i<=m;i++){
if(b[i]>='A'&&b[i]<='Z'){
int tmp=s[b[i]-'A'+1];
s[b[i]-'A'+1]=ans;
ans=((ans+ans-tmp)%mod+mod)%mod;
}
else{
if(!n) continue;
s[a[n]-'A'+1]=(s[a[n]-'A'+1]+1)%mod;
ans=(ans+1)%mod;
n--;
}
}
return printf("%lld\n",ans),0;
}
```
## 9.15
## 9.16 [P4317 花神的数论题](https://www.luogu.com.cn/problem/P4317)
## 9.17 [P3651 展翅翱翔之时 (はばたきのとき)](https://www.luogu.com.cn/problem/P3651)
## 9.18 昨天的模拟赛题
给一棵树，再给若干边，问你删去一条树边x和一条新边y 的边对(x,y) 能使图不连通的方案数。$n\leq 2e5$
提交可以私信我
题解见[另一篇博客](https://www.luogu.com.cn/blog/codesonic/post-917-mu-ni-sai)，不想重写或者copy
## 9.19 [P3694 邦邦的大合唱站队](https://www.luogu.com.cn/problem/P3694)
## 9.23 [P1248 加工生产调度](https://www.luogu.com.cn/problem/P1248)
请试图给出结论的数学证明
## 9.24 [P5889 跳树](https://www.luogu.com.cn/problem/P5889)
## 10.7 [P4219 [BJOI2014]大融合](https://www.luogu.com.cn/problem/P4219)
草 咕了好多天
今天开始更新难题
难度改为大约D2T2和D1T3。
这道题可以LCT，但是我至今不会LCT
有一个做法很tg。是个人都能看出来每次询问的相当于断掉一条边后，边两端的连通块大小的乘积。
考虑怎么维护这个连通块大小，第一个想到并查集。但是并查集询问只能询问两个互不连通的连通块。如果我先连了$(x,y)$，再对$x$或$y$所在的连通块搞点小动作，再回头询问$(x,y)$，并查集是不资瓷的。
但是我们用并查集可以维护$(x,y)$这条边所在的连通块的大小。这个时候，我们只需要知道$x$，$y$中任意一个点的把边断掉后形成的连通块大小，用整个大的连通块大小一减，也能知道两个连通块的大小从而来算乘积。
考虑怎么维护断掉后的连通块大小。
这时注意到题目中一句话
> 现在，你的任务就是随着边的添加，动态的回答小强对于某些边的负载的 询问。
然后并没有强制在线= =
好，那就离线。先把整棵树树建出来，建成一棵有根树，这样我们也知道询问的两个节点哪个是父亲：）
知道哪个是父亲后，维护子树大小比较方便，于是我们把题目变成了每次连一条边，询问一个儿子的子树大小。（因为已经用并查集维护了整个连通块的大小，只需要知道那个深度大的节点的子树大小）
接下来维护子树大小，考虑每次连边，假设连的边是$(x,y)$，$x$是父亲，那么相当于将$x$到其目前能到达的深度最小的节点这一条链的子树大小加上y的子树大小。
树链剖分，随便拉个数据结构维护就行了。这里用的是树状数组
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int n,q;
bool opt[maxn];
int x1[maxn],x2[maxn],tr[maxn],son[maxn],fa[maxn],top[maxn];
int dfn[maxn],dep[maxn],siz[maxn];
struct edgee{
int to,nxt;
}e[maxn<<1];int head[maxn],tot=0;
inline void addedge(int u,int v){
e[++tot].to=v;
e[tot].nxt=head[u];
head[u]=tot;
}
inline int lowbit(int x){
return x&-x;
}
inline void add(int pos,int val){
for(int i=pos;i<=n;i+=lowbit(i))
tr[i]+=val;
}
inline int getsum(int pos){
int res=0;
for(int i=pos;i;i-=lowbit(i))
res+=tr[i];
return res+1;
}
void dfs1(int u,int f){
siz[u]=1,fa[u]=f;
dep[u]=dep[f]+1;
for(int i=head[u];i;i=e[i].nxt){
int to=e[i].to;
if(to==f) continue;
dfs1(to,u);
siz[u]+=siz[to];
if(siz[son[u]]<siz[to])
son[u]=to;
}
}
int tim=0;
void dfs2(int u,int tp){
dfn[u]=++tim,top[u]=tp;
if(!son[u]) return ;
dfs2(son[u],tp);
for(int i=head[u];i;i=e[i].nxt){
int to=e[i].to;
if(to!=fa[u]&&to!=son[u]) dfs2(to,to);
}
}
inline int getf(int x){
int k=x;
while(k^fa[k]) k=fa[k];
while(x^fa[x]){
int tmp=fa[x];
fa[x]=k;
x=tmp;
}
return fa[x];
}
inline void upd(int x,int y,int val){
while(top[x]^top[y]){
add(dfn[top[x]],val);
add(dfn[x]+1,-val);
x=fa[top[x]];
}
add(dfn[x]+1,-val);
add(dfn[y],val);
}
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=q;i++){
char s[3];
scanf("%s",s);
scanf("%d%d",&x1[i],&x2[i]);
if(s[0]=='A') {
opt[i]=0;
addedge(x1[i],x2[i]);
addedge(x2[i],x1[i]);
}
else if(s[0]=='Q') opt[i]=1;
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
dfs1(i,0);
dfs2(i,i);
}
}
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=q;i++){
if(!opt[i]){
int f1=getf(x1[i]),f2=getf(x2[i]);
if(dep[f1]<dep[f2]) swap(f1,f2),swap(x1[i],x2[i]);
upd(x2[i],f2,getsum(dfn[x1[i]]));
fa[f1]=f2;
}
else {
if(dep[x2[i]]>dep[x1[i]]) swap(x1[i],x2[i]);
int s=getsum(dfn[x1[i]]);
printf("%lld\n",1ll*s*(getsum(dfn[getf(x1[i])])-s));
}
}
return 0;
}
```
## 10.12 [P5166 xtq的口令](https://www.luogu.com.cn/problem/P5166)
前几天复习初赛咕了
不过这个编辑器写了1k2行现在好卡啊
因为图连出来是DAG，所以最优解只有一种，把最优解需要涂色的序列染成1，不需要的染成0
可以考虑到一个性质就是 修改区间的时候 整个区间任何一个染色都不如染他们连的那个父亲
于是变成区间赋0和询问区间外需要涂色的个数
询问区间外涂色的个数容斥减一下就行了
没写珂朵莉树，也没写题解里有人写的树状数组
不过树状数组那个写法可以过会去学一学
下面是极其平凡的线段树
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ls (rt<<1)
#define rs (rt<<1|1)
const int maxn=1000010;
int n,q;
struct node{
int sum,tag;
}tr[maxn];
int cnt[maxn],in[maxn];
inline void pushup(int rt){
tr[rt].sum=tr[ls].sum+tr[rs].sum;
}
inline void pushdown(int rt,int l,int r){
if(!tr[rt].tag) return ;
tr[rt].sum=tr[rt].tag=0;
tr[ls].tag=tr[rs].tag=1;
}
inline void build(int rt,int l,int r){
if(l==r){
tr[rt].sum=!in[l];
return ;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(rt);
}
inline int que(int rt,int l,int r,int L,int R){
if(l==L&&r==R) return tr[rt].tag?0:tr[rt].sum;
pushdown(rt,L,R);
int mid=(L+R)>>1;
if(r<=mid) return que(ls,l,r,L,mid);
else if(l>mid) return que(rs,l,r,mid+1,R);
else return que(ls,l,mid,L,mid)+que(rs,mid+1,r,mid+1,R);
}
inline void modify(int rt,int l,int r,int L,int R){
if(L==l&&r==R){
tr[rt].tag=1;
return ;
}
pushdown(rt,L,R);
int mid=(L+R)>>1;
if(r<=mid) modify(ls,l,r,L,mid);
else if(l>mid) modify(rs,l,r,mid+1,R);
else {
modify(ls,l,mid,L,mid);
modify(rs,mid+1,r,mid+1,R);
}
tr[rt].sum=(tr[ls].tag?0:tr[ls].sum)+(tr[rs].tag?0:tr[rs].sum);
}
int main(){
scanf("%d%d",&n,&q);
for(int i=1,cnt;i<=n;i++){
scanf("%d",&cnt);
for(int j=1,y;j<=cnt;j++){
scanf("%d",&y);
in[y]=1;
}
}
build(1,1,n);
while(q--){
int opt;scanf("%d",&opt);
if(opt==1){
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",que(1,1,n,1,n)-que(1,l,r,1,n));
}
else {
int l,r,v;
scanf("%d%d%d",&l,&r,&v);
modify(1,l,r,1,n);
}
}
return 0;
}
```
## 10.13 [P3102 [USACO14FEB]Secret Code S](https://www.luogu.com.cn/problem/P3102)
这几天月考 明天开始可能断更
看我有没有心情复习的意思↑
顺便为了我方便 现在改为每天同时更新题解和题目
（这题窝看傻了不会，于是看了第一篇题解/kk）
枚举四种情况dfs即可。
记忆化搜索
```cpp
#include<bits/stdc++.h>
using namespace std;
const int mod=2014;
string s;
map<string,int> f;
inline int dfs(string s){
if(f[s]) return f[s];
int res=1;
int l=s.length();
for(int i=1;i*2<l;i++){
if(s.substr(0,i)==s.substr(l-i,i))
(res+=dfs(s.substr(i,l-i))+dfs(s.substr(0,l-i)))%=mod;
if(s.substr(0,i)==s.substr(i,i))
(res+=dfs(s.substr(i,l-i)))%=mod;
if(s.substr(l-2*i,i)==s.substr(l-i,i))
(res+=dfs(s.substr(0,l-i)))%=mod;
}
return f[s]=res%2014;
}
int main(){
cin>>s;
cout<<(dfs(s)+mod-1)%mod;
return 0;
}
```
### 10.22 [P4979 矿洞：坍塌](https://www.luogu.com.cn/problem/P4979)
以后再咕我是狗
直接线段树/ODT维护即可
练码力的
SEGT：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ls (rt<<1)
#define rs (rt<<1|1)
const int maxn=500010;
int n,m;
char s[maxn];
struct node{
int col[maxn<<2],tag[maxn<<2];
node(){memset(tag,-1,sizeof tag);}
inline void pushup(int rt){
col[rt]=col[ls]==col[rs]?col[ls]:-1;
}
inline void pushdown(int rt){
if(tag[rt]==-1) return ;
col[ls]=col[rs]=tag[ls]=tag[rs]=tag[rt];
tag[rt]=-1;
}
inline void build(int rt,int l,int r){
if(l==r){
col[rt]=s[l]-'A'+1;
return ;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(rt);
}
inline void modify(int rt,int l,int r,int ql,int qr,int val){
if(ql<=l&&qr>=r){
col[rt]=tag[rt]=val;
return ;
}
pushdown(rt);
int mid=(l+r)>>1;
if(ql<=mid) modify(ls,l,mid,ql,qr,val);
if(qr>mid) modify(rs,mid+1,r,ql,qr,val);
pushup(rt);
}
inline int query(int rt,int l,int r,int ql,int qr){
if(ql>r||qr<l) return 0;
if(ql<=l&&qr>=r) return col[rt];
pushdown(rt);
int mid=(l+r)>>1;
int lft=query(ls,l,mid,ql,qr);
int rht=query(rs,mid+1,r,ql,qr);
if(lft==0) return rht;
if(rht==0) return lft;
if(lft==-1||rht==-1) return -1;
if(lft==rht) return lft;
return -1;
}
}seg;
int main(){
scanf("%d",&n);
scanf("%s",s+1);
scanf("%d",&m);
seg.build(1,1,n);
while(m--){
char opt[3];
scanf("%s",opt);
if(opt[0]=='A'){
int l,r;char val;
scanf("%d%d %c",&l,&r,&val);
seg.modify(1,1,n,l,r,val-'A'+1);
}
else {
int l,r;
scanf("%d%d",&l,&r);
int L=seg.query(1,1,n,l-1,l-1);
int R=seg.query(1,1,n,r+1,r+1);
if(seg.query(1,1,n,l,r)!=-1 && ( L!=R || !L || !R )) puts("Yes");
else puts("No");
}
}
return 0;
}
```
ODT一会写 需要开O2
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node{
int lft,rht,val;
node(int l,int r=-1,int v=0):lft(l),rht(r),val(v){}
bool operator <(node a)const {
return lft<a.lft;
}
};
set<node> s;
#define IT set<node>::iterator
inline IT split(int pos){
IT it=s.lower_bound(node(pos));
if(it!=s.end()&&it->lft==pos) return it;
it--;
int l=it->lft,r=it->rht;
int v=it->val;
s.erase(it);
s.insert(node(l,pos-1,v));
return s.insert(node(pos,r,v)).first;
}
inline void assign(int l,int r,int v){
IT itr=split(r+1),itl=split(l);
s.erase(itl,itr);
s.insert(node(l,r,v));
}
inline bool check(int l,int r){
IT itr=split(r+1),itl=split(l);
int res=(itl->val);
for(IT it=itl;it!=itr;it++){
if(res!=it->val) return 0;
}
if(l==1||r==n) return 1;
itl--;
return itl->val!=itr->val;
}
const int maxn=500010;
char str[maxn];
int main(){
scanf("%d",&n);
scanf("%s",str+1);
scanf("%d",&m);
for(int i=1;i<=n;i++)
s.insert(node(i,i,str[i]-'A'+1));
while(m--){
char opt[3];
scanf("%s",opt);
if(opt[0]=='A'){
int l,r;char val;
scanf("%d%d %c",&l,&r,&val);
assign(l,r,val-'A'+1);
}
else if(opt[0]=='B'){
int l,r;
scanf("%d%d",&l,&r);
if(check(l,r))puts("Yes");
else puts("No");
}
}
return 0;
}
```
### 10.24 P3761 [TJOI2017]城市
昨天听级会 所以我咕了 这不算咕（理直气壮）
n方不难 推荐想完想On
下面是n方
```cpp
#include<bits/stdc++.h>
using namespace std;
int n;
const int maxn=10010;
struct node{
int to,nxt,val;
}tr[maxn<<1];
int head[maxn],tot=0;
inline void addedge(int u,int v,int w){
tr[++tot].to=v;
tr[tot].val=w;
tr[tot].nxt=head[u];
head[u]=tot;
}
int fst[maxn],sec[maxn],up[maxn],ans[maxn];
int u[maxn],v[maxn],w[maxn];
int MAXX=0;
int dfs1(int u,int fa){
fst[u]=sec[u]=0;
for(int i=head[u];i;i=tr[i].nxt){
int to=tr[i].to;
if(to==fa) continue;
int v=tr[i].val+dfs1(to,u);
if(v>fst[u]) {
sec[u]=fst[u];
fst[u]=v;
}
else if(v>sec[u]) sec[u]=v;
}
MAXX=max(MAXX,fst[u]+sec[u]);
return fst[u];
}
int dfs2(int u,int fa){
int res=(1<<30);
ans[u]=max(fst[u],up[u]);
for(int i=head[u];i;i=tr[i].nxt){
int to=tr[i].to;
if(to==fa) continue;
int v=tr[i].val+fst[to];
if(v==fst[u]) up[to]=max(up[u],sec[u])+tr[i].val;
else up[to]=max(up[u],fst[u])+tr[i].val;
}
for(int i=head[u];i;i=tr[i].nxt)
if(tr[i].to^fa) res=min(res,dfs2(tr[i].to,u));
return min(res,ans[u]);
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
int uu,vv,ww;scanf("%d%d%d",&uu,&vv,&ww);
u[i]=uu,v[i]=vv,w[i]=ww;
addedge(uu,vv,ww);addedge(vv,uu,ww);
}
int Ans=(1<<30);
for(int i=1;i<n;i++){
MAXX=0;
memset(up,0,sizeof up);
dfs1(u[i],v[i]);dfs1(v[i],u[i]);
Ans=min(Ans,max(dfs2(u[i],v[i])+dfs2(v[i],u[i])+w[i],MAXX));
}
return printf("%d\n",Ans),0;
}
````
### 10.25 38 无聊的数列
顺便今天学学树上分块
https://www.cnblogs.com/hua-dong/p/8275227.html
加等差数列也有一个记录lazytag的方法
不过我好像忘了
这题可以直接差分 变成区间加和区间询问
但是如果询问的是区间怎么办呢..
线段树速通
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=400010;
int n,m;
int tr[maxn],tag[maxn],a[maxn];
#define ls (rt<<1)
#define rs (rt<<1|1)
inline void pushup(int rt){
tr[rt]=tr[ls]+tr[rs];
}
inline void pushdown(int rt,int len){
if(!tag[rt]) return;
tr[ls]+=tag[rt]*(len-(len>>1));
tag[ls]+=tag[rt];
tr[rs]+=tag[rt]*(len>>1);
tag[rs]+=tag[rt];
tag[rt]=0;
}
inline void build(int rt,int l,int r){
if(l==r) {
tr[rt]=a[l];
return ;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(rt);
}
inline void modify(int rt,int l,int r,int ql,int qr,int val){
if(ql<=l&&qr>=r){
tr[rt]+=val*(r-l+1);
tag[rt]+=val;
return ;
}
pushdown(rt,r-l+1);
int mid=(l+r)>>1;
if(ql<=mid) modify(ls,l,mid,ql,qr,val);
if(qr>mid) modify(rs,mid+1,r,ql,qr,val);
pushup(rt);
}
inline int que(int rt,int l,int r,int ql,int qr){
if(ql<=l&&qr>=r)
return tr[rt];
pushdown(rt,r-l+1);
int mid=(l+r)>>1,res=0;
if(ql<=mid) res+=que(ls,l,mid,ql,qr);
if(qr>mid) res+=que(rs,mid+1,r,ql,qr);
return res;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
while(m--){
int opt;scanf("%d",&opt);
if(opt==1){
int l,r,k,d;
scanf("%d%d%d%d",&l,&r,&k,&d);
modify(1,1,n,l,l,k);
if(r>l) modify(1,1,n,l+1,r,d);
if(r!=n) modify(1,1,n,r+1,r+1,-(k+(r-l)*d));
}
else {
int x;scanf("%d",&x);
printf("%d\n",a[x]+que(1,1,n,1,x));
}
}
}
```
### 10.26 P2325 [SCOI2005]王室联邦
昨天的分块
原来是构造题...
抄了题解，其实自己应该写得出来 只是要学树分块看看有没有优美的做法
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=10010;
const int maxm=20010;
struct node{
int nxt,to;
}tr[maxn];int tot=0,head[maxn];
int rt[maxn],cnt=0;
int bel[maxn];
int n,B;
inline void addedge(int u,int v){
tr[++tot].nxt=head[u];
tr[tot].to=v;
head[u]=tot;
}
int stk[maxn],top=0;
void dfs(int u,int fa){
int lst=top;
for(int i=head[u];i;i=tr[i].nxt){
int to=tr[i].to;
if(to==fa) continue;
dfs(to,u);
if(top-lst>=B){
rt[++cnt]=u;
while(top>lst) bel[stk[top--]]=cnt;
}
}
stk[++top]=u;
}
int main(){
scanf("%d%d",&n,&B);
for(int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
addedge(u,v);addedge(v,u);
}
dfs(1,0);
if(!cnt) rt[++cnt]=1;
while(top) bel[stk[top--]]=cnt;
printf("%d\n",cnt);
for(int i=1;i<=n;i++) printf("%d ",bel[i]);
puts("");
for(int i=1;i<=cnt;i++) printf("%d ",rt[i]);
puts("");
return 0;
}
```
去写写树分块的题吧...
草 发现找不到题写
### 附加题 P3304 [SDOI2013]直径
本来根据【所有直径中点重合】的定理很容易做
但是翻题解看到了一个更加巧妙的方法
> 统计每条边构成直径的方案数，如果由这条边构成的直径的方案数等于全局方案数，那么这条边就必选。
很显然的做法但是我没想到诶..
那就写写看
结果没写正确做法
随机拎出几条直径，这些直径的交集就是答案
结果我拎了十条过了
xsl
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=400010;
int n;
struct node{
int to,nxt,w,id;
}tr[maxn];int head[maxn],tot=0;
struct edge{
int U,V,W,id;
}s[maxn];
int rt1,rt2;
inline void addedge(int u,int v,int w,int id){
tr[++tot].to=v;
tr[tot].id=id;
tr[tot].w=w;
tr[tot].nxt=head[u];
head[u]=tot;
}
int dep[maxn],mxdep=0,mxid;
void dfs(int u,int fa){
if(dep[u]>mxdep) {
mxid=u;
mxdep=dep[u];
}
for(int i=head[u];i;i=tr[i].nxt){
int to=tr[i].to;
if(to==fa) continue;
dep[to]=dep[u]+tr[i].w;
dfs(to,u);
}
}
int isans[maxn];
bool getans(int now,int V,int fa){
if(now==V) return 1;
for(int i=head[now];i;i=tr[i].nxt){
int to=tr[i].to;
if(to==fa) continue;
if(getans(to,V,now)){
isans[tr[i].id]++;
return 1;
}
}
return 0;
}
signed main(){
scanf("%lld",&n);
for(int i=1;i<n;i++){
scanf("%lld%lld%lld",&s[i].U,&s[i].V,&s[i].W);
s[i].id=i;
}
int DDD=0;
int Tim=30;
for(int limit=1;limit<=Tim;limit++){
random_shuffle(s+1,s+n);
memset(head,0,sizeof head);tot=0;memset(dep,0,sizeof dep);memset(tr,0,sizeof tr);
for(int i=1;i<n;i++) addedge(s[i].U,s[i].V,s[i].W,s[i].id),addedge(s[i].V,s[i].U,s[i].W,s[i].id);
dfs(1,0);rt1=mxid;
mxdep=0;memset(dep,0,sizeof dep);
dfs(rt1,0);
rt2=mxid;
getans(rt1,rt2,0);
DDD=mxdep;
}
int Ans=0;
for(int i=1;i<n;i++) if(isans[i]==Tim) Ans++;
printf("%lld\n%lld\n",DDD,Ans);
}
```
### 10.27 P2767 树的数量
数学题
当然也可以DP过 但是我打算数学方法过
从根节点开始向外连边，考虑倒每个点可以向外连的边数有m条，有n个点。
变成$nm$条边选$n-1$条边。
然后可能会连成环 但是这个可以算
乘上没连到已经连过的点的概率$\prod_{i=1}^{n-1} \frac{i}{i+1}=\frac{1}{n}$
就当是复习逆元了...
```cpp
#include<bits/stdc++.h>
using namespace std;
const int mod=10007;
int n,m;
int inv[mod],fac[mod],ifac[mod];
int main(){
scanf("%d%d",&n,&m);
inv[1]=1;
for(int x=2;x<mod;++x) inv[x]=(-(mod/x)*inv[mod%x])%mod+mod;
fac[0]=ifac[0]=1;
for(int x=1;x<mod;x++) fac[x]=(fac[x-1]*x)%mod,ifac[x]=ifac[x-1]*inv[x]%mod;
printf("%d\n",(((fac[(n*m)%mod]*ifac[n-1])%mod*ifac[n*m-n+1])%mod*inv[n])%mod);
}
```
### 10.28 P2184 贪婪大陆
假设询问的是区间$[l,r]$
很容易发现答案等于r之前的左端点个数减去l之前的区间右端点个数
随便拉个数据结构维护这俩即可
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=400010;
#define ls (rt<<1)
#define rs (rt<<1|1)
int n,m;
struct node{
int s[maxn],tag[maxn];
inline void pushup(int rt){
s[rt]=s[ls]+s[rs];
}
inline void pushdown(int rt,int len){
if(!tag[rt]) return ;
tag[ls]+=tag[rt];
tag[rs]+=tag[rt];
s[ls]+=tag[rt]*((len+1)>>1);
s[rs]+=tag[rt]*(len>>1);
tag[rt]=0;
}
inline void modify(int rt,int l,int r,int ql,int qr){
if(ql<=l&&qr>=r){
tag[rt]+=1;
s[rt]+=(r-l+1);
return ;
}
pushdown(rt,r-l+1);
int mid=(l+r)>>1;
if(ql<=mid) modify(ls,l,mid,ql,qr);
if(qr>mid) modify(rs,mid+1,r,ql,qr);
pushup(rt);
}
inline int que(int rt,int l,int r,int pos){
if(l==r) return s[rt];
int mid=(l+r)>>1;
pushdown(rt,r-l+1);
if(pos<=mid) return que(ls,l,mid,pos);
else return que(rs,mid+1,r,pos);
}
}tr1,tr2;
int main(){
scanf("%d%d",&n,&m);
while(m--){
int opt;
scanf("%d",&opt);
if(opt==1){
int l,r;
scanf("%d%d",&l,&r);
tr1.modify(1,1,n,l,n);
tr2.modify(1,1,n,r,n);
/*puts("tr1");for(int i=1;i<=n;i++) printf("%d ",tr1.que(1,1,n,i));puts("");
puts("tr2");for(int i=1;i<=n;i++) printf("%d ",tr2.que(1,1,n,i));puts("");*/
}
else{
int l,r;scanf("%d%d",&l,&r);
printf("%d\n",tr1.que(1,1,n,r)-tr2.que(1,1,n,l-1));
}
}
return 0;
}
```
### 10.29 P6858 深海少女与胖头鱼
草
深海少女与峰哥（确信）
为什么能在战棋里施放带剧毒的黑暗天际————
> 你的克苏恩具有剧毒，对面全是胖头鱼，请问期望情况下你的克苏恩具有多少攻击力才能解光场
胖头鱼$\texttt{RIP}$
很容易看出 ~~（因为经常整活，很快就想到）~~ 只需要考虑$m=1$或者$0$的情况，$m$为其他值都能很容易转化为$m=1$的情况。
$f(n,m)$表示剩下$n$条圣盾剧毒鱼，$m$条剧毒鱼
那么只需要推$f(n,0)$和$f(n,1)$即可
$f(n,0)$只能破盾
所以$f(n,0)=f(n-1,1)+1$
$f(n,1)$，有$\frac{1}{n+1}$概率可以撒掉一条鱼，其他都是白给
$f(n,1)=\frac{1}{n+1}f(n,0)+\frac{n}{n+1}f(n,1)+1$
是个递归定义的柿子，所以解方程
解得
$f(n,1)=f(n,0)+n+1$
然而$f(n,0)$我们已经蒜过了，于是变成
$f(n,1)=f(n-1,1)+n+2$
所以可以递推蒜
但是这个肯定是个二次函数
代特值也行，其他方法也行。可以算出$f(n,1)=\frac{n^2+5n+2}{2}$
$m>1$的情况考虑打不打到圣盾即可
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
inline int fpw(int a,int b){
int res=1;
while(b){
if(b&1) (res*=a)%=mod;
(a*=a)%=mod;
b>>=1;
}
return res;
}
int f(int n,int m){
if(m==0) return (f(n-1,1)+1)%mod;
else if(m==1) return ((n*n+5*n+2)/2)%mod;
else {
return
(((m*fpw(n+m,mod-2))%mod*f(n,m-1)+1)%mod
+(n*fpw(n+m,mod-2))%mod*f(n+m-1,1)%mod)%mod;
}
}
signed main(){
int n,m;
scanf("%lld%lld",&n,&m);
printf("%lld\n",f(n%mod,m));//这里没膜调了好久
return 0;
}
```
### 10.30 P6859 蝴蝶与花
挺有意思的题
我什么时候才能想出有意思的idea啊/dk
这个权值只有1和2非常能玩味
因为只有1和2，所以应该很容易找到一个区间满足区间和为$s$。
比如从$l=1$开始，考虑一个$R$使得$\sum_{i=1}^R a_i$小于等于$s$且最大
如果有的话最好。没有的话可以发现区间和只和$s$相差1。
怎么调出这个$1$出来？
如果r的下一位是1，那直接将r右移一位
下一位是2，右移一位后，如果$l$是1，那l也右移一位就行了
第一位和$r+1$都是2，那就只能都右移一位，继续执行以上操作。
可以发现，这就是询问$1$和$R$向右连续有多少个2。
直接线段树维护一下，二分位置找到$R$，再找有多少个连续2即可
因为$n=2e6$，需要卡常，把二分的过程写成循环会比较好。写成递归不太好过。
还有一种我不会的树状数组两个log写法
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000010;
int n,m;
int a[maxn],sum[maxn<<2],num[maxn<<2];
#define ls (rt<<1)
#define rs (rt<<1|1)
#define GG {puts("none");continue;}
inline void pushup(int rt){
sum[rt]=sum[ls]+sum[rs];
num[rt]=num[ls]+num[rs];
}
inline void build(int rt,int l,int r){
if(l==r) {
sum[rt]=a[l];
num[rt]=(a[l]==1);
return ;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(rt);
}
inline void modify(int rt,int l,int r,int pos,int val){
if(l==r) {
sum[rt]=val;
num[rt]=(val==1);
return ;
}
int mid=(l+r)>>1;
if(pos<=mid) modify(ls,l,mid,pos,val);
else modify(rs,mid+1,r,pos,val);
pushup(rt);
}
inline int quesum(int rt,int l,int r,int ql,int qr){
if(ql<=l&&qr>=r) return sum[rt];
int mid=(l+r)>>1,res=0;
if(ql<=mid) res+=quesum(ls,l,mid,ql,qr);
if(qr>mid) res+=quesum(rs,mid+1,r,ql,qr);
return res;
}
inline int quenum(int rt,int l,int r,int ql,int qr){
if(ql<=l&&qr>=r) return num[rt];
int mid=(l+r)>>1,res=0;
if(ql<=mid) res+=quenum(ls,l,mid,ql,qr);
if(qr>mid) res+=quenum(rs,mid+1,r,ql,qr);
return res;
}
inline int searchsum(int rt,int l,int r,int val){
if(l>r) return 0;
while(l<r){
int mid=(l+r)>>1;
if(sum[ls]>=val) r=mid,rt=ls;
else l=mid+1,val-=sum[ls],rt=rs;
}
return l;
}
inline int searchnum(int rt,int l,int r,int val){
while(l<r){
int mid=(l+r)>>1;
if(num[ls]>=val) r=mid,rt=ls;
else l=mid+1,val-=num[ls],rt=rs;
}
return l;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
a[n+1]=1;
build(1,1,n+1);
while(m--){
char opt[3];scanf("%s",opt);
if(opt[0]=='A'){
int x;scanf("%d",&x);
if(x>sum[1]-1||x==0) GG;
int pos=searchsum(1,1,n+1,x);
if(quesum(1,1,n+1,1,pos)==x){
printf("1 %d\n",pos);
continue;
}
if(a[1]==1) {
printf("2 %d\n",pos);
continue;
}
int L=searchnum(1,1,n+1,1),
R=searchnum(1,1,n+1,quenum(1,1,n+1,1,pos)+1);
if(pos+L-1>n&&R>n)GG;
if(R+1<L+pos+1){
printf("%d %d\n",R-pos+1,R);
continue;
}
else printf("%d %d\n",L+1,L+pos-1);
}
if(opt[0]=='C'){
int pos,val;scanf("%d%d",&pos,&val);
a[pos]=val;modify(1,1,n+1,pos,val);
}
}
return 0;
}
```
### 10.31 P2634 [国家集训队]聪聪可可(https://www.luogu.com.cn/problem/P2634)
最后一道难题~
这一周会给比较板子的题
可以树形DP，也可以点分治
CSP后再回归难点的题8
DP更好写，过会写点分治：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=400010;
struct node{
int to,nxt,w;
}tr[maxn];int head[maxn],tot=0;
int f[maxn][3];
int n;
inline void addedge(int u,int v,int w){
tr[++tot].to=v;
tr[tot].nxt=head[u];
tr[tot].w=w;
head[u]=tot;
}
inline int gcd(int x,int y){
if(!(x&&y)) return x|y;
int t;while(t=x%y) x=y,y=t;
return y;
}
const int mod=3;
int ans=0;
inline void dfs(int u,int fa){
f[u][0]=1;
for(int i=head[u];i;i=tr[i].nxt){
int to=tr[i].to,w=tr[i].w;
if(to==fa) continue;
dfs(to,u);
for(int j=0;j<=2;j++) ans+=f[to][j]*f[u][(-j-w+100000*mod)%mod]*2;
for(int j=0;j<=2;j++) f[u][(j+w)%3]+=f[to][j];
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++) {
int u,v,w;scanf("%d%d%d",&u,&v,&w);
w%=mod;
addedge(u,v,w);addedge(v,u,w);
}
dfs(1,0);
ans+=n;
int GCD=gcd(ans,n*n);
printf("%d/%d\n",ans/GCD,n*n/GCD);
return 0;
}
```
点分治目前如下~~但是他T了~~ 已经过了
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=400010;
struct node{
int to,nxt,w;
}tr[maxn];int head[maxn],tot=0;
int ans=0;
bool vis[maxn];
int n;
int son[maxn],sum;
int rt,siz[maxn];
int nte[4],dis[maxn];
inline void addedge(int u,int v,int w){
tr[++tot].to=v;
tr[tot].nxt=head[u];
tr[tot].w=w;
head[u]=tot;
}
inline int gcd(int x,int y){
if(!(x&&y)) return x|y;
int t;while(t=x%y) x=y,y=t;
return y;
}
void getrt(int u,int fa){
siz[u]=1,son[u]=0;
for(int i=head[u];i;i=tr[i].nxt){
int to=tr[i].to;
if(vis[to]||to==fa) continue;
getrt(to,u);siz[u]+=siz[to];
son[u]=max(siz[to],son[u]);
}
son[u]=max(sum-siz[u],son[u]);
if(son[u]<=son[rt]) rt=u;
}
void getdis(int u,int fa){
++nte[dis[u]%3];
for(int i=head[u];i;i=tr[i].nxt){
int to=tr[i].to;
if(to==fa||vis[to]) continue;
dis[to]=(dis[u]+tr[i].w)%3;
getdis(to,u);
}
}
inline int calc(int x,int w){
memset(nte,0,sizeof nte);
dis[x]=w%3;
getdis(x,0);
return nte[2]*nte[1]*2+nte[0]*nte[0];
}
inline void solve(int u){
vis[u]=1;
ans+=calc(u,0);
for(int i=head[u];i;i=tr[i].nxt){
int to=tr[i].to,w=tr[i].w;
if(vis[to]) continue;
ans-=calc(to,w%3);
son[0]=n,rt=0;
sum=siz[to];
getrt(to,u);solve(rt);
}
}
signed main()
{
scanf("%d",&n);
son[0]=sum=n,rt=0;
for(int i=1,u,v,w;i<n;i++){
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w%3);
addedge(v,u,w%3);
}
getrt(1,0);
solve(rt);
int k=gcd(ans,n*n);
printf("%d/%d",ans/k,n*n/k);
return 0;
}
```
### 11.1
tag 简单trick
内部题目/kel
我以为大象只能上下左右走
于是
```cpp
#include<bits/stdc++.h>
using namespace std;
bool a1=0,a2=0,a3=0,a4=0;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
int x,y;cin>>x>>y;
if(y>=0&&y>=x&&y>=-x) a1=1;
if(y<=0&&y<=x&&y<=-x) a2=1;
if(x<=0&&x<=y&&x<=-y) a3=1;
if(x>=0&&x>=y&&x>=-y) a4=1;
}
if(a1&&a2&&a3&&a4) puts("NO");
else puts("YES");
return 0;
}
```
但是过了！！！
然而很容易卡
```
2
1 2
-1 -2
```
正解的分类比较对
```cpp
#include <iostream>
using namespace std;
const int MAX = 1e5 + 5;
struct p {
long long x;
long long y;
};
int main() {
int n;
struct p a[MAX];
bool up = 1, down = 1, left = 1, right = 1;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].x >> a[i].y;
if (a[i].x >= 0)
right = 0;
if (a[i].x <= 0)
left = 0;
if (a[i].y >= 0)
up = 0;
if (a[i].y <= 0)
down = 0;
}
if (right || left || up || down)
cout << "YES" << endl;
else
cout << "NO" << endl;
return 0;
}
```
过于浅显就不写题解了
本系列最简单的一题哦~
### 11.2
tag 搜索
毛毛有n堆石子，其中第i堆石子有Si个石子，每个石子大小为1。
现在牛牛有一些袋子，他每次会选择其中一堆，用袋子装走其中m个石子，如此往复，直到所有堆的石子数少于m。
为了使牛牛装完之后剩余最大堆的石子数尽可能多，毛毛决定事先将某些石子堆进行合并，即选择一些堆，将它们合成一堆，如此往复形成新的若干堆。请你帮助毛毛制定合理的策略，并计算剩余最大堆的石子数。
$n\leq 35$
有个subtask是$n\leq 20$
发现就是$n$个数选几个数让他们之和膜$m$最大
可以$2^n$枚举所有取法然后取最大值
35约为$20\times 2$ 所以很容易想到折半搜索
先求出俩数组表示第$1$个到$n\frac{n}{2}$个能组成的数和$n\frac{n}{2}+1$到$n$能组成的数
然后~~过滤洗涤干燥~~去重排序
对于第一个数组每一个数二分一下能和第二个数组凑成的最大值
算是折半搜索大板子了
```cpp
#include<bits/stdc++.h>
using namespace std;
/*
先暴力求1~n/2和 n/2~n 能搞出来的石头个数
搞成俩数组
排序
第一个数组的每个数lowerbound一下mod-ai
4 4
5 2 4 1
*/
const int maxn=41;
int n,m;
int a[maxn];
int pt[2][(1<<22)+10],cnt[2];
void dfs(int l,int r,int now,int sum,int id){
//cerr<<l<<' '<<r<<' '<<now<<' '<<sum<<' '<<id<<endl;
pt[id][++cnt[id]]=sum;
if(now==r) return ;
dfs(l,r,now+1,sum,id);
dfs(l,r,now+1,(sum+a[now+1])%m,id);
}
inline bool cmp(int a,int b){
return a>b;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
//cerr<<"n/2:"<<n/2<<endl;
pt[0][++cnt[0]]=0;
pt[1][++cnt[1]]=0;
dfs(1,n/2,0,0,0);
dfs(n/2+1,n,n/2,0,1);
sort(pt[0]+1,pt[0]+1+cnt[0]);
sort(pt[1]+1,pt[1]+1+cnt[1]);
cnt[0]=unique(pt[0],pt[0]+1+cnt[0])-pt[0];
cnt[1]=unique(pt[1],pt[1]+1+cnt[1])-pt[1];
sort(pt[0]+1,pt[0]+1+cnt[0],cmp);
sort(pt[1]+1,pt[1]+1+cnt[1],cmp);
int Ans=0;
/*
puts("start:");
for(int i=1;i<=cnt[0];i++) cerr<<pt[0][i]<<' ';puts("");
for(int i=1;i<=cnt[1];i++) cerr<<pt[1][i]<<' ';puts("");
puts(":end");
*/
for(int i=1;i<=cnt[0];i++){
int x=pt[0][i];
Ans=max(Ans,(pt[1][upper_bound(pt[1]+1,pt[1]+1+cnt[1],m-x,greater<int>())-pt[1]])+x);
}
printf("%d\n",Ans);
return 0;
}
```
### 11.3 [CF815B Karen and Test](https://www.luogu.com.cn/problem/CF815B)
tag 结论与比较难一点的trick
列几种情况出来
$a,b,c,d$
$a+b,b-c,c+d$
$a+c,b+d$
$a-b+c-d$
---
$a,b,c,d,e,f$
$a+b,b-c,c+d,d-e,e+f$
$a+c,b+d,c+e,d+f$
$a+c-b-d,b+c+d+e,c+e-d-f$
$a+2c+e,b+2d+f$
$a+b+2c+2d+e+f$
---
$a,b,c,d,e,f,g,h$
$...$
$a+3c+3e+g,b+3d+3f+h$
$a+b+3c+3d+3e+3f+g+h$
对于$n$为偶数，很容易发现倒数第二行是$C_{\frac{n}{2}-1}^i$。
是奇数先膜你一遍把他变成偶数即可。
然后倒数第二行的两个数中间是加是减可以由$n%2$为2还是0找到规律。
这个题其实很容易发现每个数的贡献最后肯定会类似杨辉三角。
而且一眼就能看出来要考虑贡献。
注意判断$n=1$
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int maxn=200010;
int a[maxn],b[maxn],s[maxn];
inline int fpw(int a,int b){
int res=1;
while(b){
if(b&1) (res*=a)%=mod;
(a*=a)%=mod;b>>=1;
}
return res;
}
inline int C(int a,int b){
return s[b]*fpw(s[a],mod-2)%mod*fpw(s[b-a],mod-2)%mod;
}
signed main(){
int n;
scanf("%lld",&n);
s[1]=s[0]=1;
for(int i=2;i<=n;++i) s[i]=s[i-1]*i%mod;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
if(n==1){
printf("%lld\n",a[1]);
return 0;
}
if(n%2){
n--;int opt=1;
for(int i=1;i<=n;i++){
b[i]=a[i]+opt*a[i+1];
opt*=-1;
}
for(int i=1;i<=n;i++)
a[i]=b[i];
}
//for(int i=1;i<=n;i++) cerr<<a[i]<<' ';puts("");
int opt;
int ans=0;
if(n%4==2) opt=1;
if(n%4==0) opt=-1;//C可能反了
for(int i=1;i<=n;i+=2)
(ans+=(C(i/2,n/2-1)*(a[i]+mod)%mod))%=mod;
for(int i=2;i<=n;i+=2)
(ans+=((C((i-1)/2,n/2-1)*(a[i]+mod))%mod*(opt+mod))%mod)%=mod;
printf("%lld\n",ans);
return 0;
}
```
接下来来看可怜8
### 11.4 P5858 「SWTR-03」Golden Sword
いいよ！こいよ！
tag:DP
算是比较套路的DP题
首先设$f_{i,j}$表示$i$加入时炉子里有$j$个材料的最大耐久
我刚开始设的是还没弹出的最老材料是$j$的的最大耐久 其实一样而且这个比较难算
所以用了大部分人写的上面这个
接下来随便推推柿子
考虑 $f_{i,j}$ 从哪里转移来。任何一个$f_{i-1,k}(j-1\leq k\leq min(w,j+s-1))$都可以转移来，从中取max即可，此时复杂度$O(n$
发现对于同一个i，不同的j，前驱状态可以单调队列优化.
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=5510;
#define int long long
int n,w,s;
int a[maxn],val[maxn],q[maxn];
int f[maxn][maxn];//i放入时，有j个
signed main(){
scanf("%lld%lld%lld",&n,&w,&s);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
memset(f,128,sizeof f);
f[0][0]=0;
for(int i=1;i<=n;i++){
int l=1,r=1;
q[l]=f[i-1][w];
val[l]=w;
for(int j=w;j;j--){
while(val[l]>j+s-1&&l<=r) l++;
while(q[r]<f[i-1][j-1]&&l<=r) r--;
val[++r]=j-1;
q[r]=f[i-1][j-1];
f[i][j]=q[l]+j*a[i];
}
}
int ans=-(1ll<<60);
for(int i=0;i<=w;i++)
ans=max(ans,f[n][i]);
return printf("%lld\n",ans),0;
}
```
### 11.5 P2824 [HEOI2016/TJOI2016]排序
tag 线段树 数据结构 二分
一年多前写的暴力开O2过了？？
注意到如果序列改为01序列而不是排序，就可以由线段树方便的维护（区间覆盖，最后单点查询）
二分一个值，序列中大于它的改为1，其余改为0，用线段树维护修改过程，检查p点的01继续二分即可
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ls (rt<<1)
#define rs (rt<<1|1)
const int maxn=5e5+10;
int n,m,q;
int tr[maxn<<2],tag[maxn<<2];
int a[maxn],b[maxn];
struct Q{
int opt,l,r;
}que[maxn];
inline void pushup(int rt){
tr[rt]=tr[ls]+tr[rs];
}
inline void pushdown(int rt,int l,int r){
if(tag[rt]==-1) return ;
int mid=(l+r)>>1;
tag[ls]=tag[rs]=tag[rt];
tr[ls]=tag[rt]*(mid-l+1);
tr[rs]=tag[rt]*(r-mid);
tag[rt]=-1;
}
inline void build(int rt,int l,int r){
if(l==r){tr[rt]=b[l];return;}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(rt);
}
inline void modify(int rt,int l,int r,int ql,int qr,int val){
if(ql<=l&&qr>=r){
tag[rt]=val;
tr[rt]=val*(r-l+1);
return ;
}
if(ql>r||qr<l) return;
int mid=(l+r)>>1;
pushdown(rt,l,r);
if(ql<=mid) modify(ls,l,mid,ql,qr,val);
if(qr>mid) modify(rs,mid+1,r,ql,qr,val);
pushup(rt);
}
inline int query(int rt,int l,int r,int ql,int qr){
if(ql<=l&&qr>=r)return tr[rt];
int mid=(l+r)>>1,ans=0;
pushdown(rt,l,r);
if(ql<=mid) ans+=query(ls,l,mid,ql,qr);
if(qr>mid) ans+=query(rs,mid+1,r,ql,qr);
return ans;
}
inline int judge(int num){
for(int i=1;i<=n;i++) b[i]=a[i]>=num;
memset(tr,0,sizeof tr);
memset(tag,-1,sizeof tag);
build(1,1,n);
for(int i=1;i<=m;i++){
int opt=que[i].opt,l=que[i].l,r=que[i].r;
int cnt=query(1,1,n,l,r);
if(opt==0){
modify(1,1,n,r-cnt+1,r,1);
modify(1,1,n,l,r-cnt,0);
}
else {
modify(1,1,n,l,l+cnt-1,1);
modify(1,1,n,l+cnt,r,0);
}
}
return query(1,1,n,q,q);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++) scanf("%d%d%d",&que[i].opt,&que[i].l,&que[i].r);
scanf("%d",&q);
int l=1,r=n,ans=1;
while(l<=r){
int mid=(l+r)>>1;
if(judge(mid))
l=mid+1,ans=mid;
else r=mid-1;
}
printf("%d\n",ans);
return 0;
}
```
PS build最后没pushup调了一节课
PS PS 然后RE看了讨论排除了ql=qr-1的情况
PS PS PS 所以我自己写会调成傻逼
### 11.5 easy version P6801 [CEOI2020]花式围栏
tag：数据结构
单调栈维护即可
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
const int maxn=100010;
int n,h[maxn],w[maxn],ans=0;
int stk[maxn],top=0,sum=0;
inline int calc(int x){
return x*(x-1)/2%mod;
}
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&h[i]);
for(int i=1;i<=n;i++) scanf("%lld",&w[i]);
stk[++top]=0;
for(int i=1;i<=n+1;i++){
sum=0;
while(h[stk[top]]>h[i]) {
int u=stk[top--];
(sum+=w[u])%=mod;
ans+=(calc(h[u]+1)-calc(max(h[i],h[stk[top]])+1)+mod)%mod*calc(sum+1)%mod;
ans%=mod;
}
w[i]+=sum;
stk[++top]=i;
}
return printf("%lld\n",ans),0;
}
```
### 11.6 P5590 赛车游戏
### 11.8 [CF815D Karen and Cards](https://www.luogu.com.cn/problem/CF815D)
PS 应该是没人看了所以文笔和文体大概会放飞自我
给$n,p,q,r$。再给$n$个三元组，询问有多少个三元组满足$a,b,c$中至少两个大于每个$a_i,b_i,c_i$。$p,q,r$是对$a,b,c$的限制。
注意这里指的是对于每个三元组都可以单独比较，比如第一个三元组我只需要b和c比他大，第二个a和b比他大。
难题。
官方题解好像是单调栈扫描线，然而我不想写扫描线
（不过好像是扫描线经典套路）
我先考虑改成二元组，至少一个大于的做法。
考虑每个$a_i$，计算对于每个$i$大于还是小于等于$a_i$的方案数
这个很好做。如果把$a_i$和$b_i$画在数轴上，$a_i$每一小段（指$a_i$到$a_{i+1}$，因为不减有重复）乘上对应的$b_i$，加上$a_i$到$maxb-b_i$ 就是答案，maxb表示b封顶的值
哈哈哈哈哈哈哈感觉自己在胡言乱语，应该没人看得懂吧
（为什么我会想笑呢）
于是就看luogu的题解
不得不说luogu这个题解的做法是真的仙
关于扫描线：我不写了
仍然枚举$x$，这个过程其实顺便枚举了$a_i$。
从大到小枚举，记当前枚举到的最大的$b_i$和$c_i$。
实际上是$a_i\geq x$中最大的$b_i$和$c_i$
再记一个$MX_j$表示$b_i\geq j$中最大的 $c_i$
枚举每个$x$，对于每个$x$，答案为
$$\sum_{mx2+1}^q r-max(MX_i,mx3)$$
（因为要求$z>c_i$且$y>b_i$）
然后这样是$n$方的，然而发现后面那一项有规律可循，前一段选择$MX_i$,后一段$mx3$。
所以找到这两段的分界点统计~
真的很难啊 我哭哭
甚至觉得扫描线单调栈比这个还好搞（）
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,p,q,r;
const int maxn=1e7+10;
struct node{
int b,c,nxt;
}card[maxn];int head[maxn],tot=0;
int MX[maxn];//bi>=j 中 最大的ci
inline void insert(int a,int b,int c){
card[++tot].b=b;
card[tot].c=c;
card[tot].nxt=head[a];
head[a]=tot;
}
int sum[maxn];
signed main(){
scanf("%lld%lld%lld%lld",&n,&p,&q,&r);
for(int i=1;i<=n;i++){
int a,b,c;
scanf("%lld%lld%lld",&a,&b,&c);
insert(a,b,c);
MX[b]=max(MX[b],c);
}
for(int i=q-1;i;i--) MX[i]=max(MX[i],MX[i+1]);
for(int i=1;i<=q;i++) sum[i]=sum[i-1]+MX[i];
int mxb=0,mxc=0,k=q+1;
int ans=0;
for(int x=p;x;x--){
for(int i=head[x];i;i=card[i].nxt){
int y=card[i].b,z=card[i].c;
mxb=max(mxb,y),mxc=max(mxc,z);
while(k>mxb+1&&MX[k-1]<mxc) k--;
}
k=max(k,mxb+1);
ans+=(r-mxc)*(q-k+1)+r*(k-mxb-1)+(sum[mxb]-sum[k-1]);
}
return printf("%lld\n",ans),0;
}
```
回来看可怜~
### 11.9 [P1360 [USACO07MAR]Gold Balanced Lineup G](https://www.luogu.com.cn/problem/P1360)
应该很多人做过
全体+1相当于没加，所以元素大小只要找其中一个元素定0比较就行了
第一个固定为0，塞进map里比较就行了
就像政治说的真理和谬论相互依存之类的吧
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m;
inline int lowbit(int x){
return (x&-x);
}
map<vector<int>,int> mp;
inline int Log2(int x){
int res=0;
while(x>1){
res++;
x>>=1;
}
return res;
}
int main(){
scanf("%d%d",&n,&m);
int ans=0;
vector<int> now(m);
mp[now]=0;
for(int i=1;i<=n;i++){
int x;scanf("%d",&x);
if(x&1) for(int j=0;j<m;j++)now[j]--;
while(x){
now[Log2(lowbit(x))]++;
x-=lowbit(x);
}
if(mp.count(now)) ans=max(ans,i-mp[now]);
else mp[now]=i;
}
return printf("%d\n",ans),0;
}
```
### 11.10 [P3691 妖精大战争](https://www.luogu.com.cn/problem/P3691)
提示 这个人不仅写题解瞎写，选题也瞎选了
机 器 学 习
神 经 网 络
[3B1B Part1](https://www.bilibili.com/video/av15532370)
[3B1B Part2](https://www.bilibili.com/video/BV1Ux411j7ri)
[3B1B Part3](https://www.bilibili.com/video/BV16x411V7Qg/)
总有一天我也要造造这种题/cy
嗯。。。可能以后会写一篇神经网络算法学习？
也可以各种乱搞分块过
抄一个神经元写法当入门（by orangebird）：
因为这条线无限向上走肯定是太阳，无限向左右走也肯定答案确定。
$wx,wy$把$x,y$的位置表示成了大于0还是小于0来判断是在直线上还是下，加上$wbias$让参数更加准确。
然后拿已知数据训练他。
详见orangebird的题解
```cpp
#include<bits/stdc++.h>
using namespace std;
inline double Rand(){
return (double) (rand()%10000)/10000.0;
}
int n,m;
double wx,wy,wbias,learn,bias=1;
inline int solve(double x,double y){
double res=x*wx+y*wy+bias*wbias;
return res>0?1:-1;
}
inline void train(double x,double y,double k){
double res=solve(x,y);
double err=k-res;
wx=wx+err*x*learn;
wy=wy+err*y*learn;
wbias=wbias+err*bias*learn;
}
int main(){
srand(time(0));
wbias=Rand()*2-1;
wx=Rand()*2-1;
wy=Rand()*2-1;
int cas;
scanf("%d%d%d",&n,&m,&cas);
learn=0.0005;
for(int i=1;i<=n;i++){
double x,y;int k;
cin>>x>>y>>k;
train(x,y,k);
}
for(int i=1;i<=m;i++){
double x,y;
cin>>x>>y;
cout<<solve(x,y)<<endl;
}
return 0;
}
```
### 11.11 [P5482 [JLOI2011]不等式组](https://www.luogu.com.cn/problem/P5482)
### 11.12 [CF553C Love Triangles](https://www.luogu.com.cn/problem/CF553C)
翻译中用爱边和恨边让题目更容易做了
如果用0和1会难想不少。
考虑到边形成的联通块内所有其他连边已经确定，而联通块之间可以连恨边和爱边。
这有些类似于一个二分图结构。
但是原图可能有不合法的情况，我们先把边连起来。然后dfs判断合不合法顺便统计连通块个数即可。
感觉绿题难度（如果用0和1可能会变成蓝） 我真的不是故意水黑题啊awa
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
const int maxn=1000010;
int n,m;
int vis[maxn],col[maxn];
struct node{
int to,nxt,w;
}G[maxn<<1];int head[maxn],tot=0;
inline void addedge(int u,int v,int w){
G[++tot].nxt=head[u];
G[tot].to=v;
G[tot].w=w;
head[u]=tot;
}
inline int fpw(int a,int b){
int res=1;
while(b){
if(b&1) (res*=a)%=mod;
(a*=a)%=mod;
b>>=1;
}
return res;
}
void dfs(int u,int fa,int flg){
if(vis[u]){
if(col[u]^flg){
puts("0");
exit(0);
}
return ;
}
vis[u]=1;col[u]=flg;
for(int i=head[u];i;i=G[i].nxt){
int to=G[i].to;
if(to==fa) continue;
dfs(to,u,G[i].w?flg:-flg);
}
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
int ans=0;
for(int i=1;i<=n;i++){
if(!vis[i]){
ans++;
dfs(i,0,1);
}
}
printf("%lld\n",fpw(2,ans-1));
return 0;
}
```
### 11.13
遇到了很奇怪的事情
### [Normal CF274A k-Multiple Free Set](https://www.luogu.com.cn/problem/CF274A)
div1 的A题。拿来休闲一下
序列中每个元素都不相同，那每次取了一个元素就不能取他的$k$倍，但是可以取$k^2$倍
具体化为一条链的形状，就变成了给很多条链，每条边连接链的两个节点，分别为$x$和$x*k$。
可以算成每条链最多取链长除以二上取整个数的点。
也可以只从端点开始取
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int n,k;
int a[maxn],ans=0;
map<int,int> mp;
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+1+n);
for(int i=1;i<=n;i++) {
int x=a[i];
if(!mp[x]){
mp[x*k]=1;
ans++;
}
}
printf("%d\n",(ans+1)/2);
return 0;
}
```
### [附加 Normal P3692 夏幻的考试](https://www.luogu.com.cn/problem/P3692)
> ▇▇▇：3691和3692都写了，下一道题是3693？
> 我：guna
儒 略 历
3 6 9 3 恐 惧 症
直接模拟 一遍过!
```cpp
#include<bits/stdc++.h>
using namespace std;
int T,n;
string s;
string ans;
inline int trans(string s){
int res=0,pw=16*16*16*8;
for(int i=0;i<16;i++){
res+=(s[i]-'0')*pw;
pw/=2;
}
return res;
}
int main(){
scanf("%d%d",&T,&n);
cin>>ans;
for(int tim=1;tim<=T;tim++){
string t;
cin>>t;
int ID=trans(t);
if(ID>10000||ID<1) {
puts("Wrong ID");
puts("");
cin>>t;
for(int i=1;i<=n;i++) cin>>t;
continue;
}
else {
printf("ID: %d\n",ID);
cin>>s;
if(s=="01"){
if(t[15]=='1') puts("Type Correct");
else puts("Type Incorrect");
}
else if(s=="10"){
if(t[15]=='0') puts("Type Correct");
else puts("Type Incorrect");
}
else {
puts("Type Incorrect");
}
int res=0;
for(int i=0;i<n;i++){
string f;
cin>>f;
if(f=="1000"&&ans[i]=='A') res++;
if(f=="0100"&&ans[i]=='B') res++;
if(f=="0010"&&ans[i]=='C') res++;
if(f=="0001"&&ans[i]=='D') res++;
}
printf("%.1lf\n\n",(double)res*100/n);
}
}
return 0;
}
```
下次写3693（大雾）
### 11.14 让我睡个觉行不行，行不行，行不行
> ▇▇▇：不行
[P3708 koishi的数学题](https://www.luogu.com.cn/problem/P3708)
因为我对读柿子过敏就把柿子展开了
然后发现竖行有规律
然后考虑每个数对答案的贡献，直接反过来预处理就行了
小 聪 明
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int n;
typedef long long ll;
ll ans=0;
int a[maxn];
int main(){
scanf("%d",&n);
for(int i=2;i<=n;i++)
for(int j=i;j<=n;j+=i)
a[j]+=i;
for(int i=1;i<=n;i++){
ans+=n-a[i]-1;
printf("%lld ",ans);
}
return puts(""),0;
}
```
### 11.15 [P4915 帕秋莉的魔导书](https://www.luogu.com.cn/problem/P4915)
> ▇▇▇：为什么全是东方背景啊
> 我：针真的不是故意选的啊
> ▇▇▇：下次是不是3693了啊
> 我：guna
要熄灯了 先贴代码
题解明天补>_<
评价一下 使用线段树并动态开点比较巧妙，但是与期望的结合比较生硬
这个动态开点看起来就是很经典的套路，然而 我 第一次 做？
闭着眼睛都能想出来询问就是询问区间和/区间长度。因为询问本质是然后做一个前缀和
所以每次单点修改就变成了区间加（从修改的位置到末尾），询问区间前缀和之和。
这一部分真的没什么意思。。。亮点是接下来因为因为你不知道序列的末尾所以用动态开点线段树
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000010;
#define int long long
struct node{
int lft,rht;
int sum,tag;
node():lft(0),rht(0),sum(0),tag(0){}
}tr[maxn<<2];
int n,m,cnt=1;
#define ls tr[rt].lft
#define rs tr[rt].rht
inline void pushdown(int rt,int len){
if(!tr[rt].tag) return;
if(!ls)ls=++cnt;
if(!rs)rs=++cnt;
tr[ls].tag+=tr[rt].tag;
tr[rs].tag+=tr[rt].tag;
tr[ls].sum+=tr[rt].tag*(len-(len>>1));
tr[rs].sum+=tr[rt].tag*(len>>1);
tr[rt].tag=0;
}
inline void pushup(int rt){
tr[rt].sum=tr[ls].sum+tr[rs].sum;
}
inline void modify(int rt,int l,int r,int ql,int qr,int val){
if(l>qr||r<ql) return ;
if(l>=ql&&r<=qr){
tr[rt].tag+=val;
tr[rt].sum+=val*(r-l+1);
return ;
}
int mid=(l+r)>>1;
pushdown(rt,r-l+1);
if(!ls) ls=++cnt;if(!rs) rs=++cnt;
modify(ls,l,mid,ql,qr,val);
modify(rs,mid+1,r,ql,qr,val);
pushup(rt);
}
int query(int rt,int l,int r,int ql,int qr){
if(l>qr||r<ql) return 0;
if(l>=ql&&r<=qr) return tr[rt].sum;
pushdown(rt,r-l+1);
int mid=(l+r)>>1;
int res=0;
res+=ls?query(ls,l,mid,ql,qr):0;
res+=rs?query(rs,mid+1,r,ql,qr):0;
return res;
}
const int INF=(1<<30);
signed main(){
scanf("%lld%lld",&n,&m);
for(int pos,val,i=1;i<=n;i++){
scanf("%lld%lld",&pos,&val);
modify(1,1,INF,pos,INF,val);
}
while(m--){
int opt,pos,val;
scanf("%lld%lld%lld",&opt,&pos,&val);
if(opt==1)
printf("%.4lf\n",(double)query(1,1,INF,pos,val)/(val-pos+1));
else modify(1,1,INF,pos,INF,val);
}
return 0;
}
```
### 11.16 [P4912 帕秋莉的魔法](https://www.luogu.com.cn/problem/P4912)
这次是故意的（半恼
简单DP题，直接设选前$i$个，咒语长度为$j$的最大贡献，然后对于每个状态枚举上一个状态DP就行了
时间复杂度$O(n^2m)$
因为有负数，所以加上个较大值防止越界
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=2520;
const int GG=2510;
int n,m;
int f[maxn][maxn+GG];//fij表示前i个选i，体积为j
int a[maxn],b[maxn],w[maxn][maxn];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i],&b[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&w[i][j]);
memset(f,128,sizeof f);
f[0][GG]=0;
for(int i=1;i<=n;i++)
for(int j=a[i];j<maxn+GG;j++)
for(int k=0;k<i;k++)
if(f[k][j-a[i]]!=f[0][0])
f[i][j]=max(f[i][j],f[k][j-a[i]]+b[i]+w[k][i]);
int ans=-(1<<30);
for(int i=1;i<=n;i++)
ans=max(ans,f[i][m+GG]);
if(ans==-(1<<30)) puts("-1");
else printf("%d\n",ans);
return 0;
}
```
### 11.16 魔法题
[P4914 難題「龍の頸の玉 -五色の弾丸-」](https://www.luogu.com.cn/problem/P4914)
以后都搬东方题算了
先画个图
感性理解发现 $k$ 为偶数肯定会被打到
以辉夜所在的点为原点，建立平面直角坐标系，$k$ 为奇数则轨迹经过$x$轴时碰到的点必定是无理点，辉夜在有理点。
所以 $k$ 为奇数就不会被打到，偶数就会。~~擦弹，就硬擦弹~~
以上是魔法做法。但是可以过。（？？？
甚至卡cin（恼
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
int T;
scanf("%d",&T);
while(T--){
double a;int k;
scanf("%lf%lf%lf%lf%d",&a,&a,&a,&a,&k);
puts(k&1?"yes":"no");
}
return 0;
}
```
科学做法。发现$v,t$没用
然后通过初中计算几何知识就可以求出AOB和BOC的角度（上面两个顶点形成的角对称不考虑），与$\frac{360}{k}$比较就可以算出来
所以是个初中计算几何题~
### 11.17 [P5131 荷取融合](https://www.luogu.com.cn/problem/P5131)
看起来就像期望DP
但是状态很不好设计，看了题解把状态改为两个，答案变为所有方案的贡献和/方案总数。
感觉应该是很好用常见的$\texttt{tirck}$...?
方案总数很好求，设$f_{i,j}$表示前$i$个选$j$个的方案数，考虑选与不选，$f_{i,j}=f_{i-1,j}+f_{i,j-1}$，好像很类似组合数，但其实差了点。
贡献和设$g_{i,j}$表示前$i$个选$j$个贡献和。
$g_{i,j}=g_{i-1,j}+g_{i,j-1}\times a_i$
时空复杂度均为$O(nk)$，但是空间会爆，滚掉变成$O(k)$就好了
有个题解说要用线性求逆元，实际上上只需要求一次逆元。
~~我劝这位年轻人耗子尾汁，题解区要互帮互助，不要搞窝里斗，谢谢朋友们！~~
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=100010;
int n,K;
int a[maxn];
int f[2][maxn],g[2][maxn];
const int mod=19260817;
inline int fpw(int a,int b){
int res=1;
while(b){
if(b&1) (res*=a)%=mod;
(a*=a)%=mod;b>>=1;
}
return res;
}
signed main(){
scanf("%lld%lld",&n,&K);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
f[0][0]=1;
for(int i=1;i<=n;i++){
int k=i&1;
f[k][0]=g[k][0]=1;
for(int j=1;j<=K;j++){
f[k][j]=(f[!k][j]+f[k][j-1])%mod;
g[k][j]=(g[!k][j]+g[k][j-1]*a[i])%mod;
}
}
printf("%lld\n",g[n&1][K]*fpw(f[n&1][K],mod-2)%mod);
return 0;
}
```
### 11.17 加餐题
[P3801 红色的幻想乡](https://www.luogu.com.cn/problem/P3801)
全 是 东 方
每次取反一列或者一行
先不考虑交叉的血色红雾，搞两棵线段树，每次取反打一下标记
询问的时候要减去交叉，这个时候容斥减掉就行了
简单数据结构题
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100010;
#define ls (rt<<1)
#define rs (rt<<1|1)
int n,m,q;
struct SEGT{
ll tr[maxn<<2];
void pushup(int rt){
tr[rt]=tr[ls]+tr[rs];
}
void modify(int rt,int l,int r,int pos){
//cerr<<"modify:"<<rt<<' '<<l<<' '<<r<<endl;
if(l==r){
tr[rt]^=1;
return ;
}
int mid=(l+r)>>1;
if(pos<=mid) modify(ls,l,mid,pos);
if(pos>mid) modify(rs,mid+1,r,pos);
pushup(rt);
}
ll que(int rt,int l,int r,int ql,int qr){
if(l>=ql&&r<=qr) return tr[rt];
int mid=(l+r)>>1;
if(qr<=mid) return que(ls,l,mid,ql,qr);
else if(ql>mid) return que(rs,mid+1,r,ql,qr);
else return que(ls,l,mid,ql,qr)+que(rs,mid+1,r,ql,qr);
}
}T1,T2;
int main(){
scanf("%d%d%d",&n,&m,&q);
while(q--){
int opt;
scanf("%d",&opt);
if(opt==1){
int x,y;
scanf("%d%d",&x,&y);
T1.modify(1,1,n,x);
T2.modify(1,1,n,y);
}
else {
int X1,X2,Y1,Y2;
scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
ll res1=T1.que(1,1,n,X1,X2);
ll res2=T2.que(1,1,n,Y1,Y2);
// cerr<<"query result "<<res1<<' '<<res2<<endl;
printf("%lld\n",res1*(Y2-Y1+1-res2)+res2*(X2-X1+1-res1));
}
}
return 0;
}
```
### [P5129 不可思议的迷宫](https://www.luogu.com.cn/problem/P5129)
不会做，下一个
### 11.18 [P3797 妖梦斩木棒](https://www.luogu.com.cn/problem/P3797)
数据结构，好啊！
发现 $\texttt{X}$ 没有用，先不考虑
然后很容易设计出线段树需要维护的信息，左边有没有左括号，右边有没有右括号和是不是全为X
合并亦不难
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=200010;
#define ls (rt<<1)
#define rs (rt<<1|1)
struct node{
bool L,R,T;//左开，右开，全为X
int val;
node(){}
node(bool l,bool r,bool t){
L=l,R=r,T=t;val=0;
}
}tr[maxn<<2];
int n,m;
inline node merge(node a,node b){
node res;
res.T=a.T&b.T;
res.L=a.T?b.L:a.L;
res.R=b.T?a.R:b.R;
res.val=a.val+b.val;
if(a.R&&b.L&&!a.T&&!b.T) res.val++;
return res;
}
inline void pushup(int rt){tr[rt]=merge(tr[ls],tr[rs]);}
inline void build(int rt,int l,int r){
if(l==r){
if(l==1) tr[rt]=node(0,1,0);
else if(l==n) tr[rt]=node(1,0,0);
else tr[rt]=node(1,1,1);
return ;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(rt);
}
inline void modify(int rt,int l,int r,int pos,int val){
if(l==r){
if(val==0) tr[rt]=node(1,0,0);
else if(val==1) tr[rt]=node(0,1,0);
else tr[rt]=node(1,1,1);
return ;
}
int mid=(l+r)>>1;
if(pos<=mid) modify(ls,l,mid,pos,val);
if(pos>mid) modify(rs,mid+1,r,pos,val);
pushup(rt);
}
inline node que(int rt,int l,int r,int ql,int qr){
if(ql<=l&&qr>=r) return tr[rt];
int mid=(l+r)>>1;
if(qr<mid+1) return que(ls,l,mid,ql,qr);
if(ql>mid) return que(rs,mid+1,r,ql,qr);
return merge(que(ls,l,mid,ql,qr),que(rs,mid+1,r,ql,qr));
}
int main(){
scanf("%d%d",&n,&m);
build(1,1,n);
while(m--){
int opt;scanf("%d",&opt);
if(opt==1){
int x,t;char c;
scanf("%d %c",&x,&c);
if(c=='X') t=2;
else if(c=='(') t=1;
else t=0;
modify(1,1,n,x,t);
}
else {
int l,r;scanf("%d%d",&l,&r);
printf("%d\n",que(1,1,n,l,r).val);
}
}
return 0;
}
```
### 11.19[P5515 [MtOI2019]灵梦的计算器](https://www.luogu.com.cn/problem/P5515)
> ▇▇▇：真就全是东方了呗
我不会数学题。
官方题解用了微分科技，但是我不会。
但是因为$a,b$非常大（指对于指数来说），所以函数的增长速度非常大，大到在$x$变化范围很小（只有1）的时候可以视为一条斜率很大的直线
因为只显示整数部分，只需要统计每次询问有多少答案就行了
每次询问的答案即为高度除以斜率
```cpp
#include<bits/stdc++.h>
namespace Mker{
// Powered By Kawashiro_Nitori
// Made In Gensokyo, Nihon
#define uint unsigned int
uint sd;int op;
inline void init() {scanf("%u %d", &sd, &op);}
inline uint uint_rand()
{
sd ^= sd << 13;
sd ^= sd >> 7;
sd ^= sd << 11;
return sd;
}
inline double get_n()
{
double x = (double) (uint_rand() % 100000) / 100000;
return x + 4;
}
inline double get_k()
{
double x = (double) (uint_rand() % 100000) / 100000;
return (x + 1) * 5;
}
inline void read(double &n,double &a, double &b)
{
n = get_n(); a = get_k();
if (op) b = a;
else b = get_k();
}
}
using namespace Mker;
int T;
double n,a,b;
int main(){
scanf("%d",&T);
init();
double ans=0;
while(T--){
read(n,a,b);
double k=a*pow(n,a-1)+b*pow(n,b-1);
ans+=1.0/k;
}
printf("%.5lf\n",ans);
return 0;
}
```
### 11.19 中学找规律题 [P4275 萃香的请柬](https://www.luogu.com.cn/problem/P4275)
先考虑单个字符的情况
不会，我选择打表
```
S
SL
SLS
SLSSL
SLSSLSLS
SLSSLSLSSLSSL
```
这里发现每一个序列=前两个拼起来，在这上面做文章就行啦。
（怎么证明？可以轻易数学归纳法证明。也可以由前三个状态归纳出后面所有状态。）
所以大萃香的个数也是前两个加起来
然后考虑询问的区间前面的部分，如果大于斐波那契数列的某一项就可以全部一起减掉
其他部分依次考虑，看情况加上斐波那契数列的那一项即可。
多个字符，因为会经过无限长的时间，所以实际只和第一个字符有关，第一个如果是 $\texttt{L}$ 马上就会变成 $\texttt{B}$，只需要一个时间单位。所以也无影响
所以这个第一个字符串是无效输入= =
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int f[114];
signed main(){
char s[3];scanf("%s",s);
f[0]=f[1]=1;for(int i=2;i<=90;i++) f[i]=f[i-1]+f[i-2];
int m;scanf("%lld",&m);
while(m--){
int a,b,ans=0;
scanf("%lld%lld",&a,&b);a--;
for(int i=90;i>=0;i--){
if(a>=f[i]&&b>=f[i])
a-=f[i],b-=f[i];
else if(a>=f[i])
a-=f[i],ans-=f[i-1];
else if(b>=f[i])
b-=f[i],ans+=f[i-1];
}
printf("%lld\n",ans);
}
return 0;
}
```
### 11.20 [CF441C Valera and Tubes](https://www.luogu.com.cn/problem/CF441C)
确实是很简单的题，但是我细节处理不好WA了几次
这里是蛇形构造法，把连续的绕在一起就行了
练习码力和细节罢了。。
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int main(){
scanf("%d%d%d",&n,&m,&k);
int block=n*m/k;
int now=0;
int cnt=0;
bool flag=0;
for(int i=1;i<=n;i++){
if(i%2){
for(int j=1;j<=m;j++){
if(now==k-1&&!flag) {printf("%d ",n*m-(i-1)*m-j+1);flag=1;}
if(now==k-1) {printf("%d %d ",i,j);continue;}
cnt++;
if(cnt==1) printf("%d ",min(block,1+n*m-((i-1)*m+j)));
printf("%d %d ",i,j);
if(cnt==block) {
cnt=0;
puts("");
now++;
}
}
}
else {
for(int j=m;j>=1;j--){
if(now==k-1&&!flag) {printf("%d ",n*m-(i-1)*m-(m-j));flag=1;}
if(now==k-1) {printf("%d %d ",i,j);continue;}
cnt++;
if(cnt==1) printf("%d ",block);
printf("%d %d ",i,j);
if(cnt==block) {
cnt=0;
puts("");
now++;
}
}
}
}
return 0;
}
```
### 11.21 [CF767E](https://www.luogu.com.cn/problem/CF767E)
一个叫做带悔贪心的东西
听上去很毒瘤（可持久化¿）但是其实是个简单的 $\texttt{trick}$ 。
直接贪心，如果能用 $\texttt{1}$ 元支付就支付。如果不能，就向前则找用 $\texttt{1}$ 元支付的一天，换成用 $\texttt{100}$ 元支付。
这样你会获得 $\texttt{100}$ 金币。（这是一个巧妙的性质，你获得了那个收银员的找零和自己交上去的那一部分）
然后这里我们可以贪心地选择之前支付会导致不满意度最小的一天，因为无论选择哪一天都是获得100金币（当然如果这一天不满意度最小就选今天）。这个用堆维护就行力...
这样我们就将一个不能贪心的问题变成了可以贪心的问题 确实很神奇
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000010;
int n,m,val[maxn],a[maxn],b[maxn],w[maxn];
bool vis[maxn];
struct node{
int w,id;
bool operator <(const node &rhs)const {
return w>rhs.w;
}
};
priority_queue<node> q;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&val[i]);
a[i]=val[i]/100,b[i]=val[i]%100;
if(!b[i]) vis[i]=1;
}
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
long long ans=0;
for(int i=1;i<=n;i++){
if(m>=b[i]){
if(b[i]) q.push((node){(100-b[i])*w[i],i});
}
else {
if(!q.empty()&&q.top().w<=(100-b[i])*w[i]){
ans+=q.top().w;q.pop();
q.push((node){(100-b[i])*w[i],i});
}
else {ans+=(100-b[i])*w[i];};
m+=100;
}
m-=b[i];
}
printf("%lld\n",ans);
while(!q.empty()) {
vis[q.top().id]=1;
q.pop();
}
for(int i=1;i<=n;i++){
if(vis[i]) printf("%d %d\n",a[i],b[i]);
else printf("%d 0\n",a[i]+1);
}
return 0;
}
```
PS. 这篇博客4k行了，编辑器已经卡死了————
### 11.22 待补
### 11.23 [P1858 多人背包
](https://www.luogu.com.cn/problem/P1858)
01背包前$k$优解。
因为$k$很小，所以复杂度应该是$O(nmk)$
令$f_{i,j}$表示体积为$i$的第$k$优解（滚掉一维了），很容易发现当$i$确定，$j$递增时$f_{i,j}$递减。
那么我们由上一个$f_{i,k}$从大到小考虑，得出来的结果肯定也是从大到小的。
我们要考虑上一个 $f_{i-1,k}$ 和 $f_{i-w_i,k}$ 考虑，由$k$从大到小考虑，拿出前$k$个即可，后面的不会被选到。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=5010;
int k,v,n,ans=0;
int c[maxn],w[maxn];
int f[maxn][maxn];
int main(){
memset(f,128,sizeof f);
scanf("%d%d%d",&k,&v,&n);
for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&c[i]);
f[0][1]=0;
for(int i=1;i<=n;i++){
for(int j=v;j>=w[i];j--){
int t1=0,t2=0,t[55],len=0;
while(t1+t2<=k){
if(f[j][t1+1]>f[j-w[i]][t2+1]+c[i])
t[++len]=f[j][++t1];
else t[++len]=f[j-w[i]][++t2]+c[i];
}
for(int x=1;x<=k;x++) f[j][x]=t[x];
}
}
for(int i=1;i<=k;i++) ans+=f[v][i];
printf("%d",ans);
}
```
### 11.23 发散思维 [CF1338D Nested Rubber Bands](https://www.luogu.com.cn/problem/CF1338D)
看起来很不好想的题
但是我们发现两个点如果相连则必然不能嵌套
而且如果不相连则不能有交（包含或分离）
想到这里可能会以为是最大独立集，但是又不像。
仔细思考可以想出反例，如下图
```cpp
7
1 2
2 3
3 4
4 5
3 6
6 7
```
![]()（草 我的csacademy加载不出来，图片请在颅内脑补）
这里$1,5,7$三个点显然无法互相嵌套，这组数据答案为3而不是4。
参考下图（以下图片全部用画图粗制滥造）
红圈儿表示 $3$ 号点，这里显示了 $1 2 3 4 5 $ 号点，可以发现 $67$ 号点无论怎么放也没法嵌套进去。
（因为 $2 4$ 号点已经将再画一圈的路【截断】了）
推广这个情况，可以得出一个更加普遍的结论。且发现答案即为**树上任意一条链及其相邻的点的最大独立集**
设$f_{i,0/1}$为第 $i$ 个点选不选的答案，树形dp即可
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=200010;
struct node{
int to,nxt;
}tr[maxn];int head[maxn],tot=0;
int f[maxn][2];
int in[maxn];
int n;
inline void addedge(int x,int y){
tr[++tot].to=y;
tr[tot].nxt=head[x];
head[x]=tot;
}
int ans=1;
void dfs(int u,int fa){
f[u][0]=0,f[u][1]=1;
for(int i=head[u];i;i=tr[i].nxt){
int to=tr[i].to;
if(to==fa) continue;
dfs(to,u);
ans=max(ans,f[u][0]+f[to][1]);
ans=max(ans,f[u][0]+f[to][0]);
ans=max(ans,f[u][1]+f[to][0]);
f[u][0]=max(f[u][0],f[to][1]+in[u]-2);
f[u][0]=max(f[u][0],f[to][0]+in[u]-2);
f[u][1]=max(f[u][1],f[to][0]+1);
}
ans=max(ans,f[u][1]);
}
int main(){
scanf("%d",&n);
for(int i=1,x,y;i<n;i++){
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
in[x]++,in[y]++;
}
dfs(1,0);
printf("%d\n",ans);
return 0;
}
```
### 11.24 [P6672 [清华集训2016] 你的生命已如风中残烛](https://www.luogu.com.cn/problem/P6672)
早就想造这题了！！！
大概是某个乱斗的idea...
把每个卡的值减一，变成问多少个排列的所有前缀和都大于等于0。
学一个叫做圆排列的东西，表示把一些东西排成一个圆的方案数。
很自然想到，我们抓出来一个合法序列，把某个前缀和大于0的位置（尽量选最后的）放到这个排列最后面，则又对应一个合法的排列了。
问题是这样做每个合法排列可能会被算多次。
这里有个做法（据 说 是 套 路）就是在序列最后面先放个 $ -1$，这个时候就额外要求前缀和最后等于 $-1$ 。但是把那个位置放到后面后，对应的序列依然合法，且这个最后的 $-1$ 变成了另外一个合法序列中间的 $-1$ ，也就是说一个合法序列会被多算 $m+1-n$ 次。
答案为$\frac{n!}{m-n+1}$。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
signed main(){
int n;scanf("%lld",&n);int m=0;
for(int i=1;i<=n;i++){
int x;scanf("%lld",&x);
m+=x;
}
int ans=1;
for(int i=1;i<=m;i++){
if(i==m-n+1) continue;
(ans*=i)%=mod;
}
return printf("%lld\n",ans),0;
}
```
好难 写完代码又忘了怎么推的了
### 11.25 [P7096 [yLOI2020] 泸沽寻梦](https://www.luogu.com.cn/problem/P7096)
手速训练。
区间异或和为0，做法要是不用取前缀和，那这个出题人就违背了友善的社会主义核心价值观
所以我们先取前缀和，变成询问有多少对相同的数
考虑每次修改只影响到一个前缀和，直接修改就得了，用个map维护每个数出现的次数就可以很方便地统计答案
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=200010;
int n,m;
int ans=0;
int a[maxn],s[maxn];
unordered_map<int,int> mp;
int isodd=0,maxx=0,minn=(1ll<<60);
int sum=0;
signed main(){
ans=0;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=n;i++) s[i]=s[i-1]^a[i];
mp[0]++;
for(int i=1;i<=n;i++){
ans+=mp[s[i]];
mp[s[i]]++;
}
// cerr<<ans<<endl;
while(m--){
int p,x;scanf("%lld%lld",&p,&x);
ans-=(--mp[s[p]]);
s[p]^=x;
ans+=(mp[s[p]]++);
if(ans&1) isodd++;
maxx=max(ans,maxx);
minn=min(ans,minn);
sum^=ans;
//cerr<<ans<<endl;
}
printf("%lld\n%lld\n%lld\n%lld\n",sum,isodd,maxx,minn);
return 0;
}
```
### 11.26 [P2324 [SCOI2005]骑士精神](https://www.luogu.com.cn/problem/P2324)
并不知道为什么能过
我的估价函数估的值是正常人的$\frac{5}{3}$
但是我也不知道其他地方哪里慢了导致我得把估价函数写的这么假才能过
```cpp
#include<bits/stdc++.h>
using namespace std;
char a[6][6];
const int goal[7][7]={
{0,0,0,0,0,0},
{0,'1','1','1','1','1'},
{0,'0','1','1','1','1'},
{0,'0','0','*','1','1'},
{0,'0','0','0','0','1'},
{0,'0','0','0','0','0'}
};
inline int guess(){
int cnt=0;
for(int i=1;i<=5;i++)
for(int j=1;j<=5;j++)
if(a[i][j]!=goal[i][j])cnt++;
return cnt+cnt*2/3;
}
inline bool check(){
if(a[1][1]==a[1][2]&&a[1][2]==a[1][3])
if(a[1][3]==a[1][4]&&a[1][4]==a[1][5])
if(a[1][5]==a[2][2]&&a[2][2]==a[2][3]&&a[2][3]==a[2][4])
if(a[2][4]==a[2][5]&&a[2][5]==a[3][4])
if(a[3][4]==a[3][5]&&a[3][5]==a[4][5])
if(a[1][1]=='1')
if(a[5][5]==a[5][4]&&a[5][4]==a[5][3])
if(a[5][3]==a[5][2]&&a[5][1]==a[5][2])
if(a[5][1]==a[4][1]&&a[4][1]==a[4][2]&&a[4][2]==a[4][3])
if(a[4][3]==a[4][4]&&a[4][4]==a[3][1])
if(a[3][1]==a[3][2]&&a[3][2]==a[2][1])
if(a[5][5]=='0')
if(a[3][3]=='*') return 1;
return 0;
}
inline bool in(int i,int j){
return i>=1&&i<=5&&j>=1&&j<=5;
}
int tim=0;
int maxdep=0;
bool dfs(int dep){
if(guess()/2+maxdep-dep>maxdep) return 0;
if(dep==0){
if(check()) return 1;
else return 0;
}
bool res=0;
int xi,xj;
for(int i=1;i<=5;i++)for(int j=1;j<=5;j++)
if(a[i][j]=='*') xi=i,xj=j;
int i=xi,j=xj;
if(in(i-2,j-1)){
swap(a[i-2][j-1],a[i][j]);
if(dfs(dep-1)) res=1;
swap(a[i-2][j-1],a[i][j]);
}
if(in(i-1,j-2)){
swap(a[i-1][j-2],a[i][j]);
if(dfs(dep-1)) res=1;
swap(a[i-1][j-2],a[i][j]);
}
if(in(i+1,j-2)){
swap(a[i+1][j-2],a[i][j]);
if(dfs(dep-1)) res=1;
swap(a[i+1][j-2],a[i][j]);
}
if(in(i+2,j-1)){
swap(a[i+2][j-1],a[i][j]);
if(dfs(dep-1)) res=1;
swap(a[i+2][j-1],a[i][j]);
}
if(in(i+1,j+2)){
swap(a[i+1][j+2],a[i][j]);
if(dfs(dep-1)) res=1;
swap(a[i+1][j+2],a[i][j]);
}
if(in(i+2,j+1)){
swap(a[i+2][j+1],a[i][j]);
if(dfs(dep-1)) res=1;
swap(a[i+2][j+1],a[i][j]);
}
if(in(i-1,j+2)){
swap(a[i-1][j+2],a[i][j]);
if(dfs(dep-1)) res=1;
swap(a[i-1][j+2],a[i][j]);
}
if(in(i-2,j+1)){
swap(a[i-2][j+1],a[i][j]);
if(dfs(dep-1)) res=1;
swap(a[i-2][j+1],a[i][j]);
}
return res;
}
int main(){
int T;scanf("%d",&T);
while(T--){
for(int i=1;i<=5;i++)
scanf("%s",a[i]+1);
for(int dep=0;dep<=15;dep++){
maxdep=dep;
if(dfs(dep)){
printf("%d\n",dep);
goto a;
}
}
puts("-1");
a:;
}
}
```
### 11.27 搞我心态 [P6584 重拳出击](https://www.luogu.com.cn/problem/P6584)
首先我猜正解猜过头了
认为起始节点所有子树中关键点dep最深的两个才对答案有影响。
交上去顺利通过了第一个subtask
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=4e5+10;
struct node{
int to,nxt;
}tr[maxn<<1];int tot=0,head[maxn];
int dep[maxn];
int n,m,K,X;
bool yy[maxn];
inline void addedge(int u,int v){
tr[++tot].to=v;
tr[tot].nxt=head[u];
head[u]=tot;
}
int res=0;
void dfs(int u,int fa){
dep[u]=dep[fa]+1;
if(yy[u])res=max(res,dep[u]);
for(int i=head[u];i;i=tr[i].nxt){
int to=tr[i].to;
if(to==fa) continue;
dfs(to,u);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++) {
int x,y;scanf("%d%d",&x,&y);
addedge(x,y);addedge(y,x);
}
scanf("%d",&m);
for(int i=1;i<=m;i++){
int x;scanf("%d",&x);
yy[x]=1;
}
scanf("%d%d",&K,&X);
int mx1=0,mx2=0;
dep[X]=0;
for(int i=head[X];i;i=tr[i].nxt){
int to=tr[i].to;
res=0;dfs(to,X);
if(res>mx1){
mx2=mx1;
mx1=res;
}
else if(res>mx2)
mx2=res;
}
//cerr<<mx1<<' '<<mx2<<"<-\n";
int ans=0;
while(1){
ans++;
if(mx1<=K&&mx2<=K) {break;}
if(mx1<mx2) swap(mx1,mx2);
if(mx1>mx2) mx1-=2;
else if(mx1==mx2) mx1-=1,mx2-=1;
}
printf("%d\n",ans);
return 0;
}
```
好，然后对拍查错。$n=100$才有幸有了第一个错误数据点
我把他画进csacademy里
草——我要死了
然后试图把它理顺
把关键点以外的无用点扔掉才知道错在哪。。。
最后还是屈服写了换根DP
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=400010;
struct node{
int to,nxt;
}tr[maxn<<1];int head[maxn],tot;
inline void addedge(int u,int v){
tr[++tot].nxt=head[u];
tr[tot].to=v;
head[u]=tot;
}
int ans=(1<<30);
int n,m,k,rt;
bool vis[maxn];
int f[maxn][2],g[maxn];
int dep[maxn];
void dfs1(int u,int fa){
dep[u]=dep[fa]+1;
if(vis[u]) f[u][0]=g[u]=0;
for(int i=head[u];i;i=tr[i].nxt){
int to=tr[i].to;
if(to==fa) continue;
dfs1(to,u);
if(f[to][0]+1>f[u][0]){
f[u][1]=f[u][0];
f[u][0]=f[to][0]+1;
}
else if(f[to][0]+1>f[u][1]) f[u][1]=f[to][0]+1;
}
}
void dfs2(int u,int fa){
for(int i=head[u];i;i=tr[i].nxt){
int to=tr[i].to;
if(to==fa) continue;
g[to]=max(g[to],g[u]+1);
if(f[to][0]+1==f[u][0])
g[to]=max(g[to],f[u][1]+1);
else g[to]=max(g[to],f[u][0]+1);
dfs2(to,u);
}
g[u]=max(g[u],f[u][0]);
}
int main(){
scanf("%d",&n);
memset(f,-0x3f,sizeof f);
memset(g,-0x3f,sizeof g);
for(int i=1;i<n;i++){
int x,y;scanf("%d%d",&x,&y);
addedge(x,y);addedge(y,x);
}
scanf("%d",&m);
for(int i=1;i<=m;i++){
int x;scanf("%d",&x);
vis[x]=1;
}
scanf("%d%d",&k,&rt);
dep[0]=-1;
dfs1(rt,0);dfs2(rt,0);
for(int i=1;i<=n;i++)ans=min(ans,dep[i]+1+max(g[i]-dep[i]-k,0));
printf("%d\n",max(0,ans));
return 0;
}
```
### 11.28/11.29 洛谷月赛 能写几道写几道
第一题 [P7106 双生独白](https://www.luogu.com.cn/problem/P7106)
把那个字符串在十六进制下取反就行了
取反就是 $15-x$ 。
```cpp
#include<bits/stdc++.h>
using namespace std;
char s[10];
int main(){
scanf("%s",s+1);
int len=strlen(s+1);
for(int i=2;i<=len;i++){
if(s[i]=='0') s[i]='F';
else if(s[i]=='1') s[i]='E';
else if(s[i]=='2') s[i]='D';
else if(s[i]=='3') s[i]='C';
else if(s[i]=='4') s[i]='B';
else if(s[i]=='5') s[i]='A';
else if(s[i]=='6') s[i]='9';
else if(s[i]=='7') s[i]='8';
else if(s[i]=='8') s[i]='7';
else if(s[i]=='9') s[i]='6';
else if(s[i]=='A') s[i]='5';
else if(s[i]=='B') s[i]='4';
else if(s[i]=='C') s[i]='3';
else if(s[i]=='D') s[i]='2';
else if(s[i]=='E') s[i]='1';
else if(s[i]=='F') s[i]='0';
}
printf("%s",s+1);
return 0;
}
```
第二题 构造题[P7107 天选之人](https://www.luogu.com.cn/problem/P7107)
不带记号的=m-带记号，所以考虑带记号的即可。
其中$k$张写了记号，我们尽可能把$k$张分给$p$个人，让每个人尽量多且一样，另外几张($<p$)张为了不让有个人分太多，每个人优先分$mx-1$张。
然后判断能不能合法就行了。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,k,p;
signed main(){
scanf("%lld%lld%lld%lld",&n,&m,&k,&p);
int mx=min(k/p,m);
int mn=k-mx*p;
if((mx-1)*(n-p)>=mn){
puts("Yes");
for(int i=1;i<=p;i++) printf("%lld %lld\n",mx,m-mx);
for(int i=p+1;i<=n;i++){
if(mn>mx-1) {
mn-=mx-1;
printf("%lld %lld\n",mx-1,m-(mx-1));
}
else{
printf("%lld %lld\n",mn,m-mn);
mn=0;
}
}
}
else puts("No");
return 0;
}
```
写了半天 我是傻逼
第三题 数学题 [P7108 移花接木](https://www.luogu.com.cn/problem/P7108)
很讨厌写数学题谢谢。
感觉要分$a>b,a<b,a=b$来考虑
先搞个最简单的$a=b$，直接吧下面所有几乎无限长的子树扔掉即可
就是叶子节点数，答案为$ab^h$
当$a<b$时，我们要把下面好长的东西补上来，再断掉多余的
然而叶子一开始就需要砍掉，所以可以把砍掉的叶子往上接所以就当成接木操作处理
每一次接都会产生新的叶子，最后还是要砍掉$ab^h$个叶子
发现叶子肯定比上面的多，所以答案还是$ab^h$。
所以猜测$a>b$的时候答案也是$ab^h$
看样例发现不是，但是拿了15分
当$a>b$时
反正发现砍叶子的$ab^n$次操作一定存在，不如考虑还需要操作哪里（样例算出来比正解少）
把叶子砍了之后，非叶子节点还有$a-b$叉需要砍掉
那么有多少个$a-b$？
$\sum_{i=0}^{h-1}b^i$个
这是个等比数列，拿出祖传的求和公式，$\frac{b^h-1}{b-1}$
然后答案就是$ab^h+(a-b)\frac{b^h-1}{b-1}$
好小啊
$\huge{ab^h+(a-b)\frac{b^h-1}{b-1}}$
不用求和公式70分，对初中选手不友好差评
好像要求个逆元，写前面两个就写过快速幂了
```cpp
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
inline long long fpw(long long a,long long b){
long long res=1;
while(b){
if(b&1) (res*=a)%=mod;
(a*=a)%=mod;
b>>=1;
}
return res;
}
int main(){
int T;scanf("%d",&T);
while(T--){
long long a,b,h;scanf("%lld%lld%lld",&a,&b,&h);
if(a<=b)printf("%lld\n",(a*fpw(b,h))%mod);
else {
printf("%lld\n",((a*fpw(b,h))%mod +( (a-b)*((fpw(b,h)-1)*(fpw(b-1,mod-2))%mod))%mod)%mod);
}
}
}
```
草 没有判0没有逆元30分
```cpp
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
inline long long fpw(long long a,long long b){
long long res=1;
while(b){
if(b&1) (res*=a)%=mod;
(a*=a)%=mod;
b>>=1;
}
return res;
}
int main(){
int T;scanf("%d",&T);
while(T--){
long long a,b,h;scanf("%lld%lld%lld",&a,&b,&h);
if(a<=b)printf("%lld\n",(a*fpw(b,h))%mod);
else {
if(b==1){
printf("%lld\n",(a+(a-1)*h)%mod);
continue;
}
printf("%lld\n",((a*fpw(b,h))%mod +( (a-b)*((fpw(b,h)-1)*(fpw(b-1,mod-2))%mod))%mod)%mod);
}
}
}
```
第四题 交互题[P7109 滴水不漏](https://www.luogu.com.cn/problem/P7109)
没写过交互题。
这就是为什么炸评测机吗 交互和spj（
先考虑第一次操作，肯定不能将两杯未知的倒在一起，因为这样会丢失信息
我们除非在做水的搬运工，也没必要将两杯已知数量的水倒在一起。
常见情况下，将一杯已知倒进未知，也并不会使未知的减少（多了一杯空的或者满的）
那么特殊情况是啥 刚好倒满算一种，但是如果我们一杯已知一杯未知，知道能刚好倒满就是两杯已知，所以这个矛盾
还有一种是其中一杯是1，因为1要么1要么0
那第一次操作大概是询问一杯是不是满的。
发现一个奇妙的性质是$a_i\leq i$。
那么这时候询问第一杯就能知道第一杯是1还是0.
那现在知道第1杯，可以先询问第二杯是不是满的，如果是第二杯就是2。如果不是且第一杯空就把第二杯往第一杯倒，否则就把第一杯往第二杯倒。就可以确定第二杯是多少。
现在知道第1 2杯，考虑第三杯，也可以利用前两杯确定。
这样做会不会达到$O(\Sigma_{i=1}^{n}i)$？
考虑第4杯，似乎只需要用第1和第2杯确定？
这样的结论不太靠谱，考虑第16杯可不可以用空的1 2 4 8 确定？
先倒8 如果满了跑去倒4，如果没满就把8倒回来去倒4
以此类推。
似乎是可以的，那大概口胡完了，等个人教我写交互.jpg
第五题 [P7110 晚秋绝诗](https://www.luogu.com.cn/problem/P7110)
数据结构题。
旗子就是告诉你左右两个山峰和中间形成一个等差数列，他们的高度差相等
旗子给的信息是可以传递的，比如第1个和第n个已知，2到$n-1$插旗，那么也能全部知道。
再比如，2,3,4,5,6插旗，我们只需要知道$[1,7]$中的任意两个，也能知道$[1,7]$中的所有。
到此为止 等我写的时候再继续更（
### 12.1 CF1111 Edu div.2 ABC
和$\texttt{henryy}$一起开的Virtual Contest
一点也不是edu难度啊
A题不说
B题henryy贪心假了，但是其实不用贪心，枚举删掉几个人就可以知道此时最优答案
取max即可
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=100010;
int n,k,m;
int a[maxn];
signed main(){
scanf("%lld%lld%lld",&n,&k,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
sort(a+1,a+1+n);
double sum=0,ans=0;
for(int i=n-1;i>=0;i--){
sum+=a[i+1];
if(i<=m) ans=max(ans,(sum+min(m-i,(n-i)*k))/(n-i));
}
printf("%.9lf",ans);
return 0;
}
```
C题分治
每个区间答案为直接删这个区间的的代价和分成两个儿子的代价的min
看起来不好做但是其实挺简单啊..
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=100010;
int a[maxn];
int n,k,A,B;
inline int DP(int l,int r){
int L=upper_bound(a+1,a+1+k,l-1)-a;L--;
int R=upper_bound(a+1,a+1+k,r)-a;R--;
int cnt=R-L;
if(!cnt) return A;
if(l==r) return B*cnt;
int mid=(l+r)>>1;
return min(cnt*B*(r-l+1),DP(l,mid)+DP(mid+1,r));
}
signed main(){
scanf("%lld%lld%lld%lld",&n,&k,&A,&B);
for(int i=1;i<=k;i++) scanf("%lld",&a[i]);
sort(a+1,a+1+k);
printf("%lld\n",DP(1,1ll<<n));
return 0;
}
```
### 12.2 CF512 div.1 ABD
C网络流不会所以不写
A [CF510C Fox And Names](https://www.luogu.com.cn/problem/CF510C)
考虑到确定了字典序相当于确定字符间的顺序，其他字符可以随便排
很容易联想到拓扑排序
需要连边的连边，然后拓扑排序即可
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=114;
char c[maxn][maxn];
int n;
int ans[maxn],tot;
int vis[maxn];
struct node{
int to,nxt;
}G[maxn];int head[maxn],tl=0;
inline void addedge(int u,int v){
G[++tl].nxt=head[u];
G[tl].to=v;
head[u]=tl;
}
int dfs(int u){
if(vis[u]) return vis[u]>1;
vis[u]=1;
for(int i=head[u];i!=-1;i=G[i].nxt){
int to=G[i].to;
if(!dfs(to)) return 0;
}
ans[++tot]=u;
vis[u]=2;
return 1;
}
int main(){
scanf("%d",&n);
memset(head,-1,sizeof head);
for(int i=1;i<=n;i++)
scanf("%s",c[i]+1);
for(int i=1;i<n;i++){
int j=1,len1=strlen(c[i]+1),len2=strlen(c[i+1]+1);
while(j<=min(len1,len2)&&c[i][j]==c[i+1][j])j++;
if(j==len2+1) return puts("Impossible"),0;
if(j<=len1) addedge(c[i][j]-'a',c[i+1][j]-'a');
}
for(int i=0;i<26;i++) if(!dfs(i)) return puts("Impossible"),0;
int T=27;
while((T--)-1)putchar(ans[T]+'a');
return 0;
}
```
B [CF510D Fox And Jumping](https://www.luogu.com.cn/problem/CF510D)
很容易想到DP，但是$l_i$太大塞不下。。。
> 设$cp_i$ 表示最大公约数为$i$时的代价，裴蜀定理即可
于是把DP数组扔进map里，遍历的时候改为迭代器即可
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=310;
int n;;
int l[maxn],c[maxn];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&l[i]);
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
map<int,int> cp;cp[0]=0;
for(int i=1;i<=n;i++){
for(map<int,int> :: iterator it=cp.begin();it!=cp.end();it++){
int d=__gcd((*it).first,l[i]);
cp[d]=min(cp[d]?cp[d]:(1<<30),(*it).second+c[i]);
}
}
return printf("%d\n",cp[1]?cp[1]:-1),0;
}
```
草 代码真短
D [CF512D Fox And Travelling](https://www.luogu.com.cn/problem/CF512D)
算是比较难的思维题
而且很思维，几乎没有算法和数据结构（
总之很有趣的一个题..
初看上去很不可做（这场的C题看上去也很不可做，但是！！居然用二分图完成了一个奇妙的转化！！有兴趣可以去看一下~）
但是很快发现在环中的点一定不会被遍历，于是我们先把环给烧了
正在推柿子...
要卷积 打扰了打扰了
换做一道E题
[CF512E Fox And Polygon](https://www.luogu.com.cn/problem/CF512E)
构造题 好耶！
因为直接做比较难（很启发的启发式搜索？），然后限制比较宽松
起始状态$S$,终结状态$T$，我们可以考虑找到一个状态$F$，然后找$S->F$和$T->F$。
$F$取什么比较简单？
可以考虑到所有边都连向1。
那就可以做了，连向1很方便但是代码比较复杂
看到了题解写的挺好的奇技淫巧...
> 枚举每个点，在这个点的左右两边分别找到一个与11点相连的点。根据分法（划分为数个三角形）可知，这两个点必然相连。然后删去这两点间的这条对角线并存储步骤即可。
来自 `Walker_V` 的题解..
虽然不会证明步骤在 $2w$ 以内，但是可以过
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
int n;
bool G1[maxn][maxn],G2[maxn][maxn];
struct node{
int u,v;
}op1[20010],op2[20010];
int cnt1=0,cnt2=0;
int main(){
scanf("%d",&n);
for(int u,v,i=1;i<=n-3;i++){
scanf("%d%d",&u,&v);
G1[u][v]=G1[v][u]=1;
}
for(int u,v,i=1;i<=n-3;i++){
scanf("%d%d",&u,&v);
G2[u][v]=G2[v][u]=1;
}
for(int i=1;i<n;i++)G1[i][i+1]=G1[i+1][i]=G2[i][i+1]=G2[i+1][i]=1;
G1[n][1]=G1[1][n]=G2[1][n]=G2[n][1]=1;
for(int i=2;i<=n;i++){
while(!G1[1][i]){
int su=i-1,sv,eu=0,ev;
for(int j=i+1;j<=n;j++)
if(G1[1][j]) {
sv=j;
break;
}
for(int j=1;j<=n;j++)
if(G1[su][j]&&G1[sv][j]){
if(!eu) eu=j;
else {
ev=j;
break;
}
}
op1[++cnt1]=(node){su,sv};
G1[su][sv]=G1[sv][su]=0;
G1[eu][ev]=G1[ev][eu]=1;
}
}
for(int i=2;i<=n;i++){
while(!G2[1][i]){
int su=i-1,sv,eu=0,ev;
for(int j=i+1;j<=n;j++)
if(G2[1][j]) {
sv=j;
break;
}
for(int j=1;j<=n;j++)
if(G2[su][j]&&G2[sv][j]){
if(!eu) eu=j;
else {
ev=j;
break;
}
}
op2[++cnt2]=(node){eu,ev};
G2[su][sv]=G2[sv][su]=0;
G2[eu][ev]=G2[ev][eu]=1;
}
}
printf("%d\n",cnt1+cnt2);
for(int i=1;i<=cnt1;i++) printf("%d %d\n",op1[i].u,op1[i].v);
for(int i=cnt2;i;i--) printf("%d %d\n",op2[i].u,op2[i].v);
return 0;
}
```
↑刚好代码5k行，编辑器已经几乎 动不了了——
### 并不知道什么时候写 [P2783](https://www.luogu.com.cn/problem/P2783)
想起了很久很久以前完全看不懂这道题的日子（包括背景题意）
如今我学上了有机，搓上了炉石（）
真的 很有一番感慨啊
虽然不知道这题什么时候写，但我退役前会去写的。
时光啊
---
> Ragnaros，赐予我力量！
今天是12.3 刚好复习Tarjan就来写了..
大板子，tarjan一下然后树上差分LCA就行了
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=10010;
const int maxm=50010;
int n,m;
struct Tree{
int head[maxn],tot,fa[maxn][15],dep[maxn],vis[maxn];
struct edge{int to,nxt;}e[maxm<<1];
void addedge(int u,int v){e[++tot].to=v,e[tot].nxt=head[u],head[u]=tot;}
void dfs(int x,int fat){
dep[x]=dep[fat]+1,fa[x][0]=fat;
for(int i=1;i<=14;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=head[x];i;i=e[i].nxt)if(e[i].to^fat)dfs(e[i].to,x);
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=14;i!=-1;i--)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
if(x==y)return x;
for(int i=14;i!=-1;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int getdis(int x,int y){return dep[x]+dep[y]-2*dep[lca(x,y)]+1;}
}T;
struct Graph{
int head[maxn],tot,dfn[maxn],low[maxn];
int tim,bel[maxn],stk[maxn];
int top,col;
struct {int to,nxt;}e[maxm<<1];
void addedge(int u,int v){e[++tot].to=v,e[tot].nxt=head[u],head[u]=tot;}
void tarjan(int u,int fa){
dfn[u]=low[u]=++tim,stk[++top]=u;
for(int i=head[u];i;i=e[i].nxt){
int to=e[i].to;if(to==fa) continue;
if(!dfn[to]) tarjan(to,u),low[u]=min(low[u],low[to]);
else low[u]=min(low[u],dfn[to]);//没写这句MLE了几次
}
if(dfn[u]==low[u]){
++col;while(stk[top]^u) bel[stk[top--]]=col;
bel[stk[top--]]=col;
}
}
void sub(){
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);
for(int u=1;u<=n;u++)for(int i=head[u];i;i=e[i].nxt)if(bel[e[i].to]^bel[u])T.addedge(bel[e[i].to],bel[u]);
T.dfs(1,0);
}
}G;
void Print(int x){
char c[34];int cnt=0;
while(x){
if(x&1) c[++cnt]='1';
else c[++cnt]='0';
x>>=1;
}
if(!cnt) putchar('0');
else for(int i=cnt;i;i--) putchar(c[i]);
puts("");
}
int main(){
scanf("%d%d",&n,&m);
G.col=G.top=0;
for(int u,v,i=1;i<=m;i++){scanf("%d%d",&u,&v);G.addedge(u,v);G.addedge(v,u);}
G.sub();
int q;scanf("%d",&q);
for(int i=1;i<=q;i++){
int x,y;scanf("%d%d",&x,&y);
Print(T.getdis(G.bel[x],G.bel[y]));
}
return 0;
}
```