• 等级
  • 8256 访问
  • 161 原创
  • 2 转发
  • 34424 排名
  • 3 评论
  • 20 获赞

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

在最大流的基础上把BFS换成SPFA即可。 #include<bits/stdc++.h> using namespace std; const int maxn = 100050; const int INF = 0x3f3f3f3f; int head[maxn]; bool vis[maxn]; int dis[maxn]; int flow[maxn]; int n,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 秒 空间限制:131072 KB 分值: 20 难度:3级算法题 收藏 关注 N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。 例如: 1 2 3 4,有不少合并方法 1 2 3 4 => 3 3 4(3) => 6 4(9) ...

2018-10-05 10:22:33

【ACM模板】~持续更新

1、组合公式+逆元阶乘打表 void init(){ fact[0]=inv[1]=factinv[0]=inv[0]=fact[1]=factinv[1]=1; for(int i=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

6000ms 262144K In Tree City, there are nnn tourist attractions uniquely labeled 111 to nnn. The attractions are connected by a set of n−1n - 1n−1 bidirectional roads in such a way that a tourist can ...

2018-10-02 15:00:36

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

GCD Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 16412 Accepted Submission(s): 6314 Problem Description Given 5 integers: 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(int l=1,r;l&lt...

2018-09-27 10:44:19

【codeforces Div2】Technocup 2019 - Elimination Round 1(A,B,C)

Technocup 2019 - Elimination Round 1 比赛迟到了15分钟。 (A) 大水题就不说了,有1输出HARD,否则输出NO; #include<bits/stdc++.h> using namespace std; const int maxn = 1e6+10; const int INF = 0x3f3f3f3f; typedef long long ...

2018-09-24 15:24:55

【2018 ICPC北京网赛】 A Saving Tang Monk II(BFS)

《Journey to the West》(also 《Monkey》) is one of the Four Great Classical Novels of Chinese literature. It was written by Wu Cheng’en during the Ming Dynasty. In this novel, Monkey King Sun Wukong, pig ...

2018-09-22 17:52:34

【BZOJ 1211】HNOI2004]树的计数(组合数学+Purfer序列)

1211: [HNOI2004]树的计数 Time Limit: 10 Sec Memory Limit: 162 MB Submit: 3149 Solved: 1181 [Submit][Status][Discuss] Description 一个有n个结点的树,设它的结点分别为v1, v2, …, vn,已知第i个结点vi的度数为di,问满足这样的条件的不同的树有多少棵。给定n,d1,...

2018-09-21 18:29:35

【杜教BM模板】焦作网赛L

杜教BM线性递推模板,黑科技啊 可以通过已知的前几项推出递推式ORZ #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <m...

2018-09-17 08:36:02

如何将代码上传到github

摸索了一番发现其实很简单, 1、首先我们需要申请一个github账号。 2、下载git bash 链接:点击进入官网 下载后打开是这个页面 3(绑定个人账号)、 输入: git config --global user.name +"用户名" git config --global user.email + "注册邮箱" //引号必须加上 4、生成ssh key ss...

2018-09-12 22:05:56

【codeforces 1036C】Classy Numbers(数位dp)

C. Classy Numbers time limit per test3 seconds memory limit per test256 megabytes inputstandard input outputstandard output Let’s call some positive integer classy if its decimal representation c...

2018-09-12 21:21:34

【POJ 3252】Round Numbers(数位dp)

Round Numbers Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 16160 Accepted: 6650 Description The cows, as you know, have no fingers or thumbs and thus are unable to play S...

2018-09-11 18:09:34

【HDU 3555】Bomb(数位dp)

Bomb Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others) Total Submission(s): 23401 Accepted Submission(s): 8811 Problem Description The counter-terrorists foun...

2018-09-11 17:05:34

【牛客练习赛26 B】烟花(dp)

链接:https://www.nowcoder.com/acm/contest/180/B 来源:牛客网 小a有个烟花,每个烟花代表着互不相同的颜色,对于第个烟花,它有的概率点燃,现在小a要去点燃它们,他想知道产生颜色的期望个数 及 产生恰好产生种颜色的概率 输入描述: 第一行两个整数 接下来一行个数,第个数表示第个烟花被点燃的概率 输出描述: 输出有两行 第一行表示产生不同颜色的...

2018-09-09 10:48:36

【Codeforces Round #508div2】(A,B,C,D)

A. Equality time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output You are given a string s of length n , which consists only of the firs...

2018-09-07 07:51:07

BZOJ刷题指南

http://lbn187.is-programmer.com/posts/103404.html

2018-09-05 21:05:00

2013GCPC C题 Chess(BFS+路径打印)

https://www.jisuanke.com/contest/1546/100748 基础的BFS和路径输出,方向开多一点就好了。 #include<bits/stdc++.h> using namespace std; const int maxn = 100050; struct point{ int x,y; int pre; int step...

2018-09-04 15:50:30

codancer

为信仰而战斗
关注
  • 学生
  • 中国 河南省 焦作市
奖章
  • 持之以恒