Scalpel's Blog

Stay hungry, Stay foolish.

C++类型推断(一)模版类型推断

C++ Template Type Reduction

模版是C++非常重要的组成部分,是泛型编程的基础,当我们定义一个函数模版时,经常会遇到推测其类型的情况,本文分成三种情况来讨论。模版的定义形式如下: template<typename T> void f(ParamType param); f(expr); // 调用f 编译器会根据expr的类型来推断ParamType和T的类型,这两者通常是不同的,ParamType...

Codeforces 653D Delivery Bears(二分搜索+网络流)

Binary search & Maximum Flow

题目链接 题意: 有n个节点m条边的有向图,每条边有权重,有x只熊背着货物从节点1送到节点n,每个熊背负的重量相等,每条边所经过的货物重量之和不能超过它的权重,问最多运送多少货物。 思路: 二分每只熊背负的重量,每条边的流量可以转化为它的权重除以每只熊背负的重量(为了防止溢出,可每次取其与x的较小值),判断最大流是否为x,是的话继续增加熊背负的重量,重新建图跑最大流。 #include...

Codeforces 652C Foe Pairs(Two Pointers)

题目链接 题意: 给出一个长度为n的数列和m个数对,求出总共有多少个不同的区间,区间内不包含任何数对。 思路: 先求出每个数在数列中的位置,然后对每个数对,假设,求出与a构成数对的最左边的元素,最后从右向左枚举每个位置,设可选择的最右元素为,答案即为ans += r - i + 1。 #include <iostream> #include <algorithm>...

Codeforces 638C Road Improvement(DFS)

题目链接 题意: 有n个城市,给出n-1条双向道路使它们都相互连通,每天可选择任意多不相邻的路维修,每条路一天就可以修完,求出最少多少天可以把所有的路都修完。 思路: 因为有n个点,n-1条边,所以是一棵树,用DFS对其遍历,只要相邻的两条路维修的那一天不一样即可,例如如果有一条边第2天维修,它有三条相邻的边,则可依次在第1、3、4天维修,对每条边以此类推,类似于图染色问题。 #inc...

我的Vim配置文件

My Vim Runconfig

配置Clang complete实现自动补全 let g:clang_library_path="/usr/lib/llvm-3.8/lib" let g:clang_auto_select=1 "select first entry in popup menu but don't insert in code let g:clang_complete_auto=1 "auto compl...

引水工程(最小生成树)

Minimum Spanning Tree

题目链接 题意: 有N个区域需要建设水资源工程,可以自建水库解决缺水,也可以从已有水源的地区建立管道引水,给出自建水库的费用和相互引水的费用,求工程的最小花费。 思路**: 最小生成树的模板题,稠密图,可以用Prim算法。以引水的费用作为边权,找到自建费用最低的区域,以它为根,通过比较自建和引水的最小值来不断生成树。 #include <iostream> #include...

Codeforces 629C Famil Door and Brackets(动态规划)

Dynamic programming

题目链接 题意: 给出一个只由和构成的字符串s,其长度为m,在其前后分别添加字符串p和q,使其总长度为n,并且字符串的和数量相等,任意前缀的的数量不少于,求有多少种p和q使字符串成立。 思路: 设为字符串长度为i,的个数比多j个的方案数,初始化为,转移为 又和可以互换,所以,然后枚举串s,求出和数量的最小差值minum和最终的差值finum。因为括号要匹配,所以p和q是对称的,通过枚举p...

Codeforces 627F Group Projects(动态规划)

Dynamic programming

题目链接 题意: 有n个人完成一项团队项目,第i个人可花费时间独立完成自己的一份工作,把n个人划分成多组,定义每组的imbalance为其中的最大值减最小值,求有多少种分组方案使各组的imbalance之和最多为k。 思路: 首先对排序,然后利用动态规划来做。设为考虑了i个人,有j个组是开放的(只有的最小值,没有最大值,组内还可以继续加人),imbalance之和为t。对第i个人有四种转...

Codeforces 627B Factory Repairs(树状数组)

Binary Indexed Tree

题目链接 题意: 一个工厂需要生产一些木材,每天可以生产a个,但是因为一些机器坏了,所以一天只能生产b个,可以选择某一天开始修复机器,修好需要k天,并且这段时间不能再生产,之后会恢复到产量a。在n天中,工厂会接一些订单,每个订单需要一个木材并且在当天生产完成。然后给出q个操作,有两种格式: 表示在第di天新增了个订单; 表示选择在第pi天修复机器。 输出对每个,最多可以满足总共多少订单...

HDU3472 HS BDC(混合图欧拉回路)

网络流&并查集

题目链接 题意: 给出一些单词,问是否能将所有单词首尾相连,每个单词用且仅用1次,其中有些单词可以反转。 思路: 先说一下如何求解混合图欧拉回路的问题:   因为存在有向边,所以可以把剩下的无向边随意定向化为有向边,这样充要条件就是每个节点的入度等于出度。   首先利用并查集判断图的连通性,如果不连通,那么无解。接下来就是让节点的入度等于出度,怎么做呢,因为无向边可以随意定向,每次对一条...