9 Speedcell

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 2w+

HDU 1595 find the longest of the shortest

就是简单求以下这个式子,所以直接按照公式枚举就好了。 maxe∈path(sp(V,E))sp(V,E/{e})\underset{e\in path(sp(V, E))}{\max} sp(V, E/\{e\})#include <iostream>#include <cstdio>#include <cstring>#include <numeric>#include <algorit

2015-10-01 02:10:27

HDU 2191 汶川大地震

裸的多重背包问题,直接上二进制优化吧,没事什么特别的。#include <iostream>#include <cstdio>#include <algorithm>#include <numeric>using namespace std;const int MAX = 102;struct _ { const int none = -1; int money, dp[MAX]

2015-08-02 20:53:05

Codeforces 558E - A Simple Task

算法总在某个范围不大的维度上直接暴力。这次的维度是字符集的大小,总共只有26个字符,所以直接用counting sort,其实这货也算是桶排吧,但是要能用这样的排序还有一个条件是不区分原子吧。 每次操作在制定的区间上,先查询出每个字符分别有多少个,然后按大小排列好。查询和排列用线段树维护,所以每次操作都是O(logn)O(logn)的复杂度。最后从头到尾查一次就好了。 之前用Python写了这

2015-07-16 00:58:45

Python语法糖-装饰器

这里用来记录Python各种甜得发腻的语法糖,以及各种变形用法。太初,神谕(pythonic),import light,于是有了光。装饰器是用来给函数增加新功能的,对于支持高阶函数的语言,函数参数直接穿进去就好了。但是Python提供了更为优雅的解决方案,只需要一个@就能搞定。装饰器函数需要单独写出来,两层,第一层接受一个函数function就可以了,第二层构造一个函数来接受

2014-01-16 23:43:25

regex.alf.nu 正则表达式题解

人人上看到有人分享这个,玩了两下觉得好有意思,我自己也还没玩通,边玩边写吧。Plain Strings 观察一下就发现左边都含有foo,右边都没有,所以简单写成{CSDN:CODE:foo}就好了。

2013-12-21 19:55:54

Windows下Sublime Text 2常用配置

Package Control import urllib2,os; pf='Package Control.sublime-package'; ipp=sublime.installed_packages_path(); os.makedirs(ipp) if not os.path.exists(ipp) else None; urllib2.install_opener(urllib

2013-11-26 23:27:09

Sublime Text 2 常用配置

Package Control import urllib2,os; pf='Package Control.sublime-package'; ipp=sublime.installed_packages_path(); os.makedirs(ipp) if not os.path.exists(ipp) else None; urllib2.install_opener(urllib2.

2013-11-26 23:18:31

HDU 4446 IT Companies

去年金华的题,现场看了一下就直接放下了。这题是直接构造答案就好了:c[i]来自两部分,[-i+1,-1]和[i+1,n]。如果当前c[i]==0,且i最小,则说明这两段都没有比i公司要大的了,并且如果在[1,i-1]这段区间如果有比i还要大的话,那么这个i肯定不是让c[i]等于0的最小的i。所以如果当前有最小的i使c[i]==0,那么i为当前最大。如果没有的话,取最小的c[i],这些比他大的公

2013-10-22 16:05:41

POJ 2391 Ombrophobic Bovines

好题一枚,问最短多少时间能然牛都进入牛棚,理所应当地牛棚有容量限制。同样容易想到最短时间是跑最远的那头牛需要的时间,最大值最小化,显而易见地二分了。然后就是建图的问题,这里需要拆点[trick 1],看了题解领悟到拆点的作用不只是度限制,还可以有方向限制的作用,类似于包含了阶段维的DP。假设本来A可以到B,B可以到C,但是A不能到C,如果不拆点的话,A就可以通过B到C了。[trick 2]距离

2013-10-21 23:06:47

ZOJ 2760 How Many Shortest Path

最多多少条不想交的最短路,正反两次SPFA然后枚举边可以确定这条边在不在最短路上,在的话就在网络里加边,这里的不想交是指边不想交,所以容量限定为1就好了……那个s==t的时候输出inf,坑死我了……/* Author : Speedcell Update : 2013-10-16Version : soppYcell 2.4*/#include #include #in

2013-10-21 18:16:28

SPOJ NETADMIN Smart Network Administrator

保证满流的情况,最小化源点到制定点集上每条边的流量最大值。最小最大化问题惯用二分,SPOJ似乎很喜欢点标号乱搞?/* Author : Speedcell Update : 2013-10-16Version : soppYcell 2.4*/ #include #include #include #include #include #include #incl

2013-10-21 17:36:40

SPOJ IM Intergalactic Map

从1出发经过2到达3,不走相同边,从2做源点,1、3合并为汇点看最大流是不是2就好了……点标号会坑爹,map处理……/* Author : Speedcell Update : 2013-10-16Version : soppYcell 2.4*/#include #include #include #include #include #include #incl

2013-10-21 17:11:35

POJ 3281 Dining

典型的度限制问题,因为每头牛要从食物和饮料里面各选一个,所以放在中间整体就限制了牛不会重复选。点标号虐麻烦,写跪了直接单独搞函数……/* Author : Speedcell Update : 2013-10-16Version : soppYcell 2.4*/#include #include #include #include #include #includ

2013-10-21 13:06:31

POJ 1149 PIGS

《网络流建模汇总》上面提到的先硬性建图,然后简化是个很好的想法,跟神经网络的一样,最后学习出来的函数人类是否能够理解不重要……掩……不过这个图简化之后还算能够理解,首先阶段性是每个顾客是一个阶段。然后顾客购买之后能够重新分配,因为是要让顾客买到最多,所以将顾客缩为一个点之后只有从同一个猪圈里面买了猪的顾客才需要重新分配。因为顾客得到的是所有他能打开的猪圈的猪的数目,所以从原点流向顾客的是这个顾

2013-10-20 20:22:39

POJ 2406 Power Strings

这神一样其丑无比的代码,等忙过这阵子好好总结自己的模板,太可怕的代码了……RMQ只需要求出height[2]到各个点的最小值,然后查询的时候返回height[max(rank[0],rank[x])]就是lcp(str,x)……从小到大枚举回文长度,判断各个循环节与原串的lcp是不是等于循环节的长度,全部等于才是一个真正的循环节。/* Author : Speedcell Upda

2013-10-20 00:58:54

SPOJ DISUBSTR Distinct Substrings

每个子串一定是某个后缀的前缀,然后枚举后缀就知道这个后缀能贡献多少个子串,然后height可以查到有多少个重复了,所以累加答案就好了……/* Author : Speedcell Update : 2013-10-16Version : soppYcell 2.4*/#include #include #include #include #include #incl

2013-10-19 10:06:53

POJ 1200 Crazy Search

试验一发Bllizard的字符串哈希函数……/* Author : Speedcell Update : 2013-10-08Version : soppYcell 2.3*/#include #include #include #include #include #include #include #include #include #include #

2013-10-18 13:31:55

POJ 3974 Palindrome

同上题……/* Author : Speedcell Update : 2013-10-08Version : soppYcell 2.3*/#include #include #include #include #include #include #include #include #include #include #include #include

2013-10-17 23:36:41

HDU 3068 最长回文

复习Manacher,几个注意如下:记录的当前最大位置是指能覆盖当前枚举中心最远的位置,不一定是全局最大值,所以最后的答案不是这个位置而要单独max一遍,而且更新这个值也是p[o]+o和p[i]+i比较。间隔位置加首尾都放上#,个数是l+1个,所以新字符串长度是2*l+1,刚好处理成奇数,回文串新技能get……首字放上一个绝对不会出现的东西隔开,好想法,尾部天然\0所以不用放,然后首部

2013-10-17 23:24:24

CSU 1329 一行盒子

今年的省赛题目,现场的时候觉得链表查找就是O(n)的复杂度然后就没想了,最后YY一个线段树+平衡树的巨负责无比的东西结果写跪了,泪……维护一个bool型的pre用来表示当前的前向指针是next[0]还是next[1],这样翻转操作可以O(1)完成……/* Author : Speedcell Update : 2013-10-08Version : soppYcell 2.3*

2013-10-16 10:48:00

查看更多

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