zhangxixi的博客

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15689484.html 题目链接 由于BZOJ已挂，这里是黑暗爆炸和hydro的备份 黑暗爆炸： 国王奇遇记 国王奇遇记加强版 hydro： 国王奇遇记 国王奇遇记加强版 题目 Katharon 国有着悠久的历史，每个慕名而来的游客都渴望能在 Katharon 国发现一些奇怪的宝藏。而作为国王的 Kanari 君也梦想着有一天发现自己国家的宝藏,从而成为世界上最富有的人。 Kanari 国王和 katherine 皇后凭着 14 年...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15689044.html (a+b)n=∑k=0nCnkakbn−k\Large(a+b)^n=\sum_{k=0}^n C_n^ka^kb^{n-k} (a+b)n=k=0∑n​Cnk​akbn−k 在化简一些式子时有用 因此，2n2^n2n （也就是当 a=b=1a=b=1a=b=1 ）时也可以表示为： 2n=∑k=0nCnkakbn−k\Large2^n=\sum_{k=0}^n C_n^ka^kb^{n-k} 2n=k=0∑n​Cnk​a...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15685484.html 求： {S≡b1(moda1)S≡b2(moda2)⋯S≡bi(modai)⋯S≡bn(modan)\Large\begin{cases}S\equiv b_1\pmod {a_1}\\ S\equiv b_2\pmod {a_2}\\ \cdots\\ S\equiv b_i\pmod {a_i}\\ \cdots\\ S\equiv b_n\pmod {a_n}\\ \end{cases}⎩⎨⎧​S≡b1​(mo...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15685317.html 前言 拓欧总是记不住，总是想不懂，希望写篇博客加深影响。 拓展欧几里得定理推论 求： ax+by=gcd⁡(a,b)\Large ax+by=\gcd(a,b) ax+by=gcd(a,b) 的其中一组整数解 x,yx,yx,y。 首先可以证明必有解（留坑） 按照欧几里得定理：gcd⁡(a,b)=gcd⁡(b,a%b)\gcd(a,b)=\gcd(b,a\%b)gcd(a,b)=gcd(b,a%b) k1x′+k2y′=...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/articles/15679108.html 题单 容斥和组合数 自我介绍 吕欣。活跃在 2016 - 2019 年的一个 OIer。参加过 NOI 2015 (铁牌)，NOI 2016 (金牌）。2017 年进入清华大学姚班读书。在 2017 - 2019 年给各种 OI 比赛出过一些题（清华集训 2017 生成树计数；NOIWC 2019 I君的商店；NOI 2019 I君的探险；CTSC 2019 氪金手游），对（当时的）命题风格/环境/人有一定...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15675706.html 题目链接 题目 相比 WildleopardWildleopardWildleopard 的家，他的弟弟 MildleopardMildleopardMildleopard 比较穷。他的房子是狭窄的，而且在他的房间里仅有一个灯泡。每天晚上，他徘徊在自己狭小的房子里，思考如何赚更多的钱。有一天，他发现他的影子的长度随着他在灯泡和墙壁之间走动时会发生变化。一个突然的想法出现在他的脑海里，他想知道在房间里他的影子的最大长度。 ...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15674805.html 题目链接 题目 一个点每过一个单位时间就会向四个方向扩散一个距离，如图。 两个点a、b连通，记作e(a,b),当且仅当a、b的扩散区域有公共部分。连通块的定义是块内的任意两个点u、v都必定存在路径e(u,a0),e(a0,a1),…,e(ak,v)。给定平面上的n给点，问最早什么时刻它们形成一个连通块。 思路 二分答案+并查集。 首先二分时间 ttt。 如果两个点能直接相连，则他们的曼哈顿距离小于二倍 ttt。并且把...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15674729.html 题目链接 题目 对于给定的一个长度为N的正整数数列 A1∼NA_{1\sim N}A1∼N​，现要将其分成 MMM（M≤NM\leq NM≤N）段，并要求每段连续，且每段和的最大值最小。 关于最大值最小： 例如一数列 4 2 4 5 14\ 2\ 4\ 5\ 14 2 4 5 1 要分成 333 段。 将其如下分段： [4 2][4 5][1][4\ 2][4\ 5][1] [4 2][4 5][1] 第一段和为 666...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15674711.html 题目链接 题目 明明做作业的时候遇到了 nnn 个二次函数 Si(x)=ax2+bx+cS_i(x)= ax^2 + bx + cS​i​​(x)=ax​2​​+bx+c，他突发奇想设计了一个新的函数 F(x)=max{Si(x)},i=1…nF(x) = max{S_i(x)}, i = 1ldots nF(x)=max{S​i​​(x)},i=1…n。 明明现在想求这个函数在 [0,1000][0,1000][0,1...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15673449.html 题目链接 题目 给定长度为 n 的数列 a，如果 （按位与），则在 i,j 之间存在一条长度为 的边，求 1 至所有点的最短路。 思路 暴力连边，边太多，最多 n2n^2n2 条，MLE+TLE。 于是考虑减少边的数量。 首先建32个虚点。 然后加入 aia_iai​ 在第 kkk 位上为1，就在 iii 和第 kkk 个虚点当中连边，边权为 aia_iai​。 这样最多有 n×32n\times 32n×32 条边。...