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...

Posted by Scalpel on April 23, 2016

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

Binary search & Maximum Flow

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

Posted by Scalpel on April 17, 2016

Codeforces 652C Foe Pairs(Two Pointers)

题目链接 题意： 给出一个长度为n的数列和m个数对，求出总共有多少个不同的区间\((x, y)\)，区间内不包含任何数对。 思路： 先求出每个数在数列中的位置，然后对每个数对\((a, b)\)，假设\(pos[a]\lt pos[b]\)，求出与a构成数对的最左边的元素\(l[a]=\min(l[a],pos[b])\)，最后从右向左枚举每个位置，设可选择的最右元素为\(r=\min(...

Posted by Scalpel on April 14, 2016

Codeforces 638C Road Improvement(DFS)

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

Posted by Scalpel on April 3, 2016

我的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...

Posted by Scalpel on March 28, 2016

引水工程(最小生成树)

Minimum Spanning Tree

题目链接 题意： 有N个区域需要建设水资源工程，可以自建水库解决缺水，也可以从已有水源的地区建立管道引水，给出自建水库的费用\(W_i\)和相互引水的费用\(P_{i,j}\)，求工程的最小花费。 思路**： 最小生成树的模板题，稠密图，可以用Prim算法。以引水的费用作为边权，找到自建费用最低的区域，以它为根，通过比较自建和引水的最小值\(lowcost_i=\min(G_{k,i},...

Posted by Scalpel on March 22, 2016

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

Dynamic programming

题目链接 题意： 给出一个只由\((\)和\()\)构成的字符串s，其长度为m，在其前后分别添加字符串p和q，使其总长度为n，并且字符串的\((\)和\()\)数量相等，任意前缀的\((\)的数量不少于\()\)，求有多少种p和q使字符串成立。 思路： 设\(dp_{i,j}\)为字符串长度为i，\((\)的个数比\()\)多j个的方案数，初始化为\(dp_{0,0}=1\)，转移为\(...

Posted by Scalpel on March 16, 2016

Codeforces 627F Group Projects(动态规划)

Dynamic programming

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

Posted by Scalpel on March 10, 2016

Codeforces 627B Factory Repairs(树状数组)

Binary Indexed Tree

题目链接 题意： 一个工厂需要生产一些木材，每天可以生产a个，但是因为一些机器坏了，所以一天只能生产b个，可以选择某一天开始修复机器，修好需要k天，并且这段时间不能再生产，之后会恢复到产量a。在n天中，工厂会接一些订单，每个订单需要一个木材并且在当天生产完成。然后给出q个操作，有两种格式: \(1, d_i, a_i\) 表示在第di天新增了\(a_i\)个订单； \(2, p_i\) 表...

Posted by Scalpel on March 6, 2016

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

网络流&并查集

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

Posted by Scalpel on March 4, 2016

FEATURED TAGS
生活 C++ 编程开发 Linux 软件使用 题解 网络流 HDU Codeforces 动态规划 DFS Binary Search Dynamic Programming 数据库 51Nod 网络编程
ABOUT ME

C++/Linux Programmer and ACMer

FRIENDS