AT1219 历史研究

一道回滚莫队的例题。
莫队算法能够解决很多类似于求和的询问问题。但是对于求最值的询问它无能为力。这是因为莫队需要一个区间既能够拓展又能够收缩。
对于求最值类的问题,它只能够拓展,不能够收缩。
这时候我们可以使用一种被称为「回滚莫队」的算法。
具体来说,对于每个块内的询问,我们都分成两部分来处理。一部分是将右端点推进,另一部分则是将左端点推进。对于每一个询问,我们在求得它向右端点推进的值以后,暴力统计上左端点对它的贡献即可。
请注意回滚莫队不能奇偶分块。结合回滚莫队的性质可以很容易理解。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
int BLOCK,NUM;
int bl[100005],lb[100005],rb[100005];
struct Query{
	int l;
	int r;
	int id;
	inline bool operator<(const Query &B)const{
		return (bl[l]^bl[B.l])?(bl[l]<bl[B.l]):(r<B.r);
	}
}q[100005];
int n,m,a[100005],cnt1[100005],cnt2[100005],loc[100005],typ[100005];
long long ans[100005];
void init(){
	scanf("%d%d",&n,&m);
	BLOCK=std::sqrt(n);
	NUM=std::ceil((double)n/BLOCK);
	for(int i=1;i<=NUM;++i){
		lb[i]=BLOCK*(i-1)+1;
		rb[i]=BLOCK*i;
		for(int j=lb[i];j<=rb[i];++j){
			bl[j]=i;
		}
	}
	rb[NUM]=n;
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
		loc[i]=a[i];
	}
	std::sort(loc+1,loc+1+n);
	int tot=std::unique(loc+1,loc+1+n)-loc-1;
	for(int i=1;i<=n;++i){
		typ[i]=std::lower_bound(loc+1,loc+1+tot,a[i])-loc;
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	std::sort(q+1,q+1+m);
	int p=1;
	for(int i=0;i<=NUM;++i){
		int l=rb[i]+1,r=rb[i];
		long long nw=0;
		for(int j=1;j<=n;++j){
			cnt1[j]=0;
		}
		for(;bl[q[p].l]==i;++p){
			int ql=q[p].l,qr=q[p].r;
			long long tmp=0;
			if(bl[ql]==bl[qr]){
				for(int j=ql;j<=qr;++j){
					cnt2[typ[j]]=0;
				}
				for(int j=ql;j<=qr;++j){
					++cnt2[typ[j]];
					tmp=std::max(tmp,1ll*cnt2[typ[j]]*a[j]);
				}
				ans[q[p].id]=tmp;
				continue;
			}
			while(r<qr){
				++r;
				++cnt1[typ[r]];
				nw=std::max(nw,1ll*cnt1[typ[r]]*a[r]);
			}
			tmp=nw;
			while(l>ql){
				--l;
				++cnt1[typ[l]];
				nw=std::max(nw,1ll*cnt1[typ[l]]*a[l]);
			}
			ans[q[p].id]=nw;
			while(l<rb[i]+1){
				--cnt1[typ[l]];
				++l;
			}
			nw=tmp;
		}
	}
	for(int i=1;i<=m;++i){
		printf("%lld\n",ans[i]);
	}
}

int main(){
	init();
	return 0;
}

AGC029

这一场打得还行,可惜C没有调出来。不过还是暴涨七百多分。摸不透算分机制。

AGC 29 A
给定一个01序列,每一次可以把01变成10,求最大操作次数。
猜结论题(其实证明很显然)。结论是每一个1后面的0的个数之和。

#include<iostream>
#include<cstdio>
#include<cstring>

int n;
char ch[200005];
int sm[200005];
void init(){
	std::cin>>(ch+1);
	n=std::strlen(ch+1);
	for(int i=1;i<=n;++i){
		ch[i]=(ch[i]=='B'?1:0);
	}
	sm[n+1]=0;
	for(int i=n;i>=1;--i){
		sm[i]=sm[i+1]+(ch[i]^1);
	}
	long long ans=0;
	for(int i=1;i<=n;++i){
		if(ch[i]){
			ans+=sm[i+1];
		}
	}
	printf("%lld",ans);
}

int main(){
	init();
	return 0;
}

AGC 29 B
给定一个序列,问从中最多能找出多少个数对使得它们的和是二的次幂。
贪心。考虑从大往小遍历,如果一个大的数能够找到一个比它小的数配成二的次幂,那么不选这个大的数肯定不会更优。
用\(map\)优化一下即可。

#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>

std::map<int,int> mp;

int n,a[200005];

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
		mp[a[i]]?(++mp[a[i]]):mp[a[i]]=1;
	}
	std::map<int,int>::iterator it=mp.end();
	--it;
	
	int ans=0,nw;
	while(1){
		if(it->second==0){
			goto loop;
		}
		nw=it->first;
		for(int i=30;i>=1;--i){
			while(it->second>=1&&(1<<i)-nw>=0&&mp[(1<<i)-nw]>=1&&(nw!=(1<<(i-1)))){
				--mp[(1<<i)-nw];
				it->second-=1;
				++ans;
			}
			while(it->second>=2&&nw==(1<<(i-1))){
				it->second-=2;
				++ans;
				
			}
		}
		loop:
			if(it==mp.begin()){
				break;
			}
			--it;
	}
	
	printf("%d\n",ans);
} 

int main(){
	init();
	return 0;
}

AGC 29 D
容易知道,每一轮T一定是能走就走。因为如果T不走,那么A就可以通过不走来强迫游戏结束。
并且,如果P经过了一个障碍上方,游戏就结束了。所以A一定会尽可能地让P走到一个障碍上方。
故而,A不往右走,只有两种情况。一,是下方存在一个障碍;二,是右边有障碍挡住。
很显然,如果固定起始点,只有横坐标与纵坐标相同的点才会挡住A。
因此,每一次A被挡住了,就更新起始点,然后向下走即可。

#include<iostream>
#include<cstdio>
#include<algorithm>

struct data{
	int x;int y;
	inline bool operator<(const data &B){
		return x==B.x?y<B.y:x<B.x;
	}
	inline void init(int X,int Y){
		x=X,y=Y;
	}
}a[200005];
int n,h,w;
void init(){
	scanf("%d%d%d",&h,&w,&n);
	int x,y;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&x,&y);
		a[i].init(x,y);
	}
	std::sort(a+1,a+1+n);
	int nw=0;
	for(int i=1;i<=n;++i){
		if(a[i].x-nw==a[i].y){
			++nw;
		}
		if(a[i].x-nw>a[i].y){
			printf("%d\n",a[i].x-1);
			return;
		}
	}
	printf("%d\n",h);
}

int main(){
	init();
	return 0;
}

ABC113

第一次尝试打\(AtCoder\),考前紧张刺激地对着\(google\)学日语,不过真正到了开考了还是英语读起来比较靠谱。

\(Beginner\)的比赛还是比较水的,我涨了\(400pts\),似乎是\(Beginner\)能涨到的最高分了?不太清楚。

\(ABC113 A – Discount Fare\)
打卡题,没什么可说的。
\(ABC113 B – Palace\)
大力模拟即可。
\(ABC113 C – ID\)
排序。善用STL可以高效得分。
\(ABC113 D – Number of Amidakuji\)
一道有一定难度的DP题。
\(f_{i,j}\)表示,走到\(f_{i,j}\)并用完横杠的方案数。
然后我们可以发现,这种方案数是可以直接计算出来的——具体来说要乘上一个斐波那契数。这是因为放置东西的时候不能同行。
可以类比爬楼梯问题。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define Max(_A,_B) (_A>_B?_A:_B)
#define Min(_A,_B) (_A<_B?_A:_B)
#define Abs(_A) ((_A)?(_A):(-(_A))
#define INF 0x3f3f3f3f
/*
ABC113 A - Discount Fare
*/ 
long long x,y;
void init(){
    scanf("%lld%lld",&x,&y);
    printf("%lld",x+(y>>1));
}
int main(){
	init();
	return 0;
}

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define Max(_A,_B) (_A>_B?_A:_B)
#define Min(_A,_B) (_A<_B?_A:_B)
#define Abs(_A) ((_A)?(_A):(-(_A))
#define INF 0x3f3f3f3f
/*
ABC113 B - Palace
*/ 
int n,loc[100005];
double t,a,h[100005];
inline double cmp(int a,int b){
    return h[a]<h[b];
} 
void init(){
    scanf("%d",&n);
    scanf("%lf%lf",&t,&a);
    for(int i=1;i<=n;++i){
        scanf("%lf",&h[i]);
        h[i]=t-h[i]*0.006;
        h[i]-=a;
        h[i]=(h[i]<0)?(-h[i]):h[i];
        loc[i]=i;
    }
    sort(loc+1,loc+1+n,cmp);
    printf("%d",loc[1]);
}
int main(){
	init();
	return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define Max(_A,_B) (_A>_B?_A:_B)
#define Min(_A,_B) (_A<_B?_A:_B)
#define Abs(_A) ((_A)?(_A):(-(_A))
#define INF 0x3f3f3f3f
/*
ABC113 C - ID
*/ 
int n,m;
struct data{
    int a;
    int b;
    int id;
}tl[100005];
vector<data> nl[100005];
inline bool cmp(const data &a,const data &b){
    return a.b<b.b;
}
inline bool cmp2(const data &a,const data &b){
    return a.id<b.id;
}
void init(){
    scanf("%d%d",&n,&m);
    int x,y;
    data nw;
    for(int i=1;i<=m;++i){
        scanf("%d%d",&x,&y);
        nw.b=y;
        nw.id=i;
        nw.a=x;
        nl[x].push_back(nw);
    }
    for(int i=1;i<=n;++i){
        sort(nl[i].begin(),nl[i].end(),cmp);
    }
    int tp=0;
    for(int i=1;i<=n;++i){
        for(int j=0;j<nl[i].size();++j){
            nl[i][j].b=j+1;
            tl[++tp]=nl[i][j];
        }
    }
    sort(tl+1,tl+1+m,cmp2);
    for(int i=1;i<=m;++i){
        printf("%.6d%.6d\n",tl[i].a,tl[i].b);
    }
}
int main(){
	init();
	return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define Max(_A,_B) (_A>_B?_A:_B)
#define Min(_A,_B) (_A<_B?_A:_B)
#define Abs(_A) ((_A)?(_A):(-(_A))
#define INF 0x3f3f3f3f
#define MOD 1000000007
/*
ABC113 D - Number of Amidakuji
*/
//w 棍子,k 列数。 
long long h,w,k;
long long ans=0;
long long f[105][10];
long long fib[1005];
//Y取X的情况。 
void init(){
    scanf("%lld%lld%lld",&h,&w,&k);
    memset(f,0,sizeof(f));
    fib[1]=fib[2]=1;
    for(int i=3;i<=1000;++i){
        fib[i]=(fib[i-1]+fib[i-2])%MOD;
    }
    f[0][1]=1;
    for(int i=1;i<=h;++i){
        for(int j=1;j<=w;++j){
            if(j>1){
                f[i][j]=(f[i][j]+(f[i-1][j-1]*fib[w-j+1]*fib[j-1])%MOD)%MOD;
            }
            if(j<w){
                f[i][j]=(f[i][j]+(f[i-1][j+1]*fib[w-j]*fib[j])%MOD)%MOD;
            }
            f[i][j]=(f[i][j]+(f[i-1][j]*fib[j]*fib[w-j+1])%MOD)%MOD;
        }
    }
    printf("%lld",f[h][k]);
}
int main(){
	init();
	return 0;
}

 

ARC098 D Xor Sum2

一道简单双指针题。
首先猜结论:\(x\ xor\ y==x+y\)当且仅当\(x\&y==x+y\)
那么,令函数\(f_l\)表示,以\(l\)为左端点最远能拓展到的右端点。
我们可以发现,\(f_{l+1}\)也一定至少能拓展到这个点。
这时候我们则可以在固定左端点的同时移动右端点。每一次移动,从这个右端点到这个左端点之间所有的左端点构成的区间都是合法的。
统计即可得解。


#include<iostream>
#include<cstdio>
using namespace std;

int n,a[200005];
void init(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    long long ans=0,nw=0;
    int l=1,r=1;
    while(r<=n){
        while((!(nw&a[r]))&&r<=n){
            nw|=a[r++];
            ans+=(r-l);
        }
        nw^=a[l++];
    }
    printf("%lld",ans);
}
int main(){
    init();
    return 0;
} 

 

ARC100 E Or Plus Max

其中,\(f[k]\)表示递推到第i位的最大值。
那么,\(f[k]\)显然是可以从\(f[k-1]\)递推来的。
这时候只要考虑\(i|j==k\)的值。
枚举k的子集,求最大值。
这样做是\(O(松松松)\)的。
考虑优化。
我们可以发现,对于k的每一个子集,它的子集的最大值是已经求过的。
那么我们只需要考虑枚举每一个k子集的一部分,可以考虑每一次把它反与上一个\(2^l\),并求Max和次Max。
这样有解,复杂度\(O(n*2^n)\)。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Swap(_A,_B) ((_A)^=(_B)^=(_A)^=(_B))
using namespace std;
//mx[i][0]表示最大值,mx[i][1]表示次大值。 
int f[1<<18],n,a[1<<18];
int nw,mxx,lmxx,sa,sb,st;
struct data{
    int v;
    int nm;
    bool operator ==(const data &x)const{
        return this->v==x.v&&this->nm==x.nm;
    }
}lst[40],mx[1<<18][2];
inline bool cmp(const data &x,const data &y){
    return x.v>y.v;
}
//处理第k个数,它的最大值和次大值。 
int wrk(int k){
    nw=0,mxx=0,lmxx=0,sa=-1,sb=-1,st=0;
    lst[++st]=(data){a[k],k};
    for(int i=0;(1<<i)<=k;++i){
        if((k>>i)&1){
            nw=k^(1<<i);
        }else{
            continue;
        }
        lst[++st]=mx[nw][0];
        lst[++st]=mx[nw][1];
    }
    sort(lst+1,lst+1+st,cmp);
    unique(lst+1,lst+1+st);
    mx[k][0]=lst[1],mx[k][1]=lst[2];
    return mx[k][0].v+mx[k][1].v;
}
void init(){
    scanf("%d",&n);
    const int MAX=1<<n;
    for(int i=0;i<MAX;++i){
        scanf("%d",&a[i]);
    }
    f[0]=0,mx[0][0].v=a[0],mx[0][1].v=0,mx[0][0].nm=0,mx[0][1].nm=-1;
    for(int k=1;k<MAX;++k){
        f[k]=wrk(k);
        f[k]=Max(f[k],f[k-1]);
        printf("%d\n",f[k]);
    }
}
int main(){
    init();
    return 0;
}