难度估计：绿，紫，紫，紫。

A

注意到，若可以使答案为 $x$ ，则对所有位置都操作一次可以使其变为 $x-1$ ，所以答案具有可二分性，考虑二分。

考虑如何判断答案 $x$ 是否可行。反复从 $1$ 到 $n$ 遍历，每遍历到一个大于 $x$ 的数，就对其操作直到其减到 $x$ 以下。遍历一轮后，每个数大于 $x$ 的部分至少减半，所以至多遍历 $O(\log V)$ 轮。

时间复杂度 $O(n\log n\log V)$ 。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,a[N],b[N];
int sum;
void cl(){
	sum=0;
}
bool ck(int x){
	memcpy(b,a,sizeof(a));
	while(1){
		int fl=0;
		for(int i=1;i<=n;i++){
			int v=((i<n)?(i+1):(1));
			int d=b[i]-x;
			if(d>0){
				int w=(d+1)/2;
				b[i]-=2*w;
				b[v]+=w;
				fl=1;
			}
		}
		if(!fl) break;		
	}
	for(int i=1;i<=n;i++){
		if(b[i]!=x){
			return 0;
		}
	}
	return 1;
}
void sol(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum+=a[i];
	}
	int le=0,ri=sum/n,ans=-1;
	while(le<=ri){
		int mid=(le+ri)/2;
		if(ck(mid)){
			le=mid+1;
			ans=mid;
		}
		else{
			ri=mid-1;
		}
	}
	if(ans==-1){
		cout<<"-1\n";
		return;
	}
	cout<<(sum-ans*n)<<"\n";
}
signed main(){
	freopen("energy.in","r",stdin);
	freopen("energy.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	int ct=1;
	cin>>ct;
	while(ct--){
		sol();
		cl();
	}
}

B

考虑只计算 $a_i\operatorname{and} a_j=a_i$ 的部分（即 $a_i\subseteq a_j$ ，此处的 $\subseteq$ 表示 $a_i$ 的二进制为 $1$ 的位置的集合包含于 $a_j$ 中，后文的 $\subseteq$ 符号同理），另一部分把序列反过来再做一遍，最后减掉相同的部分即可。

考虑使用序列分治。考虑如何计算 $[l,m]$ 到 $[m+1,r]$ 的贡献。将右端点 $j$ 遍历 $[m+1,r]$ ，并用双指针求出最小的 $p$ 使得 $\max(a[p,m])=\max(a[m+1,j])$ 。那么我们需要计算 $[p,m]$ 中有多少个 $i$ 满足 $a_i\subseteq a_j$ ，以及 $[l,p-1]$ 中满足 $a_i\subseteq a_j$ 的 $\max(a[i,m])$ 之和。

那么，我们需要一个数据结构，支持：

令 $s_x\gets s_x+k$ 。
求 $\sum\limits_{i\subseteq x} s_i$ 。

注意到值域只有 $2^{14}$ ，考虑将每个 $14$ 位二进制数 $x$ 分为高 $7$ 位和第 $7$ 位，分别记为 $h(x)$ 和 $l(x)$ 。令 $a_{h(x),l(x)}=s_x$ ，再记 $b_{h(x),l(x)}=\sum\limits_{i\subseteq l(x)} a_{h(x),i}$，那么每次修改和查询都只需要操作 $b$ 的至多 $2^7$ 个值。

时间复杂度 $O(n\sqrt V\log n)$ ，可以勉强通过。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5,V=(1<<14);
bool c1,c2,c3;
int len=7;
int n,a[N];
ll ans;
int mx[N],sum1[V],sum2[V];
struct ds{
	int s[128][128];
	void add(int x,int k){
		int h=(x>>len),l=(x&((1<<len)-1));
		int msk=(1<<len)-1-h;
		for(int i=msk;;i=(i-1)&msk){
			s[i|h][l]+=k;
			if(i==0) break;
		}
	}
	int que(int x){
		int h=(x>>len),l=(x&((1<<len)-1));
		int res=0;
		for(int i=l;;i=(i-1)&l){
			res+=s[h][i];
			if(i==0) break;
		}
		return res;
	}
}t1,t2;
void calc(int l,int r,int fl){
	int m=(l+r)/2;
	for(int i=m+1;i<=r;i++){
		if(i==m+1) mx[i]=a[i];
		else mx[i]=max(mx[i-1],a[i]);
	}
	for(int i=m;i>=l;i--){
		if(i==m) mx[i]=a[i];
		else mx[i]=max(mx[i+1],a[i]);
	}
	vector<pair<int,int>> op1,op2;
	for(int i=l;i<=m;i++){
		t1.add(a[i],mx[i]);
		op1.push_back({a[i],mx[i]});
	}
	if(fl){
		for(int i=l;i<=m;i++){
			sum1[a[i]]+=mx[i];
		}
	}
	int pos=m+1;
	for(int i=m+1;i<=r;i++){
		while(pos!=l&&mx[pos-1]<=mx[i]){
			pos--;
			t1.add(a[pos],-mx[pos]);
			op1.pop_back();
			t2.add(a[pos],1);
			op2.push_back({a[pos],1});
			if(fl){
				sum1[a[pos]]-=mx[pos];
				sum2[a[pos]]++;
			}
		}
		ans+=1ll*t2.que(a[i])*mx[i];
		ans+=t1.que(a[i]);
		if(fl){
			ans-=1ll*sum2[a[i]]*mx[i];
			ans-=sum1[a[i]];
		}
	}
	for(auto [x,k]:op1){
		t1.add(x,-k);
	}
	for(auto [x,k]:op2){
		t2.add(x,-k);
	}
	if(fl){
		for(int i=l;i<=m;i++){
			sum1[a[i]]=sum2[a[i]]=0;
		}
	}
	if(l<m) calc(l,m,fl);
	if(m+1<r) calc(m+1,r,fl);
}
void calc3(int l,int r){
	int m=(l+r)/2;
	for(int i=m+1;i<=r;i++){
		if(i==m+1) mx[i]=a[i];
		else mx[i]=max(mx[i-1],a[i]);
	}
	for(int i=m;i>=l;i--){
		if(i==m) mx[i]=a[i];
		else mx[i]=max(mx[i+1],a[i]);
	}
	for(int i=l;i<=m;i++){
		sum1[a[i]]+=mx[i];
	}
	int pos=m+1;
	for(int i=m+1;i<=r;i++){
		while(pos!=l&&mx[pos-1]<=mx[i]){
			pos--;
			sum1[a[pos]]-=mx[pos];
			sum2[a[pos]]++;
		}
		ans+=1ll*sum2[a[i]]*mx[i];
		ans+=sum1[a[i]];
	}
	for(int i=l;i<=m;i++){
		sum1[a[i]]=sum2[a[i]]=0;
	}
	if(l<m) calc3(l,m);
	if(m+1<r) calc3(m+1,r);
}
void sol(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	c1=c2=c3=1;
	for(int i=1;i<n;i++){
		if(!(a[i]<=a[i+1])){
			c1=0;
		}
	}
	for(int i=1;i<=n;i++){
		if(!(a[i]<=32)){
			c2=0;
		}
	}
	for(int i=1;i<=n;i++){
		if(!(__builtin_popcount(a[i])==1)){
			c3=0;
		}
	}
	if(c2){
		len=3;
	}
	if(c3){
		calc3(1,n);
	}
	else{
		calc(1,n,0);
		reverse(a+1,a+n+1);
		if(!c1) calc(1,n,1);
	}
	cout<<ans<<"\n";
}
signed main(){
	freopen("score.in","r",stdin);
	freopen("score.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	int ct=1;
	while(ct--){
		sol();
	}
}

C

令 $da_i=a_i-a_{i-1}$ ， $db_i=b_i-b_{i-1}$ ，满足 $da,db$ 均递增（以下均不考虑 $da,db$ 的第一项）。那么，查询答案相当于，把 $da,db$ 归并排序后，得到的序列 $c$ 的每个前缀和之和，再加上 $(n+m-1)(da_1+db_1)$ 。

考虑如何计算答案。 $(n+m-1)(da_1+db_1)$ 的计算是简单的，考虑如何计算 $c$ 的前缀和之和。 $c$ 中每一位的贡献为这一位的值乘以其后面的数（包括自己）的个数。预处理并动态维护 $\sum da_i\times (n-i+1)+\sum db_i\times (m-i+1)$ 表示 $c$ 中每个 $da_i$ 后面的 $da$ 的个数以及每个 $db_i$ 后面的 $db$ 的个数，那么我们只需要再计算 $da_i$ 在 $c$ 中的位置后面的 $db$ 的个数，以及 $db_i$ 在 $c$ 中的位置后面的 $da$ 的个数。考虑如何计算。

因为 $n\le 100$ ，考虑直接把 $da$ 往 $db$ 里面的合适的位置插。对每个 $da_i$ 分别考虑：将 $da_i$ 插入 $db_j$ 后面，带来的贡献为 $b_j+(m-j)\times da_i$ 。二分求出插入的位置 $j$ 。使用 $O(\sqrt m)$ 区间修改， $O(1)$ 单点查询的分块维护分别 $db,b$ ，然后对每个 $da_i$ 计算贡献即可。修改 $a$ 序列时直接暴力修改即可。

时间复杂度 $O(q\sqrt m+qn\log n)$ 。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=105,M=1e5+5,B=317;
int n,m,q,a[N],b[M],sum;
int da[N],db[M];
int tl[M],tr[M];
int bl(int i){
	return (i-1)*B+1;
}
int br(int i){
	return i*B;
}
int bc(int x){
	return (x-1)/B+1;
}
void upd_a(int x,int d){
	sum+=d*x*(x+1)/2;
	int val=0;
	for(int i=n-x+1;i<=n;i++){
		val+=d;
		da[i]+=d;
		a[i]+=val;
	}
}
void upd_b(int x,int d){
	sum+=d*x*(x+1)/2;
	int l=m-x+1;
	int bx=bc(l),by=bc(m);
	int val=0;
	if(bx==by){
		for(int i=l;i<=m;i++){
			val+=d;
			b[i]+=val;
		}
	}
	else{
		for(int i=l;i<=br(bx);i++){
			val+=d;
			b[i]+=val;
		}
		for(int i=bx+1;i<by;i++){
			tl[i]+=val+1*d;
			tr[i]+=val+B*d;
			val+=B*d;
		}
		for(int i=bl(by);i<=m;i++){
			val+=d;
			b[i]+=val;
		}
	}
}
int que_b(int x){
	int bx=bc(x);
	int res=(tl[bx]+(tr[bx]-tl[bx])/(B-1)*(x-bl(bx)));
	return b[x]+res;
}
void get_ans(){
	int res=sum+a[1]*(m-1);
	for(int i=2;i<=n;i++){
		auto val=[&](int j){
			return que_b(j)+(m-j)*da[i];
		};
		int le=1,ri=m;
		while(le+3<ri){
			int p1=le+(ri-le)/3;
			int p2=le+(ri-le)*2/3;
			if(val(p1)<val(p2)){
				ri=p2-1;
			}
			else{
				le=p1+1;
			}
		}
		int mn=le;
		for(int i=le+1;i<=ri;i++){
			if(val(mn)>val(i)){
				mn=i;
			}
		}
		res+=val(mn);
	}
	cout<<res<<"\n";
}
void sol(){
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		da[i]=a[i]-a[i-1];
	}
	for(int i=1;i<=m;i++){
		cin>>b[i];
		db[i]=b[i]-b[i-1];
	}
	for(int i=1;i<=n;i++){
		sum+=da[i]*(n+1-i);
	}
	for(int i=1;i<=m;i++){
		sum+=db[i]*(m+1-i);
	}
	while(q--){
		int op,x,d;
		cin>>op>>x>>d;
		if(op==1){
			upd_a(x,d);
		}
		else{
			upd_b(x,d);
		}
		get_ans();
	}
}
signed main(){
	freopen("array.in","r",stdin);
	freopen("array.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	int ct=1;
	while(ct--){
		sol();
	}
}

D

考虑对 $k$ 为偶数和奇数的情况分别处理。

若 $k$ 为偶数，此时奇数位和偶数位互不干扰，可以分开处理。发现合法条件等价于，不能有连续 $\frac{k}{2}$ 个位置被删除。使用简单 dp 即可求出。

若 $k$ 为奇数，考虑此时的合法条件。注意到，删去一个数后，一定不能触发加入一个新数的条件（也就是说此时 $x-2,x+k$ 都应该有数），否则我们不删去将要加入的这个数是一样的。也就是说，若 $x-2,x$ 都要被删去，那么 $x$ 一定要先删。同理，若 $x,x+k$ 都要被删去，则 $x$ 一定要先删。那么不合法条件等价于，将每个删除的点向必须后于此节点删除的点连边，最终构成至少一个环。

考虑何时会满足此不合法条件（并转化为方便计数的形式）。不难得到，其充要条件为，存在 $[l,r]$ 满足 $l,r$ 均为偶数，且 $[l,r]$ 内的偶数点均被删除。且 $[r-k,l+k]$ 内的奇数点均被删除，且两个区间内删除的点的总和 $\ge k+2$ 。这两个区间一个在另一个中间，不好计数。考虑将奇数点全部向右平移 $k+1$ 格，那么条件变为，存在 $[l,r]$ 满足 $l,r$ 均为偶数且其中的偶数点全部删除， $[r+1,l+2k+1]$ 中的奇数点全部删除。

考虑 dp。令 $f_{l,i,j}$ 表示，第 $l$ 个位置，前面恰好连续 $i$ 个偶数点被删除，后面恰好连续 $j$ 个奇数点被删除（第 $j+1$ 个奇数点必须不被删除）。初始状态 $f_{0,0,j}=1$ 。转移如下：

下一个位置为偶数点。

选：

f_{l+1,i+1,j}\gets f_{l,i,j}

不选：

f_{l+1,0,j}\gets f_{l,i,j}

下一个位置为奇数点。

f_{l+1,i,j-1}\gets f_{l,i,j}(j>0)

f_{l+1,i,h}\gets f_{l,i,j}(j=0,h\in [0,n])

下一个位置没有点。

f_{l+1,i,j}\gets f_{l,i,j}

若 $l$ 为偶数点，并满足 $l\in [k+2,n]$ ，清除不合法状态：

f_{l,i,j}=0(i>0,j>0,i+j\ge k+2)

最终答案 $\sum f_{n+k+1,i,0}$ 。

时间复杂度 $O(n^3)$ 。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=205;
int n,k,p;
void add(int &x,int y){
	x=(x+y)%p;
	if(x<0) x+=p;
}
namespace case1{
	int f[N][N];
	int calc(int m,int d){
		memset(f,0,sizeof(f));
		f[0][0]=1;
		for(int i=0;i<m;i++){
			for(int j=0;j<=i;j++){
				if(j+1<=d) add(f[i+1][j+1],f[i][j]);
				add(f[i+1][0],f[i][j]);
			}
		}
		int ans=0;
		for(int j=0;j<=d;j++){
			add(ans,f[m][j]);
		}
		return ans;
	}
	void solve(){
		int cnt1=(n+1)/2-1;
		int cnt2=n/2;
		int ans=calc(cnt1,k/2)*calc(cnt2,k/2)%p;
		cout<<ans<<"\n";
	}
};
namespace case2{
	int a[N*2],f[N][N],g[N][N];
	void cl(){
		memset(a,0,sizeof(a));
		memset(f,0,sizeof(f));
		memset(g,0,sizeof(g));
	}
	void solve(){
		n--;
		for(int i=1;i<=n;i++){
			if(i%2==1) a[i]=1;
			else a[i+k+1]=2;
		}
		for(int j=0;j<=n;j++){
			f[0][j]=1;
		}
		for(int l=0;l<n+k+1;l++){
			if(a[l+1]==0) continue;
			if(l%2==1&&k+2<=l&&l<=n){
				for(int i=1;i<=n;i++){
					for(int j=1;j<=n;j++){
						if(i+j>=k+2){
							f[i][j]=0;
						}
					}
				}
			}
			for(int i=0;i<=n;i++){
				for(int j=0;j<=n;j++){
					if(!f[i][j]) continue;
					if(a[l+1]==1){
						add(g[i+1][j],f[i][j]);
						add(g[0][j],f[i][j]);
					}
					else if(a[l+1]==2){
						if(j!=0){
							add(g[i][j-1],f[i][j]);
						}
						else{
							for(int h=0;h<=n;h++){
								add(g[i][h],f[i][j]);
							}
						}
					}
				}
			}
			memcpy(f,g,sizeof(f));
			memset(g,0,sizeof(g));
		}
		int ans=0;
		for(int i=0;i<=n;i++){
			add(ans,f[i][0]);
		}
		cout<<ans<<"\n";
		cl();
	}
};
void sol(){
	cin>>n>>k>>p;
	if(k%2==0){
		case1::solve();
	}
	else{
		case2::solve();
	}
}
signed main(){
	freopen("basket.in","r",stdin);
	freopen("basket.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	int ct=1;
	cin>>ct;
	while(ct--){
		sol();
	}
}

No comments so far...

做题记录（题解）

A

B

C

D

0 comments

Status

Development

Support

About