2022第十三届蓝桥杯省赛A组C++游记

A组，当然是 很 蓝 的 啦

答案是n*m+3，无法节省步数

先手必败

无论先手怎么下，必定可以转化为

xxxo

oooo

然后，如果先手下第一行，后手就可以下第二行中间两个

xxxx

oxxo

必败

如果先手下第二行，则后手必定可以把第二行转化为oxxx或xxxo

xxxo 或 xxxo

oxxx xxxo

必败

有种不好的预感啊，“必败”

 水，代码：

#include
#define LL long long
int main()
{
	LL sum=0,sum2=0;
	int n,i,x;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&x);
		sum=sum+1ll*x;
		sum2=sum2+1ll*x*x;
	}
	printf("%lld",(sum*sum-sum2)/2);
	return 0;
}

 有点懵了

想到了可持久化01Trie树

突然发现可以离线

于是就写了莫队

代码：

#include
#include
#include
using namespace std;
inline int gi()
{
	char c;int num=0,flg=1;
	while((c=getchar())<'0'||c>'9')if(c=='-')flg=-1;
	while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}
	return num*flg;
}
#define N 100005
#define D 320
struct node{
	int l,r,id;
	bool operator < (const node &t)const{
		return l/Dq[i].l){
			l--;
			ans+=1ll*tong[a[l]];
			tong[a[l]^x]++;
		}
		while(r>q[i].r){
			tong[a[r]^x]--;
			ans-=1ll*tong[a[r]];
			r--;
		}
		while(l0)res[q[i].id]=1;
	}
	for(i=1;i<=m;i++)
		if(res[i])printf("yes\n");
		else printf("no\n");
	return 0;
}

 完了完了，概率期望我最菜

欸，好像还挺可做的

设f[i]为从i走到n的期望步数

于是可以列出方程f[i]=f[i+1]*(1-p[i+1])+f[0]*p[i+1]+1

然后f[n]=0

迭代带入之后，可以得到f[0]=A*f[0]+B

移项除一下就完事了

代码：

#include
#include
#include
using namespace std;
const int mod=998244353;
int ksm(int x,int y)
{
	int ret=1;
	while(y){
		if(y&1)ret=1ll*ret*x%mod;
		y>>=1;x=1ll*x*x%mod;
	}
	return ret;
}
#define N 100005
int p[N];
int main()
{
	int n,x,y,i;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d%d",&x,&y);
		p[i]=1ll*x*ksm(y,mod-2)%mod;
	}
	int a=p[n],b=1;
	for(i=n-1;i>=1;i--){
		a=1ll*a*(1ll-p[i]+mod)%mod;
		b=1ll*b*(1ll-p[i]+mod)%mod;
		a=(a+p[i])%mod;
		b=(b+1)%mod;
	}
	a=(1-a+mod)%mod;
	printf("%d",1ll*b*ksm(a,mod-2)%mod);
}

 这个真的不太会了（2333

首先，正着走和倒着走是一样的

其次，我们可以把2x次，看成一次性走2x只青蛙

二分答案是显然的

但是怎么验证呢？可以考虑，对于任意两个石头i,i+1之间的空隙

 从区间[i-Y+1,i]中，所有青蛙必须有落脚点，所以，任意长度为y的范围中的石头都需要满足

H之和大于等于2x

但是这只是必要条件，所以我猜这是充要条件

代码：

#include
#include
#include
using namespace std;
#define LL long long
LL a[100005];
int main()
{
	int n,x,i,l,r,mid;
	scanf("%d%d",&n,&x);x*=2;
	a[1]=x;
	for(i=2;i<=n;i++){
		scanf("%lld",&a[i]);
		a[i]+=a[i-1];
	}
	l=1;r=n;
	while(l>1;
		bool flg=0;
		for(i=1;i<=n;i++){
			if(1ll*x>a[i]-a[max(i-mid,0)]){
				flg=1;
				break;
			}
		}
		if(flg) l=mid+1;
		else r=mid;
	}
	printf("%d",l);
}

 没思维含量，直接主席树吧

完了，不会写

突然发现可以在反向DP的时候顺带查询答案

所以用树状数组就够了

代码：

#include
#include
#include
using namespace std;
inline int gi()
{
	char c;int num=0,flg=1;
	while((c=getchar())<'0'||c>'9')if(c=='-')flg=-1;
	while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}
	return num*flg;
}
#define N 100005
#define M 1000000
#define LOG 21
int a[N],f[N],g[N];
int tre[M+50];
void update(int x,int k)
{
	while(x<=M){
		tre[x]=max(tre[x],k);
		x+=(x&-x);
	}
}
int getmax(int x)
{
	int ans=0;
	while(x){
		ans=max(ans,tre[x]);
		x-=(x&-x);
	}
	return ans;
}
int n,K;
int main()
{
	int i;
	n=gi();K=gi();
	for(i=1;i<=n;i++)
		a[i]=gi();
	for(i=1;i<=n;i++){
		f[i]=getmax(a[i])+1;
		update(a[i],f[i]);
	}
	memset(tre,0,sizeof(tre));
	int ans=f[n-K]+K;
	for(i=n;i>=K+1;i--){
		g[i]=getmax(M-a[i]+1)+1;
		update(M-a[i]+1,g[i]);
		ans=max(ans,f[i-K-1]+K+getmax(M-a[i-K-1]+1));
	}
	printf("%d",ans);
}

 恶心大模拟

不想写，最后还是写了

先按长度排序

再把L范围内的点插入set中，按极角坐标排序

然后依次扫描即可

一堆细节和特判，估计还会卡精度

代码：

#include
#include
#include
#include
#include
using namespace std;
inline int gi()
{
	char c;int num=0,flg=1;
	while((c=getchar())<'0'||c>'9')if(c=='-')flg=-1;
	while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}
	return num*flg;
}
#define N 100005
const double eps=1e-9;
const double PI=3.14159265358979;
inline double geta(double x,double y)
{
	if(fabs(x)=-eps) return 0;
		else return PI;
	}
	if(x>=eps) return PI/2-atan2(y,x);
	else return PI+PI/2-atan2(y,x);
}
struct node{
	double x,y,z;
	int id;
	bool operator < (const node &t)const{
		return geta(x,y) S;
set::iterator it;
bool cmp(node &a,node &b)
{
	return 1ll*a.x*a.x+1ll*a.y*a.y<1ll*b.x*b.x+1ll*b.y*b.y;
}
int ans[N];
int main()
{
	int n,i,j;double L;
	n=gi();L=gi();
	for(i=1;i<=n;i++){
		a[i].x=gi();
		a[i].y=gi();
		a[i].z=gi();
		a[i].id=i;
	}
	sort(a+1,a+n+1,cmp);
	now.x=0.0;now.y=L;
	for(i=1,j=1;i<=n;){
		while(j<=n&&sqrt(a[j].x*a[j].x+a[j].y*a[j].y)<=L){
			S.insert(a[j]);
			j++;
		}
		int o=i;
		it=S.lower_bound(now);
		if(it==S.end()){
			now.x=0.0;now.y=L;
			it=S.lower_bound(now);
			if(it==S.end())
				break;
		}
		node tmp=(*it);
		double tmpL=sqrt(tmp.x*tmp.x+tmp.y*tmp.y);
		tmp.x/=tmpL;tmp.y/=tmpL;
		
		ans[(*it).id]=o;i++;
		L+=tmp.z;
		now.x=tmp.x*L;now.y=tmp.y*L;
		S.erase(it);
		while(j<=n&&sqrt(a[j].x*a[j].x+a[j].y*a[j].y)<=L){
			S.insert(a[j]);
			j++;
		}
		bool flg;
		do{
			flg=0;
			
			it=S.lower_bound(now);
			node tmp2=(*it);
			if(it==S.end()){
				now.x=0.0;now.y=L;
				it=S.lower_bound(now);
				if(it==S.end())
					break;
			}
			double tmpL=sqrt(tmp2.x*tmp2.x+tmp2.y*tmp2.y);
			tmp2.x/=tmpL;tmp2.y/=tmpL;
			if(fabs(tmp2.x-tmp.x)

#include
#include
#include
int a[105],p[105],pcnt;
int tong[100];
int main()
{
	int T,n,i,j;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		pcnt=0;
		for(i=2;i<=int(sqrt(1.0*n)+0.5);i++){
			if(n%i==0){
				a[++pcnt]=i;
				do{p[pcnt]++;n/=i;}while(n%i==0);
			}
		}
		if(n!=1)
			printf("no\n");
		else{
			memset(tong,0,sizeof(tong));
			int cnt=0;
			for(i=pcnt;i>=1;i--){
				if(!tong[p[i]]){
					for(j=p[i];j<=100;j+=p[i])
						tong[j]=1;
					cnt++;
				}
			}
			if(cnt<=2)
				printf("yes\n");
			else printf("no\n");
		}
	}
}