青岛市程序设计竞赛冲刺⑦（2022市北区程序设计竞赛小学组试题）

1.2的N次方

原题：

 解题思路：

送分题，找规律，不妨看出，有2,4,8,6的规律，直接运算即可

AC代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int x;//0<x<1000000000 ²»ÓÃÌØÅÐ0µÄÇé¿ö 
int main(){
	freopen("count.in","r",stdin);
	freopen("count.out","w",stdout);
	while(cin>>x){
		int p=x%4;
		if(p==0)cout<<"6\n";
		else if(p==1)cout<<"2\n";
		else if(p==2)cout<<"4\n";
		else cout<<"8\n";
	}	
	return 0;
}

2.连续自然数的和

原题：

解题思路：

先求出前缀和sum，再用map记录每一个和的出现次数，最后累加计算即可

AC代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+5;
map<int,int>mp;
int n,k,a[N],ans=0,sum[N];
int main(){
	freopen("sum.in","r",stdin);
	freopen("sum.out","w",stdout);
	mp[0]=1;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
		mp[sum[i]]++;
	}
	for(int i=1;i<=n;i++)if(mp[sum[i]-k])ans+=mp[sum[i]-k];
	cout<<ans;
	return 0;
}

3.栈桥旅游

原题：

解题思路：

大模拟，按题目要求模拟，用sum记录船的承重，ans取MAX(sum)就是答案

AC代码：

#include<bits/stdc++.h>
#define max(a,b) (a>b?a:b)
#define ll long long
using namespace std;
const int N = 1e5+5;
ll sum=0,ans=0;
int n,m,W,w[N],a;
bool flag[N];
int main(){
	freopen("zhanqiao.in","r",stdin);
	freopen("zhanqiao.out","w",stdout);
	memset(flag,0,sizeof(flag));
	cin>>n>>m>>W;
	for(int i=1;i<=n;i++)cin>>w[i];
	for(int i=1;i<=m;i++){
		cin>>a;
		ans=max(ans,sum);
		if(!flag[a]&&sum+w[a]<=W)sum+=w[a],flag[a]=1;
		else if(flag[a])sum-=w[a],flag[a]=0;
	}
	cout<<ans;
	return 0;
}

4.投喂修狗

原题：

 解题思路：

把修狗的高度想做一座山峰，先求出“谷底”，再从“谷底”向两边遍历，遍历完必定有没遍历到的地方，记录下来，接着遍历第二次，最后累加求得答案

AC代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e4+5;
int n,a[N],ans,b[N];
vector<int>s;
struct node{
	int l,r;
}m[N];
signed main(){
	freopen("dog.in","r",stdin);
	freopen("dog.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	if(a[1]<a[2])s.push_back(1);
	for(int i=2;i<n;i++)if(a[i]<a[i-1]&&a[i]<a[i+1])s.push_back(i);
	if(a[n]<a[n-1])s.push_back(n);
	for(int i=0;i<s.size();i++){
		int beg=s[i];
		b[beg]=1;
		for(int j=beg+1;a[j]>a[j-1]&&j<=n;j++)b[j]=max(b[j],b[j-1]+1);
		for(int j=beg-1;a[j]>a[j+1]&&j>=1;j--)b[j]=max(b[j],b[j+1]+1);
	}
	int i,tot=0;
	for(i=1;i<=n;i++){
		if(!b[i]){
			tot++;
			m[tot].l=i;
			int j;for(j=i+1;!b[j]&&j<=n;j++);
			m[tot].r=j-1;
			i=m[tot].r;
		}
	}
	for(int i=1;i<=tot;i++){
		for(int j=m[i].l;j<=m[i].r;j++){
			if(a[j]==a[j-1])if(a[j]==a[j+1]||a[j]<a[j+1])b[j]=1;
			if(a[j]>a[j-1])b[j]=b[j-1]+1;
		}
		for(int j=m[i].r;j>=m[i].l;j--){
			if(b[j])continue;
			if(a[j]==a[j+1])b[j]=1;
			if(a[j]>a[j+1])b[j]=max(b[j],b[j+1]+1);
		}
	}
	for(int i=1;i<=n;i++)ans+=b[i];
	cout<<ans;
	return 0;
}