- 博客(227)
- 资源 (5)
- 收藏
- 关注
RSS订阅
原创 对于huno的更改[长期更新]
https://lemonoil.github.io看着看着，这个blog就已经跟着我快两年了。最初的好奇造就了这样一个个人blog，这种经历还是十分宝贵的吧。回想当初调试各种参数使之建成不惜弄到了第二天早上，年轻真的疯狂，OI确实疯狂。这篇文章专用来记录我对huno的各种调整。从虾米到网易云一开始我将自己的huno挂在github上时备注的是 ~一个装有虾米音乐的blo...
2018-07-07 16:33:51
852
1
原创 2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Prefer
先给一下结果： 单刷被虐成狗，ACM打到怀疑人生，I题的二分答案太丢人了，干脆退竞赛吧！！ 233，脸上笑嘻嘻，心里。。。。，这个名次也是够讽刺。 上午校内ACM全场划水，草草地a了三道后，坐观队友debug，结果比赛结束也没A，等比赛结束后花了十分钟debug，就A了，队友异样的眼神。下午没吃晚饭（午饭就随便吃了点），饿着肚子肝CF的ACM，结果不计rating！！我那么努力地a题，结果
2017-10-22 15:27:49
2064
原创 我lemonoil又回来了。。才怪。。
eiπ+1=0eiπ+1=0 e^{i\pi}+1=0 E=mc2E=mc2 E=mc^2 Ψ(x,t)=ψ0e−iEt−p→⋅x→ℏΨ(x,t)=ψ0e−iEt−p→⋅x→ℏ \Psi(x,t) = \psi_0 e^{-\frac{i Et - \vec p \cdot \vec x}{\hbar}} H^Ψ=iℏ∂Ψ∂tH^Ψ=iℏ∂Ψ∂t \hat H \Psi = i \h...
2018-03-23 17:34:02
800
1
原创 再见OI，NOIP2017退役
再见OI最后一次在学校电脑上插上自己的键盘……已经通过学军的山寨数据得到自己的大概成绩，我退役是板上钉钉的了。整体来说考得很差，day1考挂了后day2就全部求稳了，最后分数也就一般般。 没有意外模拟题写挂了，这可能是我最大的心结。简单的模拟，就因为两个细节而爆炸。千算万算也没有想到弄死自己的竟然是模拟。 想到自己学习的算法在同伴中也算数一数二的，不免有些唏嘘与遗憾。是什么导致了我的失败？不够努
2017-11-15 17:33:59
1357
原创 立足NOIP谈对于NOIP搜索的看法
近来在洛谷上做了一些NOIP往届的搜索题，也研究了一下NOIP的数据，发现并不简单。除了每年一次的游戏题外，其他题目往往还算简单。 那么历届NOIP卡AK的方法除了树上题目与图论的巧用（暂时还没有外），就只有搜索是最大的利器了。多种需要考虑的状态，抛弃了DP灵巧的状态设计，注重贪心与模型转化类的剪枝（NOIP的剪枝往往缺失套路性，一题一类剪枝）。所以后期比赛想要在NOIP上拔得头筹必须稳住搜索。我
2017-10-26 16:17:42
3375
原创 用一道题水过积性函数
就以这道SB题为例，我们来讨论一下实际题目中解决积性函数的简单问题(？). blog主蒟蒻，如果要找数论神犇请%%%idy002，或者数论大佬%%%%%Doggu。所以就不给数学上的证明了，请自学（？死记莫比乌斯反演公式）。开始： 先考虑数据范围，10710^7,很明显，线性筛。 首先一看这个函数就有φμσ0(就是τ)\varphi \, \mu \, \sigma_0(就是 \ta
2017-10-20 15:03:24
318
原创 数论训练 {限制} [扩展gcd][组合数][容斥原理]
校内题目{限制}不仅仅局限与题目本身。扩展gcd可以解决ax+by=cax+by=c的问题， 转换为d=gcd(a,b)d=gcd(a,b),a∗x/d+b∗y/d=c/da*x/d+b*y/d=c/d的问题。 因为EX_GCD可以解决形如a∗x+b∗y=gcd(a,b)a*x+b*y=gcd(a,b)的问题。 原理如下： gcd(a,b)=gcd(b,amodb)gcd(a,b) = gc
2017-10-19 18:50:29
374
原创 VIJOS1769 网络的关键边 [Tarjan][桥]
网络的关键边描述考虑一个连通的无向图，可以知道，任意两个节点都可以通过一条路径连接起来。在所有节点中，某些节点向所有与它连通的节点提供A服务（包括向它自己），同时某些节点向所有与它连通的节点提供B服务（也包括向它自己）。注意一个节点也可能同时提供A、B两种服务。当图中的某条边E被去掉的时候，如果图中有任何一个点无法接受A服务或者接受B服务，我们称E边为关键边。那么，你需要做的事情就是：1、输出图中
2017-10-18 21:27:53
372
原创 BZOJ2142 礼物 [扩展lucas定理]
2142: 礼物Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 1820 Solved: 764[Submit][Status][Discuss]Description一年一度的圣诞节快要来到了。每年的圣诞节小E都会收到许多礼物，当然他也会送出许多礼物。不同的人物在小E心目中的重要性不同，在小E心中分量越重的人，收到的礼物会越多。小E从商店中购买了n
2017-10-18 20:05:03
474
原创 BZOJ2976 出圈游戏 [EX_CRT]
2976: [Poi2002]出圈游戏Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 110 Solved: 30[Submit][Status][Discuss]Description思考扩展GCD解决mod非质数的扩展CRT问题。 第i轮有n−i+1个人，记为mi，n只有20，暴力算出该轮出圈的是第几个，记为ri。 −>-> Ans≡r1m
2017-10-18 16:55:17
648
原创 BZOJ1477 青蛙的约会 [扩展欧几里得]
1477: 青蛙的约会Time Limit: 2 Sec Memory Limit: 64 MBSubmit: 891 Solved: 519[Submit][Status][Discuss]Description 两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，
2017-10-18 15:33:04
345
原创 BZOJ3884 上帝与集合的正确用法 [欧拉函数]
3884: 上帝与集合的正确用法Time Limit: 5 Sec Memory Limit: 128 MBSubmit: 2819 Solved: 1264[Submit][Status][Discuss]Description根据一些书上的记载，上帝的一次失败的创世经历是这样的：第一天， 上帝创造了一个世界的基本元素，称做“元”。第二天， 上帝创造了一个新的元素，称作“α”。“α”
2017-10-18 15:04:49
326
原创 图论训练 混合调酒 [最短路][好题]
这道题果然质量（防AK了………………）混合调酒(d.cpp,1s,256MB)【描述】 酒吧里有 k 种鸡尾酒，每种的酒精含量（体积分数）为 ai/1000 。你想喝到酒精含量为 n/1000 的酒，因此你想要把一些鸡尾酒混合起来以达到目的。混合后酒精含量的定义为所有参与混合的鸡尾酒中酒精的体积和除以所有参与混合的鸡尾酒的体积和。你想知道最少需要购买多少杯鸡尾酒才能满足条件。假设每种鸡尾酒都无限供
2017-10-17 22:06:13
371
原创 图论训练 车站分级 [数据结构优化建边][拓扑排序]
NOIP普及组原题疯狂加难度的hard版车站分级(c.cpp,0.5s, 256MB)【描述】 一条单向的铁路线上，依次有编号为 1, 2, …, n 的 n 个火车站。每个火车站都有一个级别，最低为 1 级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站 x，则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠。（注意：起始站和终点站自然也算作事先已知需要
2017-10-17 22:01:01
416
原创 图论训练 重量差异 [并查集]
懒得找原题了，全是模板题。。。。重量差异(b.cpp,1s,256MB)【描述】 在实验室中，Nathan Wada作为助手的职责是测定两个样品的重量差异。当样品的差异很小时，使用天平比使用弹簧秤能得到更精确的结果，所以Nathan Wada只使用天平来测得一些样品的重量差。Nathan Wada偶尔会被询问一些样品的重量差，而他能否回答这些问题取决于在回答相应问题时他已经得到的测量结果。由于Na
2017-10-17 21:56:21
758
原创 图论训练 礼物分配 [差分约束]
差分约束模板题，注意判定条件要形成三角约束，不能忘记-1。礼物分配（a.cpp,1s,256MB)【描述】 为了庆祝大佬wxh的生日，众人决定为他准备礼物。现在有n个礼品盒排成一行，从1到n编号，每个礼品盒中可能有1个或0个礼品。大佬wxh提出了m个要求，形如“第l[i]到第r[i]个礼品盒当中至少有c[i]个礼品”。现在众人想知道，为了满足这些要求，所需准备的最少礼品数。 【输入】 第一行两
2017-10-17 21:50:49
410
原创 DP训练 cdoj1354 柱爷很忙 [状压DP]
找到原题 真当我不做CDOJ?工作 (work.pas/cpp/c)【题目描述】 有N件事，每件事有两个属性a，b，现在你要以某种顺序做完这N件事，考虑这个人目前做的事情是i，他做的前一件事是j，那么他做这件事的代价就是(a[i] | a[j]) – (a[i] & a[j])，如果前面没有做事，那么代价就是a[i]，但是事情总有轻重缓急之分，按原本顺序的事i最多能推迟到做完任意件紧接着事i之后的
2017-10-17 21:27:16
342
原创 DP训练 玲珑杯线上赛 Round #15 河南专场：A -- Reverse the lights [线性DP]
又找到原题。开关灯 (lamp.cpp/c/pas)【题目描述】 有n个灯，初始时都是不亮的状态，每次你可以选择一个某一个灯，不妨记为x，所有满足和x距离不超过k的灯的状态都将被翻转，选择第i个灯的代价记为c[i]，问最终所有灯都是亮的状态的最小花费。 【输入格式】 输入有两行，第一行包含两个正整数n , k。 第二行包含n个整数，分别表示c[i]。 【输出格式】 一行，表示最小花费。
2017-10-17 21:17:35
484
原创 DP训练 Codeforces 673E Levels and Regions [斜率优化dp][期望]
找到原题。游戏 (game.cpp/c/pas)【题目描述】 有n个数，编号从1到n。现在把n个数分成k组编号为1到k，使得每组内的数必须连续，组与组之间不能相交并且每个数必须属于一个组。 游戏进行的过程如下： 1. 如果n个数都已经获得了，游戏结束。否则，找到编号最小没有全部获得的组X。 2. 游戏系统会给一个空的盒子，对于组X中已经获得的数i，将ti张写着数i的卡片放入盒子中，对于组X中
2017-10-17 21:12:45
416
原创 DP训练 CDOJ1321柱爷的恋爱 [区间dp]
此题原本为我下午准备讲课的题，居然。。。10分钟ac这运气。。。果真我cdoj做多了。括号匹配 (parenthesis.pas/cpp/c)【题目描述】 给出长度为N的括号序列（只包含(,),[,]），问有多少种方法删掉这些括号的一个子集，使得剩下的括号序列是合法的，请注意不能全部删完。 【输入格式】 输入的第一行是一个整数N，表示序列的长度。 接下来一行N个字符，表示括号序列。 【输出
2017-10-17 20:59:59
344
原创 DP训练 Codeforces 816E Karen And SuperMarket [树形DP]
找到原题。购物 (shopping.cpp/c/pas)【题目描述】 商店里有n个物品，第i个物品的价格为ci元。每个物品只能买一次。商店发行了n张优惠券，每个物品各有一张优惠卷。如果使用了第i张优惠券，可以使该物品便宜di元钱，必须买商品才能够使用相对应的优惠券。第1张优惠卷可以无条件使用，但对于第i>=2张优惠卷，如果需要使用第i张优惠券，则必须先使用xi这张优惠券。 现在有b元钱，问最多能
2017-10-17 20:55:48
417
原创 DP训练 codeforces 372C Watching Fireworks is Fun [单调队列优化dp]
找到原题烟火 (fireworks.cpp/c/pas) 【题目描述】 城镇的主干道上有n个区域，从左到右编号为1到n，每个区域之间相距1个单位距离。在节日中要放m个烟火，第i个烟火会在ti时刻的ai区域放。如果在ti时刻你所处区域为x，那么你可以获得bi - | ai - x |的快乐值。在每个单位时间你可以移动不超过d个单位距离，初始的位置是任意的，求通过移动能获得快乐值和的最大值。 【输
2017-10-17 20:48:09
454
原创 BZOJ1084 最大子矩阵 [DP]
1084: [SCOI2005]最大子矩阵Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 3017 Solved: 1510[Submit][Status][Discuss]Description 这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵 不能相互重叠。Input 第一行为n,m,k
2017-10-13 21:21:01
263
原创 BZOJ1072 排列perm [暴搜]
1072: [SCOI2007]排列permTime Limit: 10 Sec Memory Limit: 128 MBSubmit: 2557 Solved: 1592[Submit][Status][Discuss]Description 给一个数字串s和正整数d, 统计s有多少种不同的排列能被d整除（可以有前导0）。例如123434有90种排列能 被2整除，其中末位为2的有30种，末
2017-10-13 19:52:12
232
原创 BZOJ1083 繁忙的都市 [MST]
1083: [SCOI2005]繁忙的都市Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 3590 Solved: 2247[Submit][Status][Discuss]Description 城市C是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市C的道 路是这样分布的：城市中有n个交叉路口，有些交叉路口
2017-10-13 19:35:20
335
原创 BZOJ1081 超级格雷码 [找规律]
1081: [SCOI2005]超级格雷码Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 639 Solved: 372[Submit][Status][Discuss]Description 著名的格雷码是指2n个不同n位二进制数（即0~2n-1，不足n位在前补零）的一个排列，这个排列满足相邻的两 个二进制数的n位数字中最多只有一个数字不同（例
2017-10-13 14:24:51
537
原创 BZOJ1055 玩具取名 [区间DP]
1055: [HAOI2008]玩具取名Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 2047 Solved: 1198[Submit][Status][Discuss]Description 某人有一套玩具，并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好，将名字中任意一个字母用“WING”
2017-10-13 12:28:34
279
原创 BZOJ1054 移动玩具 [BFS][HASH]
1054: [HAOI2008]移动玩具Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 2407 Solved: 1345[Submit][Status][Discuss]Description 在一个4*4的方框内摆放了若干个相同的玩具，某人想将这些玩具重新摆放成为他心中理想的状态，规定移动时只能将玩具向上下左右四个方向移动，并且移动的位置不能有
2017-10-13 12:00:58
375
原创 BZOJ1053 反素数ant [打表]
1053: [HAOI2007]反素数antTime Limit: 10 Sec Memory Limit: 162 MBSubmit: 3593 Solved: 2107[Submit][Status][Discuss]Description 对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足：g(x)>g(i) 0<i<x，则称x为反质数。例如
2017-10-13 11:24:17
319
原创 BZOJ1049 数字序列 [DP]
1049: [HAOI2006]数字序列Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 1732 Solved: 745[Submit][Status][Discuss]Description 现在我们有一个长度为n的整数序列A。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。 但是不希望改变过多的数，也不希望改变的幅度太大。Inp
2017-10-13 11:09:17
347
原创 BZOJ1046 上升序列 [二分][贪心]
1046: [HAOI2007]上升序列Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 5222 Solved: 1815[Submit][Status][Discuss]Description 对于一个给定的S={a1,a2,a3,…,an},若有P={ax1,ax2,ax3,…,axm},满足(x1 < x2 < … < xm)且（ ax1 <
2017-10-13 10:42:53
263
原创 BZOJ1003 物流运输 [最短路][DP]
1003: [ZJOI2006]物流运输Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 8494 Solved: 3588[Submit][Status][Discuss]Description 物流公司要把一批货物从码头A运到码头B。由于货物量比较大，需要n天才能运完。货物运输过程中一般要转 停好几个码头。物流公司通常会设计一条固定的运输路线，
2017-10-13 09:50:04
555
原创 BZOJ1143 祭祀river [二分图最大匹配]
1143: [CTSC2008]祭祀riverTime Limit: 10 Sec Memory Limit: 162 MBSubmit: 2991 Solved: 1528[Submit][Status][Discuss]Description 在遥远的东方，有一个神秘的民族，自称Y族。他们世代居住在水面上，奉龙王为神。每逢重大庆典， Y族都会在水面上举办盛大的祭祀活动。我们可以把Y族居住地
2017-10-13 08:48:08
266
原创 BZOJ1726 Roadblocks第二短路 [次短路]
1726: [Usaco2006 Nov]Roadblocks第二短路Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 1330 Solved: 631[Submit][Status][Discuss]Description贝茜把家搬到了一个小农场，但她常常回到FJ的农场去拜访她的朋友。贝茜很喜欢路边的风景，不想那么快地结束她的旅途，于是她每次回农场，都会
2017-10-12 21:55:38
647
原创 BZOJ1718 分离的路径 [边双联通][模板]
就是边双联通分量的模板题，注意一下++的位置，tot的初始值……，至于那个（leaf+1）/2,感性理解一下就好了。 若要使得任意一棵树，在增加若干条边后，变成一个双连通图，那么至少增加的边数 =（ 这棵树总度数为1的结点数 + 1 ）/ 2。1718: [Usaco2006 Jan] Redundant Paths 分离的路径Time Limit: 5 Sec Memory Limit:
2017-10-12 20:43:00
372
原创 BZOJ3694 最短路 [最短路径树]
3694: 最短路Time Limit: 5 Sec Memory Limit: 256 MBSubmit: 231 Solved: 119[Submit][Status][Discuss]Description给出一个n个点m条边的无向图，n个点的编号从1~n，定义源点为1。定义最短路树如下：从源点1经过边集T到任意一点i有且仅有一条路径，且这条路径是整个图1到i的最短路径，边集T构成最短路树
2017-10-11 15:39:05
826
原创 BZOJ 1467&&2480;3239 扩展BSGS
2480: Spoj3105 ModTime Limit: 10 Sec Memory Limit: 128 MBSubmit: 797 Solved: 273[Submit][Status][Discuss]Description已知数a,p,b，求满足a^x≡b(mod p)的最小自然数x。 Input 每个测试文件中最多包含100组测试数据。 每组数据中，每行包含3个正整数a,
2017-10-11 14:47:12
648
原创 BZOJ3504 危桥 [最大流]
3504: [Cqoi2014]危桥Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1693 Solved: 843[Submit][Status][Discuss]DescriptionAlice和Bob居住在一个由N座岛屿组成的国家，岛屿被编号为0到N-1。某些岛屿之间有桥相连，桥上的道路是双 向的，但一次只能供一人通行。其中一些桥由于年久失修
2017-10-11 13:58:35
273
原创 BZOJ2648&&2716 不讲道理的KD-tree
不得不承认KDtree的却是二维空间类距离处理利器，省去了树套树繁琐的操作，code简洁明了。为了防止KDtree我还特意加上了rebuild的操作……结果反而更满了……，cnt太小<=70000还会TLE……WCO哎，KDTREE就那样吧，随便打打，开心开心就好了。//去掉rebuild操作更快。#include<bits/stdc++.h>inline int maxn(int x,int
2017-10-10 21:59:41
741
原创 BZOJ1725 Corn Fields牧场的安排 [状压DP]
1725: [Usaco2006 Nov]Corn Fields牧场的安排Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 780 Solved: 554[Submit][Status][Discuss]DescriptionFarmer John新买了一块长方形的牧场，这块牧场被划分成M列N行(1<=M<=12; 1<=N<=12)，每一格都是一块正方形
2017-10-10 20:41:02
310
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人