caoyu01-CSDN博客

原创伸展树-入门

参考博客博客链接网上资料不少，留下自己AC代码方便以后回看，用的spt模板是博客里的1、营业额统计题目链接题意：求最小的营业额波动总和最小的营业额波动=min(|x-y|)，y是之前某天营业额解法：插入某个数，找前序以及后序即可代码：#include <cstdio>#include <iostream>#include <cmath>#include <cstri

2015-10-23 10:55:34 393

原创 578C - Weakness and Poorness 三分

题意：每个数都减x，找到合适的x，是的最大的abs(连续子序列的和)->最小解法：三分，类开口朝上的二次函数实例代码：#include <cstdio>#include <iostream>#include <cmath>#include <cstring>#include <algorithm>#include <stdlib.h>#include <map>#inc

2015-10-15 20:20:31 392

原创 Codeforces Round #324

Olesya and Rodion题意： n位数且整除k解法：当k<10时，k00....类似于此就好了当k=10时，n==1 -1 n>1 100...类似于此Kolya and Tanya题意：一些三角形放在一起，只要有一个合法的，这些算合法，每个三角形的点上有权值(1~3)，一个三角形点权之和不为6，即为合法解法：一个三角形合法=20 一个三角形不合法=

2015-10-08 09:17:57 394

原创 BestCoder Round #58

hdu5494 Problem 0. Card Game 怎么选择m个数都能赢，最小的m个数之和大于对方的最大的m个数之和就好了。#include <cstdio>#include <iostream>#include <cmath>#include <cstring>#include <algorithm>#include <stdlib.h>#include <map>#in

2015-10-06 20:16:22 403

原创 Codeforces Round #311

昨天晚上的Codeforces 写的有点逗，无状态呀~A题：题意：满足三个条件的等级数量分配，尽量让一级的最多，二等其次，输出答案。暴力const int maxn=1000+5;using namespace std;int main(){ int n; while(cin>>n) { int a,b,c; int aa,bb

2015-07-01 18:51:49 413

原创 CF 235C

题意：给你S串和n个T串，求T串的所有循环串在S中的出现次数。题目链接解法：SAM对S串建立自动机将T串更新为双倍的回文串将最新更新的T串在自动机上扫描（类似，LCS），并标记所取的节点，避免重复串就行再次选取/**********************************************************

2014-11-26 20:26:00 853

原创 SPOJ LCS2 1812

题意：多个字符串的最长公共子串解法：SAM将第一个串建立自动机后面的每个字符串就行匹配，维护每个位置的值，然后所有串中此位置取最小值拓扑序，对父节点进行更新/************************************************************************* > File Name: lcs2.cpp > A

2014-11-25 21:23:58 461

原创 SPOJ 8222 Substrings

题意：求每种长度子串的个数最多值f[len],f[len-1]....f[1]f[x]代表长度为x的子串个数最大的值*当然是用SAM艹*当然我也不会*当然SAM很强大，前期我就争取多掌握性质代码参考代码：/*******************************************************************

2014-11-25 20:31:10 497

原创 SPOJ 1811-LCS POJ 2774

SAM表示真的很难艹SPOJ LCS题目链接推荐学习的博客博客地址题意：求两个字符串的最长公共子串解法：时间限制及其的严格，SAM可以在线性时间内解决性质:每个子串都可以由S走到~ SAM真的很强大，但是我太弱/****************************************************************

2014-11-25 12:29:47 394

原创高斯消元 poj-1222、1681、1830、3185,sicily-1048

这几个题目都是翻转之后关联其他点的翻转，并且都是采用的01翻转，实属良心。另外建立增广矩阵真的很费劲 poj 1222 #include #include #include #include #include #include #include #include #include #include #include #include #include const int

2014-11-24 19:29:55 459

原创 poj 1405

题意：分财产,按1/x(1) 1/x(2)...不减序列求，x要求正整数。使给教皇的尽量少。解法：== 假如第一次剩下1/2，那么下一个人要拿走尽量多的，就是1/3，剩下的是（1/2-1/3）=1/6，那么下一个人应该选择7 依次类推。第一次剩下1/2，ans=2，第二次的时候剩下的1/2,ans=3；就是为最新剩下的1/(ans-1)-1/ans，化简得：ans=(ans-1)*

2014-11-12 20:21:39 385

原创 poj 1850&&1496

题意：用字符串的表示数，字符串符合字典序递增（这个条件就是为了出题而出，要不就太easy）解法：组合数，借用网上的解法. 求组合数->递推关系式 C[i][j]=C[i-1][j-1]+C[i-1][j]/*************************************************************************

2014-11-12 16:24:20 339

原创 poj 1410 线段与矩形相交

题意：判断是否线段有和给定的矩形右交点解法：几何模板题坑点：不一定就是左上点和右下点线段如果在矩形内也算是相交/************************************************************************* > File Name: poj1410.cpp > Autho

2014-11-10 20:10:46 457

原创 poj 1442 单调队列

题意：求第k小的值解法：两个堆栈进行维护，大顶堆的top小于小顶堆的top,那么小顶堆的所有值都小于，每次维护足够的小顶堆数量就好了。/************************************************************************* > File Name: poj1442.cpp > Author: cy

2014-11-09 22:02:59 425

原创 poj 1422 最小路径覆盖

题意：有向图，伞兵降临某项点可以遍历这个点的子树，求最少的伞兵解法：最小路径覆盖匈牙利算法节点数-最大匹配数/************************************************************************* > File Name: poj1422.cpp > Author: cy > Mail: 10

2014-11-09 19:45:49 386

原创 poj 1411 素数筛选

题意：两个素数满足l,r->l*r解法：素数筛选，暴力寻找素数筛选的时候第二组j=i*i才行，要不超时，并且要用Longlong否则会RE代码/************************************************************************* > File Name: poj1411.cpp > Autho

2014-11-09 18:48:57 610

原创 poj 1466 最大独立点集

题意：男女关系，求大的集合满足没人有关系解法：最大独立点集顶点数和-最大匹配因为建立的二倍图比如 1匹配3' 那么3必然匹配1' 所以顶点数减去匹配/2/************************************************************************* > File Name: poj1466.cpp >

2014-11-09 17:06:48 398

原创 poj 1470 LCA公共祖先次数

题意：给你树的信息，m次询问公共祖先，输出被作为祖先的次数解法：LCA离线算法Tarjan+并查集代码/************************************************************************* > File Name: poj1470.cpp > Author: cy > Mail: 1002@q

2014-11-09 15:51:52 397

原创 poj 1458 最长公共子串

dp[i][j]：i,j的位置上最长的子串转移：相等时+1，不相等时max（dp[i-1][j],dp[i][j-1]）/************************************************************************* > File Name: poj1458.cpp > Author: cy > Mail: 10

2014-11-08 22:50:38 472

原创 poj 1436 线段树 '三元组'个数

题意：给你垂线段，求最多能找到多少三元组解法：线段维护最新的阴影，并且建立关系New point :所有的点乘以二进行维护三元组的定义：任意两个垂线段可以相见，能够找到水平线连接两线段且不相交其他线段对于插入的点都要乘以2,是因为对于[1,2],[3,4],对于线段[2,3]只能表示成分居两地的两个点，但是乘以二后，最小的线段长度=2，必然存在两个段/*****

2014-11-08 19:57:52 522

原创 poj 1465 bfs+余数判重

题意：用给定的m个数字，组成最小的n的倍数解法：bfs+余数判重当遍历到已经使用过的余数，就不用加入队列了。 a%n=e; (a*10+b)%n = ? a*10%n + b%n =e*10%n+b%n =(e*10+b)%n

2014-11-08 15:29:19 445

原创 poj 2155 二维线段树/树状数组

题目：Matrix大体内容题意：初始化的矩阵为0； C->给出矩形范围，范围内的进行一次翻转操作 Q->查询某个位置0或者1 解法：二维线段树，或者树状数组树状数组：同一维详细分析树状数组无; 线段树，静等填坑树状数组/*****************

2014-10-18 12:49:48 511

原创 poj 2823 poj 3264 线段树维护最大最小值

题目：Sliding Window大体内容：题意：从后往前扫描k长的段，输出每段的最小值，最大值解法：由于时间的原因可以选择线段树（RMQ更佳）具体分析线段树维护一个最大值和最小值查询的时候不同于以往，向下递归不改变段的左右区间（具体见代码）/********************************************

2014-10-16 23:21:32 419

转载读写优化

@http://blog.csdn.net/nickwong_/article/details/38709465有一些极端情况，用scanf会超时，用putchar下面为读数字[cpp] view plaincopyvoid nextInt(int &x) //输入外挂 { do c=getchar()

2014-10-16 08:57:21 377

原创 poj 3667 最长空白段+查询最左连续段

Hotel大体分析：题意：从最左找连续空间，是否能找到。解法：同poj1823。 //是1823的加强版，但是提交记录也是呵呵了。 //多的一个操作就是查询操作了。具体分析更新操作同poj1823 查询操作： 1. 先判断是都存在 2. 如果存在，左儿子中有就递归找左儿子

2014-10-16 08:46:33 499

原创 poj 1823 最长空白段

Hotel大体分析：题意:最长的空白段，操作段的加入和删除操作解法：线段树+lazy标记具体操作：> * 线段树维护，左边最长连续，右边最长连续、中间最长连续，因为之后边上的连续段对父亲的段才有影响> * 添加Lazy标记才会保证时间~> * 转移比较难理解> * 符合poj 的一贯风格，空间一定要开的足够大（这样有意思嘛）> * lazy标记的作用就是需

2014-10-15 22:14:05 476

原创 poj 1177 线段树+离散化+扫描线求矩形并的轮廓长

Picture题意：求矩形面积并额轮廓长解法：扫描线+离散化+线段树做法：等于更新操作前后的tree[1].len差，做法这么巧妙实际我也不知道为什么。差不多的意思就是更新操作的cover变化长度就是新添加的段或者是删除掉的段，再加上最开始和最后的段更新。两次根据离散去建立线段树进行统计，得到sum=平行y轴的长度+平行于x轴的长度

2014-10-15 20:11:15 521

原创 poj 1151 poj 1389 线段树+扫描线+离散化 [矩形的面积并]

Atlantis题意：求矩形的面积并解法：扫描线+线段树+离散化扫描矩形左右边界，左边为入边，右边为出边，使用线段树维护段中的覆盖长度即可离散化y坐标，进行线段树的左右边界维护不同于传统的建树，左树为 [l,mid]，右树为[mid,r];//为了相减方便**//比如 [1,2][2,4],这样的建立方式，

2014-10-14 10:50:59 589

原创 zoj 3829

ZOJ 3829Known Notation时限空间Time Limit: 2 Seconds Memory Limit: 65536 KB参考代码：

2014-10-13 19:34:32 420

原创 hdu 4691 后缀数组+RMQ+LCP

题意：

2014-10-11 09:42:04 461

原创 poj 3281 最大匹配+拆点

“三分图”的最大匹配。B A C (食物、牛、yi)

2014-09-26 20:44:00 413

原创 hdu 1565 最大权独立集

最大权独立集=sum-最小点权覆盖集最小点权覆盖集=最小割（最大流）

2014-09-26 19:37:32 393

原创 poj 1459 最大流（Dinic）

/************************************************************************* > File Name: poj1459.cpp > Author: cy > Mail: [email protected] > Created Time: 2014/9/24 21:02:55 **************

2014-09-26 18:30:16 450

原创 HDU 4902 Nice boat

ll gcd(ll a,ll b){ if(b==0)return a; else return gcd(b,a%b);}struct Date{ int t,l,r,x;}date[maxn];struct node { ll l,r,val; // ll flag; bool temp; vectorv; ll mid

2014-09-05 23:41:04 412

原创 QuickSums - SRM 197 Div 2 dp+矩阵+暴力

QuickSums - SRM 197 Div 2题目：

2014-08-26 20:10:18 1022

原创拓扑排序 FlowerGarden - 2004 TCCC Round 1

这是拓扑排序，为毛说成dp入门题。一直看不懂题，就放弃了，但是

2014-08-26 16:27:29 1163

原创 DP中高级

好题啊~~~~~~题意：

2014-08-26 14:38:52 549

原创 DP中级

AvoidRoads - 2003 TCO Semifinals 4题目：

2014-08-25 16:36:33 555

原创 DP入门

ZigZag - 2003 TCCC Semifinals 3题意：选出一个序列，满足，想liclass ZigZag{ public : int longestZigZag(vector sequence) { int dp[55][2]; cle(dp); int len=sequence.size();

2014-08-24 11:20:55 588

转载动态规划：从入门到专家

作者：Hawstein出处：http://hawstein.com/posts/dp-novice-to-advanced.html

2014-08-24 10:26:26 521

空空如也

空空如也