- 博客(309)
- 收藏
- 关注
RSS订阅原创 2023牛客暑期多校训练营10 C Multiplication（复杂度证明）
好不容易拿了一次一血，队友说复杂度有问题，我就来证一证。，其实还远跑不满，这只是我用纯数学能证到的地步。做法就不说了，题解里有，贴个代码。做一次高精度除法以后就相当于普通。这种情况是不可能出现的，我算他是。作为整体的话，每次都会减至少。，因为只有除二和减法，都是。如果打个表，这个数不会超过。也是个无关紧要的数，远小于。的，但会跑满，肯定很慢。，否则会跳转上一种情况。，还有除法复杂度设为。其实也一样，因为哪怕。
2023-08-18 22:59:13
308
原创 2023牛客多校第一场B Anticomplementary Triangle
固定后，面积关于坐标k的函数一定是单峰函数，①：有结论：面积最大的三角形即为所求。之外，一定能取得更大的面积。证明：若有点在面积最大的三角形对应。可以当双指针做，复杂度少一个。双指针跳转，这个结论可得到。假如依然按双指针做，固定。的结合体做双指针，复杂度。时间内找到这个三角形。
2023-07-17 21:43:56
208
原创 湖北省赛2022H.Hamster and Multiplication
由于不知道怎么想的，认为只能从某个状态更新之后的状态，而不能每次用之前状态计算当前状态，所以dfs就不成立了（某个节点更新多次后才是最优的，根本不知道什么时候才能拿来更新别的点），于是我就采用了bfs，在实现时发现会爆内存，采用了滚动数组优化。我当时就试了一个9，拆成两个3，结果爆了，以为是错误的，后来才知道是我这么做的话，3可能有36个，而我当作18在做。（注意到有贡献的数肯定不存在某位是0，且1不影响乘积，其实这里就可以看出我这个定义可以改改），的值，但这样的话两个无关的状态也能转化了，故不可。
2023-04-13 16:53:01
398
原创 2019.6.25 π的无穷级数推导
π\piπ有一种简单的积分求法：π4=arctan(1)=∫0111+x2dx=∫011−x2+x4−...dx=1−13+15−17+...\frac{\pi}{4}=arctan(1)=\int_0^1\frac{1}{1+x^2}dx=\int_0^1 1-x^2+x^4-...dx=1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+...4π=arctan(1)=∫011+x21dx=∫011−x2+x4−...dx=1−31+51−71+...现在
2021-03-21 14:57:46
1410
原创 2019.6.14 巴塞尔问题
巴塞尔问题：∑n=1∞1n2\sum_{n=1}^{\infty}\frac{1}{n^2}n=1∑∞n21首先：sinxx=∑k=0∞x2k(2k+1)!\frac{sinx}{x}=\sum_{k=0}^{\infty}\frac{x^{2k}}{(2k+1)!}xsinx=k=0∑∞(2k+1)!x2k我们假设可以把这个无穷级数表示为线性因子的乘积，因为sinxx=0\frac{sinx}{x}=0xsinx=0的根出现在x=nπx=n\pix=nπ，期中n=±1,±2,
2021-03-21 14:50:26
328
原创 导数相关内容证明
导数的话，六年级就学了，那些初等函数的导数大部分证明也是那个时候就自己证出来了，但对数函数和指数函数一直是证不出来，到了初一，高数学到P82P82P82的时候才了解到（并且发现对三角函数的证明有点假）。这些东西从初一到现在高二，总有人问我怎么证，我干脆直接这里完完整整全都写下来好了。1.(f(x)⋅g(x))′=f′(x)g(x)+f(x)g′(x)1. (f(x)\cdot g(x))'=f'(x)g(x)+f(x)g'(x)1.(f(x)⋅g(x))′=f′(x)g(x)+f(x)g′(x)(f(x
2021-03-21 13:56:40
312
原创 由一维“醉酒的小鸟”引发的一些思考
一维格点上随机游走的粒子，它最终返回出发点的概率为100100%100刚开始，在五三的知识拓展部分看到这东西，我觉得十分显然，证明有手就行，结果证了半天才证出来令fnf_nfn表示，从nnn开始走，无限步后，走回000的概率我们可以得到：f1=1+f22f_1=\frac{1+f_2}{2}f1=21+f2f2=f1+f32f_2=\frac{f_1+f_3}{2}f2=2f1+f3f3=f2+f42f_3=\frac{f_2+f_4}{2}f3=2f2+f4....
2021-03-21 01:14:44
138
原创 bzoj2863: 愤怒的元首
题目Description求n个点的dag个数。Solution设fif_ifi为iii个点的dagdagdag个数。至少有iii个入度为000的点的方案为：fn−i(in)2i∗(n−i)f_{n−i}(^n_i)2^{i*(n−i)}fn−i(in)2i∗(n−i)容斥一下，则：fn=∑i=1n(−1)i−1fn−i(in)2i∗(n−i)f_n=\sum_{i=1}^{n}...
2020-01-18 10:57:19
259
原创 CSP-S2019游记
作为一名高一选手，我已经无路可退了，只能背水一战Day-1&Day0真搞不懂为啥考前两天要搞这么个模拟赛，模拟赛day1预期300，想到自己每次认为自己要AK都要爆掉起码两题，就果断给T1T3打了拍，结果还是爆掉，变成50+100+60T1是快速幂刚开始的时候long long乘long long，忘记取模爆掉了，暴力也跟它爆得一样，拍不出来T3是忘记开long long了。我感...
2019-11-16 22:55:30
416
原创 绍兴一中模拟赛3.22——踟躇（chíchú）而过
Descriptionn<=1018n<=10^{18}n<=1018，保证gcd(a,b)=1gcd(a,b)=1gcd(a,b)=1Solution考虑计算大于等于ttt的第一个满足f(x,k)=sf(x,k)=sf(x,k)=s的数我们可以从高位到低位贪心去填，每一位从零开始依次尝试，看剩余位用剩余数字去填能否大于等于 ttt我们设这个过程叫ne...
2019-03-22 20:11:00
319
原创 51nod1016 水仙花数 V2（打表）
题目夹克爷的远古帖上有打表的方法，但两份代码一个C#，一个java，懒得看水仙花数的个数是有限的，位数最多39位，不知道怎么证，反正跑出来的结果是这样的我是自己打的表，本机大概运行13s可跑出来具体方法就是：枚举水仙花数中1−91-91−9的个数，剩下的位填000，这样就能计算出水仙花数，判断1−91-91−9的个数是否与枚举的一样即可从999到111枚举可以优化我有三个剪枝（假设当前...
2019-03-21 21:29:37
97
原创 绍兴一中模拟赛3.19——白驹过隙
Description定义类仙人掌为：求类仙人掌上的最大独立集大小，(n<=50000,m<=100000)(n<=50000,m<=100000)(n<=50000,m<=100000)SolutionCode注意f[p2][p1][0][1]f[p2][p1][0][1]f[p2][p1][0][1]等于f[p...
2019-03-21 18:09:45
231
原创 绍兴一中模拟赛3.21——孰是孰非
Description有一个长为n(n≤500)n(n≤500)n(n≤500)的序列，每次可以选一段区间加上xxx，如果有数大于777就减777（保持所有数∈[1,7]∈[1,7]∈[1,7]）问：最少几次这样的操作才能使所有aia_iai都等于777Solutionstep1：step1：step1：先差分一下，令bi=ai−ai−1(1≤i≤n+1,a0=an+1=0)b_i=a_...
2019-03-21 14:15:18
160
原创 bzoj2028: [SHOI2009]会场预约
题目Solution假设当前输入的区间为[l,r][l,r][l,r]，那么当区间[x,y][x,y][x,y]满足l≤y,x≤rl≤y,x≤rl≤y,x≤r时，两区间相交我一直在想怎么同时维护左右端点，后来才发现，直接以右端点为关键字，把所有区间放进setsetset里从小到大枚举≥l≥l≥l的yyy，如果yyy对应的x≤rx≤rx≤r，那么直接删掉否则，l≤r<x≤yl...
2019-03-20 18:33:12
149
原创 绍兴一中模拟赛3.19——时光流转
DescriptionSolution离线以后点分对于每个点，都用这个点的祖先把这个点的子树更新一遍，考虑到操作时间早的才能更新晚的和题目中说的“路径上边权都大于等于valvalval”，那就用树状数组做一下二维偏序就行了Code#include<bits/stdc++.h>using namespace std;typedef long long ll;#def...
2019-03-20 14:16:59
220
2原创 2019年绍兴文理学院元培学院ACM试题总结
文章目录1.[岁月神偷](http://acm.usx.edu.cn/aspnet/Question.aspx?qid=1649)2.[字母移动游戏](http://acm.usx.edu.cn/aspnet/Question.aspx?qid=1653)3.[黑孔雀和小太阳](http://acm.usx.edu.cn/aspnet/Question.aspx?qid=1655)4.[埃及分数]...
2019-03-17 23:31:13
1450
原创 一中模拟赛3.15——树上gcd
Solution计算每个质因子在哪些点出现，然后在树上只保存这些点，通过计算大于000的g(i,j)g(i,j)g(i,j)个数来计算贡献如果质因子次数&amp;amp;gt;1&amp;amp;gt;1&amp;gt;1，那么把p2p^2p2，p3p^3p3，…，pkp^kpk都按同样方法做一遍Code代码中*q就相当于q[0]q[0]q[0]，*vis，*vis1同理#include&amp;lt;bits/st...
2019-03-15 20:39:36
254
转载 C++玄学预编译优化
自为风月马前卒#pragma GCC diagnostic error "-std=c++11"#pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibli...
2019-03-14 19:07:36
532
原创 AtCoder Grand Contest 016 C - +/- Rectangle
题目Solution首先，有一个贪心思想：选择行被hhh整除，列被www整除的点作为关键点，值为负数，其他点全是正数设关键点的点权为xxx，其他点为yyy那么，有x+y(hw−1)&amp;lt;0x+y(hw-1)&amp;lt;0x+y(hw−1)&lt;0所以，x=(1−hw)y−epsx=(1-hw)y-epsx=(1−hw)y−epsepsepseps越小越好，但是因为题目中...
2019-03-14 18:50:55
108
原创 绍兴一中模拟赛3.13——排列的区间最大值限制
Description有一个大小为n(n≤109)n(n≤10^9)n(n≤109)的排列和m(m≤50)m(m≤50)m(m≤50)个限制，每个限制(l,r,q)(l,r,q)(l,r,q)表示在区间[l,r][l,r][l,r]内的最大值必须是qqq，问是否存在一个满足所有条件的排列Solution考虑贪心（网络流也可以做，本质是一样的）分析“[l,r][l,r][l,r]内的最大值必...
2019-03-14 11:41:16
165
原创 loj#517. 「LibreOJ β Round #2」计算几何瞎暴力
题目题解（D题）数据结构题虽然难写，但是没什么好说的，具体看代码吧Codeswpswpswp是用来排序的，tottottot是用来统计答案的#include&amp;lt;bits/stdc++.h&amp;gt;using namespace std;typedef long long ll;const int N=200002;int sz[N*30],t[N*30][30],c[N*30]...
2019-03-14 09:40:18
252
原创 bzoj1202: [HNOI2005]狡猾的商人（带权并查集）
题目Codefa[x]fa[x]fa[x]表示xxx路径压缩后的父亲d[x]d[x]d[x]表示xxx到fa[x]fa[x]fa[x]的距离（有向，fa[x]fa[x]fa[x]到xxx的距离为−d[x]-d[x]−d[x]）#include<bits/stdc++.h>using namespace std;const int N=102;int n,m,x,y,z,i...
2019-03-13 20:01:11
105
原创 bzoj2440: [中山市选2011]完全平方数
题目Description求第kkk个不包含平方因子的数Solution首先肯定是二分答案xxx，然后求&lt;=x&lt;=x<=x的不包含平方因子的数的个数然后推样例的时候发现：个数=x−x22−x32−x52+x62−x72+x102个数=x-\frac{x}{2^2}-\frac{x}{3^2}-\frac{x}{5^2}+\frac{x}{6^2}-\f...
2019-03-13 19:11:48
173
原创 区间gcd
Description区间加减、区间gcdgcdgcdSolution因为gcd(a,b)=gcd(a,b−a)gcd(a,b)=gcd(a,b-a)gcd(a,b)=gcd(a,b−a)，所以可以差分，gcd(al,al+1,...,ar)=gcd(al,al+1−al,...,ar−ar−1)gcd(a_l,a_{l+1},...,a_r)=gcd(a_l,a_{l+1}-a_l,.....
2019-03-13 15:41:54
1498
原创 bzoj2560: 串珠子
题目Solution关于dp：题意可以转换为：给出一个的无向图，边有边权。定义一个子图的权值为所有边权的乘积，问所有使全部nnn个点连通的图的权值和为多少f[s]f[s]f[s]表示当前联通状态为sss，g[s]g[s]g[s]表示选sss的状态的点，连通性任意的方案数那么g[s]=∏i,j∈s(a[i][j]+1)g[s]=\prod_{i,j∈s}(a[i][j]+1)g[s]=i...
2019-03-12 19:08:42
331
原创 FFT/NTT板子
FFT#include<bits/stdc++.h>using namespace std;const int N=240002;const double pi=acos(-1.0);struct C{ double x,y;}a[N],b[N];int lim=1,i,n,r[N],l,c[N];char s[60002];C operator +(C a,C b...
2019-03-12 14:46:03
206
转载 bzoj3572: [Hnoi2014]世界树
题目题解构建虚树以后两遍dpdpdp处理出虚树上每个点最近的议事处然后枚举虚树上每一条边，考虑其对两端点的答案贡献可以用倍增二分出分界点如果aaa，bbb的分界点为midmidmid，aaa，bbb路径上aaa的第一个儿子为xxx则对aaa的贡献是size[x]−size[mid]size[x]-size[mid]size[x]−size[mid]对bbb的贡献是size[mid]−...
2019-03-12 10:21:08
141
原创 Codeforces 1138B. Circus
题目Solution我感觉这题比这场的CD难多了（E以后没时间看，但99%是做不出的）刚开始想过dpdpdp，但发现要保存前iii个数，000和111的个数差，还有s1s1s1中选择的长度，会爆然后想到了模拟，枚举两个串中111的个数kkk对于每个iii，s1s1s1和s2s2s2的情况只有444种：1：s1[i]=′0′，s2[i]=′0′1：s1[i]=&#x27;0&am...
2019-03-11 18:48:00
258
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人