lp5077 Tweetuzki 爱等差数列

令首项为\(x\),长度为\(l\)由等差数列求和式可得:
$$s=\frac{l(l-1)}{2}+l*x$$
故,题意等价于求:
使得式子:
$$2s=l(l-1+2x)$$
成立的最小\(x\)
即求使得式子成立的最大\(l\)
又,易知:
$$l<\sqrt{2s},s\le10^{12}$$
故,
$$l<10^{6}$$
显然这个复杂度是可以接受的。

#include<iostream>
#include<cstdio>
#include<cmath>
long long s;
inline void init(){
	scanf("%lld",&s);
	long long ans=0,len;
	for(long long i=1;i*i<=2*s;++i){
		if((2*s%i==0)&&(2*s/i-i+1>0)&&((s-(i*(i-1)/2))%i==0)){
			len=i;ans=((2*s)/i-i+1)>>1;
		}
	}
	printf("%lld %lld",ans,ans+len-1);
}

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

lp5079 Tweetuzki 爱伊图

看似是一道暴力模拟题,实际上是一个技巧性模拟题。
我们注意到,对于除了2和5以外的所有的数,它们的每一列的#数量都是不同的,故而我们可以用1代表”#”,0代表”.”,然后跑一遍求和即可。
对于2和5,我们特殊处理,暴力扫描即可。

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

char lst[12][100005];
int lst2[100005][12];
int cnt[100005];
int r,c;

inline bool cmp(int A,int B){
	return A>B;
}

void init(){
	scanf("%d%d",&r,&c);
	for(int i=1;i<=r;++i){
		for(int j=1;j<=c;++j){
			std::cin>>lst[i][j];
		}
	}
	for(int i=1;i<=r;++i){
		for(int j=1;j<=c;++j){
			lst2[j][i]=lst[i][j]=='#'?1:0;
		}
	}
	for(int i=1;i<=c;++i){
		std::sort(lst2[i]+1,lst2[i]+1+r,cmp);
	}
	for(int i=1;i<=c;++i){
		for(int j=1;j<=r;++j){
			cnt[i]+=lst2[i][j];
		}
	}
	int cnt1=0,cnt2=0,cnt3=0;
	for(int i=1;i<=c;++i){
		if(!cnt[i]){
			cnt1=cnt2=cnt3=0;
		}else{
			cnt1=cnt[i],cnt2=cnt[i+1],cnt3=cnt[i+2];
			if(cnt1==5&&!cnt2){
				printf("1");
			}else{
				if(cnt1==4&&cnt2==3&&cnt3==4){
					bool bo=0;
					for(int j=1;j<=r;++j){
						if(lst[j][i]=='.'&&lst[j][i+1]=='.'&&lst[j][i+2]=='#'){
							bo=1;
						}else if(lst[j][i]=='#'&&lst[j][i+1]=='.'&&lst[j][i+2]=='.'){
							if(bo){
								printf("2");
							}else{
								printf("5");
							}
							break;
						}
					}
				}else if(cnt1==3&&cnt2==3&&cnt3==5){
					printf("3");
				}else if(cnt1==3&&cnt2==1&&cnt3==5){
					printf("4");
				}else if(cnt1==5&&cnt2==3&&cnt3==4){
					printf("6");
				}else if(cnt1==1&&cnt2==1&&cnt3==5){
					printf("7");
				}else if(cnt1==5&&cnt2==3&&cnt3==5){
					printf("8");
				}else if(cnt1==4&&cnt2==3&&cnt3==5){
					printf("9");
				}else if(cnt1==5&&cnt2==2&&cnt3==5){
					printf("0");
				}
				i+=2; 
			}
		}
	}
}

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