- 博客(306)
- 收藏
- 关注
RSS订阅原创 ！！？？？
之后因为OI要荒废一段时间了，所以博客也会荒废……之前的一年里似乎有评论我也没看过……不过OI我还是很乐意有小接触的如果是我博客里做过的题或是bzoj(thinfatty)/luogu(nguxyf)等oj（其它的基本都写题解了）欢迎交流qq2039068568 然后吧，退役啦，博客开始大荒废期~~=v=*...
2018-11-11 17:02:25
470
原创 Noip 2018 tg 暴力记
noip2018是我的最后一次noip了(明年就是游走)怎么说呢，一年前的自己是心怀远大志向踏上征程，然后被虐得体无完肤回家的。我早就滚粗了——开始知道，不是所有人都适合竞赛。DAY 0出发前在机房划水，想着一些乱七八糟的事情。路上车里空气很不新鲜，头昏脑涨的，而且我们到杭州花了3h+？？去的学军似乎是新校区，总之感觉环境很不错的，四处逛逛，晚饭没怎么吃饱就回酒...
2018-11-10 22:59:44
1504
原创 bzoj 3126 [Usaco2013 Open]Photo DP+单调队列
DescriptionFarmer John has decided to assemble a panoramic photo of a lineup of his N cows (1 <= N <= 200,000), which, as always, are conveniently numbered from 1…N. Accordingly, he snapped M (...
2018-11-08 07:40:53
304
原创 迟来的解题报告——noip 2017提高组
题目请去洛谷上找找吧。我不复制粘贴了。由于差不多有1年了，所以我把6道题全部都重新做了一遍。所以题解没有看过任何网上的资料……全都是凭借当初的信息构筑起来的。代码也按照模糊的记忆重写了（部分啦部分=v=）。。 Day1T1：首先，看出a和b是互质的（虽然当时我并不是马上看出这一点）。能够被支付的物品价格p满足p=ax+by，其中，x和y都是 非负 （非负！）整数。...
2018-08-13 13:36:35
1529
原创 Noip 1999 普及组 导弹拦截 dp+二分查找
题目描述某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是 \le 50000≤50000 的正整数），计算这套系统最多能拦截多少...
2018-08-12 12:45:34
826
原创 Noip2017提高组 退役记
是真的滚粗。现在还是噙着泪打字的。以下内容可能引起大佬不适（也太菜了吧，蛤）从没想过一等也会拿不到。全校就我没一等了。先说说日程。day -1：机房内的最后一天，只好闲着整理模板。明知提高组不怎么会用到模板，但是也感觉做其他的改变不了什么了。day 0：中午启程。去衢州要整整一个下午的时间。下午车上不知道该干嘛。大家说好了要嗨结果其实
2017-11-12 20:57:42
4329
9
原创 模板整理: 部分数据结构
最重要的内容之一= = 主要整一下线段树，树状数组，st表，平衡树。 主要前3个，第4个是用来乱搞的= =会用set的应该也口译。。。 1.线段树 主要思想是把一个线段从中间分开，分别处理， 然后合并两个区间。 有区间合并性的信息都可以用线段树来维护。 常数偏大，注意数组开4倍防止越界。 还有懒惰标记，处理区间更新的情况。有时候下传标记顺序很重要。 单点修改直接log（n）修改
2017-11-10 09:42:28
516
原创 模板整理: 图论---二分图匹配
二分图要记住的性质：(n为点数) 二分图最大匹配=二分图最小点覆盖 =n-二分图最大点独立集 =n-二分图最小边覆盖 求二分图最大匹配的方法：匈牙利算法。 思路：找路增广……（网络流= =） 时间复杂度O(α∗n2\alpha*n^2)，α\alpha为一个比较小的常数。 实际题目里有些题n=4W也能跑过，所以稍微放点心。 模板：luogu3386 给出两个点集间的连边，求二分
2017-11-10 07:46:55
400
原创 模板整理: 图论---最小生成树
最小/大生成树是个非常厉害的知识点， 题目可以出得很巧， 记住它的最优子结构性质，并且很多时候性质有大用（例如货车运输） 稀疏图Kruskal，稠密图（有时候）Prim. 求最小生成树一般都是2种： 1.prim O(N2N^2)，可以用堆优化到O(N∗log(N)N*log(N))， 不是很常用，不过其实也很好写。 好吧也不能说不常用，我是指我用得比较少= = 毕竟C++一个so
2017-11-09 16:40:11
539
原创 整理: 动态规划---相关优化
注意以下内容都是在我的认知范围内，有错误在所难免…… 1.矩阵乘法优化， 具体一点地，比如当前dp状态是多维， 那么把后面几维装压变成一维， 比如f[i][j]，而i=1~n，j=1~m， 把它写成f[i]，i=1~n*m，对应转移。 假设压缩之后f[i]=∑x[j]∗f[i−pj]+Tf[i]=\sum x[j]*f[i-p_j]+T， pjp_j为某些值，x[j]x[j]为系数，T
2017-11-09 16:18:27
657
原创 模板整理: 高斯消元
表示不会线性基，只会最最辣鸡的高斯消元（应该够了吧QAQ） 高斯消元只要会手动模拟考场推也是可以的。。 主要想法就是找对角线，一个个往下找， 如果当前这个(i,i)的值非0，就其它行全部消去第i列（把第i列的值都减成0）即可。 最后求解的时候，从下往上（因为是个倒三角）求解即可， 代码写得还是挺明白的。 ……还有一种开关灯01啥啥的我似乎还不怎么会。。 还有自由变元， 消完之后有i行
2017-11-09 15:56:42
292
原创 模板整理: 图论---差分约束
详细教程看这个，挺不错 到联赛了还要看一遍教程的我是不是没救了= = 主要就记住一个套路， 如果不等式形如x[i]+b<=x[j]， 那么从i向j连一条b的边，跑最长路； 如果不等式形如x[i]+b>=x[j]， 那么从i向j连一条b的边，跑最短路。 求a[x]-a[y]的最值，跑x~y的最长/短路。 如果每个点还有额外限制（比如>=1）， 可以考虑建立超级源啊超级汇啊之类的。
2017-11-09 15:40:02
313
原创 模板整理: 图论---tarjan缩点/桥/割点
tarjan这算法没学好……气哦 目前掌握得还可以的只有缩点， 每次桥和割点只能手推。。还总是推错。 说实话也没什么难的啊。。 缩点,桥,割点之前的学习笔记 先是缩点，也就是强连通分量双联通分量这些东西。 只讨论强连通分量。 比较好理解，用DFN[u]表示到达u的时间（时间戳）， LOW[u]表示u及u的子树中能到达的最早时间戳. 那么想象一下，一个强连通分量，里面有某个u，
2017-11-09 13:21:26
689
原创 bzoj 1257 [CQOI2007]余数之和sum 数学,分段优化
Description给出正整数n和k，计算j(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值，其中k mod i表示k除以i的余数。例如j(5, 3)=3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5=0+1+0+3+3=7Input输入仅一行，包含两个整数n, k。Output输出仅一行，即j(n,
2017-11-09 11:47:35
330
原创 模板整理: 图论---网络流/最小费用最大流
NOIp……应该不会考这东西吧QAQ 考了感觉药丸。。 还是整一个比较好~ 网络流有个特点就是，最坏的上界一般都是达不到的。 1.FF 思路是每次增广1的流量，很慢的，因为容量一般挺大， 没写过，就没模板了。。O(|f|∗m|f|*m)（似乎是，有点忘了） 2.EK 思路是随意找一条增广路径，然后增广即可。 最坏O(m2nm^2n)。 就写过一次……还是早期写的……真是有
2017-11-09 09:58:20
477
原创 模板整理: 图论---最短路
最短路……基础但重要…… 主要有floyd，dijkstra，SPFA这种， 看数据范围的。 floyd还可以用来求传递闭包，也就是连通性的问题。 最短路问题：给出一张图，求s~t的最短路。 1.floyd算法。 使用它的时候一般都是用邻接矩阵计算了……//dis[i][j]一开始的初值：//若输入的边里有(i,j)，则dis[i][j]为其权值//不然dis[i][j]=INF
2017-11-09 09:42:45
521
原创 模板整理: 矩阵乘法
矩阵乘法是个灰常灰常有用的东西！ 先是定义： 矩阵乘法设A，B均为矩阵，An，Am分别表示矩阵A的行数和列数那么只有当Am=Bn的时候，A∗B才是可行的，设Am=Bn，C=A∗B，那么Cn=An，Cm=Bm，C(i,j)=∑A(i,k)∗B(k,j)矩阵乘法\\设A，B均为矩阵，A_n，A_m分别表示矩阵A的行数和列数\\那么只有当A_m=B_n的时候，A*B才是可行的，\\设A_m=B
2017-11-09 09:27:27
506
原创 模板整理:数论---组合数/欧几里得/孙子定理/费马小定理/欧拉定理及相关
对于组合数C(n,m)，意为在n个球中任取m个的方案数， 当n < m时C(n,m)=0， 当n>=m时， C(n,m)=n!m!(n−m)!C(n,m)=\frac {n!}{m!(n-m)!} 组合数的递推式，通常用的一种： C(n,m)=C(n−1,m−1)+C(n−1,m)C(n,m)=C(n-1,m-1)+C(n-1,m) 讨论第n个球取不取即可得出递推式。 通常
2017-11-09 08:39:57
449
原创 bzoj 2216 [Poi2011]Lightning Conductor 决策单调性
Description已知一个长度为n的序列a1,a2,…,an。 对于每个1<=i<=n，找到最小的非负整数p满足 对于任意的j, aj < = ai + p - sqrt(abs(i-j)) Input 第一行n，(1<=n<=500000) 下面每行一个整数，其中第i行是ai。(0<=ai<=1000000000)Output n行，第i行表示对于i，得到的pSample Input
2017-11-08 20:52:23
325
原创 bzoj 2208 [Jsoi2010]连通数 bitset
DescriptionInput 输入数据第一行是图顶点的数量，一个正整数N。 接下来N行，每行N个字符。第i行第j列的1表示顶点i到j有边，0则表示无边。 Output 输出一行一个整数，表示该图的连通数。 Sample Input 3 010 001 100 Sample Output 9 HINT对于100%的数据，N不超过2000。 传送门 沙伯题……数据还水…… 就
2017-11-08 19:28:03
358
原创 bzoj 2005 [Noi2010]能量采集 O(n)莫比乌斯反演
Description 栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可以采集太阳光的能量。在这些植物采集能量后， 栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。 栋栋的植物种得非常整齐，一共有n列，每列 有m棵，植物的横竖间距都一样，因此对于每一棵植物，栋栋可以用一个坐标(x, y)来表示，其中x的范围是1至n， 表示是在第x列，y的范围是1至m，表示是在第x列的第
2017-11-08 17:57:31
391
原创 bzoj 3944 Sum 杜教筛
DescriptionInput 一共T+1行 第1行为数据组数T(T<=10) 第2~T+1行每行一个非负整数N，代表一组询问Output 一共T行，每行两个用空格分隔的数ans1,ans2Sample Input 612813302333 Sample Output 1 12 022 -258 -3278 -31655470 2HINT 传送门 天天做裸题我没救了…… 第一问
2017-11-08 15:42:23
228
原创 bzoj 2301(1101) [HAOI2011]Problem b 莫比乌斯反演+分段优化
Description对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。 Input 第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、kOutput 共n行，每行一个整数表示满足要求的数对(x,y)的个数Sample Input 22 5 1 5 11 5 1 5 2Sample
2017-11-08 14:38:46
332
原创 bzoj 2789 [Poi2012]Letters 求逆序对
Description 给出两个长度相同且由大写英文字母组成的字符串A、B，保证A和B中每种字母出现的次数相同。 现在每次可以交换A中相邻两个字符，求最少需要交换多少次可以使得A变成B。Input第一行一个正整数n (2<=n<=1,000,000)，表示字符串的长度。 第二行和第三行各一个长度为n的字符串，并且只包含大写英文字母。Output 一个非负整数，表示最少的交换次数。 Samp
2017-11-08 10:01:10
406
原创 bzoj 2081 [Poi2010]Beads 枚举+哈希
Description Zxl有一次决定制造一条项链，她以非常便宜的价格买了一长条鲜艳的珊瑚珠子，她现在也有一个机器，能把这条珠子切成很多块（子串），每块有k（k>0）个珠子，如果这条珠子的长度不是k的倍数，最后一块小于k的就不要拉（nc真浪费），保证珠子的长度为正整数。 Zxl喜欢多样的项链，为她应该怎样选择数字k来尽可能得到更多的不同的子串感到好奇，子串都是可以反转的，换句话说，子串（1，2，
2017-11-07 21:09:37
354
原创 bzoj 1833 [ZJOI2010]count 数字计数 数位dp
Description 给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。 Input 输入文件中仅包含一行两个整数a、b，含义如上所述。 Output 输出文件中包含一行10个整数，分别表示0-9在[a,b]中出现了多少次。 Sample Input 1 99Sample Output 9 20 20 20 20 20
2017-11-07 20:03:03
272
原创 模板整理：数论---线性筛素数，线性筛欧拉函数
线性筛是一个比较有用的东东， 所以得好好记住辣。。。 对于普通的筛素数方法， 就是枚举一个i，然后和所有已知素数prime[j]相乘， i*prime[j]就不是素数了，去掉即可。 如果这样的话是基本O(nlogn)的， 线性筛就是在这个筛法的基础上加入了一个优化， 每次让一个数只被它的最小质因子筛一次， 也就是如果i%prime[j]=0，直接break即可。 这样的话就能优化到
2017-11-07 19:38:46
529
原创 bzoj 4805 欧拉函数求和 杜教筛
Description 给出一个数字N，求sigma(phi(i)),1<=i<=NInput 正整数N。N<=2*10^9Output 输出答案。Sample Input 10 Sample Output 32 HINT 传送门 太神了我竟然才会杜教筛…… 大致写写推导过程吧（虽然都是按照网上的来的QAQ） 设phi(i)表示i的欧拉函数，那么有如下式子： ∑d|iphi(
2017-11-07 19:05:22
460
原创 bzoj 1061 [Noi2008]志愿者招募 单纯形算法
Description 申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难 题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要 Ai 个人。 布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用 是每人Ci 元。新官上任三把火，为了出色地完成自己
2017-11-07 14:11:19
951
原创 Uoj #179 线性规划 单纯形算法
这是一道模板题。 （这个题现在标程挂了。。哪位哥哥愿意提供一下靠谱的标程呀？） 本题中你需要求解一个标准型线性规划： 有 n n 个实数变量 x 1 , x 2 ,…, x n x1,x2,…,xn 和 m m 条约束，其中第 i i 条约束形如 ∑ n j=1 a ij x j ≤ b i ∑j=1naijxj≤bi 。
2017-11-06 21:03:37
437
原创 spoj 1811 LCS 后缀自动机
A string is finite sequence of characters over a non-empty finite set Σ. In this problem, Σ is the set of lowercase letters. Substring, also called factor, is a consecutive sequence of characters occ
2017-11-02 19:48:40
305
原创 一周学习简单总结（二）
噜噜噜……这周上了10+days的课啊QAQ 终于能回次家。。 再大致总结总结这周的东西吧。。 虽然好多题都忘得差不多了= = 1.bzoj3745 一段区间[l,r]的贡献是min{a[l..r]}max{a[l..r]}(r-l+1) 给出序列A，求所有区间的贡献和。 分析:自己YY了一个方法（然而考试里并没有写出来QAQ） 首先一段区间[L,R]内部的贡献+对外部的
2017-11-02 19:35:50
680
原创 bzoj 2818 Gcd 欧拉函数求和
Description给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的 数对(x,y)有多少对.Input一个整数NOutput如题Sample Input4Sample Output4 HINThint对于样例(2,2),(2,4),(3,3),(4,2)1<=N<=10^7 传送门 woc666还有这种坑。。。 （啥坑待会儿讲啦） 看看这道题，看到gcd就有种莫比乌
2017-10-31 19:28:07
541
原创 bzoj 4408 [Fjoi 2016]神秘数 主席树
Description一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。例如S={1,1,1,4,13}，1 = 12 = 1+13 = 1+1+14 = 45 = 4+16 = 4+1+17 = 4+1+1+18无法表示为集合S的子集的和，故集合S的神秘数为8。现给定n个正整数a[1]..a[n]，m个询问，每次询问给定一个区间l,r，求由a[l],a[l+1],…,a[r]
2017-10-31 17:54:28
313
原创 bzoj 4818 [Sdoi2017]序列计数 矩阵乘法优化dp+容斥
DescriptionAlice想要得到一个长度为n的序列，序列中的数都是不超过m的正整数，而且这n个数的和是p的倍数。Alice还希望 ，这n个数中，至少有一个数是质数。Alice想知道，有多少个序列满足她的要求。 Input一行三个数，n,m,p。 1<=n<=10^9,1<=m<=2×10^7,1<=p<=100 Output一行一个数，满足Alice的要求的序列数量，答案对20170
2017-10-31 17:43:44
345
原创 bzoj 2423 [HAOI2010]最长公共子序列 动态规划
Description字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列 < i0，i1，…，ik-1>，使得对所有的j=0，1，…，k-1，有xij = yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的
2017-10-31 16:04:02
309
原创 bzoj 3893 [Usaco2014 Dec]Cow Jog 模拟
DescriptionThe cows are out exercising their hooves again! There are N cows jogging on an infinitely-long single-lane track (1 <= N <= 100,000). Each cow starts at a distinct position on the track, an
2017-10-31 15:40:07
341
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人