欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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=Dep[x]+Dep[y]2Dep[LCA(x,y)]

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