Luogu4180 严格次小生成树
D4T3 严格次小生成树Description:给定一张 $n$ 个点 $m$ 条边的无向图,求无向图的严格次小生成树。
设最小生成树的边权之和为 $val$ ,严格次小生成树指边权之和大于 $val$ 的生成树的最小的一个。
Solution:首先严格次小生成树根最小生成树只有一条边不同。
所以我们可以枚举所有边,如果这条边不在生成树上,那么加入生成树后一定会构成一个环,这时候将边上最大值删去即可。但考虑到严格次小生成树的最大边权与当前边权相同,所以还要记录次大值。
用树剖维护次大值和最大值即可。
Code:1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161 ...
Luogu4315 月下毛景树
D3T4 月下毛景树Description:给定一颗 $n$ 个节点有边权的树,维护以下四个操作:
Change k w 将第 $k$ 条边的边权改为 $w$
Cover u v w 将 $$ 路径上的所有边权都改为 $w$
Add u v w 将 $$ 路径上的所有边权都加上 $w$
Max u v 询问 $$ 路径上边权最大值
Solution:将边权转化为深度更大的点的点权,然后变成树剖的模板。
需要注意的是,改变路径上的边权时要去掉 $lca$ 的点权。
123456789void modify(int x,int y,int val){ while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y); updadd(num[top[x]],num[x],1,val); x=fa[top[x]]; } if(num[x]>num[y]) swap(x,y); updadd(num[x],num[y],1,val);}
要变为:
123456789void modi ...
Luogu4041 [AHOI2014]奇怪的计算器
D2T3 「AHOI2014」奇怪的计算器Desciption:传送门
Solution:如果我们先抛去 $L,R$ 的限制,很容易联想到这是个线段树的板子。
然后如果加上限制,考虑如何修改。如果我们将序列排序,操作也不hi影响序列的单调性。所以我们可以二分出一个位置,及恰好到达边界的位置。对于没超过限制的部分直接修改,超过限制区间直接覆盖即可。因为线段树query 操作的本质就就是二分,所以不需要额外二分。对于区间覆盖,维护一个最大最小值即可判断。
代码中有两个细节需要注意:
注意几个运算有优先级,覆盖操作>乘法操作>加减和那个奇怪的操作。
在运算时因为是给整个序列更改,所以直接俄打标记即可。
但其实对于所有的操作都可以化成一个操作,仍然是idx巨佬的文章
Code1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818 ...
从乡土社会视角看游民文化
从乡土社会视角看游民文化摘要: 游民文化作为脱胎于乡土社会的一种文化形式,也是中国传统文化的一部分,是乡土社会的传统背景下产生的文化。它反映了游民群体独特的心理、思维方式、行为方式和社会关系,以及折射出来的一切活动。文章以费孝通的《乡土中国》中的知识,探究游民文化的产生、发展与特点等等。
关键词: 游民;游民文化;乡土社会
一、游民文化的产生与发展 游民文化诞生自古代的中国乡土社会。三千年以来古代中国乡土社会的是一个按照父系血缘系统组建起来的乡土社会。乡土社会以农业为主,发展小农经济,依土为生的农民们大都一辈子守在一块土地上。乡土社会的不流动性也使得人们以小家族为基本社群,形成以村落为单位的生活劳作。古时候地少人多,每个家族都由自己的耕作范围,但是人口增长、自然灾害、战乱等原因,都可以使得一些人从乡土社会系统中流离出来。这些宣泄外出的人有些可以找到一个新的土地生存,又形成一个个新的家族殖民地;但还有一部分人在各式各样的命运下脱离了主流社会认可的社会秩序,他们游荡于乡镇之间,没有固定的居所,没有稳定的收入,没有确定的职业,久而久之就变成了游民了。
古代封 ...
警 钟 敲 得 稀 烂
简称:OI备忘录
upd 2023.1.10
对于普通莫队,块长设为 $\sqrt n$ 即可。但对于带修莫队,最好设置为 $n^{\frac{2}{3}}$ 。效果极为显著,快了将近2s。
upd 2022.12.24
并查集啊并查集,记得初始化啊。今天四个代码三个没有初始化(恼)
1for(int i=1;i<=n;i++) fa[i]=i;
upd 2022.11.20
不能算是个注意事项,只是觉得 1145141919这个模数挺好的
upd 2022.11.12
逻辑运算 ‘!’的优先级是高于位运算的,就是这么个小东西我调了一上午(哭)。
形如:1if(!exp)
最好写作:
1if(!(exp))
龟速乘
background:当两个 $long long$ 相乘时,很容易爆,但是如果直接写高精度那就亏大发了。
solution 1:可以使用一种类似快速幂的方法,只是吧乘法操作变成加法操作。
12345678910inline ll quickmul(ll a,ll b,ll mod){ ll res=0; while(b){ if(b&1) res=(res+a)%mod; a=(a+a)%mod; b>>=1; } return res;}
solution 2:有一种 $O(1)$ 的做法。
实际上,并不建议在比赛中使用 $O(1)$ 快速乘,除非题目非常需要卡常,毕竟浮点的精度不能保证。
1234inline llquckmul(ll a,ll b,ll mod){ return (a*b-(ll)((long double)a/mod*b)*mod+mod)%mod;}
关于原理:
首先,$long long$ 的溢出相当于自动取反和自动取模。而此方法的正确性就是取模的时候模数是一定的。
这 ...
简单数论
四中不教数论,只好用九中的进度来学习了
upd 11.18 终于开始教数论力!!!!1.数论基础2.质数2.1 质数的判定没什么好说的,幼儿园大班的知识。
什么?你说你不知道什么是质数?赶紧滚回去上幼儿园
kdw听了都要连夜跑过来打你
2.2 质数筛2.2.1 埃氏筛也不知道 $when how$ 老师 怎么教的,我一直以为这个叫欧拉筛。
原理:原理很简单,就是质数的倍数一定不是质数。所以我们就可以这样子求质数。
时间复杂度大概是 $O(nlog(log n))$。
123456789int isprime[maxn];memset(isprime,1,sizeof(isprime));//初始全为1,素数标记为0,合数标记为1isprime[2]=0;for(int i=2;i<=maxn;i++){ if(!isprime[i]){ for(int j=2;j*i<=maxn;j++) isprime[i*j]=1; }}
2.2.2 欧拉筛这才是正统欧拉筛
2.2.2.1 原理:跟埃氏筛原理相似。 ...
多叉树转二叉树
background在解决很多树形问题的时候会遇到多叉树,但是多叉树在很多时候解决起来很麻烦。根据数学家烧水的思想可以将多叉树转化为二叉树求解。同时该方法也可以将森林转化为一棵二叉树,非常实用。
solution把多叉树的第一个儿子放在左儿子,其他兄弟放在右儿子,称为“左兄弟右儿子”。
至于代码实现,输入一条边 $(u,v)$ ,表示 $v$ 是 $u$ 的孩子,如果 $u$ 的左儿子为空,就将 $v$ 放在左儿子,否则循环知道右儿子不为空放进去。12345678910111213for(int i=1;i<=n;i++){ cin>>v>>w; if(ch[v][0]==0) ch[v][0]=i; else { int temp=ch[v][0]; while(ch[temp][1]!=0) temp=ch[temp][1]; ch[temp][1]=i; } c[i]=w; in[ch[i][0]]++; in[ch[i][1]]+ ...
数据结构dp专练(汇总版)
2.6~2.9 数据结构与 $dp$ 专练,每天4题,难度不小,深蓝到深紫之间的难度。
绝大部分题来自bzoj,洛谷上只收录了一小部分。
D1T1 与或 :线段树维护二进制操作
D1T2 排队计划:推导性质+线段树维护
D1T3 Kinoman: 权值线段树
D1T4 Hotel:线段树+最长子序列
D2T1 [NOI2016]区间:双指针+线段树
D2T2 跳伞求生:贪心/线段树模拟费用流
D2T3 Cards:线段树合并
D2T4 [AHOI2014/JSOI2014]奇怪的计算器:线段树
D3T1 层流:树剖+树上染色
D3T2 Graph:树剖/dfs序+树状数组
D3T3 three:长链剖分维护 $dp$
D3T4 月下“毛景树”:树剖裸题
D4T1 [SDOI2014]旅行:树剖+主席树
D4T2 [NOI2011]嘉年华:单调队列优化 $dp$
D4T3 [BJWC2010]严格次小生成树:树剖+最小生成树
D4T4 路径的交:dfs序
Day1 线段树专题(确信D1T1 与或Description:对于一个长度为 $n$ 的序列,维护一下三个信息:
1 l r v ...
BZOJ2259 [Ohib] 新型计算机
Description:Tim 正在摆弄着他设计的“计算机”,他认为这台计算机原理很独特,因此利用它可以解决许多难题。但是,有一个难题他却解决不了,是这台计算机的输入问题。新型计算机的输入也很独特,假设输入序列中有一些数字(都是自然数 —— 自然数包括0),计算机先读取第一个数字 $S1$ ,然后顺序向后读入 $S1$ 个数字。接着再读一个数字 $S2$ ,顺序向后读 入 $S2$ 个数字 …… 依此类推。不过只有计算机正好将输入序列中的数字读完,它才能正确处理数据,否则计算机就会进行自毁性 操作!Tim 现在有一串输入序列。但可能不是合法的,也就是可能会对计算机造成破坏。于是他想对序列中的每一个数字做一些更改,加上一个数或者减去一个数,当然,仍然保持其为自然数。使得更改后的序列为一个新型计算机可以接受的合法序列。不过 Tim 还希望更改的总代价最小,所谓总代价,就是对序列中每一个数操作的参数的绝对值之和。写一个程序:从文件中读入原始的输入序列; 计算将输入序列改变为合法序列需要的最小代价;向输出文件打印结果。
Input输入文件包含两行,第一行一个正整数 $N$ , $N<1e ...
8.10夏令营测试
1. 赛后感言(?)T1-T3 属于比较简单的一眼题,J组第一题难度
T4 T6 有思路,没写完
T4 二分 + $BFS$
T6 $Tarjan$求环+$Dijstra$最短路
T5 完全没思路,并查集的做法还是比较新奇
4个小时的题只写了不到三个小时,有点可惜
2.分析1. 猴子识数题意简化:给出一个数$X$,如果是回文数,输出是第几个回文数,否则输出“NO!”。
1<=$X$<1e5
思路: 简单枚举
代码:1234567891011121314151617181920212223242526272829303132333435363738#include<iostream>#include<cstdio>#include<string>using namespace std;int main() { int d[2000]; int i,j,n,sum,b; for(i=1;i<=9;i++) //一位 d[i]=i; i=10; for(j=1;j<=9;j++) ...
BZOJ4977 跳伞求生
D2T2 跳伞求生传送门
Description:小Q最近沉迷于《跳伞求生》游戏。他组建了一支由 $n$ 名玩家(包括他自己)组成的战队,编号依次为$1,2,\dots,n$ 。这个游 戏中,每局游戏开始时,所有玩家都会从飞机上跳伞,选择一个目的地降落,跳伞和降落的时间有早有晚。在某局 游戏降落前,他们在空中观察发现地面上一共有 $m$ 间房子,编号依次为 $1$ 到 $m$ 。其中每间房子恰好有一名敌人早于他 们到达。小Q战队的第 $i$ 名玩家拥有 $a_i$发子弹,地面上第i间房子里的敌人拥有 $b_i$ 发子弹,消灭他可以获得 $c_i$ 点积 分。每名玩家必须且只能选择一间房子降落,然后去消灭里面的敌人。若第i名玩家选择了第j间房子,如果 $a_i>b_ j$ ,那么他就可以消灭该敌人,获得 $a_i-b_j+c_j$ 的团队奖励积分,否则他会被敌人消灭。为了防止团灭,小Q不允 许多名玩家选择同一间房子,因此如果某位玩家毫无利用价值,你可以选择让他退出游戏。因为房子之间的距离过长,你可以认为每名玩家在降落之后不能再去消灭其它房间里的敌人。作为小Q战队的指挥,请制定一套最 ...


![Luogu4041 [AHOI2014]奇怪的计算器](/img/posts/pCtXHYT.jpg)






![BZOJ2259 [Ohib] 新型计算机](/img/posts/pCtyx6H.jpg)

