WANSNIM-CSDN博客

原创 162. Find Peak Element

162. Find Peak ElementA peak element is an element that is greater than its neighbors.Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.The array may contain multip

2017-07-18 09:17:20 381

原创 LeetCode 119. Pascal's Triangle II

119. Pascal’s Triangle II Given an index k, return the kth row of the Pascal’s triangle.class Solution {public: vector<int> getRow(int rowIndex) { vector<int> ANS; ANS.push_ba

2017-05-11 15:46:46 463

原创 LeeCode 242. Valid Anagram

242. Valid Anagram Given two strings s and t, write a function to determine if t is an anagram of s. For example, s = “anagram”, t = “nagaram”, return true. s = “rat”, t = “car”, return false.c

2017-05-11 15:32:26 434

原创 LeetCode 278. First Bad Version

278. First Bad Version You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each versi

2017-05-04 15:54:24 319

原创 LeetCode 210 Course Schedule II

210. Course Schedule II There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prerequisites, for example to take course 0 you have to first take course

2017-05-04 14:50:22 303

原创 LeetCode 474 Ones and Zeroes

474. Ones and Zeroes In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue. For now, suppose you are a dominator of m 0s and n 1s r

2017-05-04 13:58:46 486

原创 LeetCode 150 Evaluate Reverse Polish Notation

150. Evaluate Reverse Polish Notation Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another e

2017-05-04 13:09:10 319

原创 LeetCode 168 Excel Sheet Column Title

168. Excel Sheet Column Title Given a positive integer, return its corresponding column title as appear in an Excel sheet. For example:1 -> A2 -> B3 -> C...26 -> Z27 -> AA28 -> AB难度EASY

2017-05-04 12:37:33 281

原创 LeetCode 290 Word Pattern

Word Pattern Given a pattern and a string str, find if str follows the same pattern. Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty

2017-05-03 23:53:35 311

原创 LeetCode 121 Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (ie,

2017-05-02 23:32:57 363

原创 4385: [POI2015]Wilcze doły （单调队列）

http://www.lydsy.com/JudgeOnline/problem.php?id=4385Description给定一个长度为n的序列，你有一次机会选中一段连续的长度不超过d的区间，将里面所有数字全部修改为0。请找到最长的一段连续区间，使得该区间内所有数字之和不超过p。Input第一行包含三个整数n,p,d(1<=d<=n<=2000000，0<=p<=10^16)。第二行包含

2016-09-11 21:54:24 468

原创 HDU 3415 Max Sum of Max-K-sub-sequence（求长度不超过K的最大区间和）

http://acm.hdu.edu.cn/showproblem.php?pid=3415Problem Description Given a circle sequence A[1],A[2],A[3]……A[n]. Circle sequence means the left neighbour of A[1] is A[n] , and the right neighbour of A[

2016-09-11 17:00:54 574

原创 2013-2014 Northwestern European Regional Contest (NWERC 2013)

http://codeforces.com/gym/100405/补题：A已知一个图的点数为n，且改图为连通图。告诉了每两个点之间的最短路的距离。让你构造这个图，且这个图的边数为n。Idea 1：删边法。时间接近于O（n^3 ）。根据题目中给的矩阵构造一个完全图，然后遍历每条边，看是否需这条边是多余的。如果某条边的两点间的最短路可以由其他点到达，那么这条边就是多余的，可删除。因

2016-09-07 21:31:08 802

原创 2743: [HEOI2012]采花（求区间内出现至少出现两次的数的个数）

http://www.lydsy.com/JudgeOnline/problem.php?id=2743Description萧芸斓是Z国的公主，平时的一大爱好是采花。今天天气晴朗，阳光明媚，公主清晨便去了皇宫中新建的花园采花。花园足够大，容纳了n朵花，花有c种颜色（用整数1-c表示），且花是排成一排的，以便于公主采花。公主每次采花后会统计采到的花的颜色数，颜色数越多她会越高兴！同时，她有一癖好

2016-09-02 10:49:47 961

原创 Codeforces 709B Checkpoints ( 模拟)

http://codeforces.com/problemset/problem/709/BB. CheckpointsVasya takes part in the orienteering competition. There are n checkpoints located along the line at coordinates x1, x2, …, xn. Vasya starts a

2016-08-26 11:46:12 1222

原创 Codeforces 703D Mishka and Interesting sum （树状数组求区间内不同的数的异或和）

http://www.codeforces.com/contest/703/problem/DLittle Mishka enjoys programming. Since her birthday has just passed, her friends decided to present her with array of non-negative integers a1, a2, …,

2016-08-18 23:03:33 688

原创 Codeforces 705C Thor （模拟）

http://www.codeforces.com/contest/705/problem/CThor is getting used to the Earth. As a gift Loki gave him a smartphone. There are n applications on this phone. Thor is fascinated by this phone. He has

2016-08-17 14:03:45 1050

原创 HDU 5835 Danganronpa（贪心）

http://acm.hdu.edu.cn/showproblem.php?pid=5835Problem Description Chisa Yukizome works as a teacher in the school. She prepares many gifts, which consist of n kinds with a[i] quantities of each kind,

2016-08-15 17:12:35 521

原创 HDU 5821 Ball ( 贪心）

http://acm.hdu.edu.cn/showproblem.php?pid=5821Problem DescriptionZZX has a sequence of boxes numbered 1,2,…,n. Each box can contain at most one ball.You are given the initial configuration of the balls

2016-08-12 14:36:10 729

原创 POJ 2823 Sliding Window（单调队列模板题）

http://poj.org/problem?id=2823Sliding WindowDescriptionAn array of size n ≤ 106 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. Y

2016-08-06 15:37:39 465

原创 HDU 5616 Jam's balance (乱搞思维）

Jam’s balancehttp://acm.hdu.edu.cn/showproblem.php?pid=5616Problem Description Jim has a balance and N weights. (1≤N≤20) The balance can only tell whether things on different side are the same weight

2016-08-03 16:10:28 683

原创 HDU 5685 Problem A （求逆元）

http://acm.hdu.edu.cn/showproblem.php?pid=5685(b/a) % mod = ( b*q ) % mod 。其中 q 是 a 的逆元。逆元模板：int extendGcd(int a,int b,int &x,int &y){ if (b==0) { x=1; y=0; return a

2016-08-01 15:46:18 505

原创 Codeforces 696A Lorenzo Von Matterhorn ( LCA )

http://www.codeforces.com/problemset/problem/696/AC. Lorenzo Von MatterhornBarney lives in NYC. NYC has infinite number of intersections numbered with positive integers starting from 1. There exists a

2016-07-18 20:10:01 495

原创 BestCoder 2nd Anniversary（1001 + 1002 + 1003）

1001 Oraclehttp://acm.hdu.edu.cn/showproblem.php?pid=5718题意：将n的各个数位重新排列，并将其分成两个不含前导零的正整数。请你帮助他求出这两个正整数最大的和。如果不存在这样的两个正整数，输出”Uncertain”.RE一次，数组开小了,,,这种情况貌似经常出现… 解法是：将其分成n-1位的数加一个1位的数。字符串模拟大数相加。注意不合法的

2016-07-18 15:41:18 389

原创 Codeforces 360B + Codeforces 689C ( 二分 + DP ）

http://codeforces.com/contest/360/problem/BB. Levko and ArrayLevko has an array that consists of integers: a1, a2, … , an. But he doesn’t like this array at all.Levko thinks that the beauty of the arra

2016-07-12 20:33:42 1338 1

原创后缀数组的应用

求两个子串的最长公共前缀HDU4691：http://acm.hdu.edu.cn/showproblem.php?pid=4691#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int MAXN = 1e5 + 100;typedef l

2016-05-31 14:31:01 510

原创 AC自动机入门题（HDU 2222 + HDU 2896）

AC自动机学习资料：http://blog.csdn.net/niushuai666/article/details/7002823AC自动机模板：http://www.cnblogs.com/kuangbin/p/3164106.html我这两个入门题完全是用的Kuangbin大神的板子敲的…..http://acm.hdu.edu.cn/showproblem.php?pid=2896#incl

2016-05-26 15:04:55 374

原创 HDU 4725 The Shortest Path in Nya Graph （最短路拆点建图）

http://acm.hdu.edu.cn/showproblem.php?pid=4725Problem Description This is a very easy problem, your task is just calculate el camino mas corto en un grafico, and just solo hay que cambiar un poco el a

2016-05-20 00:07:12 604

原创 HDU 4366 Successor(dfn序 + 线段树）

http://acm.hdu.edu.cn/showproblem.php?pid=4366Problem Description Sean owns a company and he is the BOSS.The other Staff has one Superior.every staff has a loyalty and ability.Some times Sean will fir

2016-05-17 16:37:46 569

原创 2016 UESTC Training for Data Structures

A - 卿学姐与公主单点更新，查找区间最值可线段树，可树状数组，也可RMQ。#include <iostream>#include <cstdio>#include <algorithm>using namespace std;#define lson l,mid,i<<1#define rson mid+1,r,i<<1|1typedef long long ll;const in

2016-04-29 16:40:46 480

原创 ZOJ 3946 Highway Project (spfa)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5718Edward, the emperor of the Marjar Empire, wants to build some bidirectional highways so that he can reach other cities from the capital as

2016-04-24 20:58:11 569

原创 CDOJ 1092 韩爷的梦 (字符串Double Hash)

Repost From : http://www.cnblogs.com/jiu0821/p/4554352.html思路：这道题目难点在于时间与内存限制很苛刻，一般的方法不能奏效，这里只能采用hash。即把每个字符串hash为一个数字，对数字进行比对，题目就ac了。还有个问题就是，hash函数的选取。我第一次选的hash函数就产生了冲突，这个可以多次选择进行测试，也可以直接采用更复杂的hash函数

2016-04-15 15:28:22 822

原创 OpenGL 利用中点算法画抛物线：y = x*x / 16

算法已不再赘述。具体学习请访问： http://blog.csdn.net/codeblocksm/article/details/50991357这里需要指出的是要将抛物线分成两部分。在斜率为1之前是一个部分，在斜率是1之后是一个部分。前面用x来自增，后面用y来自增。献出手稿：又到了开心的贴代码的时间了（///_///)//所给代码在VS2013下运行和调试成功#include <stda

2016-03-27 13:48:30 5538 3

原创 OpenGL 利用中点算法画y=kx+b直线

本文直接用（0< k<1)来说明中点算法画直线。其他的斜率可直接按照此方法进行类推。1。设一个函数为F(x,y) = y - kx - b; 若F(x,y) > 0, 那么该点在这条直线的上方若F(x,y) = 0, 那么该点在这条直线上若F(x,y) <0, 那么该点在这条直线下方2。因为k的范围是 0 < k<1，那么x平均每单位的增量是大于y的，所以以x为自增量来确定y

2016-03-27 13:32:41 4486 1

原创 POJ 2411 + POJ 2663 + POJ 3420 小方格填充之多米诺骨牌系列(状压DP)

原文链接：http://blog.csdn.net/shiwei408/article/details/8821853解决此类问题，一般都是用1*2的小方块填充 n*m的矩阵。其中n或m两者中至少有一个较小。解决此类的方法，当n和m都很小的时候，可以直接for循环枚举状态来更新求值。但是当二者间有一个稍大的时候，就需要构造矩阵来解决此类问题。通常将较小的那个数作为列用dfs来枚举两行之间的状态。

2016-03-14 22:03:54 1175

原创 POJ 2288 Islands and Bridges(状压dp)

http://poj.org/problem?id=2288Description Given a map of islands and bridges that connect these islands, a Hamilton path, as we all know, is a path along the bridges such that it visits each island ex

2016-03-12 15:43:59 392

原创 Codeforce 567C(Geometric Progression) 奇淫巧计...

http://codeforces.com/contest/567/problem/C 题意：含有n个数的数组，然后从里面找3个数ai,aj,ak，使其成为K的等比数列。还要满足这三个数的下标是逐一上升的。解题思路：将中间的数组记录 x/k 和 x*k的个数。用map来维持。写这题的题解是为了铭记一个奇淫巧计。如果 mapmm; mm[x*k]++的时候，当x*k很大的时

2016-03-12 15:00:12 2633

原创 HDU 3001 Travelling （状压dp三进制）

http://acm.hdu.edu.cn/showproblem.php?pid=3001Problem Description After coding so many days,Mr Acmer wants to have a good rest.So travelling is the best choice!He has decided to visit n cities(he insi

2016-03-10 13:55:44 442

原创状压DP入门题集锦

POJ 3254 Corn Fields 题意：一块n*m的田，1表示这个地方可以种植，0代表这个地方不能种植。植物种植还必须满足两株植物不能相邻（横竖都不行）。问共有几种种植方法，而且当什么都不种时认为是一种方法。解题思路：种植用1表示，不种植用0表示。每一行的情况就可以用一个二进制数state来存储。state的范围是 [0 ~ 1<< state). dp[i][stat

2016-03-05 10:52:18 2112 1

原创 UVA 10054 The Necklace（欧拉回路）

欧拉通路：从某点出发能遍历到所有的边欧拉回路：从某点出发遍历完所有的边再回到该点无向图是否具有欧拉通路的条件：图连通 && 有且仅有0或者2个度数为奇数的点有向图是否具有欧拉通路的条件：图连通 && 除2个端点外其余点的入度等于出度（1个端点入度比出度大1,1个端点入度比出度小1）或者所有结点入度等于出度。无向图是否

2016-03-04 19:18:29 479

空空如也

空空如也