昨天晚上又选了一套div2
题面巨长 导致昨天一半的时间都在划水 摸鱼hhh 甩个锅先
一共就过了两题 b题过的时候都两点了 就睡了
c d等会再补把
A. Nastya and Rice
题目思路
直接求出两个区间的范围 在比较就好了 大水题
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#define pi 3.1415926535898
#define ll long long
#define lson rt<<1
#define rson rt<<1|1
#define eps 1e-6
#define ms(a,b) memset(a,b,sizeof(a))
#define legal(a,b) a&b
#define print1 printf("111\n")
using namespace std;
const int maxn = 1e5+10;
const int inf = 0x1f1f1f1f;
const ll llinf =1e17+10;
const int mod = 2333;int main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);int t;scanf("%d",&t);while(t--){int n,a,b,c,d;scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);int l1=(a-b)*n;int r1=(a+b)*n;int l2=c-d;int r2=c+d;if(r1<l2||l1>r2)printf("NO\n");elseprintf("YES\n");}
}B. Nastya and Door
题目思路
用前缀和处理出每个区间的峰的数量
在遍历每个长度为k的区间就好了
因为题目说峰如果在区间端点 那么它就不是这个区间的峰
所以特判一下两个端点是否是峰值
这种题目每次写起来都挺费劲的
之前还想着记录每个峰值的坐标 在倒推区间起点
写了好久写不出来 还是太菜了
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#define pi 3.1415926535898
#define ll long long
#define lson rt<<1
#define rson rt<<1|1
#define eps 1e-6
#define ms(a,b) memset(a,b,sizeof(a))
#define legal(a,b) a&b
#define print1 printf("111\n")
using namespace std;
const int maxn = 2e5+10;
const int inf = 0x1f1f1f1f;
const ll llinf =1e17+10;
const int mod = 2333;int a[maxn],sum[maxn];
int main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);int t;scanf("%d",&t);while(t--){ms(sum,0);int n,k,cnt=0;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}a[0]=inf;a[n+1]=inf;for(int i=1;i<=n;i++){if(a[i]>a[i-1]&&a[i]>a[i+1]){sum[i]++;}}for(int i=1;i<=n;i++)sum[i]+=sum[i-1];int maxx=0,index=1;for(int i=1;i<=n-k+1;i++){int tem=sum[i+k-1]-sum[i];if(a[i]>a[i-1]&&a[i]>a[i+1])tem--;if(a[i+k-1]>a[i+k-2]&&a[i+k]<a[i+k-1])tem--;if(tem>maxx){maxx=tem;index=i;}}printf("%d %d\n",maxx+1,index);}
}
c d待补