ohEPse

题目 是一道练习 $tarjan$ 的好题。 首先读题，很容易想到是要先跑一遍 $tarjan$ 求割点。然后想想每一个连通块，分为几种情况： 如果没有割点，如果其中一个点断开，那么就会分成两个连通块，所以需要增加两个出口，在其中随便选两种就好， 共$C_n^2$种选择。 如果有一个割点，无论是否断在割点都需要一个出口，在非割点的地方随机选择即可。 如果有两个及以上割点，无论断在哪里，图都是联通的，所以不需要建立出口。 这道题有一些小坑，比如某些数据记得清零。记录最大值的变量没清零： $100pts->90pts$ （悲 然后是代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192#include<bits/stdc++.h>using namespace std;con ...

D4T1 [SDOI2014]旅行传送门 Desciption:给定一颗 $n$ 个节点的树，每个节点都有一个权值和一种颜色。 有 $q$ 个询问： CC x c 将节点 $x$ 的颜色改为 $c$ CW x w 将节点 $x$ 的权值改为 $w$ QS x y 询问 $$ 路径上与 $x,y$ 颜色相同的点的权值和 QM x y 询问 $$ 路径上与 $x,y$ 颜色相同的点的最大权值 Solution:首先明确肯定用树剖来维护询问和修改。 对于每一个宗教我们都要开一颗线段树来维护，所以考虑用主席树。 主席树+树剖，其他的与线段树+树剖一样。 Hint: 查询最大最小值得时候记得加上if(qr<l||ql>r) return 0;，不然不晓得飞到哪里去。 主席树的空间玄学问题。本题的 $maxn$ 为 $1e^5$ ，理论上要开到 $maxn<<7$ 的范围才保险，但是 SLOJ上 $maxn<<6$ 才能过。 Code:123456789101112131415161718192021222324252627282930313233343536 ...

D2T3 CardsDescription：每个卡片有 $a_i$ 和 $b_i$ 两个数。交换 $c_i$ 和 $d_i$ 两个位置上的卡片，判断能否将任意卡片翻转，保证卡片正面的数单调不减。 Solution：考虑线段树维护区间能否单调不减。合并时判断即可。但是常数巨大还在 $T$ 着呢。 对于合并的pushup 1234567891011121314void pushup(int p){ int mid=t[p].l+t[p].r>>1; //t[p].f[0][0]=t[p].f[1][0]=t[p].f[0][1]=t[p].f[1][1]=0; for(int i=0;i<=1;i++){ for(int j=0;j<=1;j++){ t[p].f[i][j]=0; for(int k=0;k<=1;k++){ for(int l=0;l<=1;l++){ t[p].f[i][j]|=t[p<<1].f[i][k]&t[p<<1|1] ...

D1T3 KinomanDesciption共有 $m$ 部电影，第 $i$ 部电影的好看值为 $w_i$。 在 $n$ 天之中,每天会放映一部电影，第 $i$ 天放映的是第 $f_i$ 部。 你可以选择 $l,r(1<=l<=r<=n)$，并观看第 $l,l+1,\dots,r$ 天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。 Solution:第 $i$ 部电影对 $[pre_i+1,i]$ 区间有贡献。用线段树维护区间最大值。每次枚举右端点，每次操作时，将 $[pre_i+1,i]$ 加上 $w_i$ ,但是前面的贡献要减去，所以$[pre_{pre_i},pre_i]$ 减去 $w_i$ 。 Code：123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707 ...

D2T3 「AHOI2014」奇怪的计算器Desciption:传送门 Solution:如果我们先抛去 $L,R$ 的限制，很容易联想到这是个线段树的板子。 然后如果加上限制，考虑如何修改。如果我们将序列排序，操作也不hi影响序列的单调性。所以我们可以二分出一个位置，及恰好到达边界的位置。对于没超过限制的部分直接修改，超过限制区间直接覆盖即可。因为线段树query 操作的本质就就是二分，所以不需要额外二分。对于区间覆盖，维护一个最大最小值即可判断。 代码中有两个细节需要注意： 注意几个运算有优先级，覆盖操作>乘法操作>加减和那个奇怪的操作。 在运算时因为是给整个序列更改，所以直接俄打标记即可。 但其实对于所有的操作都可以化成一个操作，仍然是idx巨佬的文章 Code1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818 ...

D4T3 严格次小生成树Description：给定一张 $n$ 个点 $m$ 条边的无向图，求无向图的严格次小生成树。 设最小生成树的边权之和为 $val$ ，严格次小生成树指边权之和大于 $val$ 的生成树的最小的一个。 Solution:首先严格次小生成树根最小生成树只有一条边不同。 所以我们可以枚举所有边，如果这条边不在生成树上，那么加入生成树后一定会构成一个环，这时候将边上最大值删去即可。但考虑到严格次小生成树的最大边权与当前边权相同，所以还要记录次大值。 用树剖维护次大值和最大值即可。 Code：1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161 ...

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 ...

简称：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$ 的溢出相当于自动取反和自动取模。而此方法的正确性就是取模的时候模数是一定的。 这 ...