1 codancer

尚未进行身份认证

为信仰而战斗

等级
博文 174
排名 3w+

BZOJ 1003: [ZJOI2006]物流运输(最短路+DP)

题面题意:现在有一个mmm个点eee条边的无向连通图,总共有nnn天,你每天都选取一条路径使得111到mmm的花费最小,可是在[ai,bi][a_i,b_i][ai​,bi​]天,某个节点did_idi​不能走,现在你要求这nnn天总花费最少为多少。思路:我们先标记编号为iii的点是否能在jjj天行得通,然后预处理出从第iii天到第jjj天在不改变路径情况下的最短路。接下来进行DP:我...

2019-06-12 21:07:08

拉格朗日插值的应用

引言:什么是拉格朗日插值?假设我们现在有三个点(x1,y1),(x2,y2),(x3,y3)(x_1,y_1),(x_2,y_2),(x_3,y_3)(x1​,y1​),(x2​,y2​),(x3​,y3​),现在我们要找一条唯一的二次曲线刚好经过这三个点。拉格朗日给出了一个绝妙的方法,他把我们要求的曲线的表达式等同于三个函数的累加。具体是这么操作的:第一个函数保证f1(x1)=1,f1(...

2019-06-03 19:36:51

The 13th Chinese Northeast Collegiate Programming Contest 部分题解

B.BalancedDiet题意:商店有mmm种nnn个糖果,每个糖果有一个权值,现在你要买一些糖果使得Sc\frac{S}{c}cS​最大,其中SSS为你购买的糖果的权值和,ccc为你购买的出现次数最多的那种糖果出现的种类数,但是每种糖果的购买数量不能在[1,li)[1,l_i)[1,li​)之间。思路:枚举ccc,利用前缀和求得购买的每种糖果的权值和,更新最大值。代码:#inc...

2019-05-31 18:16:10

Codeforces Round #562 (Div. 2) A B C D题解

A.CircleMetro直接模拟即可。#include<bits/stdc++.h>usingnamespacestd;intmain(){ intn,a,x,b,y; cin>>n>>a>>x>>b>>y; for(inti=1;i<=300;i++){ if(a<n)a++...

2019-05-30 19:00:03

百度AI小课堂-上升子序列(中等)(二分图染色+DP)

题面题意:一个长度为nnn的数组aaa,把他拆分成两个严格递增的数组,使得这两个数组的长度差值最小。无解输出−1-1−1.思路:对于i<ji<ji<j并且ai>=aja_i>=a_jai​>=aj​那么说明aia_iai​和aja_jaj​一定不能在同一个数组中,我们对于不能在同一组的连接一条无向边,构成一个无向图,如果这...

2019-05-27 10:43:32

Tarjan算法专练

1.迷宫城堡题意:给一个图判断是否是强连通图。题解:利用Tarjan计算图中强连通分量的个数,如果为1则是强连通图,否则不是。#include<bits/stdc++.h>usingnamespacestd;constintN=2e4+100;typedeflonglongll;vector<int>G[N];boolis_insta...

2019-05-12 15:13:51

【BZOJ 1821】[CQOI2009]中位数图(思维)

题面题意:Description给出1~n的一个排列,统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后,位于中间的数。Input第一行为两个正整数n和b,第二行为1~n的排列。Output输出一个整数,即中位数为b的连续子序列个数。SampleInput745724316SampleOutput4HINT第三...

2019-03-03 12:01:40

【BZOJ 1821】[JSOI2010]Group 部落划分 Group(并查集)

[BZOJ1821][JSOI2010]Group部落划分Group(并查集)题面题意:聪聪研究发现,荒岛野人总是过着群居的生活,但是,并不是整个荒岛上的所有野人都属于同一个部落,野人们总是拉帮结派形成属于自己的部落,不同的部落之间则经常发生争斗。只是,这一切都成为谜团了——聪聪根本就不知道部落究竟是如何分布的。不过好消息是,聪聪得到了一份荒岛的地图。地图上标注了N个野人居住的地点...

2019-03-02 22:07:46

【BZOJ 1191】[HNOI2006]超级英雄Hero(二分图匹配/枚举)

题面题意:一个有奖问答节目,有nnn个问题,mmm个锦囊。每道题你可以在某两个锦囊之间选择一个使该题通过。假设你一道题不会。在回答过程中如果错误则游戏结束。求最多通过几道题。IDEA:我们枚举回答的最后一个问题iii,每次从问题1−i1-i1−i匹配对应的锦囊。如果满足完美匹配则继续。否则输出答案。code:#include<bits/stdc++.h>usingnam...

2019-03-01 22:09:21

【HDU-1045 】Fire Net(二分图匹配/最大流)

题面题意:有一个nnnxnnn的区域。黑色为墙,白色为空白,你现在要在空白区域安装大炮。大炮的可以摧毁同行和同列的所有物品,但是大炮无法摧毁墙。求为了避免大炮之间两两攻击,最多放几门大炮。IDEA:我们构造二分图,左面的nnn个点为行,右面的nnn个点为列。如果对于第iii行有numnumnum个不连续的空白区域,说明第iii行最多可以和numnumnum列进行匹配。如果第jjj列有num...

2019-02-26 17:50:13

数论知识点总结(待更新)

数论知识点总结1.gcd1.gcd1.gcd(最大公约数)对于给出的两个数a,ba,ba,b,我们可以用欧几里得算法来计算最大公约数。欧几里得算法的精髓就在于下面这个公式:gcd(a,b)=gcd(b,agcd(a,b)=gcd(b,agcd(a,b)=gcd(b,a%b)b)b)证明:已知:gcd(a,b)∣agcd(a,b)|agcd(a,b)∣a并且gcd(a,b)∣bgcd(a,...

2019-02-26 17:41:03

【数据结构--Huffman编码】优先队列+栈实现

#include<bits/stdc++.h>usingnamespacestd;typedefstruct{ intweight; intid; intpar,lchild,rchild;}HTNode,*HuffmanTree;priority_queue<HTNode&

2018-10-25 17:27:11

【洛谷 P3381】最小费用最大流(SPFA+EK)

在最大流的基础上把BFS换成SPFA即可。#include<bits/stdc++.h>usingnamespacestd;constintmaxn=100050;constintINF=0x3f3f3f3f;inthead[maxn];boolvis[maxn];intdis[maxn];intflow[maxn];intn,m,s,t...

2018-10-10 09:47:32

【2016ICPC 沈阳onsite C】Recursive sequence(矩阵快速幂)

题面给你一个递推式F[n]=2∗F[n−2]+F(n−1)+n4F[n]=2*F[n-2]+F(n-1)+n^4F[n]=2∗F[n−2]+F(n−1)+n4求F(n)F(n)F(n).我原本以为矩阵快速幂只能用来求线性递推,还是太菜了。对于这个题母,我们注意到有有一个n4n^4n4,我们怎么办呢。因为我们无法线性的从n4n^4n4到(n+1)4(n+1)^4(n+1)4,但是我们可以分...

2018-10-05 16:18:59

【51nod 1021】石子归并(区间dp入门)

1021石子归并基准时间限制:1秒空间限制:131072KB分值:20难度:3级算法题收藏关注N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。例如:1234,有不少合并方法1234=>334(3)=>64(9)...

2018-10-05 10:22:33

【ACM模板】~持续更新

1、组合公式+逆元阶乘打表voidinit(){ fact[0]=inv[1]=factinv[0]=inv[0]=fact[1]=factinv[1]=1; for(inti=2;i<=MAXN;i++){ fact[i]=(fact[i-1]%mod*i%mod)%mod; inv[i]=(mod-mod/i)*inv[mod%i]%mod; factinv[i]=...

2018-10-03 22:15:01

【算法】01分数规划

昨天做训练赛的时候遇到了一道求最优比率的题,不会写,学长说是用01分数规划来做,于是就看了一下入门级别的。在这里先写一下自己的心得。01分数规划就是利用二分来查找最优比率的问题。首先我们看一下nyoj的一道题目:Yougth的最大化题意是每个物品都有自己的价值和重量,让你选K个物品使得这K个物品的单位价值即(v/w)最大。我们假设单位价值为t;那么对于单个物品就有v/w=tv/w=tv/w...

2018-10-03 10:23:44

【The North American Invitational Programming Contest 2016 】I、Tourists

6000ms262144KInTreeCity,therearennntouristattractionsuniquelylabeled111tonnn.Theattractionsareconnectedbyasetofn−1n-1n−1bidirectionalroadsinsuchawaythatatouristcan...

2018-10-02 15:00:36

【HDU 1695】GCD(莫比乌斯反演)

GCDTimeLimit:6000/3000MS(Java/Others)MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):16412AcceptedSubmission(s):6314ProblemDescriptionGiven5integers:a,b,c,d,k,...

2018-09-28 17:30:09

【数学技巧】整除分块

在对于求解∑i=1n⌊ni⌋\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor∑i=1n​⌊in​⌋的时候,一般暴力跑的话需要O(n)O(n)O(n)的复杂度。但是很神奇的事情是有一段的⌊ni⌋\lfloor\frac{n}{i}\rfloor⌊in​⌋是相等的,这样对于每一段我们只需要计算一次即可。因此我们的代码可以这样写for(intl=1,r;l&lt...

2018-09-27 10:44:19
奖章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周上午根据用户上周的博文发布情况由系统自动颁发。