LogeYOI Winter Day1题解

注：本题解代码均已开启反作弊功能。

前言

18:40比赛就开始了，$Payphinr-X$给我说的时候已经19:20了，，，

我少了40min的做题时间，以至于只拿到了150pts。

自闭了，我菜死了。

成绩单 (Rank10)

$Logey$强死了啊啊啊啊啊啊啊！

A

题面

分析

这题面对可爱的$Logey$真的不太友好（逃

显然我们可以暴力。

从题面得知，这是一棵二叉树，所以满足一个性质：

如果一个节点编号为$i$，那么它的左右子节点编号分别为$2i$和$2i+1$.

对于每一次询问，查看这个点是否为Gay点，如果不是，那么往上跳。

直到调到根节点为止。

代码

/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<iostream>
using namespace std;
namespace FastIO{
    const int BUFSIZE=1<<20;
    char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==it)
            it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==it)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)  flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)  putch('0');
        else if(res<0){
            putch('-');
            res=-res;
        } 
        int top=0;
        while(res){
            q[top++]=res%10+'0';
            res/=10;
        }
        while(top--)    putch(q[top]);
    }
} 
using namespace FastIO;
/* definitions */
const int MAXN = 2e6+7;
struct Node{
    int father;
    bool gay;
};
Node Tree[MAXN];
int n,m,q;
int Gay[MAXN];
int TO[MAXN];
bool PRINT[MAXN];
bool flag;
/* functions */
inline void DFS(int p){
    if(p==1){
        printf("srO lgy Orz\n");
        return;
    }
    while(p>1){
        if(Tree[p].gay==true){
            printf("LoGAY!\n");
            //PRINT[p]=true;
            flag=true;
            return;
        }
        p=Tree[p].father;
        //cout<<p<<" "; 
    }
    if(!flag) printf("srO lgy Orz\n");
}
int main(int argc,char *argv[]){
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x;
        scanf("%d",&x);
        Tree[x].gay=true;
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        scanf("%d",&TO[i]);
        if(TO[i]%2==0)Tree[TO[i]].father=TO[i]/2;
        else Tree[TO[i]].father=(TO[i]-1)/2;
        DFS(TO[i]);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

B

题面

分析

$Logey$怎么这么惨啊QAQ（再逃

其实看到这题，我第一反应是：

普及组考Treap！

而我只是知道Treap可以求区间第$k$小，而且还是$O(\log n)$的，具体实现，连原理我都不知道啊啊啊啊啊啊。

心态崩了，每日一崩。

但实际上不用，虽然大神犇$Logey$说可以线段树+二分

当时我心态就又崩了，我是不是学了假的线段树啊啊啊啊啊。(一定是我太菜了）

用两个堆维护求区间第$k$小值的查询。（一个大根堆，一个小根堆）

对于每一次输入的2操作，我们定义一个r=q+1,然后从r循环到q，把1操作的东西插入进大根堆，如果这时大跟堆中有$i$个元素，那么就把大根堆的堆顶push进小根堆里。

如此循环执行之后，输出小根堆堆顶即可。

附图自行理解：

代码

/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
/* definitions */
const int MAXN = 2e6+7;
priority_queue<int,vector<int>,greater<int> > MinQ;
priority_queue<int> MaxQ;
int Buck[MAXN];
int n,m,q;
int r=1;
/* functions */
inline void Queue(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&Buck[i]); 
    for(int i=1;i<=m;i++){
        scanf("%d",&q);
        for(int j=r;j<q;j++){
            MaxQ.push(Buck[j]);
            if(MaxQ.size()==i){
                MinQ.push(MaxQ.top());
                MaxQ.pop();
            }
        }
        r=q+1;
        printf("%d\n",MinQ.top());
        MaxQ.push(MinQ.top());
        MaxQ.pop();
    }
    return;
}
int main(int argc,char *argv[]){
    freopen("bucket.in","r",stdin);
    freopen("bucket.out","w",stdout);
    Queue();
    fclose(stdin);
    fclose(stdout);
    return 0;
}

C

题面

分析

首先我们一眼就能找到$m=0$的规律。

inline void init(){
    int ans=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        ans+=x;
    }
    for(int j=1;j<=m;j++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        Add_Edge(a,b,c);
        Add_Edge(a,b,c)
    }
    printf("%d\n",ans);
}

其他90pts

$Menci$大爷不肯给我讲啊啊啊啊啊，怎么办啊啊啊啊啊啊，
一定是我太菜了，滚~

THE END