6 caoyu01

尚未进行身份认证

CAOYU01

等级
TA的排名 5w+

伸展树-入门

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

2015-10-23 10:55:34

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

Codeforces Round #324

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

2015-10-08 09:17:57

BestCoder Round #58

hdu5494Problem0.CardGame怎么选择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

Codeforces Round #311

昨天晚上的Codeforces写的有点逗,无状态呀~A题:题意:满足三个条件的等级数量分配,尽量让一级的最多,二等其次,输出答案。暴力constintmaxn=1000+5;usingnamespacestd;intmain(){intn;while(cin>>n){inta,b,c;intaa,bb

2015-07-01 18:51:49

CF 235C

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

2014-11-26 20:26:00

SPOJ LCS2 1812

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

2014-11-25 21:23:58

SPOJ 8222 Substrings

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

2014-11-25 20:31:10

SPOJ 1811-LCS POJ 2774

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

2014-11-25 12:29:47

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

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

2014-11-24 19:29:55

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

poj 1850&&1496

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

2014-11-12 16:24:20

poj 1410 线段与矩形相交

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

2014-11-10 20:10:46

poj 1442 单调队列

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

2014-11-09 22:02:59

poj 1422 最小路径覆盖

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

2014-11-09 19:45:49

poj 1411 素数筛选

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

2014-11-09 18:48:57

poj 1466 最大独立点集

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

2014-11-09 17:06:48

poj 1470 LCA公共祖先次数

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

2014-11-09 15:51:52

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

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

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

2014-11-08 19:57:52

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!