总之就是 | ZROI CSP连测 Day1

2023-12-11 17:54:22

「0.0」序言

没啥好说的，炸了就是了（

比赛总体还是很水的，四个题都不难。

因为属于是私题，我就简单描述一下题意，然后根据题目特点给题个名字算了。（~~但是显然是用来整活的名字~~）

因为下面要放许多代码，所以我先把缺省源放在这里（

「0.1」缺省源

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cstring>

#define lowbit(x) ((x)&(-x))
#define Heriko return
#define Deltana 0
#define Romanno 1
#define S signed
#define LL long long
#define R register
#define I inline
#define CI const int
#define mst(a, b) memset(a, b, sizeof(a))
#define ON std::ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

template<typename J>
I void fr(J &x)
{
    short f(1);x=0;char c=getchar();
    
    while(c<'0' or c>'9')
    {
        if(c=='-') f=-1;
        
        c=getchar();
    }
   
    while (c>='0' and c<='9') 
    {
        x=(x<<3)+(x<<1)+(c^=48);
       
        c=getchar();
    }
   
    x*=f;
}

template<typename J>
I void fw(J x,bool k)
{
    if(x<0) x=-x,putchar('-');
   
    short stak[35],top(0);
   
    do
    {
        stak[top++]=x%10;
        x/=10;
    }
    while(x);
   
    while(top) putchar(stak[--top]+'0');
   
    k?puts(""):putchar(' ');
}

「1.0」这么小为什么不手玩呢

T1 是个小模拟（

「1.1」题目简述

定义函数 \(A(i)\) 是对 \(A(i-1)\) 的描述，\(A(1)=1\)。

如 \(A(2)=11\)，表示上一项有一个一。

以此类推，\(A(3)=21,A(4)=1211,A(5)=111221\cdots\)

求 \(A(n),(n \le 25)\)。

「1.2」思路简述

没啥好说的，我们按照题意模拟即可。

~~当然这题本身不大，\(n=25\) 时也不到 2000 位，手玩也能玩出来（~~

「1.3」Code

int a[2000],n;

struct node
{
    int cnt,id;
}

co[2000];

int lco,la(2);

void DFS(int x)
{
    if(!x)
    {
        for(R int i(1);i<=lco;++i) printf("%d%d",co[i].cnt,co[i].id);
        Heriko;
    }

    int tot(1);lco=0;

    for(R int i(2);i<=la+1;++i)
        if(a[i]!=a[i-1]) co[++lco]=(node){tot,a[i-1]},tot=1;
        else ++tot;

    int j(1);

    for(R int i(1);i<=lco;++i,j+=2) a[j]=co[i].cnt,a[j+1]=co[i].id;

    la=(lco<<1);

    DFS(x-1);
}

S main()
{
    fr(n);

    a[1]=a[2]=1;

    DFS(n-2);

    Heriko Deltana;
}

「2.0」严格递增为什么要二分呢

挺普通的一道题。

「2.1」题意简述

给出一个严格递增的序列 \(B\)，求每次修改之后序列中是否存在满足 \(B_i=i\) 的位置，修改是单纯的区间加。

询问次数 \(q \le 1000\)，序列长 \(n \le 10^7\)。

「2.2」思路简述

严格递增为什么不二分呢？

大概的思路就是在最一开始将 \(B_i\) 减去其标号 \(i\)，用树状数组维护一个差分序列，最后二分去找解。

判断是不是解，即从树状数组 \(Query\) 的结果和序列中的数相加是否为 \(0\) 即可。

「2.3」Code

CI MXX=1e7+5;

int k,n,t[MXX],a[MXX];

bool flag;

I void Modify(int x,int v) {while(x<=n) 
t[x]+=v,
x+=lowbit(x);}

I int Query(int x) {int res(0);while(x) res+=t[x],x-=lowbit(x);Heriko res;}

I bool Checker()
{
    int l(1),r(n);

    while(l<=r)
    {
        int mid((l+r)>>1);
        int temp(a[mid]+Query(mid));
        
        if(!temp) Heriko Romanno;
        else if(temp>0) r=mid-1;
        else l=mid+1;
    }
    Heriko Deltana;
}

S main()
{
    fr(k),fr(n);

    for(R int i(1);i<=n;++i)
    {
        fr(a[i]);a[i]-=i;

        if(!a[i]) flag=1;
    }

    if(flag) puts("YES");
    else puts("NO");

    for(R int i(1);i<k;++i)
    {
        int l,r,v;
        fr(l),fr(r),fr(v);
        Modify(l,v),Modify(r+1,-v);

        if(Checker()) puts("YES");
        else puts("NO");
    }

    Heriko Deltana;
}

「3.0」RMQ 为什么不写挂呢

考场因为这题写挂导致心态炸裂 \(400 \to 100\)。

「3.1」题意简述

给出一个序列，每次询问求区间 \([l,r]\) 中出现次数为奇数的数的个数。

「3.2」思路简述

这题莫队做很显然了罢，板子。

现在想来，当时没写对可能是忘记了要减去贡献……

「3.3」Code

template<typename J>
I J Habs(const J &x) {Heriko x>0?x:-x;}

CI NXX=1e5+5,QXX=1e5+5,MXX=1e5+5;

int q,n,sn,a[NXX],ans[QXX],cnt[MXX],now,l(1),r;

struct questions
{
    int l,r,id;

    bool operator < (const questions &x) const
    {
        if(l/sn!=x.l/sn) Heriko l<x.l;
        if((l/sn)&1) Heriko r<x.r;
        Heriko r>x.r;
    }
}

ques[QXX];

I void Add(const int &x)
{
    if(cnt[a[x]]&1) ++now;
    else --now;
    
    ++cnt[a[x]];
}

I void Del(const int &x)
{
    --cnt[a[x]];

    if(cnt[a[x]]&1) --now;
    else ++now;
}

S main()
{
    fr(n);sn=sqrt(n);

    for(R int i(1);i<=n;++i) fr(a[i]);

    fr(q);

    for(R int i(1);i<=q;++i) fr(ques[i].l),fr(ques[i].r),ques[i].id=i;

    sort(ques+1,ques+1+q);

    for(R int i(1);i<=q;++i)
    {
        while(l>ques[i].l) Add(--l);
        while(r<ques[i].r) Add(++r);
        while(l<ques[i].l) Del(l++);
        while(r>ques[i].r) Del(r--);

        ans[ques[i].id]=Habs(now);
    }

    for(R int i(1);i<=q;++i) fw(ans[i],1);
    
    Heriko Deltana;
}

「4.0」结论题为什么不打表呢

一道结论题，还和之前的一道 TJOI 部分重题了（

「4.1」题目简述

求 \(n\) 个点的二叉树的叶结点的期望个数，对 \(2148473647\) 取模。

「4.2」思路简述

~~哦这模数真是太好了，GoodTek！GoodWorld！GoodRage！GoodBounce！~~

因为懒了，所以以下部分摘录于 Dfkuaid 的总结

设 \(f_n\) 表示 \(n\) 个节点的不同二叉树的个数，\(g_n\) 表示 \(n\) 个节点的 \(f_n\) 个二叉树的叶结点总数。

那么我们所求即为 \(\dfrac{g_n}{f_n}\).

显然 \(f_n\) 是 \(\operatorname{Catalan}\) 数，那么我们只需要考虑如何去求 \(g_n\)。

对于每棵 \(n\) 个点 \(k\) 个叶结点的二叉树，如果我们把这 \(k\) 个叶结点分别去掉，可以得到 \(k\) 棵不同的 \(n−1\) 个节点的二叉树；
对于每棵 \(n−1\) 个点的二叉树，我们知道有 \(n\) 个位置可以挂上一个叶结点，所以通过上面的变换，每一棵 \(n−1\) 个点的二叉树可以被得到 \(n\) 次；

于是就有 \(g_n=n \times f_{n-1}\)，也就能推出 \(\dfrac{g_n}{f_n}=\dfrac{n \times f_{n-1}}{f_n}\).

又因为 \(f_n=\dfrac{C^n_{2n}}{n+1}\),因此：

\[\dfrac{g_n}{f_n}=\dfrac{n \times f_{n-1}}{f_n} = \dfrac{n(n+1)}{2(2n-1)} \]

「4.3」Code

const LL MOD(2148473647);

I LL FstPow(LL x,LL y)
{
    LL res(1);

    while(y)
    {
        if(y&1) res=(res*x)%MOD;
        x=(x*x)%MOD;
        y>>=1;
    }

    Heriko res;
}

LL n;

S main()
{
    fr(n);

    fw(n*(n+1)%MOD*FstPow(2*(2*n-1),MOD-2)%MOD,1);

    Heriko Deltana;
}

「5.0」尾声

在看 \(\tt{Dfkuaid}\) 的博客的时候，发现这样一个东西：

期望得分：\(100+100+100+100=400\)

实际得分：\(100+10+100+100=310\) 血亏QwQ —— Dfkuaid

那我也来一个罢：

期望得分：\(100+100+100+100=400\)

实际得分：\(100+0+0+0=100\) 血亏QwQ —— Baka Deltana

码农公寓