【杂记】2020年3月8日

这是默子几年前写的博客，仅留作纪念！

早上 9：30

迷迷糊糊地吃了一碗方便面，又打开了电脑。

熟悉的洛谷，熟悉的DevCpp

第一件事是，用民间数据把昨天NOI Online的代码测试了下

25+0+0

哇，心态瞬间爆炸……

（第一题明明有50的啊，第二题怎么又爆0了，第三题意料之中）

还是要调整好自己的心态，毕竟自己是真的蒟蒻,

短时间菜一点可以容忍，但绝不能容忍长时间的菜！！！

---

上午 10：30

今天距离省选还有——21天啊

调整好心态继续加油。。。

学着学着，突然发现，树状数组给我整蒙圈了

以前就是会打板子，今天花了我好长时间总于搞懂其中的原理的lowbit操作是个什么鬼了！

众所周知，树状数组可以维护区间和

比如给我们一个 num[ ] 数组，长度为 n。

并且我们打算把它加到我们的树状数组 tree[ ] 中去

如下图

树状数组修改插入操作

void update(int x,int a){
    //x是插入的位置
    //a是要插入的值
    while(x<=n){
        tree[x]+=a;
        x += lowbit(x);
        //也就是 x = x&-x
    }
}

假设 \(x=1\)，\(n=8\)，\(a=5\)，则

tree[1] += 5
tree[2] += 5
tree[4] += 5
tree[8] += 5

lowbit() 返回的是 \(x\) 在二进制表示下，末尾第一个遇到的 1 和在该位置之前的 0 的情况，比如：

0001   1   lowbit(1) = 1
0010   2   lowbit(2) = 2
0011   3   lowbit(3) = 1
0100   4   lowbit(4) = 4
0101   5   lowbit(5) = 1
0110   6   lowbit(6) = 2
0111   7   lowbit(7) = 1
1000   8   lowbit(8) = 8

给定一个数字 5201314，

其二进制表示为 100 1111 0101 1101 1010 0010，

关心最后两位 100 1111 0101 1101 1010 00**10**，

即二进制的 2。因此，lowbit(5201314) = 2。

至于具体的运算参考手边二进制运算课本，没有？那百度啊

什么，你要求和5到12区间内的和？？？

树状数组区间求和(从x到1)操作如下

int sum(int x){
    //x还是位置
	int ans = 0;
	while(x){
		ans += treen[x];
		x -= lowbit(x);
	}
	return ans;
}

ans = sum(12) - sum(5-1); //这样就可以求出5到12区间内的和了

很颓很颓的一上午，虽然我知道我可能上面没太讲清

但是那又有什么关系呢，这只是一篇类似于 日记 的东东

后日记：这里的讲解还是进行了一定的修改，使其更加通顺易读。同时改成了\(\LaTeX\)的数学公式，更加美观了。

---

中午 13：20

吃了一大盘鸡肉+两碗米饭 (具体菜名叫不上来)

来了客人，家里把以前的旧车卖了，来的是买车的人

说实话，他们都认识我，我不认识他们，233333

关上卧室门，逍遥自在

后日记：真的好能吃

---

下午 14：00

刚准备打开游戏，看看沙雕可爱的 羽羽音小鸟(はばね ことり)

以及开朗温柔的 姫城扬羽(ひめぎ あげは)

突然想起来有洛谷月赛啊……淦！

(因为我太弱，所以只做了Div2)

T1 第一眼还以为是八皇后问题，但仔细一看……什么嘛，入门组水题

20分钟愉快切掉 (中间边界条件搞错WA了两次)

T2 明显是道数学结论题，一开始写了个O(K)的算法上去

果不其然，TLE掉最后一组数据

思考了好久，推了下式子

\(\text{(n+1) * pow(2,k)}\)

鉴于k比较大，写个快速幂水过去了

T3 卡了 我两个小时

各种瞎搞算法都用过，好像是DP，但是也用前缀和搞过

最后DFS暴力14分，果断滚粗

T4 没看……

当时居然连T3都刷不过去，ε=(´ο｀*)))唉，虽然现在也刷不过去，甚至有可能T2都刷不过去，阿巴巴。

---

傍晚 19：00

打开了Steam，心不在焉地玩着 If My Heart Had Wings

羽羽音小鸟(はばね ことり)

无聊中解答了几个问题，推进了下剧情

记忆化搜索？(×)

瞎搞 (√)

---

晚上 22：00

关掉了游戏，写下博客

决定当个日更博客主

后来，还是没有日更成功，哈哈哈哈哈