Codeforces Round #738

赛时：4/6

A

注意到有这么一句话：any number of times.

我们又知道 & 运算总是不增的，所以就把所有数做 & 运算，答案一定是最优的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000,INF=1e9;
int t,n,a[N],b[N],ans;
inline ll read(){
	ll s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
	return s*w;
}
int main(){
	t=read();
	while(t--){
		n=read();ans=INF;
		for(int i=1;i<=n;++i){
			a[i]=read();
			if(i==1)ans=a[1];
			else ans&=a[i];
		}
		printf("%d\n",ans);
	}
	return 0;
}

B

只要找到一个不是问号的字符就开始交替着填，直到又找到一个，重复以上操作即可。

再注意下有可能有很多前导问号，就从第一个不是问号的位置向前交替着填。

再再注意下如果全部都是问号直接特判就行

问什么这样填就行？？

比如这样：R???B 或者 R????R ,如果按上面哪种方式填要重复一个，但倒过来想，这样怎么填都是会至少重复一个，所以这样直接搞就行。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int t,n;
char a[N];
inline ll read(){
	ll s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
	return s*w;
}
int main(){
	t=read();
	while(t--){
		n=read();
		scanf("%s",a+1);
		for(int i=1;i<=n;++i){
			if(a[i]=='R'){
				int sig=1;
				for(int j=i+1;j<=n;++j){
					if(a[j]!='?')break;
					if(sig==1)a[j]='B';
					else a[j]='R';
					sig^=1;
				}
			}
			if(a[i]=='B'){
				int sig=1,id=i;
				for(int j=i+1;j<=n;++j){
					if(a[j]!='?')break;
					if(sig==1)a[j]='R';
					else a[j]='B';
					sig^=1;id=j;
				}
				i=id;
			}
		}
		for(int i=1;i<=n;++i){
			if(a[i]=='R'){
				int sig=1;
				for(int j=i-1;j>=1;--j){
					if(sig==1)a[j]='B';
					else a[j]='R';
					sig^=1;
				}
				break;
			}
			if(a[i]=='B'){
				int sig=1;
				for(int j=i-1;j>=1;--j){
					if(sig==1)a[j]='R';
					else a[j]='B';
					sig^=1;
				}
				break;
			}
		}
		int sigg=1;
		for(int i=1;i<=n;++i){
			if(a[i]=='?'){
				if(sigg==1)a[i]='B';
				else a[i]='R';
				sigg^=1;
			}
		}
		cout<<a+1<<endl;
	}
	return 0;
}

C

如果没有第 n+1 个点的话，题目已经告诉我们路径了，就是从 1 到 n 走就行，所以我们只要想怎么把 n+1 加进去就行了。

1.放到 1 前面；

2.放到 n 后面；

3.中间挑一个位置插进去，爽啊。

这已经包含了全部情况了，因为，看题目输入：

1.条件是 \(\small a_1=1\) ；

2.条件是 \(\small a_n=0\) ；

3.条件是存在 \(\small i\in [2,n]\) 使得 \(\small a_{i-1}<a_i\) 。

然后我们发现前两种情况撇掉后，已经构造不出数组 a 不满足第三种情况，所以这题就很愉快的抬走力！

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+10;
int t,n,a[N];
inline ll read(){
	ll s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
	return s*w;
}
int main(){
	t=read();
	while(t--){
		n=read();
		for(int i=1;i<=n;++i){
			a[i]=read();
		}
		if(a[n]==0){
			for(int i=1;i<=n+1;++i)printf("%d ",i);
			printf("\n");
			continue;
		}
		if(a[1]==1){
			printf("%d ",n+1);
			for(int i=1;i<=n;++i)printf("%d ",i);
			printf("\n");
			continue;
		}
		int id=0;
		for(int i=2;i<=n;++i){
			if(a[i]>a[i-1]){
				id=i;break;
			}
		}
		if(id!=0){
			for(int i=1;i<id;++i)printf("%d ",i);
			printf("%d ",n+1);
			for(int i=id;i<=n;++i)printf("%d ",i);
			printf("\n");
			continue;
		}
	}
	return 0;
}

D

easy version

两个图造好后 \(\small n^2\) 暴力枚举，只要两个点在两个图里面都不在一个大块里面就连边。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+10;
int n,m1,m2,fa1[N],fa2[N],siz1[N],siz2[N],ans;
struct mdzz{
	int x,y;
}l[N];
inline ll read(){
	ll s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
	return s*w;
}
inline int find1(int x){
	if(fa1[x]==x)return fa1[x];
	return fa1[x]=find1(fa1[x]);
}
inline int find2(int x){
	if(fa2[x]==x)return fa2[x];
	return fa2[x]=find2(fa2[x]);
}
int main(){
	n=read();m1=read();m2=read();
	for(int i=1;i<=n;++i){
		fa1[i]=fa2[i]=i;
		siz1[i]=siz2[i]=1;
	}
	for(int i=1;i<=m1;++i){
		int u=read(),v=read();
		int x=find1(u),y=find1(v);
		fa1[x]=y;
	}
	for(int i=1;i<=m2;++i){
		int u=read(),v=read();
		int x=find2(u),y=find2(v);
		fa2[x]=y;
	}
	if(n-1==m1||n-1==m2){
		printf("0");
		return 0;
	}
	for(int i=1;i<=n;++i){
		for(int j=i+1;j<=n;++j){
			int u1=find1(i),v1=find1(j);
			int u2=find2(i),v2=find2(j);
			if(u1!=v1&&u2!=v2){
				fa1[u1]=v1;fa2[u2]=v2;
				l[++ans]=(mdzz){i,j};
			}
		}
	}
	printf("%d\n",ans);
	for(int i=1;i<=ans;++i){
		printf("%d %d\n",l[i].x,l[i].y);
	}
	return 0;
}

hard version

发现以任何顺序加入合法边都不会影响答案

所以可以定一个点（就定 1 号点就行），先尽可能的把所有在两个图里面都不与 1 号点联通的点连上

所以任意一点就只会剩下都与 1 号点联通或其中一个图与 1 号点联通的两种可能。

前者显然不用管，后者的话又分两类：

1.与图一中的 1 号点联通；

2.与图二中的 1 号点联通；

显然，所有 1 类点都联通，所有 2 类点都联通

然后只要 1 类点与 2 类点连边就行，直到不存在其中一类点就行完成力！

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m1,m2,fa1[N],fa2[N];
vector<int> ans,a,b;
inline ll read(){
	ll s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
	return s*w;
}
inline int find1(int x){
	if(fa1[x]==x)return fa1[x];
	return fa1[x]=find1(fa1[x]);
}
inline int find2(int x){
	if(fa2[x]==x)return fa2[x];
	return fa2[x]=find2(fa2[x]);
}
int main(){
	n=read();m1=read();m2=read();
	for(int i=1;i<=n;++i){
		fa1[i]=fa2[i]=i;
	}
	for(int i=1;i<=m1;++i){
		int u=read(),v=read();
		int x=find1(u),y=find1(v);
		if(x!=y)fa1[x]=y;
	}
	for(int i=1;i<=m2;++i){
		int u=read(),v=read();
		int x=find2(u),y=find2(v);
		if(x!=y)fa2[x]=y;
	}
	for(int i=1;i<=n;++i){
		int x=find1(1),y=find1(i);
		int u=find2(1),v=find2(i);
		if(x==y||u==v)continue;
		fa1[x]=y;fa2[u]=v;ans.push_back(i);
	}
	for(int i=1;i<=n;++i){
		int x=find1(1),y=find1(i);
		int u=find2(1),v=find2(i);
		if(x!=y){fa1[x]=y;a.push_back(i);}
		if(u!=v){fa2[u]=v;b.push_back(i);}
	}
	printf("%d\n",ans.size()+min(a.size(),b.size()));
	for(int i=0;i<ans.size();++i)printf("1 %d\n",ans[i]);
	for(int i=0;i<min(a.size(),b.size());++i)printf("%d %d\n",a[i],b[i]);
	return 0;
}

E

假如没有 gcd 的限制的话，应该能发现这是一个比较经典的 DP ，可以 \(\small O(nm)\) 做。

然后考虑把限制条件加进来，设上面 DP 的模型 \(\small f(a_1,a_2,...,a_n)\) 表示此数列能否满足。

所以有很显然的求和式子：

\[\sum_{a_1=1}^{r_1}{\sum_{a_2=1}^{r_2}{...\sum_{a_n=1}^{r_n}{f(a_1,a_2,...,a_n)\cdot [\gcd(a_1,a_2,...,a_n)==1]}}} \]

长得比较莫反的样子，所以：

\[\Longrightarrow \sum_{a_1=l_1}^{r_1}{\sum_{a_2=l_2}^{r_2}{...\sum_{a_n=l_n}^{r_n}{f(a_1,a_2,...,a_n)}\cdot \sum_{d|\gcd(a_1,a_2,...,a_n)}{\mu(d)}}} \]

\[\Longrightarrow \sum_{a_1=l_1}^{r_1}{\sum_{a_2=l_2}^{r_2}{...\sum_{a_n=l_n}^{r_n}{f(a_1,a_2,...,a_n)}\cdot \sum_{d|a_1\ \&\&\ d|a_2\ \&\&\ ...\ \&\&\ d|a_n}{\mu(d)}}} \]

\[\Longrightarrow \sum_{d=1}^{m}{\ \mu(d)\ \cdot}\sum_{a_1=\lceil \frac{l_1}{d} \rceil}^{\lfloor \frac{r_1}{d} \rfloor}{\sum_{a_2=\lceil \frac{l_2}{d} \rceil}^{\lfloor \frac{r_2}{d} \rfloor}{...\sum_{a_n=\lceil \frac{l_n}{d} \rceil}^{\lfloor \frac{r_n}{d} \rfloor}{f(a_1,a_2,...,a_n)}}} \]

后面这一坨就又回到了去掉限制时分析的 DP 模型了。

于是我们在 \(\small O(\) \(\large {\frac{nm}{1}}\) \(\small +\) \(\large\frac{nm}{2}\) \(\small +\ ...\ +\) \(\large\frac{nm}{m}\) \(\small )\ \approx O(nm\ln m)\) （调和级数）的时间把这道题搞定力！

（但其实 \(\small \mu(d)==0\) 根本不用算后面，不过丝毫不慌，怎么着也过得了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=108,M=1e5+10;
const ll mod=998244353;
ll n,m,pri[M],cnt,mu[M];
ll f[N][M],sum[M],tmp,ans;
//f_i,j 表示前i个质数和（除了之后）为j的方案数
bool vis[M];
struct mdzz{
	ll l,r,lt,rt;
}p[N];
inline ll read(){
	ll s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
	return s*w;
}
inline void pre_mul(){
	mu[1]=1;
	for(int i=2;i<=m;++i){
		if(!vis[i]){
			pri[++cnt]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=cnt&&i*pri[j]<=m;++j){
			vis[i*pri[j]]=1;
			if(i%pri[j]==0){
				mu[i*pri[j]]=0;
				break;
			}
			mu[i*pri[j]]=-mu[i];
		}		
	}
}
int main(){
	n=read();m=read();
	pre_mul();
	for(int i=1;i<=n;++i){
		p[i].l=read();p[i].r=read();
	}
	for(int d=1;d<=m/n;++d){
		for(int i=1;i<=n;++i){
			p[i].lt=p[i].l/d+(p[i].l%d!=0);
			p[i].rt=p[i].r/d;
		}
		for(int i=1;i<=m/d;++i)f[1][i]=0;
		for(int i=p[1].lt;i<=p[1].rt;++i)f[1][i]=1;
		for(int i=2;i<=n;++i){
			for(int j=1;j<=m/d;++j)sum[j]=(sum[j-1]+f[i-1][j])%mod;
			for(int j=p[i].lt;j<=m/d;++j){
				f[i][j]=(sum[j-p[i].lt]+mod-sum[j-min(1ll*j,p[i].rt+1)])%mod;
			}
		}
		tmp=0;
		for(int i=1;i<=m/d;++i)tmp=(tmp+f[n][i])%mod;
		ans=(ans+tmp*mu[d]+mod)%mod;
	}
	printf("%lld\n",ans);
	return 0;
}

Codeforces Round #739

赛时：3/7（wtcl）

A

暴力（+ 预处理）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+10;
int t,k,a[N],cnt;
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
	return s*w;
}
int main(){
	for(int i=1;i<=3000;++i){
		if(i%3&&i%10!=3)a[++cnt]=i;
		if(cnt==1000)break;
	}
	t=read();
	while(t--){
		k=read();
		printf("%d\n",a[k]);
	}
	return 0;
}

B

找到周期，然后对面的数字是（自己 + 周期的一半）%周期。

然后注意一下，周期一半的对面不是 0 ，特判一下。

最后算一算给的数据存不存在就行了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,a,b,c,num;
inline ll read(){
	ll s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
	return s*w;
}
int main(){
	t=read();
	while(t--){
		a=read();b=read();c=read();
		num=(abs(b-a))<<1ll;
		if(num<b||num<a||num<c){
			printf("-1\n");
			continue;
		}
		else {
			if(c==(num>>1))printf("%d\n",num);
			else printf("%d\n",(c+(num>>1))%num);
		}
	}
	return 0;
}

C

这样绕下去的话，每一次绕完，数字就到了圈数的平方。

所以可以先算绕的是哪一圈，然后判断是在圈的列上还是在行上就行了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,k,id;
inline ll read(){
	ll s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
	return s*w;
}
int main(){
	t=read();
	while(t--){
		k=read();
		for(ll i=0;;++i){
			if(i*i<k&&k<=(i+1ll)*(i+1ll)){
				id=i;break;
			}
		}
		if(id<k-id*id){
			printf("%d ",id+1);
			printf("%d\n",(id+1)*(id+1)-k+1);
		}
		else {
			printf("%d ",k-id*id);
			printf("%d\n",id+1);
		}
	}
	return 0;
}

D

因为数据最大是 9 位（ \(\small 10^9\) 另算），假设现在最优解是去数去到 1 位，那么如果只需要补数的话至多会补到 9+(9-1)=17 位

所以产生答案的 2 的 k 次幂中， k 最大也只会达到 59 （ 60~62 都可以哟，ull可以再加上 63 但都没什么用）。

k 不大，最长 19 位，完全可以暴力枚举，又因为题目的要求，只会用到 \(\small 2^k\) 的前缀，所以只要算出原串和 \(\small 2^k\) 的最长公共子序列，

然后按照题目要求，答案就是原串长度 - 最长公共子序列长度 +\(\small 2^k\) 的长度 - 最长公共子序列长度。

因为原串长度 - 最长公共子序列长度就是指原串里面要去掉的部分。

而 \(\small 2^k\) 的长度 - 最长公共子序列长度就是指原串中缺少的部分。

加起来就是答案啦。

最后只要对所有 2 的 k 次幂算一遍答案，取个 min 就完成力！

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=1e9;
int t,ans;
inline ll read(){
	ll s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
	return s*w;
}
inline void mian(){
    std::string s;
    std::cin >> s;
    for(int i=0;i<=60;i++){
        std::string t=std::to_string(1ll<<i);
        int k=0;
        for(int j=0;j<s.size();j++){
            if(k<t.size()&&s[j]==t[k])++k;
        }
        ans=std::min(ans,int(s.size())+int(t.size())-k-k);
    }
}
 
int main(){
    t=read();
    while(t--){
        ans=INF;
		mian();
		printf("%d\n",ans);
    }
    return 0;
}

E

好像乍一看，直接硬上是不行的，看看哪里有突破口。

看了半天，发现好像输出里面后面那个小串能直接算，只要从后往前扫。

最先出现的就是最后删除的，

其次出现的就是倒数第二个删除的，然后以此类推。

（不能顺着找，谁知道原串是怎么排列的呀）

因为每次删完这个字符，之后接到后面的串就不存在这个字符了，所以可以这样直接求出。

（所以不能顺着找呀）

感觉可以先求有解的情况下原串应该的长度，并且能够算出原串每个字符要有多少个。

因为只要不删掉这个字符，每次复制一遍的话，数量就会加倍，正好已经求出了小串：

对于第一个删掉的字符，数量只被复制了一遍，

对于第二个删掉的字符，数量被复制了两遍，之后又是以此类推。

又因为，被删掉后不会再出现，所以只要预处理 26 个字符各出现了几次，就能算了（连哪个位置都不需要）

最后模拟一遍构造方式，验证一下就行。

因为题目给的字符串有可能是乱写的，导致计算原串长度的时候因为除不尽或者位置不对，反而算完长度之后不会检查出来，所以再检查一遍。

（不验证的话其实可以去掉大部分无解的串，但不能做到滴水不漏，比如样例 abacabaaacaac ，如果改成 abcaabaaacaac，即使预处理算 26 种字符的个数时加上了位置，也很难检查出来，所以还是得检查一遍至少比较方便。。）

于是我们在甚至不知道复杂度的情况下把这题过力！

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t,n,m,cnt[28];
string s;
inline void clear(){
	memset(cnt,0,sizeof(cnt));
}
inline void mian(){
	clear();
	string ans,tot;
	cin>>s;n=s.size();
	for(int i=n-1;~i;--i){
		if(!cnt[s[i]-'a'+1])tot+=s[i];
		++cnt[s[i]-'a'+1];
	}
	m=tot.size();n=0;
	reverse(tot.begin(),tot.end());
	for(int i=0;i<m;++i){
		n+=(cnt[tot[i]-'a'+1])/(i+1);
		//这一位应该在原串中出现几次
	}
	if(n>s.size()){
		printf("-1\n");
		return ;
	}
	ans=s.substr(0,n);
	string chk,add=ans;
	for(int i=0;i<m;++i){
		chk+=add;
		string now;
		for(int j=0;j<n;++j){
			if(add[j]!=tot[i])now+=add[j];
		}
		add=now;n=add.size();
	}
	if(chk!=s){
		printf("-1\n");
	}
	else cout<<ans<<" "<<tot<<"\n";
}
int main(){
	scanf("%d",&t);
	for(int i=1;i<=t;++i)mian();
	return 0;
}

F

easy version

看到题目 \(k\leq 2\) ，着实小的可怜，可以用一堆 if 乱搞？？（没试过）

hard version

（注：下文“试填”表示用从当前这一位的数字 +1 到 9 去更换这一位，看是否合法）

可以想到应该尽可能不动高位，所以可以由高到低从第一个不合法的位置开始试填，然后分两种情况：

1.发现这一位试填完了都不能使其合法，往高一位继续试填；

2.发现这一位能够试填到使其合法，往低一位继续试填。

直到最低一位都合法的时候，这个数字就合法了。

于是我们又在不知道复杂度的情况下把这题过力！

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t,n,k;
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
	return s*w;
}
inline int digcnt(int x){
	int tmp=0,it;
	while(x){
		it=x%10;
		tmp|=(1<<it);
		x/=10;
	}
	return __builtin_popcount(tmp);
}
inline void mian(){
	n=read();k=read();
	while(digcnt(n)>k){
		int l=1,r=n;
		while(digcnt(r)>k){
			l*=10;r/=10;
		}
		l/=10;
		n=((n/l)+1)*l;
	}
	printf("%d\n",n);
}
int main(){
	t=read();
	for(int i=1;i<=t;++i)mian();
	return 0;
}

Codeforces Round #742

赛时：2/6（wtcl）

A

因为 L 和 R 不影响上下，所以只要让 D 和 U 互换就可以了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t, n;
char a[108];
inline int read() {
	int s = 0, w = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = (s << 3) + (s << 1) + ch - '0'; ch = getchar();}
	return s * w;
}
int main() {
	t = read();
	while (t--) {
		n = read();
		scanf("%s", a);
		for (int i = 0; i < n; ++i) {
			if (a[i] == 'D')cout<<'U';
			else if (a[i] == 'U')cout<<'D';
			else cout<<a[i];
		}
		cout<<endl;
	}
	return 0;
}

B

因为有一个 MEX ，所以长度至少 MEX 。

接下来分四种情况：

1. 这 MEX 个数的 XOR 刚好满足，长度就是 MEX 。

2. MEX 个数异或后还需要异或一个大于 MEX 的数，长度是 MEX + 1 。

3. MEX 个数异或后还需要异或一个等于 MEX 的数，长度就是 MEX + 2 ，因为 MEX 不能选进去，就需要通过两个数“凑”出 MEX 。

4. MEX 个数异或后还需要异或一个小于 MEX 的数，长度是 MEX + 1 。

搞定力!

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 10;
int t, n, m, ans, tmp, a[N];
inline int read() {
	int s = 0, w = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = (s << 3) + (s << 1) + ch - '0'; ch = getchar();}
	return s * w;
}
int main() {
	for(int i = 1; i <= 3e5; ++i)a[i] = a[i-1] ^ i;
	t = read();
	while (t--) {
		n = read(); m = read(); ans = 0; tmp = 0;
		ans = n;
		tmp = a[n-1];
		if (tmp == m) {
			printf("%d\n", ans);
			continue;
		}
		if ((tmp ^ m) == n) ans += 2;
		else ++ans;
		printf("%d\n", ans);
	}
	return 0;
}

C

这是一个关于进位的问题。

按照原来的法则，只向前进一位的话，整个操作会看起来很臃肿。比如： 44444 + 55556

但是，这道题非常好心的更改了法则，于是，

偶数位只会进位到偶数位，奇数位只会进位到偶数位，所以方案数就分成两个部分：

1. 偶数位的贡献

2. 奇数位的贡献

所以把偶数位和奇数位分离出来成两个数，根据很基本的加法和乘法原理，答案就是这分离出来的两个数相乘。

等会，还没完

哦，答案还要减一，因为是正整数。。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t, n, a, b, it, dig, sig;
inline ll read() {
	ll s = 0, w = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = (s << 3) + (s << 1) + ch - '0'; ch = getchar();}
	return s * w;
}
inline void mian() {
	n = read(); it = dig = 10;
	sig = a = b = 0;
	while (n) {
		if (!sig) a = a + n % it * 10ll / dig;
		else b = b + n % it / dig;
		n -= n % it; it *= 10ll; sig ^= 1;
		if (!sig) dig *= 10ll;
	}
	printf("%lld\n", a * b + a + b - 1);
}
int main() {
	t = read();
	while (t--) mian();
	return 0;
}

D

无非就是两个个进制之间的一个卡上限的数字游戏（大雾）

想想如果要最大，要怎么分

我们知道：

\(11_{(11)} = 1\cdot 11^1 + 1\cdot 11^0 = 12_{(10)}\)

好家伙那岂不是全部数拆成类似 &10^n& 不就在尽可能在变大吗。

于是你这么干，发现样例里面有一个不太对劲的东西。。

111 分成 4 份，这样分肯定分不完呀。。

于是去学了学 CF 上码量最小的提交，大概就是：

让高位的 \(10^n\) 尽可能地保留，然后类似 10 分成 3 份的就拆成 3 3 4 ，让上面那个反例变得合法并且保留尽可能多的贡献。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int ksm[10], t, n, s, num;
inline ll read() {
	ll s = 0, w = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = (s << 3) + (s << 1) + ch - '0'; ch = getchar();}
	return s * w;
}
inline void mian() {
	s = read(); n = read();
	for (int i = n - 1; i >= 1; -- i) {
		num = ksm[(int)log10(s - i)];
		printf("%d ", num); s -= num;
	}
	printf("%d\n", s);
}
int main() {
	ksm[0] = 1;
	for (int i = 1; i <= 9; ++ i) {
		ksm[i] = ksm[i - 1] * 10;
	}
	t = read();
	while (t--) mian();
	return 0;
}

E

一眼数据结构题，但是好像并没有什么能直接维护区间不下降子串数量的。

那先用直白明了的线段树作为参考，想一想怎么做，

想来想去可能就只有合并会不一样，其他的都是基本操作。（因为只有单点修改。。）

如何合并

不下降字串，对与要合并的两个区间，分为三种情况：

1. 只在左区间降的

2. 只在右区间降的

3. 横跨在两个区间降的

显然，前面两种答案不会互相影响，是可以直接相加的，

那么对于第三种的话：

两个区间答案的合并

先来想答案是由什么构成的。

应该是等于（左区间从右端点向左能不上升的最远距离）*（右区间从左端点向右能不下降的最远距离）

同时注意到有可能左区间和最右边的数可能大于右区间最左边的数，这样明显就不存在横跨两个区间的字串了。

所以每个区间只要维护这上面提到的四个信息就可以了就可以了。

信息传递的话后两者很明显，对其与前两者的话，肯定至少为左区间向右和右区间向左的距离。

那么如果还可以继续扩大的话，就在记录一下整个区间是否就是一个不下降串就能判断了。

至此，就基本完成了这道题了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int n, q, a[N];
struct mdzz {
	ll val, l, r, L, R;
	bool sig;
};
inline ll read() {
	ll s = 0, w = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = (s << 3) + (s << 1) + ch - '0'; ch = getchar();}
	return s * w;
}
struct SegmentTree {
	mdzz tr[N << 2];
	#define val(i) tr[i].val
	#define l(i) tr[i].l
	#define r(i) tr[i].r
	#define L(i) tr[i].L
	#define R(i) tr[i].R
	#define sig(i) tr[i].sig
	inline mdzz merge(mdzz x, mdzz y) {
		mdzz res;
		res.val = x.val + y.val;
		res.L = x.L; res.l = x.l;
		res.R = y.R; res.r = y.r;
		if (x.R <= y.L) {
			res.val += x.r * y.l;
			if (x.sig)res.l += y.l;
			if (y.sig)res.r += x.r;
			res.sig = x.sig & y.sig;
		}
		else res.sig = 0;
		return res;
	}
	inline void build(int now, int lt, int rt) {
		if (lt == rt) {
			tr[now] = (mdzz){1, 1, 1, a[lt], a[lt], 1};
			return ;
		}
		int mid = (lt + rt) >> 1;
		build(now << 1, lt, mid);
		build(now << 1 | 1, mid + 1, rt);
		tr[now] = merge(tr[now << 1], tr[now << 1 | 1]);
	}
	inline void modify(int now, int lt, int rt, int it, ll k) {
		if (lt == rt) {
			tr[now] = (mdzz){1, 1, 1, k, k, 1};
			return ;
		}
		int mid = (lt + rt) >> 1;
		if (it <= mid) modify(now << 1, lt, mid, it, k);
		else modify(now << 1 | 1, mid + 1, rt, it, k);
		tr[now] = merge(tr[now << 1], tr[now << 1 | 1]);
	}
	inline mdzz query(int now, int lt, int rt, int ls, int rs) {
		if (ls <= lt && rt <= rs) return tr[now];
		int mid = (lt + rt) >> 1;
		if (rs <= mid) return query(now << 1, lt, mid, ls, rs);
		if (ls > mid) return query(now << 1 | 1, mid + 1, rt, ls, rs);
		mdzz res = query(now << 1, lt, mid, ls, rs);
		mdzz ret = query(now << 1 | 1, mid + 1, rt, ls, rs);
		return merge(res, ret);
	}
}seg;
inline void mian() {
	int opt = read(), x = read(), y = read();
	if (opt == 1) seg.modify(1, 1, n, x, y);
	else printf("%lld\n", seg.query(1, 1, n, x, y).val);
}
int main() {
	n = read(); q = read();
	for (int i = 1; i <= n; ++ i) a[i] = read();
	seg.build(1, 1, n);
	while (q --) mian();
	return 0;
}

F

先看什么情况下无解。

对于一个被标记的点，如果周围的未被标记的点个数为奇数的话，必定无解。

那么剩下就有0个，2个，4个的可能。

0个的时候，就填0，2个的话两个点要么1，要么4，二分图染色就行了。

对于4个的情况，不能直接二分图了，也不能随便连边，万一有可能就把可能的答案连没了呢。。

那么怎么去二分图连边呢？？

再来想什么情况下无解，自然是二分图出现了奇环。

Educational Codeforces Round 114

赛时：3/6（wtcl）

A

显然构造。

先把起始字符串构造成：()()()... 这样的

然后从第二个和倒数第二个开始向里每次把“(”变为“)”，“)”变为“(”。

因为是从第二个开始的，所以前面先少个“)”，而多出来个“(”，所以能让第三个的“)”匹配的上，之后的类似。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3+10;
int t, n;
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
inline void mian() {
	n = read();
	string s;
	for (int i = 1; i <= n * 2; ++i) {
		if (i & 1) s += '(';
		else s += ')';
	}
	cout << s << endl;
	for (int i = 1; i < n; ++i) {
		if (s[i] == '(') {
			s[i] = ')'; s[n * 2 - i - 1] = '(';
		}
		else {
			s[i] = '('; s[n * 2 - i - 1] = ')';
		}
		cout << s << endl;
	}
}
int main(){
	t = read();
	while (t--) mian();
	return 0;
}

B

找上下边界。

下边界然容易找，最大答案就是这样：AA..BB..CC..的答案。

相对的，我们就应该去找答案最小的时候，

我们把三个数字看成三条边，如果能够成三角形，两条较小边可以嵌入最大边里面，由于两较小边互不影响，所以可以。

找这个方法，如果两较小边嵌入最大边过后，最大边剩下的点相邻的个数就是最小值了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3+10;
int t, a[3], n;
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
inline void mian() {
	a[0] = read(); a[1] = read(); a[2] = read(); n = read();
	sort(a, a + 3);
	if (a[0] + a[1] + a[2] - 3 >= n && n >= a[2] - a[1] - a[0] - 1) printf("YES\n");
	else printf("NO\n");
}
int main(){
	t = read();
	while (t--) mian();
	return 0;
}

C

无思维难度题。

跟着题目走，二分找第一个比龙牛的骑士和第一个比龙菜的骑士，算一下答案就可以了。

考虑正确性：显然呀。因为第一个比龙牛的骑士不需要金币，第二个比龙牛的骑士一样，但城堡里的需要的金币不一定一样。

所以第二个比龙牛的骑士比第一个比龙牛的骑士不会更优。第一个比龙菜的骑士同理。

（说了一堆废话。。）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll n, a[N], b[N], num, m, x, y;
ll pos1, pos2, ans1, ans2;
inline ll read(){
	ll s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
inline void mian() {
	x = read(); y = read();
	pos1 = lower_bound(a, a + n, x) - a;
	pos2 = lower_bound(b, b + n, x, greater<ll>()) - b;
	if (pos1 == n) pos1--;
	if (pos2 == n) pos2--;
	ans1 = max(y - (num - a[pos1]), 0ll) + max(x - a[pos1], 0ll);
	ans2 = max(y - (num - b[pos2]), 0ll) + max(x - b[pos2], 0ll);
	printf("%lld\n", min(ans1, ans2));
}
inline bool cmp(ll a, ll b) {
	return a > b;
}
int main(){
	n = read();
	for (int i = 0; i < n; ++i) {
		a[i] = read(); b[i] = a[i]; num += a[i];
	}
	sort(a, a + n);
	sort(b, b + n, cmp);
	m = read();
	while (m--) mian();
	return 0;
}

D

遇事不行，map一定嘚行。。

（其实我用的set。。）

其实思想上很暴力，就是把ban掉的放在一起，自己从每行最末尾的地方开始搜，

如果是ban掉的就加n个新方案，分别是原基础上在每一行往前一个。

由于要最大值，所以全部丢到set里面。

复杂度的话因为一共就\(10^5\)个ban掉的方案，所以时间不会爆炸。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int n, c[12], a[12][N], m, b[N];
set<vector<int> > q, it;
inline int read() {
	int s = 0, w = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = (s << 3) + (s << 1) + ch - '0'; ch = getchar();}
	return s * w;
}
int main() {
	n = read();
	vector<int> d(n + 1), f(n + 1);
	for (int i = 1; i <= n; ++i) {
		c[i] = read();
		for (int j = 1; j <= c[i]; ++j) {
			a[i][j] = read();
		}
	}
	for (int i = 1; i <= n; ++i) {
		d[i] = c[i]; d[0] += a[i][d[i]];
	}
	q.insert(d);
	m = read();
	while (m--) {
		d[0] = 0;
		for (int i = 1; i <= n; ++i) {
			b[i] = read();
			d[i] = b[i]; d[0] += a[i][d[i]];
		}
		it.insert(d);
	}
	while (233) {
		d = *--q.end();
		q.erase(--q.end());
		if (!it.count(d)) {
			for (int i = 1; i <= n; ++i) {
				printf("%d ", d[i]);
			}
			return 0;
		}
		else {
			for (int i = 1; i <= n; ++i) {
				if (d[i] != 1) {
					f = d; --f[i];
					f[0] += a[i][f[i]] - a[i][f[i] + 1];
					q.insert(f);
				}
			}
		}
	}
	return 0;
}

E（咕）

F（咕）

Codeforces Round #745 div2

赛时：3/6（wtcl）

A

暂且定义一个数列的整齐度为\(\sum_{i = 1}^{n - 1}[p_i < p_{i + 1}]\)

因为显然一个长度为2n的数列最大整齐度为2n - 1。

又显然一个整齐度为x的数列整体反转的话整齐度就是2n - 1 - x。

所以所有整齐度小于n的数列，反转后整齐度不小于n。

欸，这不正好覆盖所有数列且没有交集吗，那答案不就是(2n)! / 2吗！

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
const ll mod = 1e9 + 7;
const ll inv2 = 5e8 + 4;
ll t, n, a[N];
inline ll read() {
	ll s = 0, w = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = (s << 3) + (s << 1) + ch - '0'; ch = getchar();}
	return s * w;
}
inline void mian() {
	n = read() * 2ll;
	printf("%lld\n", (inv2 * a[n]) % mod);
}
int main() {
	a[0] = 1;
	for (ll i = 1; i < N; ++i) {
		a[i] = (a[i - 1] * i) % mod;
	}
	t = read();
	while (t--) mian();
	return 0;
}

B

不得不说出题人是存心想要害死我们。。（边有可能不合法。。）

只考虑边数在\([n - 1,(n - 1) * n / 2]\)时的构造方案。（其他的都无解呀。。）

树的直径最小，就让数看起来越胖与好咯。

很自然的就想到了菊花图，直径直接就来到了2。

那么再有什么改变的话，也只可能是在完全图的时候，任意两点间有边，所以直径为1。

就这两种直径，搞定。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t, n, m, k;
inline ll read() {
	ll s = 0, w = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = (s << 3) + (s << 1) + ch - '0'; ch = getchar();}
	return s * w;
}
inline void mian() {
	n = read(); m = read(); k = read() - 1;
	if (n - 1 == m) {
		if (n >= 3) {
			if (k <= 2) printf("NO\n");
			else printf("YES\n");
		}
		else if (n == 2) {
			if (k <= 1) printf("NO\n");
			else printf("YES\n");
		}
		else {
			if (k <= 0) printf("NO\n");
			else printf("YES\n");
		}
	}
	else if (n - 1 < m) {
		if (n >= 3) {
			ll mor = m - (n - 1);
			ll ned = (n - 1) * (n - 2) / 2;
			if (mor < ned) {
				if (k <= 2) printf("NO\n");
				else printf("YES\n");
			}
			else if (mor == ned) {
				if (k <= 1) printf("NO\n");
				else printf("YES\n");
			}
			else printf("NO\n");
		}
		else if (n == 2) {
			printf("NO\n");
		}
		else printf("NO\n");
	}
	else {
		printf("NO\n");
	}
}
int main() {
	t = read();
	while (t--) mian();
	return 0;
}

C

首先最暴力的就是\(\small O(n^2m^2)\)枚举两个点加\(\small O(nm)\)统计答案，统共\(\small O(n^3m^3)\)。

加个前缀和，\(\small O(n^2m^2)\)。

考虑怎么优化，枚举这些已经不能再优了，但是其实和前缀和思想一样，我们可以在计算许多矩形的时候利用一下前面已有的答案。

但我们还是先定上下边界，然后从左往右计算定好右边界的时候的最小答案。

（我是从右往左，因为1开始有点晕，n开始方便一点，但讲的时候还是从左往右）

然后我们可以先算最左边最小的矩形，然后发现向右扩展的时候有点麻烦，所以我们干脆先撇掉最右边这一列，这样扩展起来就好多了，

这是我们就只需要算两个东西：

1.以右边界为起点的最小矩形答案

2.以右边界为起点的其它矩形最小答案

显然情况2就是前面传下来的答案，直接就可以用，一也可以\(\small O(1)\)算。

最后再全部加上最右边这一列的贡献就可以了。

时间复杂度\(\small O(n^3)\)级。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 410, INF = 1e9;
ll t, n, m, ans, cnt[N];
ll pos[N][N], qzh[N][N];
string s[N];
inline ll read() {
	ll s = 0, w = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = (s << 3) + (s << 1) + ch - '0'; ch = getchar();}
	return s * w;
}
inline ll calc(int x1, int y1, int x2, int y2) {
	ll res = qzh[x2][y2] - qzh[x1 - 1][y2];
	ll ret = qzh[x2][y1 - 1] - qzh[x1 - 1][y1 - 1];
	return res - ret;
}
inline void mian() {
	n = read(); m = read(); ans = INF;
	for (int i = 1; i <= n; ++i) {
		getline(cin, s[i]);
		for (int j = 1; j <= m; ++j) {
			pos[i][j] = s[i][j - 1] - '0';
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			qzh[i][j] = pos[i][j];
			qzh[i][j] += qzh[i - 1][j] + qzh[i][j - 1] - qzh[i - 1][j - 1];
		}
	}
	for (int l = 1; l <= m; ++l) {
		for (int r = l + 3; r <= m; ++r) {
			cnt[n - 3] = r - l - 1 - calc(n, l + 1, n, r - 1) + 6;
			cnt[n - 3] += calc(n - 3, l + 1, n - 1, r - 1);
			cnt[n - 3] -= calc(n - 3, l, n - 1, l) + calc(n - 3, r, n - 1, r);
			for (int i = n - 4; i >= 1; --i) {
				cnt[i] = r - l - 1 - calc(i + 3, l + 1, i + 3, r - 1) + 6;
				cnt[i] += calc(i, l + 1, i + 2, r - 1);
				cnt[i] -= calc(i, l, i + 2, l) + calc(i, r, i + 2, r);
				ll num = (!pos[i][l]) + (!pos[i][r]);
				cnt[i] = min(cnt[i], cnt[i + 1] + calc(i, l + 1, i, r - 1) + num);
			}
			for (int i = 1; i <= n - 4; ++i) {
				ans = min(ans, cnt[i + 1] + r - l - 1 - calc(i, l + 1, i, r - 1));
			}
		}
	}
	printf("%lld\n", ans);
}
int main() {
	t = read();
	while (t--) mian();
	return 0;
}

D（咕）

E

直接做的话，可以发现两种操作的时间比较悬殊。

虽然两者分开来看，时间都已经到了极限，但如果我们把他们合在一起看。

我们就会想到考虑能不能把两者的时间平衡下来，从而达到降低时间复杂度的效果。

这就是分块的思想，我们能接受的小块，可以就按暴力的做法。但是大块就要在修改的时候处理好，而不同一是 \(\small O(N)\) 查询。

又注意到这些工作的机器是有周期性的，一会工作，一会修理，所以我们可以按照周期分两类。

设我们能接受的“小块”，最大周期为 \(\small P\) 。

那么在加入一个车的时候：

如果周期大于 \(\small P\) ，那么整个 \(\small M\) 个时段里面他工作的时段不会超过 \(\small M/P\) ，所以添加，删除的时候修改一个差分数组，标记每个时间段首尾就可以了，时间复杂度 \(\small O(M/P)\) 。

如果周期小于 \(\small P\) ，虽然不可能再向刚刚那样暴力修改了。但是我们可以知道对于一个时刻，我们可以判断它是否在某个机器的工作时段内。所以对于一个机器的周期，只要标记好开始的时间，之后的所有时段，查询时，只要枚举这些周期就能一网打尽。因为规定了周期是小于 \(\small P\) 的，所以时间复杂度 \(\small O(P)\) 。

综上，时间复杂度总和是 \(\small O(M/P + P)\) ，现在平衡两者的时间的能力已经到了我们手上，此时 \(\small P\) 取 \(\small \sqrt{M}\) 时就是最优的，总时间复杂度也就是 \(\small O(M\sqrt{M})\) 。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10, M = 457;
int n, m, sq, c[M][M], pos[N], num[N], ans;
struct mdzz {
	int x, y, sum;
} p[N];
inline int read() {
	int s = 0, w = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = (s << 3) + (s << 1) + ch - '0'; ch = getchar();}
	return s * w;
}
inline void mian(int i) {
	int opt = read(), k =read();
	if (opt == 1) {
		pos[k] = i;
		if (p[k].sum > sq) {
			for (int j = i; ;) {
				j += p[k].x; if (j > m) break;
				++num[j];
				j += p[k].y; if (j > m) break;
				--num[j];
			}
		}
		else {
			--c[p[k].sum][i % p[k].sum];
			++c[p[k].sum][(i + p[k].x) % p[k].sum];
			++ans;
		}
	}
	else {
		int lth = i - pos[k], now = lth % p[k].sum;
		if (now > p[k].x || now == 0) --ans;
		if (p[k].sum > sq) {
			for (int j = pos[k]; ;) {
				j += p[k].x; if (j > m) break;
				--num[j];
				j += p[k].y; if (j > m) break;
				++num[j];
			}
		}
		else {
			++c[p[k].sum][pos[k] % p[k].sum];
			--c[p[k].sum][(pos[k] + p[k].x) % p[k].sum];
		}
	}
	ans += num[i];
	for (int j = 1; j <= sq; ++j) {
		ans += c[j][i % j];
	}
	printf("%d\n", ans);
}
int main() {
	n = read(); m = read(); sq = sqrt(m);
	for (int i = 1; i <= n; ++i) {
		p[i] = (mdzz) {read(), read()};
		p[i].sum = p[i].x + p[i].y;
	}
	for (int i = 1; i <= m; ++i) mian(i);
	return 0;
}

F

式子看着很烦，没什么性质，所以转化一下：

\[\sum_{i = 1}^m (m \cdot a_{b_i}) - \sum_{i = 1}^m \sum_{j = 1}^m \min_{k = \min(b_i, b_j)}^{\max(b_i, b_j)} a_k \]

\[\Longrightarrow \sum_{i = 1}^m ((m - 1) \cdot a_{b_i}) - 2\cdot \sum_{i = 1}^m \sum_{j = i + 1}^m \min_{k = \min(b_i, b_j)}^{\max(b_i, b_j)} a_k \]

可以想到后面那个循环里面，包括 \(i\) 和 \(j\) ， \(1\) 到 \(m\) 均被提到了 \(m - 1\) 次，所以前面那坨可以放进后面了。

\[\Longrightarrow \sum_{i = 1}^m \sum_{j = i + 1}^m a_{b_i} + a_{b_j} - \min_{k = \min(b_i, b_j)}^{\max(b_i, b_j)} 2\cdot a_k \]

为了美观我们假设 \(b_i\) 为升序。（只是为了美观而已。。）

\[\Longrightarrow \sum_{i = 1}^m \sum_{j = i + 1}^m a_{b_i} + a_{b_j} - \min_{k = b_i}^{b_j} 2\cdot a_k \]

后面那托东西，越看越熟悉，这有点像树上两点间的距离呀！

\[dep_i + dep_j - 2\cdot dep_{lca(i, j)} \]

所以可以试着向树发展，现在就要想怎么构造这个树。

\(\min_{k = b_i}^{b_j} 2\cdot a_k\)，这玩意换成文字描述的话，就表示数组上两个点坐标中间的最小值。

意思就是要两个点的 \(lca\) 就是上面那玩意，哦，笛卡尔树！

那么还要求距离是 \(a_{b_i} + a_{b_j} - \min_{k = b_i}^{b_j} 2\cdot a_k\) 的话，边权要怎么设呢？

因为最后总边权只跟 \(lca\) 和那两个点的 \(a_i\) 有关，而中间的点毫无贡献，所以边权多半是个差结构，用来抵消中间点的贡献。

暂且就认为边权为所连接的两点 \(a_i\) 的差，式子化就是 \(w_{u, v} = a_u - a_v\) 。

手摸一下，两点 \(i, j\) 距离就是 \(a_{i} + a_{j} - \min_{k = i}^{j} 2\cdot a_k\) 。

这不就好起来了吗！

可以直接建树了，然后问题转化成一棵树，求任选 \(m\) 个点，使得点两两距离之和最大。

一个比较经典的 DP 模型（？）， \(f_{i, j}\) 表示 \(i\) 子树下选 \(j\) 个点的最大值。

然后从笛卡尔树的树根（就是 \(a_i\) 最小的那个点）开始 dfs ，记住每次对于一条边，转移的时候算一下这条边被经过了几次就行了。

（注：下面还有一点哟。。）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e3 + 10;
int n, m, a[N], sta[N], top, ls[N], rs[N];
int fst[N], tot, rt = 1, siz[N];
ll f[N][N];
struct edge {int nxt, to, val;} e[N];
inline int read() {
	int s = 0, w = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = (s << 3) + (s << 1) + ch - '0'; ch = getchar();}
	return s * w;
}
inline void add(int u, int v, int w) {
	e[++tot] = (edge) {fst[u], v, w};
	fst[u] = tot;
}
inline void Cartesian() {
	sta[top = 1] = 1; 
	for (int i = 2; i <= n; ++i) {
		while (a[sta[top]] > a[i] && top) --top;
		if (!top) ls[i] = sta[top + 1];
		else {
			ls[i] = rs[sta[top]];
			rs[sta[top]] = i;
		}
		sta[++top] = i;
	}
}
inline void dfs(int u) {
	siz[u] = 1;
	for (int i = fst[u]; i; i = e[i].nxt) {
		int v = e[i].to, w = e[i].val;
		dfs(v);
		int s1 = min(m, siz[u]);
		int s2 = min(m, siz[v]);
		for (int j = s1; j >= 0; --j) {
			for (int k = s2; k >= 0; --k) {
				ll anp = f[u][j] + f[v][k];
				ll rep = 1ll * k * (m - k);
				f[u][j + k] = max(f[u][j + k], anp + rep * w);
			}
		}
		siz[u] += siz[v];
	}
}
int main() {
	n = read(); m = read();
	for (int i = 1; i <= n; ++i) a[i] = read();
	Cartesian();
	for (int i = 1; i <= n; ++i) {
		if (ls[i]) add(i, ls[i], a[ls[i]] - a[i]);
		if (rs[i]) add(i, rs[i], a[rs[i]] - a[i]);
		if (a[rt] > a[i]) rt = i;
	}
	dfs(rt);
	printf("%lld\n", f[rt][m]);
	return 0;
}

其实写出来后，直观感觉时间复杂度是 \(O(n \cdot m^ 2)\) 而非 \(O(n ^ 2)\)，并不能过。

但其实我们是边合并一个子树，边计算的。所以就意思是对于一条边，我们本来是枚举的两个点的 \(siz\) 。相当于每次两个集合所有点之间相互建边，然后形成一个更大的集合，再接着枚举下一条边的时候，继续与其他集合合并。

所以宏观上来看，整个过程就是 \(n\) 个点两两连边。所以时间复杂度就是 \(O(n ^ 2)\) ，能过掉此题。