第七次训练课总结

B3957 [GESP202403 三级] 完全平方数

这道题就是求a[i]+a[j]是否是是完全平方数，也就是让我们求a[i]+a[j]是否等于y*y，所以我们可以把a[i]+a[j]赋值为sum，然后求sum的开平方根强转int型的2次方是否为等于sum，如果等于那么代表sum的开平方根是整数，也就是完全平方数。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
long long n,a[N],ans,sum ;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			sum=a[i]+a[j];
            if((int)sqrt(sum)*(int)sqrt(sum)==sum){//判断是否是是完全平方数
                ans++;
            }
		}
	}
	cout<<ans;
	return 0;
}

P2689 东南西北

这道题就是求我们能顺东南西北判断t次后我能不能到目的地，如果能那么输出走了几步。

如果为东那么x++，然后sum++。

如果为西那么x–，然后sum++，

如果为北那么y++，然后sum++，

如果为南那么y–，然后sum++，

最后如果到了就输出sum。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
long long x,y,l,r,n,sum=0;
char s;
int main(){
	cin>>x>>y>>l>>r;
	cin>>n;
	while(n--){
		cin>>s;
		if(s=='E'){ //东
			if(l>x){
				x++;
				sum++;
			}
		}
		else if(s=='N'){ //北
			if(r>y){
				y++;
				sum++;
			}
		}
		else if(s=='W'){ //西
			if(l<x){
				x--;
				sum++;
			}
		}
		else if(s=='S'){//南
			if(r<y){
				y--;
				sum++;
			}
		}
	}
	if(x==l&&y==r){
		cout<<sum;
		return 0;
	}
	cout<<"-1";
	return 0;
}

P6568 [NOI Online #3 提高组] 水壶

这道题就是让我们求前k+1个水壶的最大值，所以我们可以用前缀和来作，我们可以先求出前缀和sum[i]=sum[i-1]+a[i],然后再求c[i]-c[i-k-1]的最大值。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,k,a[N],c[N];
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		c[i]=c[i-1]+a[i];//求前缀和
	}
	int maxx=INT_MIN;
	for(int i=k-1;i<=n;i++){
		int t=c[i]-c[i-k-1];
		maxx=max(maxx,t);//求最大值
	}
	cout<<maxx;
	return 0;
}

P5594 【XR-4】模拟赛P5594

这道题就是让我们求一天要准备多少套卷子，如果一样就算一次，所以我们可以用2维桶来存，如果他等于！=0，那么代表它之前出现过那么把他+1。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
long long n,a[1005][1005],m,x,k,ans,sum;
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>x;
			a[x][j]=1;
		}
	}
	for(int i=1;i<=k;i++){
		ans=0;
		for(int j=1;j<=m;j++){
			if(a[i][j]!=0){//判断之前是否出现过
				ans++;
			}
		}
		cout<<ans<<" ";
	}
	
	return 0;
}

P12176 [蓝桥杯 2025 省 Python B] 书架还原

这道题就是让我们按照顺序把书摆回去，然后输出摆了多少遍，所以这道题我们可以用桶来作，把t[a[i]]=i,然后判断a[i]是否为i，不等于i就swap交换位置然后sum++，最后输出sum。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
long long n,a[N],t[N],x,sum=0;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
        t[a[i]]=i;//桶数组
	}
	for(int i=1;i<n;i++){
		if(a[i]!=i){//判断是否为i
			t[a[i]]=t[i];
			swap(a[i],a[t[i]]);//交换位置
    		sum++;
		}
		
	}
	cout<<sum;
	return 0;
}