11.3比赛总结

Bricks

1.题意：有一个由 B 和 W 组成的字符串，要将它划分成尽量多的区间，并使得每个区间中 B 和 W 的比例相等。

2.一道贪心题。首先特殊处理比值恒为 0 和不存在比值的情况，也就是全是 W 或者 B，明显这两种情况下每一个字符分一组就是最优解。

对于其它情况，发现所有段的比值都等于整个串里面的比值，也就是比值固定。在这个前提下，发现如果对于某一个满足比值区间，其子区间同样满足这个比值，将这个大区间拆成这个子区间和其补集同样满足条件，而且划分出的区间还多了一个。由此得出结论，每一次从边缘贪心地选取出最短可以满足条件的区间一定是最优的。

具体判断时可以计算出当前情况下满足条件需要的数量，检验这个数量是否可以被取到即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=100010;
int T,n,cnt1,cnt2,num[N],col[N],ans,c1,c2,t;
char c;
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
void init(){
	cnt1=cnt2=ans=c1=c2=t=0;
}
signed main(){
	scanf("%lld",&T);
	while(T--){
		init();
		scanf("%lld",&n);
		for(int i=1;i<=n;i++){
			scanf("%lld",&num[i]);
			for(c=getchar();c!='B'&&c!='W';c=getchar());
			if(c=='B')col[i]=1,cnt1+=num[i];
			else col[i]=2,cnt2+=num[i];
		}
		if(cnt1==0||cnt2==0){
			printf("%lld\n",cnt1+cnt2);
			continue;
		}
		int GCD=gcd(cnt1,cnt2);
		cnt1=cnt1/GCD;cnt2=cnt2/GCD;
		for(int i=1;i<=n;i++){
			if(col[i]==1){
				if(c2%cnt2!=0){
					c1+=num[i];
					continue;
				}
				t=(cnt1*(c2/cnt2))-c1;
				if(c2&&t>=0&&t<=num[i])ans++,c1=num[i]-t,c2=0;
				else c1+=num[i];
			}
			else{
				if(c1%cnt1!=0){
					c2+=num[i];
					continue;
				}
				t=(cnt2*(c1/cnt1))-c2;
				if(c1&&t>=0&&t<=num[i])ans++,c2=num[i]-t,c1=0;
				else c2+=num[i];				
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

中国象棋

（硬核打标应该能得40分）

1.如果一行或者一列有三个炮的话将会不合法，所以我们考虑记数组去存储有几列放了一个炮,有几列放了两个炮。考虑转移，状态：f[i][j][k]代表放了前ii行,有jj列是有一个棋子,有kk列是有2个棋子的合法方案数。

这时知道全部的列数,又知道一些情况的列数，所以我们可以求出不放棋子的列数

单步容斥：空的=全部的−合法的（即空的序列=m−j−k）

由3种情况：

可以在当前第i行不放棋子

可以在当前第i行放一个棋子

可以在当前第i行放两个棋子

不放棋子：f[i][j][k]=f[i−1][j][k]。

放一个棋子：不会选择放在有两个棋子的列。放在一个棋子的列：f[i][j][k]+=f[i−1][j+1][k−1]*(j+1)。放在没有棋子的列：f[i][j][k]+=f[i−1][j−1][k]*(m−(j−1)−k)。

放两个棋子：一个放在有一个棋子的列,一个放在没有棋子的列：f[i][j][k]+=f[i-1][j][k-1]*j*(m−j−(k−1)) 都放在没有棋子的列:f[i][j][k]+=f[i-1][j-2][k]* $\textrm{c}_{m-(j-2)-k}^{2}$ 都放在有一个棋子的列:f[i][j][k]+=f[i-1][j+2][k-2]* $\textrm{c}_{j+2}^{2}$

PS:记得判断边界。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f3f3f3f3f,p=1e9+9;
int n,ans=1,cnt;
int pr[N];
int pre[N];
void init(int n){
    for(int i=2;i<=n;i++){
        if(!pre[i]){
            pr[++cnt]=i;
            pre[i]=i;
        }
        for(int j=1;j<=cnt&&pr[j]*i<=n;j++){
            pre[i*pr[j]]=pr[j];
            if(i%pr[j]==0) break;
        }
    }
}
int fpm(int a,int b){
    int res=1;
    while(b){
        if(b&1){
            res*=a;
            res%=p;
        }
        a*=a;
        a%=p;
        b>>=1;
    }
    return res;
}
bool cmp(int a,int b){
    return a>b;
}
signed main(){
	freopen("math.in","r",stdin);
    freopen("math.out","w",stdout);
	cin>>n;
	init(2e5);
	vector<int> v;
	while(n!=1){
	    v.push_back(pre[n]);
	    n/=pre[n];
    }
    sort(v.begin(),v.end(),cmp);
    for(int i=2;i<=v.size()+1;i++){
        ans*=fpm(pr[i],v[i-2]-1);
        ans%=p;
    }
    cout<<ans;
    return 0;
}

小学奥数

1.这道题比较简单。

考虑暴力：可以先打标找找规律（打表打多了其实就水过10分了），可以先反过来考虑一下，先想一想把一个数分解为连续自然数之和，然后统计下来，暴力查询。

#include<bits/stdc++.h>
using namespace std;
const int kN =1e5+1,kM=1e9+9;
int n,ans=1,v[kN],r[kN];
vector<int> p,s;
void init(){
  	for(int i=2;i<kN;i++){
    	if(!v[i]) p.push_back(i);
    	for(int j=0;j<p.size()&&p[j]*i<kN;j++){
      		v[p[j]*i]=1;
      		if(i%p[j]==0) break;
    	}
  	}
}
int P(int x,int y){
  	int res=1;
  	for(;y;y>>=1,x=1ll*x*x%kM){
    	(y&1)&&(res=1ll*res*x%kM);
  	}
  	return res;
}
int C(int x, int y){
  	int res=1;
  	for(int i=2;i<=x+1;i++){
    	if(1ll*P(p[i],r[i]*y-1)*P(p[res],r[res]-1)<P(p[res],r[res]*y-1)){
      		res=i;
    	}
  	}
  	return res;
}
int main(){
  	cin>>n;
  	init();
  	for(int i=0;i<p.size()&&n;i++){
    	while(n%p[i]==0){
      		s.push_back(p[i]);
			n/=p[i];
    	}
  	}
  	fill(r,r+kN,1);
  	sort(s.begin(),s.end(),greater<int>());
  	for(int i=0,j=1;i<s.size();i++){
    	int t=C(j,s[i]);
    	j=max(j,t),r[t]*=s[i];
  	}
  	for(int i=1;i<=20;i++){
    	ans=1ll*ans*P(p[i],r[i]-1)%kM;
  	}
  	cout<<ans;
  	return 0;
}

正解：用ans来记录答案，(一个数本身就是好数)，所以要将ans的初始值设为1。可以设(x+1)+(x+2)+...+(x+d)=n。(x,d都是非负整数)。可以解得d∗(2x+d+1)=2n。令u∗v=2n,那么d=u,x=(v−u−1)/2，我们需要要求v>u且u,v得奇偶性不同。所以x,d得选择方案就是n的奇因子个数，所求的奇因子的个数，就是奇质因子的幂次+1后乘起来，所以我们需要将n分解质因数后贪心即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f3f3f3f3f,p=1e9+9;
int n,ans=1,cnt;
int pr[N];
int pre[N];
void init(int n){
    for(int i=2;i<=n;i++){
        if(!pre[i]){
            pr[++cnt]=i;
            pre[i]=i;
        }
        for(int j=1;j<=cnt&&pr[j]*i<=n;j++){
            pre[i*pr[j]]=pr[j];
            if(i%pr[j]==0) break;
        }
    }
}
int fpm(int a,int b){
    int res=1;
    while(b){
        if(b&1){
            res*=a;
            res%=p;
        }
        a*=a;
        a%=p;
        b>>=1;
    }
    return res;
}
bool cmp(int a,int b){
    return a>b;
}
signed main(){
	cin>>n;
	init(2e5);
	vector<int> v;
	while(n!=1){
	    v.push_back(pre[n]);
	    n/=pre[n];
    }
    sort(v.begin(),v.end(),cmp);
    for(int i=2;i<=v.size()+1;i++){
        ans*=fpm(pr[i],v[i-2]-1);
        ans%=p;
    }
    cout<<ans;
    return 0;
}

Triple Jump

1.这道题可以用线段树，想到似乎只能先枚举a,b然后再算h[2b−a+1]到h[r]的最大值。在分析处理中可知，很多(a,b)是无效的，会额外耗费时间。

分类讨论ha和hb的大小关系：

当ha≥hb枚举b ，可以发现：如果存在a1<a2满足ha1,ha2≥hb，那么(a1,b)是无效的。因为一组方案(a1,b,c)一定可以被(a1,a2,c)替代。也就是说需要找到最大的a满足a<b,ha≥hb。

ha<hb时枚举a，我们同样考虑b1,b2，发现一组方案(a,b2,c)一定可以被(b1,b2,c)替代。于是我们只需要找到最小的b满足a<b,ha<hb。可以用单调栈查询。枚举r，设xl是满足l=a且2b−a+1≥r的(a,b)中ha+hb 的最大值，yl是限制l=a时[l,r]的答案，那每次查询只需计算yl到yr的最大值。
考虑到r−1到r时x,y的变化，一些x会进行单点修改;然后yi会与xi+hr 取max。可以用线段树维护。

#include<bits/stdc++.h>
using namespace std;
struct tree{
	int w1,w2,tag;
}tr[2000005];
int n,m,a[500005],ans[500005],st[500005],l,r;
vector<int>v[500005];
vector<pair<int,int> >q[500005];
void pushup(int k){
	tr[k].w1=max(tr[k<<1].w1,tr[k<<1|1].w1);
	tr[k].w2=max(tr[k<<1].w2,tr[k<<1|1].w2);
}
void build(int k,int l,int r){
	if(l==r){
		tr[k].w1=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	pushup(k);
}
void update(int k,int v){
	tr[k].tag=max(tr[k].tag,v);
	tr[k].w2=max(tr[k].w2,tr[k].w1+tr[k].tag);
}
void pushdown(int k){
	if(!tr[k].tag)return;
	update(k<<1,tr[k].tag);update(k<<1|1,tr[k].tag);
	tr[k].tag=0; 
}
void change(int k,int l,int r,int x,int y,int v){
	if(x<=l&&r<=y){update(k,v);return;}
	int mid=(l+r)>>1;pushdown(k);
	if(x<=mid)change(k<<1,l,mid,x,y,v);
	if(y>mid)change(k<<1|1,mid+1,r,x,y,v);
	pushup(k);
}
int query(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y)return tr[k].w2;
	int mid=(l+r)>>1,res=0;pushdown(k);
	if(x<=mid)res=max(res,query(k<<1,l,mid,x,y));
	if(y>mid)res=max(res,query(k<<1|1,mid+1,r,x,y));
	return res;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	int top=0;
	for(int i=1;i<=n;i++){
		while(top&&a[st[top]]<a[i])v[st[top]].emplace_back(i),top--;
		if(top)v[st[top]].emplace_back(i);
		st[++top]=i;
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>l>>r;
		q[l].emplace_back(make_pair(r,i));
	}
	build(1,1,n);
	for(int i=n;i>=1;i--){
		for(int j=0;j<v[i].size();j++){
			int l=i,p=v[i][j];
			if(2*p-l<=n) change(1,1,n,2*p-l,n,a[l]+a[p]);
		}
		for(int j=0;j<q[i].size();j++) ans[q[i][j].second]=query(1,1,n,i,q[i][j].first);
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<'\n'; 
	return 0;
}