Speedcell-CSDN博客

原创 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 231

原创 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 311

原创 Codeforces 558E - A Simple Task

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

2015-07-16 00:58:45 570

原创 Python语法糖-装饰器

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

2014-01-16 23:43:25 3233 2

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

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

2013-12-21 19:55:54 861

原创 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 673

原创 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 85

原创 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 456

原创 POJ 2391 Ombrophobic Bovines

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

2013-10-21 23:06:47 503

原创 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 502

原创 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 601

原创 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 585

原创 POJ 3281 Dining

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

2013-10-21 13:06:31 470

原创 POJ 1149 PIGS

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

2013-10-20 20:22:39 433

原创 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 432

原创 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 483

原创 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 464

原创 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 426

原创 HDU 3068 最长回文

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

2013-10-17 23:24:24 495

原创 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 754

原创 HOJ 12722 Horror List

广义源点的最短路……/* Author : Speedcell Update : 2013-10-08Version : soppYcell 2.3*/#include #include #include #include #include #include #include #include #include #include #include #in

2013-10-10 16:43:59 358

原创 HOJ 12717 Cookie Selection

我可以说这题我是SBT写的么……/* Author : Speedcell Update : 2013-10-08Version : soppYcell 2.3*/#include #include #include #include #include #include #include #include #include #include #includ

2013-10-10 16:41:09 615

原创 Discreter-离散化容器

C++真是麻烦，比较函数放进来作成员函数就要报错，非得加static，好忧伤……如果是奇葩一点的数据类型只要重载了小于和等于号就没问题……cmp_ls和cmp_eq是小于和等于比较函数，一般情况下不用自己再写了吧，目前的样子是用了__COMPARER__里面的比较函数……理论上类型无限扩展？check()内部函数，维护单调性并且去重，那种要动态维护的题目还是手写线段树平衡树什么的好了…

2013-10-08 23:41:28 504

原创 HOJ 12719 Eco-driving

二分最大转角，大于当前最大转角的就不转跑SPFA看能不能到，由于只看能不能，所以一旦搜到重点就可以结束了。加了SLF优化，测试发现deque这样写效率还是挺高的……/* Author : Speedcell Update : 2013-10-08Version : soppYcell 2.3*/#include #include #include #include #i

2013-10-08 23:24:52 401

原创 Aizu 2447 A Two Floors Dungeon

状态是[x坐标][y坐标][一楼还是二楼][转换器按动次数的状态]，然后就没有然后了，switcher那里从map改成bool数组居然就从28s变成4s（HOJ大数据下），好可怕……/* Author : Speedcell Update : 2013-05-30Version : soppYcell 2.2(a)*/#include #include #include

2013-10-08 23:18:58 456

原创 PowerOJ 1736 飞行员配对方案问题

拆点连边就好了，网络流水题……/* Author : Speedcell Update : 2013-05-30Version : soppYcell 2.2(a)*/#include #include #include #include #include #include #include #include #include #include #incl

2013-10-03 22:28:02 998

转移的过程注意不要漏掉情况，这题看到多重背包且范围大就直接上二进制优化了，结果在这里出了问题。因为是要预付一些钱才能开始交易，但这个钱只用付一次就可以在同一家店一直买东西直到售罄。[trick1]二进制的话如果一来就把预付的这部分钱一起考虑了，由2^i件不能转移，但是由2^i+2^j件可以转移的情况就会被漏掉。可能是因为我习惯用加时间戳的方式来写才会有这样的问题。此题正解是转移到另外一个dp数组上

2013-09-27 15:34:32 441

原创 HOJ 12658 Evaluating Logic Expressions

神一样的短路。对于单目运算符，如果对于true和false都输出想通的东西就直接短路了，双目运算符可以左边短路，右边短路，还可以左边右边一起短路……给跪了……/* Author : Speedcell Update : 2013-05-30Version : soppYcell 2.2(a)*/#include #include #include #include #i

2013-09-25 19:43:25 387

原创 POJ 1155 TELE

树上分组背包，没什么好说的。坑：Discuss里面提到的滚动数组减少内存怎么破。/* Author : Speedcell Update : 2013-05-30Version : soppYcell 2.2(a)*/#include #include #include #include #include #include #include #include

2013-09-24 10:31:57 359

原创 HDU 4750 Count The Pairs

边排序，从点构造出树，用UFS判断是否已经连通，如果没有连通，当前加入的边可以将两边的所有点连起来，并且就是这两部分的点两两相连能取到的最小最大值。思维转不过来，真捉急……开始用map统计答案还TLE一次，这题略卡常数……/* Author : Speedcell Update : 2013-05-30Version : soppYcell 2.2(a)*/#include

2013-09-23 00:53:10 401

原创 POJ 2378 Tree Cutting

找树的重心，树的重心是去掉改点之后产生的各个分支大小都不超过N/2的点。回溯统计在已知父节点的情况下以各点为根的子树总大小和各分支的最大大小就好了，别忘了父节点那边的也算是一个分支。/* Author : Speedcell Update : 2013-05-30Version : soppYcell 2.2(a)*/#include #include #include

2013-09-17 16:05:21 400

原创调教笔记[无限建设中]

线段树POJ3225 当时把display放到主循环最后一句，发现这样可以得到正确答案，但是拿出来就会出错。当时觉得很不可思议，因为这除了跳出主循环以为并没有做任何事情。后来各种脑残调试N久才发现每次都display了就每次都query到底了，所以不存在两个lazy的情况……

2013-09-16 01:19:34 518

原创 POJ 3225 Help with Intervals

终于A了这题了，槽点略多：开闭区间使用奇偶数来区分开，这点非常巧妙，自己在写的时候没有这样想过。以前一直认为有多个lazy要维护的时候，在每次操作前就down掉就能避免掉矛盾操作的情况。这题发现是不行的，因为如果两次对同样的区间进行不同的操作，那子区间还是得到了两个操作的lazy，所以只能仔细分析每个操作的优先顺序。比如这题set操作明显是盖过xor的，如果要set了，那么下面的xor

2013-09-16 00:47:23 669

原创 HDU 4739 Zhuge Liang's Mines

这不就是个背包么！！！！！/* Author : Speedcell Update : 2013-05-30Version : soppYcell 2.2(a)*/#include #include #include #include #include #include #include #include #include #include #includ

2013-09-15 17:39:02 2021 1

原创 HDU 4737 A Bit Fun

开始写的时候是用的O(n*(logn)^2)的复杂度，固定起点二分最远能到多远然后累加，但是这样TLE了，然后直接在树上二分完事。这里顺序是倒着来的，因为这个写法是查最右点，是为了修正不能区间修改而固定最左点的做法，所以去右子树的话一定要带上左子树的状态去。这题交G++跑1000MS+，但据说数据乱搞直接平方级暴力可以100MS+……/* Author : Speedcell

2013-09-15 11:30:16 1298

原创线段树-树状数组专辑[建设中]

前略线段树这种高端大气上档次的东西，用法和树状数组一样非常灵活，一个简单比较如下：线段树树状数组操作符要求满足交换律，不要求支持区间减法满足交换律，区间减法

2013-09-15 02:19:13 599

原创 POJ 2299 Ultra-QuickSort

逆序对问题，（单点更新，区间查询），从左到右扫已知的数有多少个比当前数大。/* Author : Speedcell Update : 2013-05-30Version : soppYcell 2.2(a)*/#include #include #include #include #include #include #include #include #incl

2013-09-06 15:41:59 396

原创 JPY-RMB汇率转换

无聊随便写的，众犇亲喷。支持k,w这样的缩写，支持包括加减乘除括号的计算式，输入JPY或者RMB切换到那种货币去，回车就直接输出转换结果啦……JPY = 'JPY'RMB = 'RMB'def value(val): val = val.replace('k', '000') val = val.replace('K', '000') val = val.repl

2013-06-27 10:55:17 1887

原创 Thinking In Java-习题解答

初始化与清理

2013-06-14 22:17:07 80

原创 HDU 1712 ACboy needs your help

同一个物品的各种转移不要累加在一起了就好。/* Author : Speedcell Update : 2013-05-07Version : soppYcell 2.2*/#include #include #include #include #include #include #include #include #include #include #i

2013-05-16 16:20:49 370

静态邻接表的具体实现代码

空空如也