p1896 2005 scoi

## 前言 [传送门](https://www.luogu.com.cn/problem/P3422) [blog](https://www.luogu.com.cn/blog/JJL0610666/solution-p3422) 长沙市一中暑假第一次思维训练。 #### 前置芝士 [前缀和](hh ......

[也许更好的阅读体验](https://blog.csdn.net/Morning_Glory_JR/article/details/131462805?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22% ......

每当我们看到“最大值最小”“路径上的最大最小值”等字眼时，我们就可以考虑并查集。 我们可以尝试把这些问题转化为某种意义上按单调顺序的合并，利用并查集求解答案。以下时两例并查集的巧妙应用。 CF1213G Path Queries 注意“最大权值不大于q”，加上允许离线，我们可以把边按照权值排序，并一 ......

# [NOIP2005 普及组] 陶陶摘苹果 ## 题目描述 陶陶家的院子里有一棵苹果树，每到秋天树上就会结出 $10$ 个苹果。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有个 $30$ 厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。 现在已知 $10$ 个苹果到地面的高... ......

## 题目描述 $\text{lxhgww}$ 最近迷上了一款游戏，在游戏里，他拥有很多的装备（$n \le 10^6$），每种装备都有 $2$ 个属性，这些属性的值用 $[1,10000]$ 之间的数表示。 当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。 游戏进行 ......

# [SCOI2009] 迷路 ## 题目背景 windy 在有向图中迷路了。 ## 题目描述 该有向图有 $n$ 个节点，节点从 $1$ 至 $n$ 编号，windy 从节点 $1$ 出发，他必须恰好在 $t$ 时刻到达节点 $n$。 现在给出该有向图，你能告诉 windy 总共有多少种不同的路径 ......

[TOC] ### [题目链接](https://www.luogu.com.cn/problem/P4159 "题目链接") ### 题目内容 [SCOI2009] 迷路 题目背景 windy 在有向图中迷路了。 题目描述 该有向图有 $n$ 个节点，节点从 $1$ 至 $n$ 编号，windy ......

## 题目描述 输入两个整数 $a, b$，输出它们的和（$|a|,|b| \le {10}^9$）。 注意 1. Pascal 使用 `integer` 会爆掉哦！ 2. 有负数哦！ 3. C/C++ 的 main 函数必须是 `int` 类型，而且 C 最后要 `return 0`。这不仅... ......

# NCC2005 单点登录，常见问题和解决方案 ## 设计思路 要单点登录到NCC，首先需要在服务器端向NCC服务器注册将要登录的用户的信息以及其他一些需要的信息，这些信息将被保存在NCC服务器上，通过ssoKey进行关联映射。 在完成注册信息后，客户端在登录时需要提供ssoKey，通过该值获得登 ......

没错,数学也有分类了qaq,我之前学算法的时候妹学数学,今天算是被搞怕了(但还是不听ovo) 学会了两种方法,主要思想还是,对于每个i来说,他在从1-n中的贡献值是n/i,也就是1-n中约数含有它的数目是n/i(厉害吧,刚学的)另外一种方法是筛法,说实话这个你应该想到的(恼),不优化会爆的(30分) ......

题面 首先考虑一个贪心策略：当地板已经放满需要取出一个时，取下一次使用时间 $nxt$ 最晚的那个。 所以我们只需要一个可以快速求出一个集合中 $nxt$ 最小的点并删除，插入新点的数据结构，这里很容易想到堆。 代码很简洁，注意数组的下标是位置还是颜色（考场 100 pts 到 0 pts）。 co ......

题目链接 题目 题目描述 lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作： 0 a b 把[a, b]区间内的所有数全变成0 1 a b 把[a, b]区间内的所有数全变成1 2 a b 把[a,b]区间内的所有数全部取反 ......

总体思路其实跟用线段树维护区间最大字段和差不多，不过唯一麻烦的地方在于要算上自己。 然后我们可以开一个队列来回收那些被delete的点，这样可以节省空间，特别需要注意的是release的时候，标记什么的一定记得清空。 本来insert我是直接一个个merge的，这样就会导致特别慢，因此我们可以借助笛 ......

题目链接 题目 题目描述 我们常常会说这样的话：“X年是自Y年以来降雨量最多的”。它的含义是X年的降雨量不超过Y年，且对于任意 Y＜Z＜X，Z年的降雨量严格小于X年。 例如2002，2003，2004和2005年的降雨量分别为4920，5901，2832和3890， 则可以说“2005年是自2003 ......

在封装非MFC环境的静态库时调用了依赖MFC环境的静态库时编译测试程序报错如下： nafxcw.lib(afxmem.obj) : error LNK2005: "void * __cdecl operator new(unsigned int)" (??2@YAPAXI@Z) 已经在 LIBCMT ......

[SCOI2013]密码 Fish是一条生活在海里的鱼。有一天他很无聊，就到处去寻宝。他找到了位于海底深处的宫殿，但是一扇带有密码锁的大门却阻止了他的前进。 通过翻阅古籍，Fish 得知了这个密码的相关信息： 该密码的长度为N。 密码仅含小写字母。 以每一个字符为中心的最长回文串长度。 以每两个相邻 ......

| 2005-text4 | | | | | | command | 驾驭，控制，命令，指挥 | | aspire | 渴望，追求 v. | | aspiring | 有追求的，渴望...的 | | degradation | 毁坏，恶化，降低 | | degrade | 降低，降级，退化 | | ......

| 2005-text3 | | | | | | component | 成分，组成部分 | | formulate | 构想，规划，确切地阐述 | | revolutionary | 革命性的，创新的，革命的 | | disguise | 伪装，掩饰 v.n. | | unconscious | ......

| 2005-text2 | | | | | | inconclusive | 非决定性的，无结果的 | | conclusive | 决定性的，最后的，确定的 | | conclude | 推断，决定，作结论 | | buy | 相信，承认，接受 | | awaken | 唤醒，唤起，使意识到 | ......

| 2005-text1 | | | | | | vanish | 消失，突然不见 v. | | reputation | 名声 | | slack | 松懈，懈怠，偷懒 | | outrage | 使震怒；愤怒 v.n. | | outraged | 气愤的 | | assumption | 假定 ......

https://www.luogu.com.cn/problem/P3292 多次询问求一条链取若干点的最大异或和 考虑一个集合的最大异或和可以求出线性基完成，两个集合的线性基可以合并，但是线性基并没有可减性，于是我们求 lca 的时候只能每次往集合里添加一条链，为了保证复杂度只能用倍增做。 std ......

很巧妙的改变状态 $0$代表无插头，$1$代表有插头，且这个$"L"$还未拐弯,$2$代表有插头，且这个$"L"$已经拐过弯了 具体转移可以手推，用四进制即可 点击查看代码 #include<bits/stdc++.h> #include<unordered_map> #define int lon ......

保证了无论怎么破坏航线，图都会是一个连通图 也就是说，起码肯定有一棵生成树 考虑在生成树上U，V之间加边，会对树上各个点的割边情况产生什么影响 对于任意点对(u,v)，如果它们之间的最短路径不经过从U到V的树上路径，那是没有影响的 否则：关键路径的数目会减少 减少了多少？U，V之间树上路径经过的所有 ......

[SCOI2010] 序列操作 在dls的数据结构中级课那学了最大字段和的线段树写法，对于这道题，我们要维护的信息有： 区间左边0/1的个数， 区间右边0/1的个数 区间最长0/1的长度 区间的赋值标记 区间的取反标记 整个区间的长度 对于 1 ~ 4 是很基本的最大字段和操作 对于 两种不同的标记 ......

$\text {Day \ -2}$ 烧烤吃多了，有点拉肚子。 $\text {Day \ -1}$ 我是真的不会考试啊。 感觉我不该想着去翻多少分，只要你只是单纯想把省选考好，并且你确实做到了，那么 NOIP 的那点分确实不算什么（，但是我感觉这种东西，举个例子，就像你在长跑，你感觉你的终点线在别 ......

[SCOI2008]城堡 最大值最小，显然二分答案，但考虑二分后如何 check。 $n$ 个点 $n$ 条边，显然这是一个基环树森林。对于基环树，常用的套路是拆环为链，枚举删去哪条边。但这题是基环树森林，拆环为链的复杂太高，考虑将环和树分开处理。 树上是一个很典型的 dp，和将军令一样（不了解的可 ......

题目地址 题意：由小到大给出n年的降雨量，进行m次询问，每次询问给出一个Y和X，问X年的降雨量是否不超过Y，并且对于任意的Z∈(Y,X)的降雨量，是否都严格小于Y和X的降雨量 Solution 维护区间最大值很简单，但是要判断实在是太阴间了，这里来练习一下st表 st表 st表用于解决可重复贡献问题 ......

状压dp模板题： dp[i][j][k]为到了第i行，第i行的状态，一共有多少的国王。 预处理出第i行的所有可行的状态，显然不能有国王相邻，也不能有超过k个国王的可能 dp转移： 显然dp[ i ][ x ][ k ]是上一行情况累加过来： dp[i][x][k]+=dp[i-1][y][k-pop ......

已经不记得平衡树的样子了。 Statement 给定一个 $1\sim n$ 的序列，你有如下几个操作： 改变一个人的编号 将一个人放在序列开头 将一个人放在序列结尾 查询排名为 $k$ 的编号 对于每次操作，输出操作前这个人的排名。 Analysis 可以把操作看作是以下几个步骤 查找一个编号的排 ......

哈哈哈哈老婆我有出息了，犬犬第一次从思路到代码都是自己一发切了紫题呢~ 好了一眼数据结构。 考虑如何转化第i个时刻有威胁的情报员，若能产生威胁 则说明他们至少在i-c-1这个时刻"出生" 也就是转化为在权值线段树上查询[1,i-c-1]有多少个人。 启发了我们可以先把未来的情报员都弄下来，再记一个他 ......