难度估计：青，绿，蓝，黑。

A

考虑从低位到高位依次确定答案的每一位。

注意到，对于两个布尔变量 x,yx,y，满足：

((x+y)mod  2)=(((x⊕1)+(y⊕1))mod  2)((x+y)\mod2)=(((x\oplus 1)+(y\oplus 1))\mod 2)

也就是说，对于当前位，ansians_i 的取值不受 ansi−1ans_{i-1} 的取值的影响。

那么，我们可以直接获取 ansnans_n 的当前位的值，然后推出 ans0ans_0 到 ansn−1ans_{n-1} 的当前位的值，然后处理下一位即可。

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

#include<bits/stdc++.h>
#define int unsigned int
using namespace std;
const int N=3e5+5;
int n,a[N],b[N],ans[N];
int ap[N],bp[N],c[N];
void sol(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
	}
	for(int j=0;j<32;j++){
		for(int i=1;i<=n;i++){
			ap[i]=((a[i]>>j)&1);
			bp[i]=((b[i]>>j)&1);
		}
		int u=(ap[n]^bp[n]^c[n]);
		ans[0]|=(u<<j);
		for(int i=1;i<=n;i++){
			int las=((ans[i-1]>>j)&1);
			int w=((ap[i]^las)+(bp[i]^las)+c[i]);
			c[i]=(w>>1);
			w&=1;
			ans[i]|=(w<<j);
		}
//		assert(ans[n]==ans[0]);
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<"\n";
	}
}
signed main(){
	freopen("add.in","r",stdin);
	freopen("add.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	int ct=1;
	while(ct--){
		sol();
	}
}

B

推一下式子。

a×b∣b×gcd⁡(a,b)a\times b\mid b\times \gcd(a,b)

经典操作：令 d=gcd⁡(a,b)d=\gcd(a,b)，以及 a′=ad,b′=bda'=\frac{a}{d},b'=\frac{b}{d}，并且需要满足 gcd⁡(a′,b′)=1\gcd(a',b')=1，则有：

a′+b′∣ba'+b'\mid b a′+b′∣b′×da'+b'\mid b'\times d

因为 a′+b′a'+b' 与 b′b' 互质，则有：

a′+b′∣da'+b'\mid d

此时一定有 d≥(a′+b′)d\ge (a'+b')，即 a=a′d=a′(a′+b′)a=a'd=a'(a'+b')。所以 a≤na\le \sqrt n。同理 b≤mb\le \sqrt m。

暴力枚举 a′,b′a',b' 即可，此时 d≤min⁡(na′(a′+b′),mb′(a′+b′))d\le \min(\frac{n}{a'(a'+b')},\frac{m}{b'(a'+b')})。

时间复杂度 O(nlog⁡n)O(n\log n)，其中 log⁡\log 来源于计算 gcd⁡\gcd 判断是否互质。可以预处理 n\sqrt n 范围内的任意两数的 gcd⁡\gcd 以去掉 log⁡\log。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e6+5,B=1800;
int g[B+5][B+5];
void init(){
	for(int i=1;i<B;i++){
		for(int j=1;j<B;j++){
			if(i>=j){
				if(i%j==0) g[i][j]=j;
				else g[i][j]=g[i%j][j];
			}
			else{
				if(j%i==0) g[i][j]=i;
				else g[i][j]=g[i][j%i];
			}
//			assert(g[i][j]==__gcd(i,j));
		}
	}
}
int n,m;
ll ans;
void cl(){
	ans=0;
}
void sol(){
	cin>>n>>m;
	for(int i=1;i*i<=n;i++){
		for(int j=1;i*(i+j)<=n&&j*(i+j)<=m;j++){
			if(g[i][j]==1){
				int w=min(n/(i*(i+j)),m/(j*(i+j)));
				ans+=w;
			}
		}
	}
	cout<<ans<<"\n";
}
signed main(){
	freopen("math.in","r",stdin);
	freopen("math.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	init();
	int ct=1;
	cin>>ct;
	while(ct--){
		sol();
		cl();
	}
}

C

对输入数组进行转化，改为需要使 aia_i 数组还原为 1,2,…,n1,2,\dots,n，以下描述均在此意义下。

注意到，答案的量级在 O(log⁡n)O(\log n) 以内。然后根据某些性质或迹象可以发现，答案与 ai>ai+1a_i>a_{i+1} 的 ii 的数量 cntcnt 有关，并推测其是 ⌊log⁡2cnt⌋+1\left \lfloor \log_{2}{cnt} \right \rfloor +1。

然后考虑构造。考虑每次操作使 cntcnt 至少减半。设当前 ai>ai+1a_i>a_{i+1} 的 ii 的数量为 ww，则我们可以把序列分为 w+1w+1 个上升子串。在第 ⌊w2⌋+1\left \lfloor \frac{w}{2} \right \rfloor+1 个上升子串后截断，并在弹出过程中将原本第 ii 个与第 i+⌊w2⌋+1i+\left \lfloor \frac{w}{2} \right \rfloor+1 个上升子串中的数归并为一个上升子串。

时间复杂度 O(nlog⁡n)O(n\log n)。

#include<bits/stdc++.h>
using namespace std;
const int N=55;
int n,a[N],b[N];
void cl(){
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
}
void sol(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		b[a[i]]=i;
	}
	int cnt=0;
	for(int i=1;i<n;i++){
		if(b[i]>b[i+1]){
			cnt++;
		}
	}
	if(cnt==0){
		cout<<"0\n";
		return;
	}
	int h=(__lg(cnt)+1);
	cout<<h<<"\n";
	for(int l=0;l<h;l++){
		int w=1;
		for(int i=1;i<=n;i++){
			if(i<n&&b[i]>b[i+1]){
				w++;
			}
		}
		int lim=w/2;
		deque<pair<int,int>> s1,s2;
		vector<int> res;
		int u=1;
		for(int i=1;i<=n;i++){
			if(u<=lim){
				s1.push_back({b[i],u});
			}
			else{
				s2.push_back({b[i],u});
			}
			if(i<n&&b[i]>b[i+1]){
				u++;
			}
		}
		while(!s1.empty()||!s2.empty()){
			auto opt1=[&](){
				res.push_back(s1.front().first);
				s1.pop_front();
				cout<<'A';
			};
			auto opt2=[&](){
				res.push_back(s2.front().first);
				s2.pop_front();
				cout<<'B';
			};
			if(s1.empty()){
				opt2();
			}
			else if(s2.empty()){
				opt1();
			}
			else{
				int c1=s1.front().second;
				int c2=s2.front().second;
				auto ok1=[&](){
					return !(s1.empty()||s1.front().second!=c1);
				};
				auto ok2=[&](){
					return !(s2.empty()||s2.front().second!=c2);
				};
				while(ok1()||ok2()){
					if(!ok1()){
						opt2();
					}
					else if(!ok2()){
						opt1();
					}
					else if(s1.front()<s2.front()){
						opt1();
					}
					else{
						opt2();
					}
				}
			}
		}
		for(int i=1;i<=n;i++){
			b[i]=res[i-1];
		}
		cout<<"\n";
	}
}
signed main(){
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	int ct=1;
	cin>>ct;
	while(ct--){
		sol();
		cl();
	}
}

D

考虑如何计算一个区间的答案。考虑使用 01-Trie。

不难得到，答案可以对应为，01-Trie 上的一个点集 S={v1,v2,…,vm}S=\{v_1,v_2,\dots,v_m\}，满足任意 viv_i 的子树内的所有数都出现在区间内（以下称为“已激活”），且 viv_i 的兄弟为 vi+1v_{i+1} 的严格祖先，此时答案为 ∑u∈S2(n−depu)\sum\limits_{u\in S} 2^{(n-dep_u)}，需要最大化答案。

考虑如何较为方便的计算。发现，若先确定了 vmv_m，接下来只要一直跳到其父亲的兄弟直到根节点，并将所有到达过的已被激活的点加入 SS。

观察答案的形式，考虑使用扫描线以及历史和线段树计算答案。将 rr 从左往右扫，考虑 rr 增加 11 时，每个 ll 对应的答案会如何变化。此时会有若干个未激活的点被激活，同时每个激活的点 uu 附带一个限制 mluml_u 表示只有 l≤mlul\le ml_u 的 ll 才能使用此点。考虑激活一个点 uu 且限制为 mluml_u 时，每个 ll 的答案会如何变化。

考虑对 uu 上方的部分和下方的部分分别统计答案后合并。对于上方的部分，从 uu 一直跳到其父亲的兄弟直到根节点，记录到达过的所有已激活的点 vv 的 (mlv,2(n−depv))(ml_v,2^{(n-dep_v)})。对于下方的部分，直接对 uu 的兄弟的子树中的每一个已激活节点 vv，从 vv 一直跳到其父亲的兄弟直到节点 uu。将上下两部分的答案合并，其涉及的不同 mlml 的数量均摊不会超过 O(log⁡n)O(\log n) 量级。在历史和线段树上更新这些区间即可，更新时在线段树上二分出需要修改的位置并执行区间覆盖即可。

时间复杂度 O(nlog⁡2n)O(n\log^2 n)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1.4e5+5,M=5e5+5;
struct mat{
	int s[3][3];
};
mat operator*(const mat &a,const mat &b){
	mat res{};
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			for(int k=0;k<3;k++){
				res.s[i][k]+=a.s[i][j]*b.s[j][k];
			}
		}
	}
	return res;
}
mat bs={{
	{1,0,0},
	{0,1,0},
	{0,0,1},
}};
mat cov(int k){
	return {{
	{1,0,0},
	{0,0,0},
	{0,k,1}}};
}
mat upd={{
	{1,0,0},
	{1,1,0},
	{0,0,1},
}};
#define mid (((le)+(ri))>>1)
#define ls ((u)<<1)
#define rs (((u)<<1)|1)
#define lp ls,le,mid
#define rp rs,mid+1,ri
struct sgt1{
	mat s[N<<2],t[N<<2];
	bool vis[N<<2];
	void push_up(int u){
		for(int i=0;i<3;i++){
			s[u].s[0][i]=s[ls].s[0][i]+s[rs].s[0][i];
		}
	}
	void build(int u,int le,int ri){
		t[u]=bs;
		if(le==ri){
			s[u].s[0][2]=1;
			return;
		}
		build(lp);
		build(rp);
		push_up(u);
	}
	void ch(int u,mat k){
		s[u]=s[u]*k;
		t[u]=t[u]*k;
		vis[u]=1;
	}
	void push_down(int u){
		if(vis[u]){
			ch(ls,t[u]);
			ch(rs,t[u]);
			t[u]=bs;
			vis[u]=0;
		}
	}
	void upd(int u,int le,int ri,int x,int y,mat k){
		if(x<=le&&ri<=y){
			ch(u,k);
			return;
		}
		push_down(u);
		if(x<=mid) upd(lp,x,y,k);
		if(y>mid) upd(rp,x,y,k);
		push_up(u);
	}
	int que(int u,int le,int ri,int x,int y){
		if(x<=le&&ri<=y){
			return s[u].s[0][0];
		}
		push_down(u);
		int res=0;
		if(x<=mid) res+=que(lp,x,y);
		if(y>mid) res+=que(rp,x,y);;
		return res;
	}
}t1;
struct sgt2{
	int mn[N<<2],cov[N<<2];
	void push_up(int u){
		mn[u]=min(mn[ls],mn[rs]);
	}
	void ch(int u,int k){
		mn[u]=cov[u]=k;
	}
	void push_down(int u){
		if(cov[u]){
			ch(ls,cov[u]);
			ch(rs,cov[u]);
			cov[u]=0;
		}
	}
	void upd(int u,int le,int ri,int x,int y,int k){
		if(x<=le&&ri<=y){
			ch(u,k);
			return;
		}
		push_down(u);
		if(x<=mid) upd(lp,x,y,k);
		if(y>mid) upd(rp,x,y,k);
		push_up(u);
	}
	int que(int u,int le,int ri,int x,int y,int k){
		if(mn[u]>k) return -1;
		if(le==ri) return le;
		push_down(u);
		if(x<=mid){
			int w=que(lp,x,y,k);
			if(w!=-1) return w;
		}
		if(y>mid){
			int w=que(rp,x,y,k);
			if(w!=-1) return w;
		}
		return -1;
	}
}t2;
int n,m,a[N],ans[M];
vector<pair<int,int>> q[N];
int ml[N*2],mr[N*2],sz[N*2],vis[N*2];
vector<int> om[N];
int rval[N*2];
void opt(int l,int k){
	if(k<=0) return;
	int w=t2.que(1,1,n,1,l,k);
	if(w!=-1&&w<=l){
		t1.upd(1,1,n,w,l,cov(k));
		t2.upd(1,1,n,w,l,k);
	}
}
void get_subtr(int rt,vector<int> &res){
	res.push_back(rt);
	if(sz[rt]==1) return;
	get_subtr(rt*2,res);
	get_subtr(rt*2+1,res);
}
void rebuild(int rt,map<int,int> &res){
	vector<int> subtr;
	get_subtr(rt,subtr);
	for(int i:subtr){
		vector<pair<int,int>> s;
		if(vis[i]){
			int u=i;
			while(u!=rt){
				if(vis[u]){
					s.push_back({ml[u],sz[u]});
				}
				u/=2;
				if(u==rt) break;
				u^=1;
			}
			sort(s.begin(),s.end());
			int sum=0;
			for(int j=(int)s.size()-1;j>=0;j--){
				auto [l,w]=s[j];
				sum+=w;
				rval[l]=max(rval[l],sum);
			}
		}
	}
	for(int i:subtr){
		if(vis[i]){
			int v=ml[i];
			res[v]=max(res[v],rval[v]);
			rval[v]=0;
		}
	}
}
void solve(){
	for(int r=1;r<=n;r++){
		for(int i:om[r]){
			vis[i]=1;
		}
		for(int i:om[r]){
			map<int,int> s;
			int u=i;
			while(u!=1){
				if(vis[u]){
					s[ml[u]]=max(s[ml[u]],sz[u]);
				}
				u/=2;
				if(u==1) break;
				u^=1;
			}
			int suf=0;
			for(auto it=s.rbegin();it!=s.rend();it++){
				auto& [l,w]=(*it);
				suf+=w;
				w=suf;
			}
			map<int,int> z;
			if(i!=1){
				rebuild(i^1,z);
				int las=-1e18;
				vector<int> era;
				for(auto it=z.rbegin();it!=z.rend();it++){
					auto [l,w]=(*it);
					if(w<=las) era.push_back(l);
					else las=w;
				}
				for(int l:era){
					z.erase(l);
				}
			}
			for(auto [l,w]:s){
				auto it=z.lower_bound(l);
				if(it!=z.end()) w+=((*it).second);
				opt(l,w);
			}
			for(auto [l,w]:z){
				auto it=s.lower_bound(l);
				if(it!=s.end()) w+=((*it).second);
				opt(l,w);
			}
		}
		if(r==n){
			opt(1,n);
		}
		t1.upd(1,1,n,1,r,upd);
		for(auto [l,id]:q[r]){
			ans[id]=t1.que(1,1,n,l,r);
		}
	}
}
signed main(){
	freopen("bitwise.in","r",stdin);
	freopen("bitwise.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m;
	n=(1<<n);
	memset(ml,0x3f,sizeof(ml));
	ml[1]=1;
	mr[1]=n;
	sz[1]=n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		int u=1;
		for(int j=__lg(n)-1;j>=0;j--){
			int w=((a[i]>>j)&1);
			u=2*u+w;
			ml[u]=min(ml[u],i);
			mr[u]=max(mr[u],i);
			sz[u]++;
		}
	}
	for(int i=1;i<2*n;i++){
		om[mr[i]].push_back(i);
	}
	t1.build(1,1,n);
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		q[y].push_back({x,i});
	}
	solve();
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<"\n";
	}
}

0 comments

No comments so far...
21
Accepted
0
Solutions Liked
  1. Language
  2. Legacy mode
  3. Theme
  2. 粤ICP备2021104657号
  3. Worker 0, 18ms
  4. Powered by Hydro v5.0.7 Community