wweiyiのblog

洛谷 P5679 P5482 [P1972][https://www.luogu.com.cn/blog/yexiaofeng/#type=题解] AT5759 ThREE

【学习笔记】线段树浅谈 线段树，顾名思义，就是一棵树，上面的每个节点由一个“线段”构成，然后组成了一棵除去了最后一层外，是完全二叉树的树，又叫区间树，作用主要是单点修改，区间修改和区间查询，这里拿线段树的区间和来举例子 线段树的构建 线段树是一棵完全二叉树，我们可以可以按照与二叉堆相似的储存节点的方式，根节点为k，左子树为k<<1,右子树则为k<<1|1,因为树是递归定义的，所以我们开始递归建树。 1.建立结构体，用于存树 因为完全二叉树对应一个长度为a的区间，它需要的节点个数为4a，因此，我们要把树的大小开到区间长度的四倍 12345const int maxn=1000010;struct tree{ int l,r; long long dat,add,mul;}t[maxn*4+5]; 2.建立上传 因为每次建一棵树，父节点都要有相对应的数据更新，因此我们需要pushup来上传子节点的数据 1234void pushup(int k){ t[k].dat=(t[k<<1].dat+t[k<<1|...

信 大写的信 敬启 ​ 你好！ ​ 岁月流逝匆匆，不带走一朵云彩。时光飞奔熙攘，不带来一丝无奈。 ​ 真好啊，期末考试终于结束了，大家也都非常开心吧。特别是你，你考了一个比较好的成绩，可能是高中以来最好的成绩了吧（并没有别的意思，不要曲解）。我呢，呵呵，我考的比较炸，这几天可能处于伤心之中吧。诚然，我的确是“害人终害己”，对不起，因为我的打扰让你没有考到更高的成绩，没有我的打扰的话可能你们已经进入年级前十了吧。 ​ 这个学期过得真快啊，快得抓不到时间的尾巴，拾不到飘飘落的木叶，看不到天边的晚霞，看不到漫天的繁星，看不到那“皎皎空中孤月轮”。在这么快的一个学期中，话说也经历了很多事情呢。开学的军训，流下了快乐的汗水；军训汇报表演，拿到了丰硕的成果；广播操比赛，舞出了我们的风采；五中112周年庆典，感受着历史的底蕴；田径运动会，使我们更加团结；演讲比赛，让语言在智慧中迸发；元旦晚会，告别了过去的悲伤，迎来新的一年；期末考试，总结了过去的一个学期，为这个学期画上了一个句号。 ​ 总书记说过：“时代的潮流浩浩荡荡，历史的车轮滚滚向前，历史只会眷顾坚定者、奋进者、搏击者，而不会等待犹豫者、...

【比赛重现】从NOIP2004说开去 今天做题目，有很多题目都不会，距离今年的NOIP也只有一两百天的时间了，对于自己的水平我也是知晓的，不可能在今年有很好的成绩，但是我还是要坚持下去，毕竟，不到最后，什么也说不准。经过一些思考，我认为，真题是最重要的，只有准确把握的真题的方法与思路，才能真正地掌握一场比赛的全貌，因此，今天，从NOIP2004说开去 相对而言，NOIP2004是比较简单的，并且，这是我出生的那一年，既然，我是从那一年开始的，那么，我的故事便从2004年开始。 T1 津津的储蓄计划 【问题描述】 津津的零花钱一直都是自己管理。每个月的月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。 为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20%还给津津。因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。 例如11月初津津手中还有83元，妈妈给了津津300元。津津预计11月的...

NOI Online2021第一场游记 0 准备 2021年3月27日，一个美妙的早上，我从我温暖的被子里滚了出来，走向了襄阳五中的大门，内心踌躇：这可能是我最后一次参加NOI Online了，但是不慌，因为此时学校俨然已经被封锁起来，变成了公务员考试的考场。我从旁边的宁静湖穿过，走了比平时多了大约一倍的路程直达我的竞赛场地——大成楼，有诗云： 大成楼里集大成，大成楼旁小成生，小小大大大小成，小小大大状元名 好不费力，我从一层的电梯起步坐到五层，然后从五层的楼梯爬到六层，这里就是我所在的机房了——只有我一个人的机房。 拿出钥匙，我将钥匙插进门锁中，前后倒腾了几下，门开了，里面散发出一股灰尘的味道，我知道，是我上周月考，没有进去，已经布满灰尘了。进门之后向右转，打开电闸，快到墙的时候，又及时来了一个急转弯，走到倒数第二排的电脑面前，放下书包，踱到窗旁，打开窗户，迎接这一天的新鲜空气。 电脑缓缓地开了，滴滴的声音和窗外公务员考试的广播声加大了比赛的真实感觉，让我身临其境， 时间一分一秒地过去，终于到了8：30这个时间，题目发下来了 1 提高组 T1 愤怒的小N 鸽 T2 积木小赛...

NOI Online2021第一场游记 0 准备 2021年3月27日，一个美妙的早上，我从我温暖的被子里滚了出来，走向了襄阳五中的大门，内心踌躇：这可能是我最后一次参加NOI Online了，但是不慌，因为此时学校俨然已经被封锁起来，变成了公务员考试的考场。我从旁边的宁静湖穿过，走了比平时多了大约一倍的路程直达我的竞赛场地——大成楼，有诗云： 大成楼里集大成，大成楼旁小成生，小小大大大小成，小小大大状元名 好不费力，我从一层的电梯起步坐到五层，然后从五层的楼梯爬到六层，这里就是我所在的机房了——只有我一个人的机房。 拿出钥匙，我将钥匙插进门锁中，前后倒腾了几下，门开了，里面散发出一股灰尘的味道，我知道，是我上周月考，没有进去，已经布满灰尘了。进门之后向右转，打开电闸，快到墙的时候，又及时来了一个急转弯，走到倒数第二排的电脑面前，放下书包，踱到窗旁，打开窗户，迎接这一天的新鲜空气。 电脑缓缓地开了，滴滴的声音和窗外公务员考试的广播声加大了比赛的真实感觉，让我身临其境， 时间一分一秒地过去，终于到了8：30这个时间，题目发下来了 1 提高组 T1 愤怒的小N 鸽 T2 积木小赛...

月考周考联考屡战屡败，但是我也屡败屡战，有的时候考好，有的时候考砸，导致我的心态极不稳定，因此，决定一劳永逸，在这里写一个考试考炸了之后看了之后心情会十分舒畅，然后鼓起信心继续向前奋斗的书，也可以叫做信，美其名曰：给自己的信。 时代的潮流浩浩荡荡，历史的车轮滚滚向前，我们需要奋斗，搏击，努力，但是在学习生活中不免会遇到这样那样的挫折，比如月考考炸了，而且是前所未有的排名，因此我们首先应该反思，为什么会考砸，考砸的原因是什么呢，不要怪老师给你批错了，就是你自己的问题，如果是老师批错了的话，为什么有那么多人的分比你高呢，说明是你的能力不行，你用功用的不到位，但凡功用到了，题目练熟练了，不管怎么考，你都能写对，所以不要埋怨别人，要想一想自己的原因。想完自己的原因之后你要知道如何去调整，去总结原因，为什么呢？这次考试之前是否因为复习不到位呢，是否跟别人聊天过火呢，还是这个月有一些怠惰呢，在考试之后，一场失败的考试可以把这些问题全部反应出来，让你有机会去进步，去超越别人，去成就自我，这样的考试才是有意义的，但你又要说别人考好了怎么办，你难道就要落后于别人了吗？不是的，落后于别人只是针对于这...

【解题报告】洛谷P1896 [SOCI2005]互不侵犯 题目描述 在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。 注：数据有加强（2018/4/25） 输入格式 只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N） 输出格式 所得的方案数 输入输出样例 输入 #1 13 2 输出 #1 116 思路 互不侵犯是一道非常经典的 状态压缩Dp的题目（最主要我最近在练习状态压缩DP） 为什么不能用搜索呢，因为状态数量太多了，是一个指数级别的大爆搜，肯定不能过，而且，这个棋盘的某个格子放不放棋子是两个状态，0不放，1放，因此我们可以使用一个十进制数来表示一个二进制数，而二进制数又是一串数字，正好是由0和1组成的一个串，在看N≤9N\leq 9N≤9，因此存的下，所以我们用一个二进制数来表示每一行的状态，然而有一些状态是无用的，我们可以预处理一下（想一想，为什么） 预处理好每一行的状态之后，我们继续处理相邻两行之间的状态，处理方...

图论笔记 图 图的定义 图G是一个有序二元组(V,E)，其中V称为点集，E称为边集 无向图、有向图： 无向图：所有边都是无向边 有向图：存在一条边是有向的图 (上文为简单理解) 图的概念 **度：**一个顶点的度指的是与该顶点相关联的边的边的条数，顶点v的度称为d(v). **入度、出度：**对于有向图来说，一个顶点的度可以细分为入度和出度。一个顶点的入度指的是与其相关联的各边中，以其为终点的边数；出度则是相对的概念，指以该顶点为起点的边数。 **自环：**如果一条边的两个顶点为同一顶点，那么这个边就称为自环 **路径：**在一个图上遍历，所遍历的点叫路径 **环：**如果路径的出发点和路径的结束点一样，那么这个路径就叫做环 **简单路径：**每个点最多只走一次的路径，在简单路径中，点是不可以重复的 **简单环：**去掉起点之后，是一个简单路径，这样的环叫做简单环 特殊的图 **没有环的无向图（无环无向连通图）：**树 n个点的树有n-1条边 —>无环无向图：森林 —>无环连通图：外向树、内向树 **外向树：**树上的的所有边的方向都是向叶子节点指的 **内向树：**...

希望人没事