scmmm's blog

T1 原题，降智题。 求 的个数 卡速米打炸了，然后又犯了(int)1e18 送的分都没拿到 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586#include<iostream>#include<cmath>#include<cstdio>#include<cstring>#include<queue>#include<stack>#include<vector>#include<set>#include<map>#include<algorithm>#include<cstdlib>#include<ctime>typedef long long ll;using na ...

一眼题，由于每条路径只删去一个点是最优情况，用一个树形dp枚举这个删这个点的答案和不删这个点的答案即可 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include<iostream>#include<cmath>#include<cstdio>#include<cstring>#include<queue>#include<stack>#include<vector>#include<set>#include<map>#include<algorithm>#include<cstdlib>#include<ctime>typedef long long ll;using ...

人话题意：给定 2n2n2n 个点，其中有 mmm 条形如 (x,y)(x,y)(x,y) 表示不能同时选 (x,y)(x,y)(x,y) 的限制，问能否满足 (2i,2i−1)(i∈[1,n])(2i,2i-1)(i\in[1,n])(2i,2i−1)(i∈[1,n]) 中都能选出一个点而满足限制 首先比较无脑的 2-SAT\text{2-SAT}2-SAT 就是对于每个人取 i,i′i,i'i,i′ 然后连 (2i′,2i−1)(2i,2i−1′)(2i',2i-1)(2i,2i-1')(2i′,2i−1)(2i,2i−1′) 但是这个边处理比较毒瘤，由于 2i2i2i 不选对应了 2i−12i-12i−1 必须选，因此直接连最简单的 2i,2i−1′2i,2i-1'2i,2i−1′ 这种就可以了 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566 ...

前言 这nm sb hexo 我{{...}} 这种情况报错改了调了一个多小时 正文 人话版本： 求 Π⁡i=1nΠ⁡j=1mf(gcd⁡(i,j))\large \operatorname{\Pi}_{i=1}^{n}\limits\operatorname{\Pi}_{j=1}^{m}\limits f(\gcd(i,j))Πi=1n​Πj=1m​f(gcd(i,j)) 我们转化一下，先枚举 gcd⁡\gcdgcd Π⁡d=1nΠ⁡i=1⌊nd⌋Π⁡j=1⌊md⌋f(d)ϵ(gcd⁡(i,j))\large\operatorname{\Pi}_{d=1}^{n}\limits\operatorname{\Pi}_{i=1}^{\lfloor\frac{n}{d}\rfloor}\limits\operatorname{\Pi}_{j=1}^{\lfloor\frac{m}{d}\rfloor}\limits f(d)^{\epsilon(\gcd(i,j))}Πd=1n​Πi=1⌊dn​⌋​Πj=1⌊dm​⌋​f(d)ϵ(gcd(i,j)) ...

一共有 777 种元素，每种元素有 a[i]a[i]a[i] 个，求期望取777 个不同元素的次数 减 666 首先这是条件概率，对于iii 来说期望就是 isum∗Π(elsesum′)\frac{i}{sum}*\Pi(\frac{else}{sum'})sumi​∗Π(sum′else​) 其中 sum′sum'sum′ 每次要减一，因为取出了一个元素 只考虑1 2 3 4 5 6 71~2~3~4~5~6~71 2 3 4 5 6 7 这种情况概率就是 a1sum×a2sum−1×...×a7sum−6\frac{a_1}{sum}\times\frac{a_2}{sum-1}\times...\times\frac{a_7}{sum-6}suma1​​×sum−1a2​​×...×sum−6a7​​ 与此同时，乘上 7!7!7! 此外还要乘上sum−6sum-6sum−6 123456789101112131415161718192021222324252627282930#include<stdio.h>#include<iostrea ...

坑啊，没这个节点也算回文也要输出 Yes 貌似没见着用重链剖分的写的，于是就来写一波 按照套路设 $ f[i][j][k] $ 表示 $ i $ 的子树内深度为 jjj 的字母 kkk 的个数 然后判断能否有回文只需看是否有两个及以上的字母出现次数为奇数次即可 另外像上面那样开数组的话用指针估计有点难受，建议 j,kj,kj,k 压成一维 一定不要想我作死先判断不合法的情况 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112#include<touwenjian.h>using namespace std;const int maxn=500500;int *f[maxn], ...

CF123E Maze 子节点顺序被打乱，每个点可以回溯一次，每条边边权都为1，给你每个点为起点和终点的概率，问你我们访问这个树的期望长度 结论 若父亲为 xxx 要访问的节点为 yyy 显然 zzz 若在 yyy 前面则访问 yyy 的时候距离会加 2size[z]2size[z]2size[z] 并且这个概率时12\frac{1}{2}21​ 因此，父亲到儿子期望的走的距离为 sz[father]sz[father]sz[father] 或者是∑sz[son[t]]+1\sum{sz[son[t]]}+1∑sz[son[t]]+1 此时我们记录在 ttt 子树中为起点的概率之和为 sumsumsum 这个点 ttt 为终点的概率为 yyy 那么答案就是 sum∗sz[t]∗ysum*sz[t]*ysum∗sz[t]∗y 不在这个子树中的同理，枚举每一个点为终点记录答案即可 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565 ...

提示：第一次打开latex会炸，请刷新 备考 由于之前的实在是太卡了，因此把它独立出来 5G 第五代移动通信技术（英语：5th generation mobile networks或5th generation wireless systems、5th-Generation，简称5G或5G技术）是最新一代蜂窝移动通信技术，也是继4G（LTE-A、WiMax）、3G（UMTS、LTE）和2G（GSM）系统之后的延伸。5G的性能目标是高数据速率、减少延迟、节省能源、降低成本、提高系统容量和大规模设备连接。Release-15中的5G规范的第一阶段是为了适应早期的商业部署。Release-16的第二阶段将于2020年4月完成，作为IMT-2020技术的候选提交给国际电信联盟（ITU） [1] 。ITU IMT-2020规范要求速度高达20 Gbit/s，可以实现宽信道带宽和大容量MIMO。 运算符 相同优先级中，按结合性进行结合。大多数运算符结合性是从左到右，只有三个优先级是从右至左结合的，它们是单目运算符、条件运算符、赋值运算符。 P,NP等 名称 描述 P 确定多 ...

无源汇上下界可行流 首先保证最小流量 设每个点 δ(t)=f(N+(t),t)−f(N−(t),t)\delta(t)=f_{(N^+(t),t)}-f_{(N^-(t),t)}δ(t)=f(N+(t),t)​−f(N−(t),t)​ 然后每条边的流量 flownew=flowmax−flowminflownew=flowmax-flowminflownew=flowmax−flowmin 此时若 δ(t)<0\delta(t)<0δ(t)<0 表示 ttt 流出不足，因此它的出边要增加流量，连一条 t,Tt,Tt,T 的边,容量为δ(t)\delta(t)δ(t) 若$ \delta(t)=0$ 流量守恒，不管 若δ(t)>0\delta(t)>0δ(t)>0 那么说明流出过多，因此要增加入邻域的流量，连一条S,TS,TS,T 的边 若 SSS 到 TTT 满流，说明可以实现流量平衡 为什么可行呢，一个点不可能同时和 S,TS,TS,T 相连，并且与 S,TS,TS,T 相连的边都可以2实现并且我们在新图已经忽略这些边带来的贡献（必然贡献进入答案 ...

¬ 等逻辑运算符优先级 最近 待办 NOIP 2011 T26 NOIP 2013 T27 CSP 模拟 2020 T18 NOIP 2015 T19 时间复杂度分析 容斥原理 康托展开 csp 2019 74 T6 由数字1, 1, 2, 4, 8, 8所组成的不同的4位数的个数是（）。 这个似乎没有更好的办法了，枚举四位数的组合 组合 个数 1124 A(4,2)=12A(4,2)=12A(4,2)=12 1128 A(4,2)=12A(4,2)=12A(4,2)=12 1148 A(4,2)=12A(4,2)=12A(4,2)=12 1248 A(4,1)=24A(4,1)=24A(4,1)=24 1288 A(4,2)=12A(4,2)=12A(4,2)=12 1488 A(4,2)=12A(4,2)=12A(4,2)=12 2488 A(4,2)=12A(4,2)=12A(4,2)=12 1188 C(4,2)=6C(4,2)=6C(4,2)=6 总和即为102102102 T8 G是一个非连通无向图（没有重边和自环），共有2 ...