[2022年蓝桥杯C/C++ A组]个人做题记录

碎碎念

欸嘿，鸽了小半年

去做了一些不喜欢的事情，但兜兜转转，还是acm最香捏

求和

题意

求\(\sum_{i=1}^n\sum_{j=1}^n a_i*a_j (i!=j)\)

题解

感觉是去年的时候笨人唯一做满分的题……
经典前缀和，设\(sum[i]=\sum_{j=i}^na[j]\)，答案即为\(\sum_{i=1}^{n-1}a[i]*sum[i+1]\)

#define int long long
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=n;i>=1;i--)
	{
		if(i==n) sum[i]=a[i];
		else sum[i]=a[i]+sum[i+1];
	}
	int ans=0;
	for(int i=1;i<n;i++)
	{
		ans+=a[i]*sum[i+1];
	}
	cout<<ans;
}

选数异或

妙妙题，没有任何算法和数据结构的东东，纯思维

题意

给定n,m,x(x非负)，给出a[1]到a[n]，m次询问a[l]到a[r]内有无一对数字异或为x，若有输出yes，否则输出no

题解

边读边处理，对于每一个数字a[i]，记录其最新出现位置last[a[i]]=i
可以找到其左侧最近的和其异或为x的数字\(a[i]\oplus x\)，位置即为\(last[a[i]\oplus x]\)
设dp[i]为 a[1]~a[i]所有满足异或为x的数对中左边的数的最大位置，则$$dp[i]=max(dp[i-1],last[a[i]\oplus x])$$
则查询[l,r]时只需查看dp[r]是否>=l即可。
注意在更新dp[i]后再更新last[a[i]]，否则针对x=0的cornerCase会死得很惨

void solve()
{
	cin>>n>>m>>x;
	for(int i=1;i<=2000000;i++) last[i]=-1,dp[i]=-1;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		int b = x^a[i];
		dp[i]=max(dp[i-1],last[b]);
		last[a[i]]=i;
	}
	for(int i=1;i<=m;i++)
	{
		int l,r;cin>>l>>r;
		if(dp[r]>=l) puts("yes");
		else puts("no");
	}
}

爬树的甲壳虫

题目和题解都看懂了，比去年的自己多了一点期望dp芝士，可惜不能独立做出来，也很难独立推出来，，
待补

青蛙过河

去年水了一个二分+暴力判断做法，复杂度爆表，不知道过了几组

设跳跃能力距离为y，只要所有长度为y的区间都满足石头高度总和为2*x，则一定有解，否则无解