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;
}