3 lethalboy

尚未进行身份认证

暂无相关简介

等级
TA的排名 2w+

求解两个日期之间相隔的天数 C++

首先考虑将日期转化成编号,使得编号差就是日期的天数差对于y年m月d日来说,令其编号为从公元1年1月1日到这天(包括这天)的天数前y-1年的天数就是 (y-1)*365+(y-1)/4-(y-1)/100+(y-1)/400第y年的前m-1个月的天数可以暴力求出(注意判断闰年的2月)第y年第m个月的天数就是d了 代码如下:boolcheck(intx)//判...

2018-07-27 11:47:31

poj1696

题意:有一只右眼坏掉的外星虫子,只能左拐(逆时针转向),平面上有一些食物,设y坐标最小的食物的y坐标为y0,则虫子从(0,y0)出发,行走路径不能相交,也不能沿路返回,问最多吃掉多少食物。解法:不断求凸包知识点:凸包的求法(我用了Graham)代码:#include#include#include#include#include#defineN200020#d

2017-10-15 12:55:08

poj1066

题意:一个由四条长为100的线段围起来的正方形区域,有n条内部的端点在边界的线段,现可以从边界任意一点出发,穿过线段中点,区域内有一宝藏,求要拿到宝藏需要至少穿过多少条线段(包括边界)。解法:到达边界终点后可以在空白区域随意移动,所以枚举边界上的出发点贪心的将出发点与宝藏连起来判断与多少线段严格相交即可。知识点:判断线段相交代码:#include#include#incl

2017-10-15 12:51:27

poj2653

数据随机,topstick不超过1000,可以直接暴力知识点:判断两个线段是否相交————向量叉积代码:#include#include#include#include#include#defineN200020#defineeps1e-7#definesosudoubleusingnamespacestd;intn;structnode{s

2017-10-15 12:46:40

bzoj1041 圆上的整点(一种新奇的思路)

用了一种新奇的方法重温了这道题目。学弟发来的定理很妙呦orz:有上述定理,则问题转化为求r^2的%4余1因子数和%4余3因子数。用约数个数定理,去掉偶因子后可以求出两者之和因此,求其中一种即可。从%4余1的因子数下手吧易知%4余1的因子定是由任意多个%4余1的质数和偶数个%4余3的质数相乘得来的任意多个%4余1的质数实际上就是最大的%4余1的质数的因子数,

2017-06-15 10:05:58

bzoj3265 noi2008志愿者招募 【线性规划】

听说这是道费用流神题,学了线性规划后发现这题好裸.......目标函数 min{ci*xi}约束方程 sigma(s[i,j]*xj>=ai)发现转化成对偶问题后不用处理常数项为负的情况所以,转化成对偶问题:目标函数 max{ai*yi}约束方程 sigma(s[j,i]*yj效率对比:不转化对偶问题,用辅助型直接做:

2017-05-28 14:25:54

带花树算法

算法思想:①找增广路②过奇环中任意一点有增广路,则过奇环亦有增广路,所以可以将奇环缩点算法流程:以一个当前未匹配上的点为s点,染为白色,bfs染色,只许白点进队。当两个白色点有边时,说明遇到奇环,缩点。当遇到一个未染色且未匹配点时,找到增广路,修改匹配后退出。代码:#include#defineN200020usingnamespacestd

2017-05-25 16:00:12

Codeforces Round #411 (Div. 2) 题解

A:l=r时输出l,否则输出2(没判l=rwa到哭)B:根本不需要c,形如aabb的字符串一定满足要求C:显然凑越多的(i+j)=n+1越好,且之间转移的代价亦要最小,容易发现转移的最小代价为1,所以答案就是(n/2)-1+(n&1)D:发现最终的字符串前半部分都是b,后半部分都是a,且a的个数不变,b增加的个数就是最小操作数,那么实际上一次操作就相当于将a右移一位并在左侧多加一

2017-05-05 13:07:23

hdu2899 (三分/二分/模拟退火)

题目大意:求函数的最小值,y为给出的实数,x∈[0,100]解法①:  首先x>=0可知,函数在定义域上为单峰凹函数,三分即可。解法②:  对函数求导,当导函数为0时取得极值,发现导函数为增函数,二分即可。解法③:  模拟退火可以求峰值函数最值,套用即可。注意:精度恶心,解法①②eps最好开到1e-7,解法③开到1e-8效率:三

2017-04-20 17:52:09

bzoj 2445 最大团(阶乘取模+中国剩余定理CRT)

题意即求下式:m∑x|nn!(x!)nx(nx!)m∑x|nn!(x!)nx(nx!)m∑x|nn!(x!)nx(nx!)m∑x|nn!(x!)nx(nx!)根据欧拉定理: 对于互质的正整数a和n,有 aφ(n) ≡1modn  可知,求指数式子模1e9-402的值然后快速幂即可。O(sqrt(n))分解质因数求值,注意

2017-04-18 10:00:10

bzoj2001 [Hnoi2010]City 城市建设 动态最小生成树

昨晚水冬令营课件看到这题,感觉蛮有意思的,学习了一波,抽象式理解,今天又看了大佬的代码,彻底弄懂了这个东西。WC2013顾昱洲在《浅谈一类分治算法》中提到了动态最小生成树的分治做法,我来梳理下我的理解。这个算法有两个重要的操作:①reduction:对于一张图,reduction操作的目的是删除一定不会出现在最小生成树中的边,以此减小图的规模流程:我们假设对于当前这张图,有

2017-04-13 17:31:40

poj2449 K短路模板题

昨晚看WC论文发现自己连K短路的经典A*算法还不会,补了一波,模板题输出-1后没return继续跑wa了一早上......算法流程:①在反向图中求出t到每个点的最短路②从原点bfs,估价f=d+dis[x],即当前已走的路径长度+最短路径③遇到第k次汇点就是答案据说这复杂度是O(n*k)的....不会证.....代码:#include#include

2017-04-13 11:13:36

博弈知识小汇(省选复习)

只汇总出OI中常见的博弈定理或结论,不给出证明,需要证明可自行百度。一:(Nim系列)①Nim博弈题设:有n堆石子,第i堆有ai个石子,两人进行游戏,每轮可以选择一堆取出若干石子(>1),不能取者败。结论:令S=a1^a2...^an,若S=0则先手必败,否则先手必胜②Nim扩展题设:有n堆石子,第i堆有ai个石子,两人进行游戏,每轮可以选择一堆取出结论:让所有a

2017-03-31 17:53:20

codeforces 789 div2 题解

被闹钟叫醒再睡过真是心塞,只好熬得更晚刮完div2作补偿.......AB就略了吧,B稍稍有点恶心但也是代码题C的话是可以预先处理出差分后的绝对值序列,然后发现实际上就是求这个序列的最大子段和,基础dp知识D有点意思,要分两部分来算,一部分是自环,另一部分是其他边,发现自环集合里随便取两个作为只经过一次的都是可行的,所以是C(num,2),这个显

2017-03-30 05:44:04

poj2154 color (polya定理+欧拉函数)

ColorTimeLimit: 2000MS MemoryLimit: 65536KTotalSubmissions: 10277 Accepted: 3348DescriptionBeadsofNcolorsareconnectedtogetherintoacircularnecklaceof

2017-03-27 11:49:26

莫比乌斯反演复习(省选复习)

公式: ①②莫比乌斯函数:•mu[i]为莫比乌斯函数,定义如下:•(1)若i=1则mu[i]=1•(2)若i=p1*p2*p3...pk,pi为互异素数,那么mu[i]=(-1)^k•(3)其它情况下mu[i]=0有性质:证明不是重点,略。莫比乌斯函数的线性筛法在两篇前的博客中已经提到problem1:bzoj2440莫

2017-03-26 21:42:22

简单数论知识梳理(省选复习)

(noip数论算法汇总)①扩展欧几里得intex_gcd(inta,intb,int&x,int&y){ if(!b) { x=1,y=0; returna; } intg=ex_gcd(b,a%b,x,y); intt=x;x=y,y=t-a/b*y; returng;}应用及要点:one: 求形如ax+by=gcd(a,b)的一组解(

2017-03-23 21:14:01

利用线性筛法解决的数学函数或问题小汇(省选复习)

准备省选的过程中发现数学这一块的结论是学的快忘得也快,而因此就有了总结出一篇博客来深化记忆同时也方便大家学习,我会在接着的几个博客中重点梳理数学相关的知识内容,有什么疏漏或不足之处还望指出。①线性筛法求素数(略)voidinit(){ for(inti=2;i<=n;i++) { if(!vis[i])prime[++cnt]=i; for(intj=1;j

2017-03-23 20:13:29

bzoj2049洞穴勘测(lct模板题,lct详解)

2049:[Sdoi2008]Cave洞穴勘测TimeLimit: 10Sec  MemoryLimit: 259MBSubmit: 8231  Solved: 3881[Submit][Status][Discuss]Description辉辉热衷于洞穴勘测。某天,他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测,辉辉发现这片区域由n个洞穴(分别

2017-03-23 18:04:32

codeforces 785E. Anton and Permutation

E.AntonandPermutationtimelimitpertest4secondsmemorylimitpertest512megabytesinputstandardinputoutputstandardoutputAntonlikespermutations,especial

2017-03-17 11:39:44

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!