Spring Garden

P6824 「EZEC-4」可乐题目背景很久以前，有一个 pigstd，非常迷恋美味的可乐。为了得到美味的可乐，他几乎用尽了所有的钱，他甚至对自己的 npy 也漠不关心其实是因为他没有npy，更不爱好看戏。除非买了新可乐，才会坐上马车出门炫耀一番。每一天，每个钟头他都要喝上一瓶新可乐。 pigstd 最近又买了许多箱新可乐——当然，这些可乐只有聪明的人才能喝到。 题目描述pigstd 现在有 $n$ 箱可乐，第 $i$ 箱可乐上标着一个正整数 $a_{i}$。 若 pigstd 的聪明值为一个非负整数 $x$，对于第 $i$ 箱可乐，如果 $(a_{i} \oplus x )\le k$，那么 pigstd 就能喝到这箱可乐。 现在 pigstd 告诉了你 $k$ 与序列 $a$，你可以决定 pigstd 的聪明值 $x$，使得他能喝到的可乐的箱数最大。求出这个最大值。 输入格式第一行两个由空格分隔开的整数 $n,k$。 接下来 $n$ 行，每行一个整数 $a_i$，表示第 $i$ 箱可乐上标的数。 输出格式一行一个正整数，表示 pigstd...

P3379 【模板】最近公共祖先（LCA）题目描述如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。 输入格式第一行包含三个正整数 $N,M,S$，分别表示树的结点个数、询问的个数和树根结点的序号。 接下来 $N-1$ 行每行包含两个正整数 $x, y$，表示 $x$ 结点和 $y$ 结点之间有一条直接连接的边（数据保证可以构成树）。 接下来 $M$ 行每行包含两个正整数 $a, b$，表示询问 $a$ 结点和 $b$ 结点的最近公共祖先。 输出格式输出包含 $M$ 行，每行包含一个正整数，依次为每一个询问的结果。 输入输出样例 #1输入 #1123456789105 5 43 12 45 11 42 43 23 51 24 5 输出 #11234544144 说明/提示对于 $30%$ 的数据，$N\leq 10$，$M\leq 10$。 对于 $70%$ 的数据，$N\leq 10000$，$M\leq 10000$。 对于 $100%$ 的数据，$1 \leq N,M\leq 500000$，$1 \leq x, y,a ,b \leq...

定义 在一棵树中，如果选择某个结点为根，可以使得它的最大子树最小，那么这个结点就被称作这棵树的重心 性质 以重心为树根时，所有子树的大小不会超过全树大小的一半 （假设重心有一子树超过了，以这棵子树的根为新的重心即可推出矛盾） 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样（假设目标点从重心往别的点偏移了一个单位，那么不少于半数的点到目标点的距离增加一个单位，不超过半数的点到目标点的距离减少一单位，易知总代价上升，故目标点就在重心处） 把两棵树通过一条边相连得到一棵新的树，那么新树的重心在连接原来两棵树重心的路径上 （与2的证明类似，假设偏移推矛盾） 在一棵树上添加或删除一个结点，那么它的重心最多只移动一条边的距离 （最多只可能是一棵子树的大小比一半多1，往该子树偏移一个单位即可，若偏移过多则会打破平衡） 求法 （DFS）step1. 对于一个根结点u，求出每个子树的大小，加和后1记为size[u]，注意该点父结点构成的子树大小不用单独求，可直接使用 n-size[u] 求出step2....

P1099 [NOIP 2007 提高组] 树网的核题目描述设 $T=(V,E,W)$ 是一个无圈且连通的无向图（也称为无根树），每条边都有正整数的权，我们称 $T$ 为树网（treenetwork），其中 $V$，$E$ 分别表示结点与边的集合，$W$ 表示各边长度的集合，并设 $T$ 有 $n$ 个结点。 路径：树网中任何两结点 $a$，$b$ 都存在唯一的一条简单路径，用 $d(a, b)$ 表示以 $a, b$ 为端点的路径的长度，它是该路径上各边长度之和。我们称$d(a, b)$ 为 $a, b$ 两结点间的距离。 $D(v, P)=\min{d(v, u)}$, $u$ 为路径 $P$ 上的结点。 树网的直径：树网中最长的路径成为树网的直径。对于给定的树网 $T$，直径不一定是唯一的，但可以证明：各直径的中点（不一定恰好是某个结点，可能在某条边的内部）是唯一的，我们称该点为树网的中心。 偏心距 $\mathrm{ECC}(F)$：树网 $T$ 中距路径 $F$ 最远的结点到路径 $F$...

...

迟迟时间明明不太匆忙心情明明不太煎熬我们却走得有些囫囵吞枣黄昏迟迟等不到翳暗弯月迟迟攀不上树梢于是一声再会显得为时尚早 落寞蜿蜒在沙粒上海浪迟迟 吞没不了谁与谁的年少海枯石烂 谁能等到于是一句诺言说得太早 浮生行舟 不用停棹何苦聆听那细弱曲调虚构着谁和谁的哀伤个中滋味 体会不到于是一滴眼泪落得太早 炊烟迟迟 升起不了硝烟迟迟 挥散不了月上柳梢 苦捱不到倾盖的欢喜怎堪蹉跎到老于是一根白发生得太早 曾几何时 车马迟迟有些词句会不会显得太早？ 问海呼吸——这不可避免等待海浪沾湿你的眼帘泡沫——是一种语言我的疑问逃过了你的眼却等不到浮出水面 是什么让我抬不起眼为什么让我有苦难言耳朵注满了盐脚底灌上了铅 眼泪是一尾狡猾的鱼么言语是一串虚无的珍珠么我耳边也曾划过你的眼泪么什么——看见什么——追逐什么——最后呼吸什么——在失眠之前让我们先陷入长眠 等待着沧海化为桑田你遗忘了许多东西偶然想起水面下满是句点溺毙是一种心安的睡眠

龙吟趁道路施工我把心脏抛到水泥地 多年以后空荡荡的胸膛里地下列车呼啸而过 我于是有一颗蛰龙般的心么？ 落耳每当经过工地我感到心悸重型机械敲击钢筋水泥像法官的惊堂木锤断了我的耳朵 落下来 快落下来了这一锤是否会斩断所有生路？我落荒而逃 失魂落魄 审判的声音却经年不息锯锉着我并不像钢筋的脆弱神经 直到大厦落成那天才得一夕安寝 高楼在睡梦里投下阴影我猛然惊醒想起多年前将耳朵落在工地里

算法简介SPFA算法求解最短路一句话总结 当边权可能为负的情况下，每个被更新了距离的点都有可能更新它所连的所有点 带着这个思想来看下面的具体步骤吧！（别忘了在纸上比划比划哦~ 步骤 将起始点的dis设为0并放入队列 获取当前队列的第一个顶点并删除 对该点的所有连边更新距离 将step3中被更新了并且不在队中的点入队 重复step2~4，直到队列为空 代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849// SPFA算法// 主要思想：每个点的距离被更新后都有可能再去更新其他点的距离#include <bits/stdc++.h>using namespace std;const int MAXN = 5e5+10;int n, m;int h[MAXN], e[MAXN], ne[MAXN], w[MAXN], cnt, s;void add(int a, int b, int c) {    e[cnt] = b,...

通讯延迟(csp第35次)时间限制： 1.5 秒 空间限制： 512 MiB 相关文件： 题目目录（样例文件） 题目描述给定二维平面上 n 个节点，以及 m 个通讯基站。第 i 个基站可以覆盖以坐标 (xi,yi) 为中心、2ri​ 为边长的正方形区域，并使正方形区域内（包含边界）所有节点以 ti​ 单位时间的延迟进行相互通讯。 求节点 1 到 n 的最短通讯延迟。 输入格式从标准输入读入数据。 第一行包含空格分隔的两个正整数 n、m； 接下来 n 行，每行两个整数 xi,yi，代表第 i 个节点的坐标； 接下来 m 行，每行四个整数 xj,yj,rj,tj​，代表第 j 个通讯基站的坐标，通讯半径与通讯延迟。 输出格式输出到标准输出。 输出一行，即节点 1 到 n 的最短通讯延迟；如果无法通讯，则输出 Nan。 样例输入12345678910115 50 02 44 05 35 51 2 2 53 5 2 62 0 2 14 2 2 35 4 1...

P1950 长方形题目描述小明今天突发奇想，想从一张用过的纸中剪出一个长方形。 为了简化问题，小明做出如下规定： （1）这张纸的长宽分别为 $n,m$。小明将这张纸看成是由$n\times m$个格子组成，在剪的时候，只能沿着格子的边缘剪。 （2）这张纸有些地方小明以前在上面画过，剪出来的长方形不能含有以前画过的地方。 （3）剪出来的长方形的大小没有限制。 小明看着这张纸，想了好多种剪的方法，可是到底有几种呢？小明数不过来，你能帮帮他吗？ 输入格式第一行两个正整数 $n,m$，表示这张纸的长度和宽度。 接下来有 $n$ 行，每行 $m$ 个字符，每个字符为 * 或者 .。 字符 * 表示以前在这个格子上画过，字符 . 表示以前在这个格子上没画过。 输出格式仅一个整数，表示方案数。 输入输出样例 #1输入 #112345676 4.....***.*...***...*.*** 输出 #1138 说明/提示【数据规模】 对 $10%$ 的数据，满足 $1\leq n\leq 10,1\leq m\leq 10$ 对 $30%$ 的数据，满足 $1\leq n\leq...