ACagain-CSDN博客

原创 dfs序二进制优化 Codeforces Round #316 (Div. 2)D. Tree Requests

D. Tree Requests time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Roman planted a tree consisting of n vertices. Each vertex contains a lo...

2018-04-16 21:00:34 230

原创 Codeforces Round #318 D. Bear and Blocks

D. Bear and Blocks time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Limak is a little bear who loves to play. Today he is playing by destro...

2018-04-16 20:37:38 157

原创 Codeforces Round #320 (Div. 2)C. A Problem about Polyline

题目： There is a polyline going through points (0, 0) – (x, x) – (2x, 0) – (3x, x) – (4x, 0) – … - (2kx, 0) – (2kx + x, x) – ….We know that the polyline passes through the point (a, b). Find minimum ...

2018-04-16 20:32:23 133

原创 Codeforces Round #313 (Div. 2)C. Gerald's Hexagon

Gerald got a very curious hexagon for his birthday. The boy found out that all the angles of the hexagon are equal to . Then he measured the length of its sides, and found that each of them is equal t...

2018-03-29 21:09:39 172

原创 cf311div2 D Vitaly and Cycle

题目 After Vitaly was expelled from the university, he became interested in the graph theory.Vitaly especially liked the cycles of an odd length in which each vertex occurs at most once.Vitaly was ...

2018-03-26 16:41:12 234

原创完全背包 cf302div2 C

C. Writing Code time limit per test3 seconds memory limit per test256 megabytes inputstandard input outputstandard output Programmers working on a large project have just received a task to write

2018-02-06 22:36:00 178

转载浅谈数据的离散化

转自：http://www.cnblogs.com/kevince/p/3893531.html ——By Kevince最近做了一些需要离散数据的题目，比如URAL 1019 以及POJ 2528等，由于数据较大，如果用传统的方法建立对应的数据结构消耗的内存和时间肯定是不能被接受的。由于以前没有怎么接触过需要离散化的题目，于是就通过自己最近的做题经验以及网上的部分资料，整理并讲解了常用的离

2017-09-28 20:56:04 365

原创快速幂 LightOJ 1282 - Leading and Trailing

题意就是求n的k次方的前三位和后三位 - 后三位快速幂取模就行。 - 前三位，首先pow(n,k)=pow(10,k*lg(n)),此时可以看出pow(n,k)的值的位数是由k *lg(n)的整数部分决定，而值是由其小数部分决定，因此只取前三位的话让k *lg(n)的小数部分在加上2即可，然后再将其转化为整数形式，舍去后面的小数。即pow(10,2+fmod(k *log10(n),1))

2017-08-22 20:56:38 205

原创欧拉常数（调和级数求和） Harmonic Number

In mathematics, the nth harmonic number is the sum of the reciprocals of the first n natural numbers: In this problem, you are given n, you have to find Hn. InputInput starts with an integer T

2017-08-21 21:30:50 8509

原创素数筛 LightOJ - 1259 Goldbach`s Conjecture

Goldbach's conjecture is one of the oldest unsolved problems in number theory and in all of mathematics. It states:Every even integer, greater than 2, can be expressed as the sum of two primes [1].Now

2017-08-21 21:24:44 164

原创 dijskstra算法及其队列优化，spfa，floyd Til the Cows Come Home POJ - 2387

Description Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs her beauty sleep, so she wa

2017-08-18 20:35:37 345

原创区间dp uva 10003 - Cutting Sticks

题意就是给出棍子的长度和n个切点，让你把它切成n+1段，每次切时花费价值为此时棍子的长度，问怎样切才能使最终花费最少。区间dp，就是指一整段区间的最优值可以由其中几段小区间的最优值来决定，因此次类问题一般都是从小到大枚举区间的大小，然后再求每一个该大小的区间的最优值，最终得到整个区间的最优值。#include<iostream>#include <algorithm>#include <cs

2017-08-18 20:30:31 212

原创双调欧几里得旅行商问题 UVA 1347 Tour

题目：https://odzkskevi.qnssl.com/f85205c68ae5f131a579c799f71b7b69?v=1502173334 旅行商问题描述：平面上n个点，确定一条连接各点的最短闭合旅程。这个解的一般形式为NP的（在多项式时间内可以求出）J.L. Bentley 建议通过只考虑双调旅程(bitonictour)来简化问题,这种旅程即为从最左点开始，严格地从左到右直至最右

2017-08-16 21:06:20 199

原创 Floyd+Bellman-ford求正环 hdu1317 XYZZY

Problem Description It has recently been discovered how to run open-source software on the Y-Crate gaming device. A number of enterprising designers have developed Advent-style games for deployment on

2017-08-10 16:34:04 253

原创 Kruskal+二进制枚举 POJ 2784 Buy or Build

题目：https://odzkskevi.qnssl.com/95fc8c37ba05359d81df6779e817c236?v=1501937229因为q很小，所以直接枚举所有的方案就行。首先求不用方案时的最小生成树，然后每次枚举方案时只需考虑初次最小生成树中的边就可以，如果每次都用所有边会tle。感觉自己写的又长又蠢。。。二进制枚举for(int i=0;i<(1<<q);i++)

2017-08-10 10:46:21 208

原创最小生成树kruskal POJ 3522 Slim Span

题目：https://odzkskevi.qnssl.com/8e16f8701018d0e3529ac3ca319e1f67?v=1502277241 最简单的kruskal，主要参考紫书代码 kruskal算法就是先给边按权值大小排序，然后从小到大遍历，用并查集判断边上的两个点是否在同一集合，如果不是的话将其添加进去，直到所有的点都加入到集合中。#include <iostream>#in

2017-08-10 10:39:25 186

原创 LCS Common Subsequence

A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = #include <iostream>#include <algorithm>#include <cstring>using namespace std

2017-08-08 19:23:15 204

原创 01trie树 HDU 5536Chip Factory

Problem Description John is a manager of a CPU chip factory, the factory produces lots of chips everyday. To manage large amounts of products, every processor has a serial number. More specifically, t

2017-08-08 18:50:56 167

原创 trie树 POJ 2503 Babelfish

DescriptionYou have just moved from Waterloo to a big city. The people here speak an incomprehensible dialect of a foreign language. Fortunately, you have a dictionary to help you understand them. Inp

2017-08-08 17:52:42 248

原创最长回文子串 V2（Manacher算法）

回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。输入一个字符串Str，输出Str里最长回文子串的长度。Input 输入Str（Str的长度 <= 100000) Output 输出最长回文子串的长度L。 Sample InputdaabaacSample Output5#include <iostream>#include <cstring

2017-08-07 22:28:43 208

原创 KMP HDU 1686 Oulipo

The French author Georges Perec (1936–1982) once wrote a book, La disparition, without the letter 'e'. He was a member of the Oulipo group. A quote from the book: Tout avait Pair normal, mais tout s

2017-08-07 22:25:58 192

原创多重背包 HDU 2844 Coins

多重背包可转化为01背包，首先将件数C二进制分解为多个件数的集合，这些件数可以组合成任意小于等于C的数字，而且不会重复。如7 7=111，可以分解为100,010,001，这三个数可以组合为任意小于等于7的数，而且每种组合都会得到不同的数。 13 13=1101，可以分解为0001,0010,0100,0110，前三个数可以组合成7以内的任意数，加上6就可以组合为任意大于6小于等

2017-08-03 18:54:12 218

原创 Line belt 三分嵌套

In a two-dimensional plane there are two line belts, there are two segments AB and CD, lxhgww's speed on AB is P and on CD is Q, he can move with the speed R on other area on the plane.How long must h

2017-07-30 22:10:06 219

原创三分板子 zoj 3203

Compared to wildleopard's wealthiness, his brother mildleopard is rather poor. His house is narrow and he has only one light bulb in his house. Every night, he is wandering in his incommodious house, t

2017-07-30 22:06:45 293

原创二分板子 poj 3122 pie

题目 My birthday is coming up and traditionally I’m serving pie. Not just one pie, no, I have a number N of them, of various tastes and of various sizes. F of my friends are coming to my party and e

2017-07-30 22:03:38 209

原创 ZOJ - 3870Team Formation(位运算）

题目 For an upcoming programming contest, Edward, the headmaster of Marjar University, is forming a two-man team from N students of his university.Edward knows the skill level of each student. He has fo

2017-07-30 18:48:33 148

原创 01背包及完全背包问题（51Nod - 1085，HDU 1114 Piggy-Bank）

51Nod - 1085题目：在N件物品取出若干件放在容量为W的背包里，每件物品的体积为W1，W2……Wn（Wi为整数），与之相对应的价值为P1,P2……Pn（Pi为整数）。求背包能够容纳的最大价值。 Input 第1行，2个整数，N和W中间用空格隔开。N为物品的数量，W为背包的容量。(1 <= N <= 100，1 <= W <= 10000) 第2 - N +

2017-06-20 14:35:00 330

原创 POJ2533Longest Ordered Subsequence(LIS)

Description A numeric sequence of ai is ordered if a1 < a2 < … < aN. Let the subsequence of the given numeric sequence (a1, a2, …, aN) be any sequence (ai1, ai2, …, aiK), where 1 <= i1 < i2 < … < iK <

2017-06-05 23:57:54 155

原创 HDU 1069 Monkey and Banana(dp)

HDU 1069 Monkey and Banana(dp) A group of researchers are designing an experiment to test the IQ of a monkey. They will hang a banana at the roof of a building, and at the mean time, provide the monkey

2017-05-31 22:35:34 146

zero