NOI

[NOI2021] 轻重边 具体思路 树剖维护一下即可。 Code #include<bits/stdc++.h> using namespace std; const int N=1e5+5; struct edge{ int x,y,pre; }a[2*N]; int last[N],alen; ......

首先要明确，对于一个结点，其儿子的遍历顺序是确定的，在 DFS 序和 BFS 序中相同。 而 BFS 序更容易确定一棵树的深度，只需要知道在哪些结点分了层。 所以可以通过 DFS 序来确定 BFS 中的分层方案。 然后分类讨论： \(BFS_u+1=BFS_v\)，\(DFS_u>DFS_v\)，相 ......

P6185 首先考虑只有 \(t=2\) 的情况，我们发现假如把读入的所有边连成一张图，则在同一联通块的点可以通过不断传递做到一个 \(+1\) 一个 \(-1\) ，也就是说在这个联通块内的点的和是不会改变的，因此让这个联通块内 \(a_i=b_i\) 就等价于 \(\sum a_i = \sum ......

[NOI2010] 超级钢琴 题解 说点闲话 原本不想写这个题解的 但是看到我的代码居然长度为2048B->刚好2KiB，然后还跟题号相同QAQ 题目翻译 给你一段序列，求出其中从第\(1\)大到第\(k\)大的子区间的和。 思路解析 首先可以想到一个简单的暴力，对于每一个区间开头\(i\)，和区间 ......

题目描述 公元11380年，一颗巨大的陨石坠落在南极。于是，灾难降临了，地球上出现了一系列反常的现象。当人们焦急万分的时候，一支中国科学家组成的南极考察队赶到了出事地点。经过一番侦察，科学家们发现陨石上刻有若干行密文，每一行都包含5个整数： 1 1 1 1 6 0 0 6 3 57 8 0 11 3 ......

洛谷传送门 LOJ 传送门 两条路径的交点数量只和起点数量有关。容易发现是终点排列的逆序对数的奇偶性。求一个 \(f_{i, j}\) 表示从第 \(1\) 层的第 \(i\) 个点到第 \(k\) 层的第 \(j\) 个点的路径数量，对这个矩阵求行列式即可。 对于相交的路径数不用考虑，因为总存在和 ......

NOI2017-游戏-2sat https://www.luogu.com.cn/problem/P3825 题意：有三种赛车A，B，C，以及用字符串 \(s\) 描述的地图，\(s_i=a/b/c\) 表示第 \(i\) 个地图不能用对应的 A/B/C 类型的赛车， \(s_i=x\) 表示可以选 ......

D1T1 回家路线 好久之前写的，忘了具体细节，但是发现有平方项所以考虑拆项之后斜率优化。 D1T2 机器人 考虑 DP。 记 \(f_{l,r,i}\) 表示 \([l,r]\) 这段区间，最大值为 \(i\) 的方案数，同时记 \(g_{l,r,i}=\sum\limits_{j=1}^if_{ ......

免责声明：考试当天不用 VMware，用 VituralBox，但我喜欢 VMware，且系统内部使用方法基本一样。 VMware 下载 NOI Linux 2.0 下载 一、安装 VMware 打开 VMware-Workstation-Lite-17.0.1-21139696-精简安装注册版.e ......

P2024 [NOI2001] 食物链 法一：种类并查集 A->B->C->A [1,n]:表示同类, [n+1,2n]：表示猎物,[2n+1,3*3]：表示天敌 点击查看代码 #include<bits/stdc++.h> using namespace std; const int N = 5e ......

写在前面 网上的东西比较多，也比较杂乱，不是很方便，所以我整合了一些关于 Noi-Linux2.0 虚拟机装机方法+代码编辑环境+实地编程的介绍，看完至少能用起来打代码了。 NOI 官网公告（JS 开始使用 Noi-Linux2.0 作为唯一操作系统）：https://www.noi.cn/gyno ......

一、NOI Linux 2.0 用法 打开终端。 Ctrl + Alt + T 进入超级管理员。 sudo su 列出当前文件夹下的子目录。 ls 进入下层文件夹 a。 cd a 在当前目录（下面同样）新建一个文件 a.cpp。 touch a.cpp 编辑 a.cpp。 gedit a.cpp 编 ......

题解 P7468【[NOI Online 2021 提高组] 愤怒的小 N】 problem 首先是有一个字符串 \(S=\texttt{"0"}\)，做无限次“将 \(S\) 的每一位取反接在 \(S\) 后面”的操作，形如 \(S=0110100110010110\cdots\)。 另外给一个 ......

P9479 [NOI 2023] 桂花树 好题！ 可以先看看这个，虽然感觉并没有什么用（ 先考虑第一条限制。 在纸上画几个图，大概可以分成以下几类（左边是原树，右边是有 \(n+m\) 个点的新树）： 黑色点表示原树上的点，蓝色点表示新加入的点。 上面三个图分别代表：新点挂在原树的一个点上成为叶节点 ......

写这篇 blog 的原因是某个小朋友要考 CSP 了还不会用 linux，怎么回事呢。 单击图片即可放大。 前置- linux 虚拟机的安装 在官网 / 其他地方下载 VMware。 在 noi 官网 下载 NOI linux 的 .iso 文件。（可能系统会把这玩意识别成压缩包，但不要闲得没事把它 ......

字符串（题解） 题目描述 近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气，让动物们凭自己的真才实学向游客要吃的，园长决定开设算法班，让动物们学习算法。 一句话题意：我们会处理kmp算法中的fail[]数组，来记录[1, i ]的真前后缀的最大 ......

二叉查找树 首先该树的中序遍历是唯一可以确定的（直接按照数据值排序即可）。 然后，因为权值可以被修改成一切实数，故我们完全可以把权值离散化掉。 于是我们现在可以设置一个 DP 状态 \(f[l,r,lim]\) 表示： 区间 \([l,r]\) 中的所有东西构成了一棵子树，且树中最小权值不小于 \( ......

又是一道锻炼代码能力的题目。 首先遇到这种求经过多少个节点的题可以先缩点，然后我们考虑那个特殊限制怎么用。 如果对于两个强联通分量 \(x\) 能到 \(z\)，\(y\) 能到 \(z\)，则 \(x,y\) 之间一定有一个限制，假设这个限制是 \(x\) 能到 \(y\)，那么我们可以只记录 \ ......

25:求特殊自然数 总时间限制: 1000ms 内存限制: 65536kB描述 一个十进制自然数,它的七进制与九进制表示都是三位数，且七进制与九进制的三位数码表示顺序正好相反。编程求此自然数,并输出显示。 输入无。输出三行：第一行是此自然数的十进制表示；第二行是此自然数的七进制表示；第三行是此自然数 ......

NOI2024省选训练赛 11 解题报告 目录NOI2024省选训练赛 11 解题报告A. 小L的栈DescriptionConstraintsSolutionConclusionB. intervalDescriptionConstraintsSolutionConclusionC. Digit ......

P2048 [NOI2010] 超级钢琴 题目链接 RMQ好题，但是不知道为啥hzoi放到了lca的题单 这道题思路想了一半然后卡了，不知道怎么处理重复贡献的问题。 然后he了眼题解，茅塞顿开。可以再次将最优分成两个，再次计算。 全程维护音符的前缀和，和区间最大值。 结构体内存最大值，左端点，右端点 ......

转载自 这里 一、Linux 的基本操作（命令行） 打开命令行 在 Noi Linux 中可以使用快捷键 Ctrl + Alt + T 打开命令行终端 Linux的目录 Linux 是没有 Windows 下硬盘分区的概念的，所有设备均会被挂载到一个统一的文件系统，Linux 下的目录有两种： 绝对 ......

题解 accoders::NOI 5510【飞翔的胖鸟（fly）】 problem 求 \(f(x)=\frac{ah}{\sin(x)}+bx\) 在 \((0,\frac\pi 2]\) 上的最小值。 solution \(\sin'(x)=cos(x); \cos'(x)=-\sin(x)\) ......

题解 accoders::NOI 5508【漂亮大厨（cook）】 part 1 区间加 \(x\)，区间询问有多少个数字 \(\leq y\)。\(n,m\leq 10^5,x\leq 200,y\leq 10^7\)。 考虑 P5356 [Ynoi2017] 由乃打扑克 的做法，分块，块内按照值 ......

题解 accoders::NOI 5511【漂亮轰炸（bomb）】 http://47.92.197.167:5283/contest/406/problem/4 BZOJ3252 是弱化版。 problem 一棵树，边带权。\(Q\) 次询问，给定 \(k\) 和一个首都点，选择 \(k\) 条路 ......

P6190 [NOI Online 1 入门组] 魔法 该题中用到的矩阵加速 Floyd 可能存在负环，但是这个题是可以用的，所以不能每次跑完之后把各个节点到自己的距离更新为 0 ！ 最外层循环才是中转站节点，不管什么时候都是这样的。特别是在矩阵乘法中，一般的矩阵相乘都是最内层循环遍历行和列，而矩阵 ......

称编号 \(> n\) 的点为新点。 由条件 1 可以推出树 \(T\) 为结点 \(1 \sim n\) 在树 \(T'\) 上的 虚树。 由条件 2 可以推出 \(\forall 1 \le u < v \le n + m, \operatorname{lca}(u, v) \le v + k\ ......

没什么好说的，一题不会。 D1T1. 面基之路 考虑瓶颈在于最后一个网友的面基时间。 Trick：可以看作 所有网友都在同一时间（显然一定也是同一位置）面基，因为各个网友和 hehe 桑本人都是独立行动，而且可以原地不动。 也就是求一个最快的集合点（包括顶点和各边的中点）。直接边转点，枚举最短路之和 ......

原题 原题中父母的走路方式为先去 \(A,B\) 中较近的一个，因此我们可以让 \(A,B\) 隔得非常远，这样他的父母就会疲于奔命 因此我们让直径的两个端点为 \(A,B\) ，枚举 \(C\) 点的位置，答案即为 \(dist(A,B)+\min(dist(A,C)+dist(B,C))\) 最 ......

来补题了昂。 D1T1 轻重边 对于原树进行重链剖分，使用一颗线段树维护每一条重边是否时“重边”，然后对于轻边，在父亲出维护最后一次通过 \(1\) 操作清空“重边”的时刻，在查询时只会遇到 \(O(\log n)\) 条轻边，直接查询这个轻边时“重边”的时刻是否晚于父亲清空的时刻即可。 D1T2 ......