「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