私たち、 輝きたい! — Woshiluo 的 2018 总结

00 写在开头

私たち、 輝きたい!

我们,想要闪闪发光!

“2018年真的是有趣的一年呢”,Woshiluo 如是说道

说真的,别说在年初,就是在今年9月,我也想不到我现在会这样,作为一名省队选手在努力,在弱省中,书写着属于自己的篇章……

01 风平浪静的年初

一月初的时候逐渐找到了写作业的感觉,再也不用每天晚上写作业写到老晚了

期末成绩出来,英语满分?进步约100名?

寒假欢乐培训,在3&4班听金哥讲bfs,第一次发现常数问题是如此重要

在2班金哥讲了许多种类的DP,当时第一次接触邻接表,头还是晕的

暑假作业成功全部推到最后一天

期初考试,除去语文,我好像可以年级前十?

这一切听起来都是那么的有希望,仿佛只要今后一直努力下去,身上的兵二校服将会再穿五年

02 抛向湖面上的一颗石头

一次OI上课的机会,杨老师[我的Oi教练]表明了她想将我送去126中的思想,这个话题被在兵二的同班同学听到,回去报告给了班主任?

然后从此在我平静如水的生活中抛进了一块石头,至今它所引起的水波,仍未平静

兵二似乎对这个事情的反应有点大……

正当我企图一步步平静下来这些水波时,在五月份时,杨老师却也发出了最后通碟

兵二代表着稳健的前途,126中代表这遥不可及的梦想

那一阵子,我正在补Lovelive,在某一瞬间内,我也想到了自己,如果自己敢像千歌,像穗乃果一样,向着梦想奔跑,是否,也能够书写出属于自己的奇迹,属于自己的希望 ……

03 追寻着遥不可及的梦想

我最终还是选择来到了126中,每天下午过去学一下听起来很厉害的数据结构与神仙算法,实际上大家都没记住几个,但却对算法水平有了一个不易观察却很重要的提升

每天同时进行着文化课和OI的学习肯定是要付出代价的,过度的熬夜终究使自己在之后相当长一阵时间内的思维迟钝和身体不适,本来就处于亚健康的身体终究还是会隔三差五出现问题

但是那阵时间真的是相当欢乐的……

有着各种各样还算可以看清的目标,可以实现(?)的目标

那时我希望自己能够普及一等,明年参加提高,争取省队

04 宛若繁花般灿烂的暑假

暑假初每天在天百待着基本上就是语文数学OI(数学),当时`15owzLy1`大佬给我们讲数学,听说了好多自己根本没听说过的东西

杨老师告诉我7月底有个网安赛,没人去,我要不要过去凑个数,一问,吃住行参赛费用全免?去去去,西安三日游能不去吗

去了一趟西安,莫名奇妙随便写写就三等奖了?然后原来这比赛还是有奖金的?

感觉莫名奇妙减了不少rp,以及获得一个奥妙重重的称号网安选手

八月初杨老师告诉我们可以去常州集训?仔细想了想,去吧,看看内地的选手

后来被证实被虐成傻逼,不过也获得不少奇怪的加成……

不过也有负buff,养成了Oi考试睡觉的奇怪习惯……

值得一起的是我的手机成功在常州用上了内地的主板

05 接近又远离梦想的NOIP

开学以后,每天依然文化课Oi一同训练,然后 ,但是因为NOIP的原因每天培训时间加长了,身体终于还是打出了GG,要么停课要么放弃Oi,仔细想了想,我是因Oi而来,遂停课

Wahacerdalao向杨老师表明了觉得我可以参加提高组的思想,杨老师同意了这个看法

停课开始还好,过了一个月左右吧,成绩开始出现波动,然后开始疯狂爆炸,基本上每次垫底吧

连杨老师都说了,你这次还是参加普及组吧

那时感觉,自己好像选错了路,为什么不好好学文化课啊 ……

Wahacer Dalao告诉我,按照你自己的想法走就对了

仔细想了一想,还是去提高组一下,算是当经验吧,大体也不会太拉平均分

然后事情的结果就非常有意思了,详见[NOIP2018游记]

06 属于自己的未来

私たち、 輝きたい!

我们,想要闪闪发光

NOIP 成绩出来了,全省第四,XJ没有省选,直接A队

后面上了几天的课,又申请了停课,当我再坐到熟悉的电脑面前的时候,回忆起NOIP时,五味杂陈

开始几天将NOIP前埋的坑都填了(比如某个从NOIP前看到NOIP后的小说)

后来继续向前学,依然觉得什么东西不太对经,约是在12月底的时候我发现,我把Oi,学死了

开始好好认真的举一反三,锻炼思维的时候,已经是停课后两周

果然NOIP前的集训还是对我造成一定的负面心里阴影的

07 尾声

依稀记得Wahacer大佬坚持我应该参加提高组
依稀记得兵二同学们一起努力的次次活动
依稀记得常州淳朴的商店阿姨
依稀记得调到通宵图论
依稀记得调到半夜的Web
依稀记得写到深夜的作业
依稀记得看到半夜的动漫

我超额达成了自己的目标,于今年进入省队

我又有了新的目标,我想在接下来的舞台上闪闪放光

只要朝着梦想奔跑,总有一天会实现的吧?

尽自己努力,做自己最好

]]>

线段树?前缀和?主席树! — 主席树初步 — Luogu P3834 【模板】可持久化线段树 1(主席树)

值得一提的是,静态主席树比单纯的线段树求区间和要短……

0 前置技能点

  • 线段树
  • 前缀和
  • 离散化(权值线段树求第k大前置技能)
  • 正常状况下的大脑 一定的Debug能力

1 主席树

1.1 静态

1.1.1 权值线段树

我们现在看一下这个问题

区间第$k$大

我会排序!

$ N,M \leq 2e5$

我会排序!等下,时间复杂度不对

是的,显然这需要一个数据结构来维护它

我们来想想,如果只求第$k$大的话,有什么做法?

平衡树,权值线段树

加上区间查询?

我会Splay

嗯,Splay是一个比较优秀的解决方案,

但是权值线段树真的没有用武之地吗

1.1.2 可持久化

可持久化

这是一个非常有趣的名词

许多数据结构都可以可持久化

eg: 可持久化数组,可持久化平衡树,可持久化并查集等

什么是可持久化呢

可以访问历史版本的数据结构,我们通常就称其为可持久化数据结构

1.1.3 前缀和与权值线段树

我们先来回顾一下如果我们查询全局第$k$大时的步骤

  1. 离散化
  2. 按排名建立权值线段树
  3. 按照与二叉搜索树中查找第$k$大一样的方法查找并输出

有一种办法,建立 $ n^2 $ 棵线段树(枚举每个区间),但这种做法显然是不且实际的

但是如果我们仔细思考便会发现,我们对与区间$ [1,1] [1,2] [1,3] [1,4] \cdots [1,n] $ 中建立的权值线段树中的每一个节点都满足前缀和性质

也就是说我们只需要建立$n$棵权值线段树了

1.1.4 可持久化与权值线段树

到了这一步,我们的问题在空间与时间上都存在了

很明显,我们的空间有太多重复的叶子节点[区间相同,权值相同]

所以如果两个节点,它们的左节点(或者右节点)重复,我们可以将它们指向一个叶子

经过这么操作我们的时间也得到了大幅度优化,从原来的$O(n^2log(n))$变成了$O(nlog(n))$,空间也优化到$nlog(n)$

这么一来,这些线段树变成一个数据结构,我们可以访问历史版本

是的,这就是可持久化权值线段树,也称主席树

1.1.5 静态主席树

#include <cstdio>
#include <algorithm>
const int N=2e5+1e4;
int n,m,l,r,k,tcnt,idcnt;
int nid[N],rt[N],rk[N];
struct val{
    int now,id;
}a[N];
bool cmp(val a,val b){
    return a.now<b.now;
}
struct Persistable_Segment_Tree{
    int left,rig;
    int sum;
}tree[N*20];
void update(int &root,int left,int rig,int val){
    tree[tcnt++]=tree[root];
    tree[tcnt-1].sum++;
    root=tcnt-1;
    if(left==rig) return ;
    int mid=(left+rig)>>1;
    if(val<=mid) update(tree[root].left,left,mid,val);
    else update(tree[root].rig,mid+1,rig,val);
}
int query(int left_root,int rig_root,int k,int left,int rig){
    int dep=tree[tree[rig_root].left].sum-tree[tree[left_root].left].sum;
    if(left==rig) return left;
    int mid=(left+rig)>>1;
    if(k<=dep) return query(tree[left_root].left,tree[rig_root].left,k,left,mid);
    else return query(tree[left_root].rig,tree[rig_root].rig,k-dep,mid+1,rig);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
    scanf("%d",&a[i].now);
    a[i].id=i;
    }
    std::sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    rk[a[i].id]=i;
    tcnt=1;
    for(int i=1;i<=n;i++){
    rt[i]=rt[i-1];
    update(rt[i],1,n,rk[i]);
    }
    for(int i=1;i<=m;i++){
    scanf("%d%d%d",&l,&r,&k);
    printf("%d\n",a[query(rt[l-1],rt[r],k,1,n)].now);
    }
}

1.2 动态(带修)

Waiting For Updating

]]>

NOIP 2018 游记

用这篇文章,记述自己误打误撞到今天的 OI 路程

Day 0

早上一起来说是有兴Dalao随便看了看去调板子了

结果板子也没调出来,看了一天的番,就当是休息了吧….

下午去七十中看机子,感觉城里的空气竟然比郊区要好

七十中的键盘十分好用,以至于我回到机房都用不习惯自己的键盘了

晚上和15owzLy1大佬一起吃饭,回机房的路上说道:

“这场考试,我就写六道暴力”

这句话,或许是我为数不多的正面Flag

Day 1

提高组

T1: 疑似是原题目???看似还想写个暴力,发现写暴力似乎比写我印象中的正解要难写…没法对拍

T2: 上来觉得是数论,直接就开始写暴力了…写暴力的时候顺便优化了几个地方,一算复杂度貌似是正解?然而我对拍没学,于是自创对拍放后台和优化前的程序拍去了

T3: 对于m=1的部分直接树的直径,不过wahacer讲的时候我没听…自己推了一个出来,后来觉得二分和贪心可做,但是最后因为不可证否就觉得有问题就没写(现在想想不可证否不就是对的吗…血亏)

出来遇到15owzLy1大佬,讨论了一下,听他说他 t2 没写出来,但是 t3 拿了好多暴力分,感觉自己暴力还是不行

普及组

T1: 没啥可以说的,和往年一样,稍微注意一下就不会出事的题目

T2: 题面可以说是非常普及组了,说了一堆最后可以一句话题意的那种,然后我精简题意的时候出了点小问题…

T3: 上来觉得这道题是一个泛化背包…推了大半天然而什么都没有推出来,最后发现随便dp就可以的时候已经写不完了…

T4: 开始觉得哈夫曼编码可做…待我把规律找完写的时候发现…内存会爆炸,然后就弃了这道题目

出来和以前兵二的几个同学和别的几个老朋友对了一下题目,感觉不太对经…

Day 2

提高组

T1: 看到题目的时发现是个基环树…说好这个东西不考的呢?树的部分随便写了些,然后基环树部分因为可以觉得每条边走好几次然后调了半天什么都没有出来,”反正都说了只写暴力了,不写了”

T2: 数学题?暴力暴力暴力,搜索好啊

T3: 第一眼过去觉得是没有上司的舞会让后搞一些比较厉害的东西,不过本着写暴力的心态,直接树形dp走人

下午

“估算一下的话 tg大概 100+100+25+60+25+45=355?”

考完试直接去的一中,遇到Wahacer大佬,给他说了一下我的成绩,就开始疯狂说我省队稳了,当时觉得今年题目还行,可能大家都和我差不多之类的

吃了饭回来,15owzLy1回来说他分数350-400疯狂膜拜大佬

大概聊了一下,感觉好多人都能300+

After

一点NOIP后的小记

我不是jiangtao爷爷,所以自然而然的回到了和机房差一座山的126中去,即使想像15owzLy1他们一样每天到机房,感觉还是艰难

Day +8

大概是CCF说的吧,今天早上十点发布成绩

我请假到一中机房里等成绩

原来每天上午吵吵嚷嚷等着评测结果叨叨题目的人全都不见了

也就只能看到jiangtao c0per15owzLy1在非重要课程的时候翘课过来

这么说来,我似乎很难再看见高二的学长们了呢

心里难受

坐在电脑前面刷了一天官网,成绩还是没出来…

Day +9

不可能以同样的理由请两天假,于是我回到班里,忐忑不安的上了半天的课程,一出来就打开手机看到了成绩

100+100+20+68+20+24=332

感觉还行把

Day2 t3 最后五分钟改的INF结果改锅了,原地爆炸

其他的都基本上是预期以内

总结

提高组

主观问题

  • 数学能力依然有所欠缺
  • 不敢将自己的思维往下想,实现出来
  • 时间规划有细节问题

普及组

主观问题

  • 对长题面把握中心能力有所欠缺

客观问题

  • 上午提高下午普及…
  • 提高题目做多了,思考题目方向有问题
  • 键盘backspace有问题(去年是空格键有问题)

终章

借用 BeyondLimits 博客中的一段话

一个个 OIer 的竞赛生涯总是从一场 NOIP 开始,大多也在一场 NOIP 中结束,好似一次次轮回在不断上演。
如果这次 NOIP 是你的起点,那么祝你的 OI 生涯如同夏花般绚烂。
如果这次 NOIP 是你的终点,那么祝你的 OI 回忆宛若繁星般璀璨。

对于我来说,这场 NOIP 宛若我 OI 生涯中的起点,但我的 OI 生涯能否如同夏花般绚烂?

一切,交给时间,也交给自己

尽自己努力,做自己最好

]]>

玄学数学 — Luogu P1762 偶数

0x01 写在之前

题目链接: [https://www.luogu.org/problemnew/show/P1762]

这道题形象生动的说明了从几何层面来找规律是多么的方便

~~打表找规律是多么的我方便~~

0x02 题目

题目一看…

杨辉三角?

%2意义下的面积?

输出一下看看吧

1
1 1
1   1
1 1 1 1
1       1
1 1     1 1
1   1   1   1
1 1 1 1 1 1 1 1
1               1
1 1             1 1
1   1           1   1
1 1 1 1         1 1 1 1
1       1       1       1
1 1     1 1     1 1     1 1
1   1   1   1   1   1   1   1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1                               1
1 1                             1 1
1   1                           1   1
1 1 1 1                         1 1 1 1
1       1                       1       1
1 1     1 1                     1 1     1 1
1   1   1   1                   1   1   1   1
1 1 1 1 1 1 1 1                 1 1 1 1 1 1 1 1
1               1               1               1
1 1             1 1             1 1             1 1
1   1           1   1           1   1           1   1
1 1 1 1         1 1 1 1         1 1 1 1         1 1 1 1
1       1       1       1       1       1       1       1
1 1     1 1     1 1     1 1     1 1     1 1     1 1     1 1
1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 

这是在每一位都%2后只输出1后得到的结果

好好看啊wq

你为什么不试试在这里面找找规律呢?

我们可以很明显的观察到,每一个三角形都是由下面一个三角形所叠加出来的

1
11

每个第$ 2^i $ 行,就是一个三角形的结尾

每个第$ 2^i $ 行,就是由三个第 $ 1 $ 到 $ 2^{i-1} $的三角形组成

看起来第$ 2^i $ 行的结果我们可以算出来:

$$ f(1)=1 $$
$$ f(i) = f(i/2)*3 $$

整理一下:
第 $ 2^i $ 行有 $ 3^{i-1} $ 个1

恩,快速幂大法解决就可以

问题在于,不是$2^i$的怎么办?

恩,先打表找规律吧>_<

    1 : 1                1
    2 : 1 1                3
    3 : 1   1                5
    4 : 1 1 1 1                9
    5 : 1       1               11
    6 : 1 1     1 1               15
    7 : 1   1   1   1               19
    8 : 1 1 1 1 1 1 1 1               27
    9 : 1               1               29
   10 : 1 1             1 1               33
   11 : 1   1           1   1               37
   12 : 1 1 1 1         1 1 1 1               45
   13 : 1       1       1       1               49
   14 : 1 1     1 1     1 1     1 1               57
   15 : 1   1   1   1   1   1   1   1               65
   16 : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1               81
   17 : 1                               1               83
   18 : 1 1                             1 1               87
   19 : 1   1                           1   1               91
   20 : 1 1 1 1                         1 1 1 1               99
   21 : 1       1                       1       1              103
   22 : 1 1     1 1                     1 1     1 1              111
   23 : 1   1   1   1                   1   1   1   1              119
   24 : 1 1 1 1 1 1 1 1                 1 1 1 1 1 1 1 1              135
   25 : 1               1               1               1              139
   26 : 1 1             1 1             1 1             1 1              147
   27 : 1   1           1   1           1   1           1   1              155
   28 : 1 1 1 1         1 1 1 1         1 1 1 1         1 1 1 1              171
   29 : 1       1       1       1       1       1       1       1              179
   30 : 1 1     1 1     1 1     1 1     1 1     1 1     1 1     1 1              195
   31 : 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1              211
   32 : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1              243 

随便推一个吧qwq

14?

首先先找到2的次幂–8

ans+=27

剩下的相当于是 第6层 ×2

以此类推qwq

以下是代码

#include <cstdio>
#include <cmath>
const long long mod=1000003;
long long sum,ans,n;
inline long long lowbit(long long x){return x&(-x);}
inline long long ksm(long long a,long long p){// 标准快速幂
    long long res=1,base=a;
    while(p){
        if(p&1) res=(res*base)%mod;
        base=(base*base)%mod;
        p>>=1;
    }
    return res;
}
long long dfs(long long now){
    long long tmp=lowbit(now);// lowbit 用于快速找到第一个我可以分层的地方
    if(tmp==now){
        ans=ksm(3,(std::log(now)/std::log(2)));// tmp==now 说明 now 是 2的次幂 ( log 快速求指数)
        return 2; // 翻倍
    }
    else{
        long long tmp1=dfs(now-tmp);// 剪掉算过的
        ans=(ans+tmp1*ksm(3,(std::log(tmp)/std::log(2))))%mod;
        return tmp1*2;
    }
}
int main(){
    scanf("%lld",&n);
    dfs(n);
    if(n%2==0) sum=(((1+n)%mod)*((n/2)%mod))%mod;
    else sum=((((1+n)/2)%mod)*(n%mod))%mod;
    // 都说这个地方要乘法逆元之类的高端操作...我就直接暴力了
    printf("%lld",((sum-ans)%mod+mod)%mod);
}
]]>

倍增/ST表/离散化–NOIP 2012 提高组 开车旅行

0x01 写在之前

题目链接:https://www.luogu.org/problemnew/show/P1081

前置技能: ST表 双向链表 倍增 离散化

一看省选/NOI-又是NOIP的题目,我们就大概可以知道这又是一个代码难度较高的高级暴力
▄︻┻┳═一…… ☆<(= ̄□ ̄=!)>

我们将会有以下几种方法优化暴力

  • 转化问题
  • 倍增 / 二分/ 数论优化 反正我是不会
  • 数据结构

那么,先看题目吧

0x02 题目

经过简单的分析题目,我们可以知道,看起来需要预处理了,毕竟看起来并没小于等于$O(m\log(n))$的在线算法

离线的话,倍增和ST表是$O(\log(n))$的

哪我们需要预处理什么呢

  • 我们需要知道在每个点时小A小B分别会前往哪里,已经在$2^j$后到达哪里
  • 以及到达每一步需要的步数

不太好做?

这个时候就应该祭上离散化,在排序并离散化后我们可以快速的通过双向链表快速的求出小A小B将会前往何处及前往的距离

剩下的东西就是ST表的东西了

0x03 代码

#include <cstdio>
#include <algorithm>
const int N=110000;
inline int Aabs(int a){return a>0?a:0-a;}
struct ci{
    int l,r,id,now,hei;
}c[N];
int n,m,pre,nxt,now,ans,p;
int nid[N],next_a[N],next_b[N],sta[N][25],stb[N][25],f[N][25];
long long x,dis_a,dis_b;
double Min=2147483647;
// helper functions start
// cmp(ci a,ci b)
// sort helper functions
// return bool
bool cmp(ci a,ci b){
    return a.hei<b.hei;
}
// fir()
// find tht nearst
// return bool
inline bool fir(){
    if(pre==0) return true;
    if(nxt==0) return false;
    return c[nxt].hei-c[now].hei<c[now].hei-c[pre].hei;
}
// sec(int x,int y)
// find second nearst in a and b
// x > now y < now
// return int
// - the second nearst's id
inline int sec(int x,int y){
    if(x==0) return c[y].id;
    if(y==0) return c[x].id;
    if(c[x].hei-c[now].hei<c[now].hei-c[y].hei) return c[x].id;
    else return c[y].id;
}
// get_dis(long long x,int p)
// Get the dis_a ans dis_b
// - x the Max distance
// - p start
// return void
inline void get_dis(long long x,int p){
    dis_a=dis_b=0;
    for(int j=20;j>=0;j--){
        if(f[p][j]&&(long long)dis_a+dis_b+sta[p][j]+stb[p][j]<=x){
            dis_a+=sta[p][j];
            dis_b+=stb[p][j];
            p=f[p][j];
        }
    }
    if(next_a[p]&&dis_a+dis_b+sta[p][0]<=x) dis_a+=sta[p][0];
}
// helper funtions end
// readin()
// readin
inline void readin(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&c[i].hei);
        c[i].id=i;
    }
}
// init()
// find pre and nxt / Discretization
inline void init(){
    std::sort(c+1,c+n+1,cmp);
    for(int i=1;i<=n;i++){
        nid[c[i].id]=i;
        c[i].l=i-1;
        c[i].r=i+1;
    }
    c[1].l=c[n].r=0;
    for(int i=1;i<=n;i++){
        now=nid[i];pre=c[now].l;nxt=c[now].r;
        if(fir()) next_b[i]=c[nxt].id,next_a[i]=sec(c[nxt].r,pre);
        else next_b[i]=c[pre].id,next_a[i]=sec(nxt,c[pre].l);
        if(pre) c[pre].r=nxt;
        if(nxt) c[nxt].l=pre;
    }
}
// make_st()
// make st table
inline void make_st(){
    for(int i=1;i<=n;i++){
        f[i][0]=next_b[next_a[i]];
        sta[i][0]=Aabs(c[nid[i]].hei-c[nid[next_a[i]]].hei);
        stb[i][0]=Aabs(c[nid[next_a[i]]].hei-c[nid[f[i][0]]].hei);
    }
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            f[i][j]=f[f[i][j-1]][j-1];
            sta[i][j]=sta[i][j-1]+sta[f[i][j-1]][j-1];
            stb[i][j]=stb[i][j-1]+stb[f[i][j-1]][j-1];
        }
    }
}
// Ans_all()
// find Max of dis_a / dis_b
inline void Ans_all(){
    scanf("%lld",&x);
    for(int i=1;i<=n;i++){
        get_dis(x,i);
        if(Min>(1.0*dis_a/dis_b)){
            Min=1.0*dis_a/dis_b;
            ans=i;
        }
    }
    printf("%d\n",ans);
}
// Ans()
// get ans of all ask
inline void Ans(){
    scanf("%d",&m);
    while(m--){
        scanf("%d%lld",&p,&x);
        get_dis(x,p);
        printf("%lld %lld\n",dis_a,dis_b);
    }
}
int main(){
    readin();
    init();
    make_st();
    Ans_all();
    Ans();
}
]]>

树形背包 — Luogu P1273 有线电视网

0x01 写在开头

题目链接:[https://www.luogu.org/problemnew/show/P1273]

前置技能 : 树形DP

如果做过选课的话,想必各位一看到就知道这是一道树形DP的题目

0x02 题目

题目中要求我们在以收入$\geq 0$的前提下,支持尽可能多的叶子节点

因此我们可以这么定义一个类似背包状态转移方程
$$
f(now,i+j)=max(f(now,i+j),f(son,j)+f(now,i)-val)
$$
这不就是背包吗<(=°д)ノ

边界条件
$$
f(i,j)=-INF(0\leq i \leq N,0 \leq j \leq M)
$$
设为$-INF$是为了防止无法转移

看起来很显然是吧

让我们来看看代码:

0x03 代码

#include <cstdio>
#include <cstring>
const int N=3100;
inline int Max(int a,int b){return a>b?a:b;}
int _case;
int ans,v,w,n,m,son[N];
int f[N][N];
// edge start
struct edge{
    int to,next,val;
}e[N];
int ehead[N],ecnt;
inline void add_edge(int now,int to,int val){
    ecnt++;
    e[ecnt].to=to;
    e[ecnt].val=val;
    e[ecnt].next=ehead[now];
    ehead[now]=ecnt;
}
// edge end
// dfs start
void dfs(int now){
    if(now>n-m){// 只有用户才会算到叶子节点中
        son[now]=1;
        return ;
    }
    f[now][0]=0;
    for(int u=ehead[now];u;u=e[u].next){
        dfs(e[u].to);
        for(int i=son[now];i>=0;i--){
            for(int j=1;j<=son[e[u].to];j++){// 注意循环顺序,不这么循环会重复计算一些东西
                f[now][i+j]=Max(f[now][i+j],f[now][i]+f[e[u].to][j]-e[u].val);
            }
        }
        son[now]+=son[e[u].to];
    }
}
// dfs end
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n-m;i++){
        scanf("%d",&_case);
        while(_case--){
            scanf("%d%d",&v,&w);
            add_edge(i,v,w);
        }
    }
    memset(f,-0x3f,sizeof(f));
    for(int i=1;i<=m;i++) scanf("%d",&f[n-m+i][1]);
    dfs(1);
    for(int i=1;i<=m;i++){
        if(f[1][i]>=0) ans=i;
    }
    printf("%d",ans);
}
]]>

单模式串匹配算法 — KMP

KMP

看毛片KMP算法

KMP算法作为一个单模式串匹配算法,以$ O(n+m) $ 的时间复杂度俯视众生吊打各路匹配算法

但是其扩展性的艰难和通用性的低下往往很少用于项目中的实现,但对于我们Oier来说速度才最重要的
KMP的代码量并不大,思维难度也并非其他玄学算法那么高,时间也很优秀,是一种值得用于搞事情的算法

算法理念

传统匹配

在普通的查询算法中,我们通常采用一下的方法:

int ans=0;
for(int i=0;i<alen;i++){
    int t=0;
    while(1){
        if(t>=blen) break;
        if(a[i+t]!=b[t]) break;
        t++;
    }
    if(t>blen) ans++;
}
模式串: ab
文本串: fdsfdfdvab

emmmmm $ O(n) $??优秀

模式串: sb
文本串: sssa

$O(nm)$???什么状况?

好吧,我们知道了,这个东西最快$O(n)$,最慢…$O(nm)$

KMP匹配

显然如果我们在上面的第二个例子中
我们如果能知道,我现在失配了,应当直接更改当前s在模式串中的位置就可以高效的完成匹配

为此,我们定义一个next数组,用「自己匹配自己」的思想,快速找到,当我们适配失败的时候,迅速找到这一位可能在模式串中的位置

这样就避免了往回的问题,大大降低了时间复杂度–$O(n+m)$

代码实现

题目链接: [https://www.luogu.org/problemnew/show/P3375]

#include <cstdio>
#include <cstring>
using namespace std;
int kmp[11000000];
char a[1100000],b[1100000];
int main(){
    scanf("%s",a+1);
    scanf("%s",b+1);
    int alen=strlen(a+1);
    int blen=strlen(b+1);
    int k=0;
    for(int i=2;i<=blen;i++){
        while(k>0&&b[i]!=b[k+1]) k=kmp[k];
        if(b[i]==b[k+1]) k++;
        kmp[i]=k;
    }
    k=0;
    for(int i=1;i<=alen;i++){
        while(k>0&&a[i]!=b[k+1]) k=kmp[k];
        if(a[i]==b[k+1]) k++;
        if(k==blen) {printf("%d\n",i-blen+1);k=kmp[k];}
    }
    for(int i=1;i<=blen;i++) printf("%d ",kmp[i]);
}

KMP 求最小循环节

「KMP这个算法,一般很少考板子题,他通常会给你出一些思维型的,比如,next数组的妙用….」

Next数组的思想不单在KMP中很有用,在对付其他字符串处理问题甚至多模式串匹配中,我们仍将见到他的身影

比如求一个串的最小循环节

很显然len-next[len]即为循环节长度

  • 如果$ len \mod len-next_{len} = 0 $ 则表明字符串是完全由循环解循环构成
  • 如果不是说明需要添加,如果设循环节长度为$L$,则添加的字母个数$ L-len%L = L-next[len]%L $

当然不止这些,至于还有什么吗wq你总会遇到的啦

End

最后,祝rp++

]]>

[SDOI2011]染色 — 树链剖分

0x01 写在之前–树链剖分

什么是树链剖分?可以吃吗?

树链剖分 – Luogu P3384 [模板] 树链剖分

在链接中的博文中,我们已经说明什么为树链剖分以及树链剖分的用处

很明显,树链剖分可以处理:

  • 两个点之间的最短路径上的操作[LCA可部分替代/LCT万能]
  • 子树之间的操作[DFN序可替代]

由于我们已经将一棵树变成了多条链,且编号是连续的,所以我们就可以转化成各种RMQ问题,然后各种东西瞎整

显然大多数情况线段树,都比较靠谱,但是如果是线段树,就不得不说到两个大头:pushuppushdown

大多数的比较毒瘤难的线段树,就在pushuppushdown上..

0x02 题目

题目链接:[https://www.luogu.org/problemnew/show/P2486]

在两个点的最短路径上操作?树剖!

但是…它求颜色怎么弄?

当然是在两个大头上弄

我们注意序号的连续和树上的连续是相同的,所以说我们可以在线段树上存三个值:

  • 左端点颜色
  • 右端点颜色
  • 总颜色段数量

然后在合并的时候考虑两个左右是否相等即可

查询时同理

0x03 代码

#include <cstdio>
using namespace std;
const int N=100010;
const int M=100010;
int n,m,u,v,x,y,z;
int col[N],ncol[N];
char op[3];
// edge start
struct edge{
    int to,next;
}e[M<<1];
int ecnt,ehead[N];
// 标准建树
inline void add_edge(int now,int to){
    ecnt++;
    e[ecnt].to=to;
    e[ecnt].next=ehead[now];
    ehead[now]=ecnt;
}
// edge end
// Heavy-Light Decompostion start
// Heavy-Light Decompostion 树链剖分
// 树链剖分板子
int son[N],dep[N],mson[N],fa[N];
void dfs1(int now,int la,int depth){
    fa[now]=la;
    dep[now]=depth;
    int Max=-1;
    for(int i=ehead[now];i;i=e[i].next){
        if(e[i].to==la) continue;
        dfs1(e[i].to,now,depth+1);
        son[now]+=son[e[i].to]+1;
        if(son[e[i].to]>Max){Max=son[e[i].to];mson[now]=e[i].to;}
    }
}
int id[N],top[N],idcnt;
void dfs2(int now,int la){
    id[now]=++idcnt;
    ncol[id[now]]=col[now];
    if(top[now]==0) top[now]=now;
    if(son[now]==0) return ;
    top[mson[now]]=top[now];
    dfs2(mson[now],now);
    for(int i=ehead[now];i;i=e[i].next){
        if(e[i].to==la||e[i].to==mson[now]) continue;
        dfs2(e[i].to,now);
    }
}
// Heavy-Light Docompostion end
// Segment Tree start
// 线段树
struct T{
    int left,rig,colnum;
}tree[N<<2];
int lazy[N<<2];
inline void pushup(int now){
    tree[now].colnum=tree[now<<1].colnum+tree[now<<1|1].colnum;
    if(tree[now<<1].rig==tree[now<<1|1].left) tree[now].colnum--;// 中间相等就一定要减一
    tree[now].rig=tree[now<<1|1].rig;tree[now].left=tree[now<<1].left;
}// 上传标记注意
inline void pushdown(int now){// 下传标记
    if(lazy[now]!=0){
        tree[now<<1].left=tree[now<<1].rig=tree[now<<1|1].left=tree[now<<1|1].rig=lazy[now];
        tree[now<<1].colnum=tree[now<<1|1].colnum=1;
        lazy[now<<1]=lazy[now<<1|1]=lazy[now];
        lazy[now]=0;
    }
}
void build_tree(int now,int left,int rig){// 建树
    if(left==rig){
        tree[now].rig=tree[now].left=ncol[left];
        tree[now].colnum=1;
        return ;
    }
    build_tree(now<<1,left,(left+rig)>>1);
    build_tree(now<<1|1,((left+rig)>>1)+1,rig);
    pushup(now);
}
void change_col(int now,int left,int rig,int from,int to,int val){
    if(from<=left&&rig<=to){// 更改颜色
        tree[now].rig=tree[now].left=val;
        tree[now].colnum=1;
        lazy[now]=val;
        return ;
    }
    pushdown(now);
    int mid=(left+rig)>>1;
    if(from<=mid) change_col(now<<1,left,mid,from,to,val);
    if(to>mid) change_col(now<<1|1,mid+1,rig,from,to,val);
    pushup(now);
}
int query_col(int now,int left,int rig,int from,int to){// 查找颜色段
    if(from<=left&&rig<=to) return tree[now].colnum;
    pushdown(now);
    int mid=(left+rig)>>1,res=0;
    if(from<=mid) res+=query_col(now<<1,left,mid,from,to);
    if(to>mid) res+=query_col(now<<1|1,mid+1,rig,from,to);
    if(from<=mid&&to>mid&&tree[now<<1].rig==tree[now<<1|1].left) res--;
    pushup(now);
    return res;
}
inline int find_col(int now,int left,int rig,int en){// 单点查找
    if(left==rig&&left==en) return tree[now].left;
    int mid=(left+rig)>>1;
    pushdown(now);
    pushup(now);
    if(en<=mid) return find_col(now<<1,left,mid,en);
    if(en>mid) return find_col(now<<1|1,mid+1,rig,en);
    return 0;
}
// Segment Tree end
// Answer start
inline void ask_change(int left,int rig,int col){// 更改
    while(top[left]!=top[rig]){
        if(dep[top[left]]<dep[top[rig]]){
            int tmp=left;
            left=rig;
            rig=tmp;
        }
        change_col(1,1,n,id[top[left]],id[left],col);// 区间修改
        left=fa[top[left]];
    }
    if(id[left]>id[rig]){
        int tmp=left;
        left=rig;
        rig=tmp;
    }
    change_col(1,1,n,id[left],id[rig],col);
}
inline int ask_colnum(int left,int rig){// 询问
    int res=0;
    while(top[left]!=top[rig]){
        if(dep[top[left]]<dep[top[rig]]){
            int tmp=left;
            left=rig;
            rig=tmp;
        }
        res+=query_col(1,1,n,id[top[left]],id[left]);
        int ta=find_col(1,1,n,id[top[left]]);
        int tb=find_col(1,1,n,id[fa[top[left]]]);// 单个颜色查找
        if(ta==tb) res--;// 相邻减一
        left=fa[top[left]];
    }
    if(id[left]>id[rig]){
        int tmp=left;
        left=rig;
        rig=tmp;
    }// 上面已经把该减的都减过了,这里就不用减掉了
    res+=query_col(1,1,n,id[left],id[rig]);
    return res;
}
// Answer end
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&col[i]);
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        add_edge(u,v);
        add_edge(v,u);
    }
    dfs1(1,0,1);
    dfs2(1,0);
    build_tree(1,1,n);
    while(m--){
        scanf("%s",op);
        if(op[0]=='C'){
            scanf("%d%d%d",&x,&y,&z);
            ask_change(x,y,z);
        }
        else if(op[0]=='Q'){
            scanf("%d%d",&x,&y);
            printf("%d\n",ask_colnum(x,y));
        }
    }
}


]]>

繁忙过后,一切归平 — 2018 暑假总结

0x01 写在前头

这次的暑假,从中国学生的角度来说可能更本就不是放假,下面这张表是关于我整个暑假的大概情况:

  • 7.1-7.14 天百数学&&信竟
  • 7.14-7.19 一中竞赛机房日常培训
  • 7.20-7.22 西安电子科技大,全国中学生网络安全竞赛
  • 7.23-8.6 一中竞赛机房日常培训
  • 8.6-8.22 江苏常州信息学竞赛集训
  • 8.22-9.1 一种竞赛机房日常培训
  • 9.2 报道

哇我这一个暑假都在干些什么

1×01 数学方面

这个暑假,在数学方面有不少的新知识的输入

  • 7.1-7.14 天百数学

这个是被我们信息学竞赛老师拉过去的,他们高一预科….楞是把我拉上了

知识点:

  • 弧度制
  • 函数的周期性,单调性,奇偶性
  • 指数函数&&对数函数
  • 三角函数入门
  • 集合的交并补

显然,这些知识对我目前还没有什么用,但是在计算机方面学到的东西就比较多:

  • 计算几何初步
  • 排列组合/卡特兰数
  • gcd的各种特性
  • 反演入门
  • 博弈论和SG函数
  • 欧拉函数与积性函数
  • 欧拉筛/线性筛
  • 乘法逆元
  • 高斯消元
  • 矩阵乘法/矩阵快速幂

这些东西考的就比较有用了qwq

经常见到

1×02 信息学方面

数据结构:

  • 平衡树入门
  • 树链刨分
  • 可持久化线段树入门
  • 单调队列/栈

图论:

  • 最大/小生成树
  • 2-sat
  • 网络流入门
  • tarjan

暴力搜索:

  • meet in the middle
  • 玄学剪枝(可行化剪枝&&最优化剪枝)
  • 迭代加深

加强了基础:

  • 二分
  • 线段树
  • 排序

1×03 其他方面

1x03x01 在考试/竞赛方面

  1. 睡眠得当,过多过少过度打乱作息都是大忌
  2. 会不会,先写暴力 有一点是一点,不拿百不拿
  3. 相信自己

1x03x02 其他方面

  1. 假期作业要早规划>_<
  2. 有钱人的家庭难以理解
  3. 不能为利是图,你的心思跟你待久了,别人都会明白
  4. 有其父必有其子
  5. 多和基层人打好关系

2×00 写在最后

这个暑假实际上,比上课的时候还要忙许多,不过,俗话说的好:”痛并快乐着。”你做了什么,就会收获什么

尽自己努力,做自己最好

相信这个世界和你自己

]]>

20180813 考试 解题报告&&题解

T1 吃蛋糕

标准解答就是一看就知道的exgcd

然而本蒟蒻没有看出来写了个错误的小学奥数的解法…

T2 01 串

首先如果你思想没有什么问题的化,30% 的分数还是很好拿上的

标准解答字符串hash

先求出Hash,然后STL强行维护匹配一下…

T3 没有上司的舞会

对于另 30%数据,满足每个会员要么没有上司,要么没有下属。

t

这一部分的数据点就非常的显然了…

维护上司数和下属数,输出最大即可

标准解答玄学网络流,我是真的写不来了wq

]]>