scmmm's blog

前言（考古发掘者的） 自己也在这上面付出很多心血，虽然可能下面全是学术垃圾。 也会慢慢的把这下面的东西搬到其他地方，所以下面不会更了。 但是里面的东西应该会成为我的学习资料（乐） title: Artucv.cpp date: 845-06-13 11:54:54 tags: 前言 侧边栏炸了 短期的目标 笛卡尔树 容斥 带标号联通无向图计数 带标号欧拉图计数 dp套dp 斜率优化dp 树剖换根 很多数据结构 数据结构 树剖 实质 是一个重链剖分，寻找lcalcalca的时候每次规模减半，故时间复杂度O(nlogn)O(nlogn)O(nlogn) 用处 求lcalcalca或者水LCTLCTLCT的部分分 操作 dfs1dfs1dfs1 得到深度关系以及重儿子，父子关系 dfs2dfs2dfs2 进行剖分，得到重链 换根 本质上并不需要换根，我们完全可以用之前求得的id序列来描述这个树，因为重新换根来重建这棵树是完全没必要的(在复杂度上面不太占优势) 首先我们考虑换根后怎么求得lcalcalca，显然是可以 线段树 主席树 beautiful pair 题意就是找到满足 形如 ...

前言 萌新的数据结构板子，可能有些地方很抽象，反正是自己用。 st表 写个线段树不好？不好，容易被卡常。 O(1)O(1)O(1) 查询 O(nlog⁡n)O(n \log n)O(nlogn) 预处理以及空间消耗 遇到卡空间的题，可以把查询一次改成查询多个区间多次，常数还是很优秀，但是实际写起来有没有树状数组优是个问题？我在老脆克斯里面有道题用了这个方法。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include<bits/stdc++.h>#define endl '\n'using namespace std;const int maxn=2e6+5;int n,m,a[maxn];namespace stb{ int st[21][maxn]; int l2[maxn]; void pre() { for(int i=2;i<=n;i++) l2[i]=l2[i> ...

前言 萌新做了下 CF1750 D\text{CF1750 D}CF1750 D 发现自己对容斥的理解完全不深入 容斥，顾名思义，就是分别算每个的贡献，然后减去重复的贡献。 我们考虑容斥的应用。 应用 求 [1,m][1,m][1,m] 满足 gcd⁡(x,n)=1\gcd(x,n)=1gcd(x,n)=1 的个数 显然，我们考虑唯一分解定理， n=p1k1∗p2k2∗p3k3∗...∗pnknn=p_1^{k_1}*p_2^{k_2}*p_3^{k_3}*...*p_n^{k_n}n=p1k1​​∗p2k2​​∗p3k3​​∗...∗pnkn​​ 我们考虑 ki>0k_i>0ki​>0 的情况 换句话说 nnn 不能是 pip_ipi​ 的倍数，这显然就是一个容斥原理。 123456789101112131415161718192021222324mmp=tmp;tmp=a[i];int sz=0,d[30]={0};for(int j=1;p[j]*p[j]<=mmp;j++){ if(mmp%p[j]==0) { ...

对于上周的总结 上周的训练断了，可能也为 ICPC\text{ICPC}ICPC 爆炸埋下种子。 毕竟这东西一两周的积累远远不够 这周末打完西安赛后，应该会空出很多时间，准备开始机器学习的学习以及部分生信的学习。 11月7日 写了下 CF 1750 的 C D CF1750 C. Complementary XOR 题目大意，给你 a,ba,ba,b 两个 01 串，询问是否能通过以下操作 f(l,r)f(l,r)f(l,r) 将 a,ba,ba,b 变成两个全为 0 的序列 f(l,r)f(l,r)f(l,r) 操作把 i∈[l,r]i\in [l,r]i∈[l,r] 中的 aia_iai​ 变为 i−aii-a_ii−ai​ ，将i∉[l,r]i\notin[l,r]i∈/[l,r] 的 bib_ibi​ 变为 1−bi1-b_i1−bi​ 首先我们考虑 a=b,a=¬ba=b,a=\neg ba=b,a=¬b 这两个都有一个很显然的结论，如果 ai=bi=1a_i=b_i=1ai​=bi​=1 那么我们可以进行 f(1,r),f(1,r−1)f(1,r),f(1,r-1)f(1, ...

P5648 Mivik的神力 神！ deco\color{black}{\text{d}}\color{red}{\text{eco}}deco 神 原来的题意就是问 ∑i=lrRMQ(l,i)\sum\limits_{i=l}^{r}{\text{RMQ}(l,i)}i=l∑r​RMQ(l,i) 强制在线 拿到题的网友直呼不可做，分析也没分析啥，但是考虑一个点要作为[l,i][l,i][l,i] 的RMQ的话说明左边都比它小，也就是最大的比他小，然后这样就可以牵出一条链，根据性质还可以进一步推出这是一颗树！ 然后怎么办，统计[l,r][l,r][l,r] 的答案 [l,i][l,i][l,i] 的 ansansans 就是 lll 牵出来到 iii 的一条链中最大的节点，这样可以拿 $ 90$ 分 再考虑性质，发现上面那部分可以倍增来做 原题时限0.1s，下面的做法常数大了 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#incl ...

Day -1 参加了热身赛。 热身赛 T1 第一题叫你猜东北大学几月份建的，实际上在参赛手册上，但是显然我们没看，很抽象，猜 121212 个月，猜了十次才过。好在可做，勉强算签到题。 T2 L. Random Permutation 第二题是说，生成一个序列，每个数字在 iii 位置上生成的概率是 1n\frac{1}{n}n1​ 问你期望他大于多少个排列。 显然的，我们考虑 f(x)f(x)f(x) 为只放进了前 xxx 的数的排列方案数，有 f(x)=x∗f(x−1)∗n−x+1nf(x)=x*f(x-1)*\frac{n-x+1}{n}f(x)=x∗f(x−1)∗nn−x+1​ 换句话说 f(x)=n!∗n!nnf(x)=\frac{n!*n!}{n^n}f(x)=nnn!∗n!​ T3 B. The Great Wall 第三题才有意思，告诉你一个长度为 nnn 的序列，希望你找到将这个序列分成 nnn 个区间后最大值减去最小值的和的最大值 我们不妨令 fi,j,1/2/3f_{i,j,{1/2/3}}fi,j,1/2/3​ 表示前 iii 个数中已经分出来 jjj 个区间， ...

前言 很难受，自己缺少太多基础只是了，很多看起来可做的都写不了，自己实在是太菜了。 希望沈阳可以混一个 cu\color{gold}\text{cu}cu 吧。 另外这个题就太体现 ACM 思维的活跃性以及严谨性了，我还太菜，希望明年能拿个 Au\text{Au}Au 吧 F. Fields Division 题目大意，一个图，每个点点权 2i2^i2i 询问将图分成两个连通块后，两边权值和相差最小的方案。 显然 2n2^n2n 这个点太大了，我们考虑把它单独分开，剩下 n−1n-1n−1 个点找跑一个并查集， n−1n-1n−1 号点所在的连通块和其他即为所求。 I. Invested Money 题目大意，你借了钱后，每三十天还一次钱，如果那天是周末，就咕到周一 现在告诉你你多久借了钱，询问最近多少天后要还钱。 首先打表，发现 919191 是一个循环节，那么我们直接就暴力好了（噩梦的开始） 但是你会发现大 WA 特 WA 因为前面那些数字不在循环里面，你仅仅是把后面的放进循环节了，所以我们保留前919191和一个循环节才可以。 12345678910111213141516171 ...

最基础部分 定义 字符集，字符串（这东西显然不需要打一遍定义） 子串，这个东西表示一段连续的S[i...j],i≤jS[i...j],i\leq jS[i...j],i≤j 有时候，用S[i...j],i>jS[i...j],i>jS[i...j],i>j表示空串 子序列，s[p1...pk],pis[p_1...p_k],p_is[p1​...pk​],pi​递增并且满足1≤p1<pk≤∣S∣1\leq p_1<p_k\leq|S|1≤p1​<pk​≤∣S∣ 前缀，从串首开始到某个位置的子串。 后缀，从某个位置到串末尾的子串。为啥每次都会打成猴嘴 字典序，顾名思义就是按照字符顺序比较的方法，或者说以第iii个字符为第iii关键字进行大小比较，空集是最小的 回文串，倒着和正着都一样的串 输入，输出 哈希 把一个子串映射成为一个数字，一般的写法是这样的 f(S)=∑sip∣S∣−if(S)=\sum s_ip^{|S|-i}f(S)=∑si​p∣S∣−i 我们先令 n=∣S∣n=|S|n=∣S∣ 那 f(S)=s1∗pn−1+s2∗pn−2+...+s ...