- 2024-11-05多校A层冲刺NOIP2024模拟赛18
多校A层冲刺NOIP2024模拟赛18\(T1\)A.选彩笔(rgb)\(100pts/100pts\)观察到\(0\ler,g,b\le255\)且答案具有单调性,故考虑二分答案。将\(r,g,b\)分别抽象成三维坐标下的\(x,y,z\)。设当前二分出的答案为\(mid\),由调整法分析可知若存在一个边长为\(mid\)的
- 2024-11-04好题收集
好题,比较有trick/套路的题,印象深刻的题P4240毒瘤之神的考验拆式子与根号分治思想的极致融合。给\(n,m\),求\[\sum\limits_{i=1}^n\sum\limits_{j=1}^m\varphi(ij)\]对998244353取模,多测。\(n,m\le10^5,T\le10^4\)设\(n\lem\)。先要知道一个经典的式子:\[\varph
- 2024-11-04组合数学
组合基础与数论基础组合数Lucas定理\[\foralln,m,\in\mathbb{N},n\geqm,p\in\mathbb{P},\binom{n}{m}\equiv\binom{\lfloorn/p\rfloor}{\lfloorm/p\rfloor}\binom{n\bmodp}{m\bmodp}\pmod{p}\]证明:引理:\(\forallp\in\mathbb{P},n\in[1,p-1]\cap
- 2024-11-04AtCoder Beginner Contest 378 考试总结
发挥还行,就是罚时吃饱了,B题卡精度卡成78了。赛时得分:ABCDEFG√√√√√××[ABC378A]Pairing先对序列排个序,然后从小往大扫,如果和之后匹配了就贡献加一,然后跳过一个位置继续匹配。时间复杂度\(O(4)\)。#include<bits/stdc++.h>#definelllon
- 2024-11-03Min-25 筛
Min-25筛参考\(\text{OI-Wiki}\)和2018集训队论文朱震霆《一些特殊的数论函数求和问题》。\(\text{Min-25}\)的本质是埃式筛和数论分块,其实并没有什么高级的技巧。记\(x/y=\lfloor\frac{x}{y}\rfloor\),\(pr_k\)表示第\(k\)小的质数,\(\text{lpf}(i)\)表示\(i\)
- 2024-11-03第一讲 有理数与绝对值
2024.11.2Part1基础部分【例1】已知$y=|2x+6|+|x-1|-4|x+1|$,求$y$的最大值。解:直接零点分段即可,易得$y$的最大值为$6$。Part2$$\mathscr{Abel}$$变换【例1】若已经给出两个数列${a_n},{b_n}$,构造数列${c_n}$使得$c_n=a_nb_n$,令$T_n=\sum\li
- 2024-11-02Educational CF Round 171
游记理所当然VP了秒速过A,打B犯了一天的傻逼看错条件理所当然的只过了一道愉快开启改题生活当然改题也挺那啥的题解A挺简单的找\(X,Y\)的最小值,即找到长方形可框住的最大的正方形直接输出此正方形的顶点坐标即可证明考虑超出此正方形的点在旋转平移以后都会超出长方形范
- 2024-11-02微积分选学
函数极限如果对于任意整数\(\epsilon\),总存在\(\delta\)使得对于所有能使\(0<|x-x_0|<\delta\)成立的\(x\)都有\(|f(x)-A|<\epsilon\),那么\(A\)就是\(f(x)\)在\(x_0\)处的极限,记作:\[\lim\limits_{x\rightarrowx_0}f(x)=A\]函数在\(x_0\)处的极限与其在\(x_0
- 2024-10-30QOJ #9317. Rivals
题面传送门直接做显然不太好做,考虑转化成每次都从\(n\)个怪中随机挑一个出来打,但是只有挑到还有血量的怪才算入“打了一次”。使用生成函数来刻画这个东西:当打了一次,乘上一个\(y\),打了有效的一次,乘上一个\(x\)。枚举最后一次有效攻击打到了哪个身上,则每个怪的EGF就是\[x^
- 2024-10-30[一直更新中]一句话题解
目录一句话题解2024.10.29AT_abc290_fAT_arc156_c2024.10.30P5749[IOI2019]排列鞋子AT_abc285_e一句话题解不能什么题都随便写写就过了,留点印象好一点。一直更新。2024.10.29AT_abc290_f组合数数。满足树的形态要有\(\sumdeg_i=2n-2\)。考虑目前有\(k\)个儿子节点,直径
- 2024-10-29省选前模拟赛记录
日期类型ABCD总分小经验0820省选/互测赛\(\color{green}{数论分块/性质}\)\(\color{blue}{期望}\)\(\color{blue}{生成函数/多项式}\)16大样例/longlong0824省选/互测赛\(\color{green}{FWT}\)\(\color{green}{Ad-hoc}\)\(\color{blue}{数据结构优
- 2024-10-27DYN / 消防局的设立 / Spread of Information / 将军令 题解
前言四倍经验:[POI2011]DYN-Dynamite;[HNOI2003]消防局的设立;[ARC116E]SpreadofInformation;将军令。题意简述给你一棵\(n\)个结点的树和点集\(S\),你要选出\(k\)个关键点\(T\),求\(\min\max\limits_{u\inS}\min\limits_{v\inT}\operatorname{dis}(u,v)\)
- 2024-10-26修改Linux服务的文件打开句柄数
在bash中,有个ulimit命令,提供了对shell及该shell启动的进程的可用资源控制。主要包括打开文件描述符数量、用户的最大进程数量、coredump文件的大小等。在centos5/6等版本中,资源限制的配置可以在/etc/security/limits.conf设置,针对root/user等各个用户或者*代表所有用户来设
- 2024-10-24[Coci2011]kamion 题解
前言题目链接:Hydro&bzoj;黑暗爆炸。题意简述给你一张\(n\)个点\(m\)条边的有向图。有\(p\)种括号,每条边的边权可以是这\(p\)种括号中某一种的左括号或者右括号,也可以为空。问你有多少条从\(1\)开始到\(n\)的长度小于等于\(k\)的路径,满足括号匹配,或者剩余若干未
- 2024-10-24吉米多维奇杂题选解——数列极限
吉米多维奇杂题选解——数列极限一、用定义证明数列极限等式T1.求证:\(\lim\limits_{n\to\infty}\dfrac{n^\alpha}{c^n}=0,(a>0,c>1)\)证明:令\(k=\left\lfloor\alpha\right\rfloor+1\),则\(\dfrac{n^\alpha}{c^n}<\dfrac{n^k}{c^n}=\left(\dfrac{n}{(\sqrt[k]{c})^n}\
- 2024-10-23小红的树上路径查询(hard)
小红的树上路径查询(hard)题目描述本题和$hard$难度的区别是,询问的次数有多次!小红拿到了一棵树,她有多次询问,每次询问输入一条简单路径$x,y$,她想知道树上所有节点到该路径的最短路之和是多少,你能帮帮她吗?定义节点到路径的最短路为:节点到路径上所有点的最短路中,值最小的那个。
- 2024-10-23一点生成函数
前置知识你可能需要了解一些生成函数基础。应该可以先看,看不懂再去学。约定\(F\)表示函数,\(f\)表示一个生成函数(一个拥有无限项的多项式?)。\([x^i]f\)表示多项式\(f\)的\(x^i\)的系数。函数\(\to\)普通生成函数封闭形式如果有这样一个函数\[i=0,G(i)=0\]\[i
- 2024-10-23Public NOIP Round #7
A答案为\(\sum\limits_{k\ge0}\sum\limits_{i=1}^n\sum\limits_{j=1}^n[a_i+b_j\ge10^k]\)。先把\(a,b\)排序,枚举\(k\)后双指针统计答案即可。时间复杂度\(O(n(\logn+\logV))\)。B若\(|a_i-a_j|=k\)就在它们之间连一条无向边。因为保证序列没有
- 2024-10-22【NOIP2021】方差 题解
前言题目链接:洛谷;LOJ;UOJ。题意简述给你单调不降序列\(\{a_n\}\),你可以让\(a_i\getsa_{i-1}+a_{i+1}-a_i\),求操作后方差的最小值。\(n\leq10^4\),\(1\leqa_i\leq600\)。题目分析仔细观察操作,发现实际上是将\(a_i\)按照\(a_{i-1}\)和\(a_{i+1}\)的
- 2024-10-222022.10.27
CSP-S寄了,被COVID-19定点打击。练习情况P1402酒店之王P1231教辅的组成P2891[USACO07OPEN]DiningG最大流,关键在建图,以P1402为例。一开始我是这样建的。源点->房间->客人->菜品->汇点看起来没有问题,但实际上这有很大问题。如:这样的图,一个人就贡献了2次
- 2024-10-222022.10.20
练习情况P3601签到题有意思的题目,先筛出\(10^6\)的质数,每个质数对\(l\)~\(r\)的贡献。每个质数在\(l\)~\(r\)下界是\((\dfrac{(l-1)}{P}+1)P\)可以用分块思想理解Code:for(LLi=1;prime[i]*prime[i]<=r;i++){for(LLj=((l-1)/prime[i]+1)*prime[i];j<=
- 2024-10-22欧拉函数
欧拉函数通项\(\varphi(n)=n\prod\limits_{i=1}^n(1-\dfrac{1}{p_i})\)常用性质当\(n\)为质数时,\(\varphi(n)=n-1\)当\(gcd(n,m)=1\)时\(\varphi(nm)=\varphi(n)*\varphi(m)\)\(\varphi(p^k)=p^k-p^{k-1}\)欧拉反演\(n=\sum\limits_{d|n}\varph
- 2024-10-22xyd 好题分享1
ARC061F3人でカードゲーム三人
- 2024-10-20区间缩小
区间缩小题目描述给定一个正整数$n$,我们初始设定两个变量$l$和$r$,其中$l=1$,$r=n$。我们将执行以下步骤:如果$l=r$,则结束操作;否则,执行步骤$2$。从区间$[l,r]$中等概率地选取一个正整数$x$。然后,以下两种情况互斥地发生:以概率$p$将$l$更新为$x$,以概率$1−p$将
- 2024-10-18唐氏儿学莫比乌斯反演
不会莫比乌斯反演,所以来学。很多博客看不懂/kk。题目P2522\[\sum\limits^b_{i=a}\sum\limits_{j=c}^{d}[\gcd(i,j)=k]\]容斥,\[\sum\limits^b_{i=a}\sum\limits_{j=c}^{d}[\gcd(i,j)=k]= \sum\limits^b_{i=1}\sum\limits_{j=1}^{d}[\gcd(i,j)=k]- \sum\limits^b_{i=1}\s