6月练习赛Round1 总结
程序员文章站
2024-03-18 22:59:40
...
6月练习赛Round1 总结
总结
1.简单题也不会做……DP和贪心简直是我的克星
2.题做少了,导致做题速度贼慢,眼看着比赛结束时间逼近,代码还没敲完。那是多么绝望的心情TAT
A 饥饿的奶牛
代码短得我都觉得好笑…然而就是给我一万年我也写不出来。只要考DP,立马GG
老祖宗,该打,该打!
B 平衡的队列
竟然暴力卡到了90
正解是前缀和,只不过遇到0的时候要变成-1求前缀和。前缀和数组为A[x],当A[i]==A[j]时,[i+1,j]中的0,1数量相等。
C 颜色间距
想出了正解,然而写完代码连样例都没时间过了…在A题上卡了1.5h
结论:若两个同颜色的点之间的间距最大,那么其中有一个必定是深度最深的那个点。
预处理出每种颜色深度最深的点p,然后依次把每个点拿去和对应颜色的p点求距离。
D 和谐数
树状数组搞一下就可以了
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 101000
using namespace std;
struct node{int x,id;}in[N];
bool cmp(node a,node b){return a.x<b.x;}
int Tree[N];
int Lowbit(int x){return x&(-x);}
int getsum(int x){
if(!x)return 0;
int Ans=0;
for(int i=x;i;i-=Lowbit(i))Ans+=Tree[i];
return Ans;
}
void Modify(int x,int d){
if(!x)return;
for(int i=x;i<N;i+=Lowbit(i))Tree[i]+=d;
}
int f1[N],f2[N];
int main(){
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)
{scanf("%d",&in[i].x);in[i].id=i;}
sort(in+1,in+n+1,cmp);
for(int i=1;i<=n;i++){
int k=in[i].id;
f1[k]=k-getsum(k)-1;//left max
Modify(k,1);
}
reverse(in+1,in+n+1);
memset(Tree,0,sizeof(Tree));
for(int i=1;i<=n;i++){
int k=in[i].id;
f2[k]=getsum(n)-getsum(k-1);
Modify(k,1);
}
int Ans=0;
for(int i=1;i<=n;i++)
if(max(f1[i],f2[i])>2*min(f1[i],f2[i]))Ans++;
printf("%d",Ans);return 0;
}