2019-01-18 23:26:17 |  0 Comments  |  STL

[转载]6 个技巧,提升 C++11 的 vector 性能

6 个技巧,提升 C++11 的 vector 性能

Vector 就像是 C++ STL 容器的瑞士军刀。Bjarne Stoutsoup 有一句话 – “一般情况下,如果你需要容器,就用 vector”。像我们这样的普通人把这句话当作真理,只需要照样去做。然而,就像其它工具一样,vector 也只是个工具,它能提高效率,也能降低效率。

这篇文章中我们可以看到 6 种优化使用 vector 的方法。我们会在最常见的使用 vector 的开发任务中看到有效的方法和无效的方法,并以此衡量有效使用 vector 会带来怎样的性能提升,并试图理解为什么能得到这样的性能提升。

性能测试的搭建和方法:

  • 所有测试都在我的 Surface Book 中运行,这台笔记本拥有主频 2.6Ghz 的酷睿 i7 处理器,8 GB 内存,安装了 Windows 10 操作系统并使用 VS2015 C++ 编译器编译运行。

  • 我们会使用 Stopwatch。这个工具由 Kjell 创建,在 https://github.com/KjellKod/Stopwatch 可以找到。

  • 我们会运行每个测试 100 次,然后计算平均运行时间来作为依据。运行测试的代码在这里。你可以自由下载,用于在你自己的系统中评估 vector 的性能。那里提供的代码段只反映了一次循环,这让事件变得简单。

  • 我们在 vector 中存入 TestStruct 结构的数据,并使用 FillVector() 来填充 vector。它们的定义如下。

// Test struct to be inserted/removed from vector
struct BigTestStruct
{
  int iValue = 1;
  float fValue;
  long lValue;
  double dValue;
  char cNameArr[10];
  int iValArr[100];
};
// Helper function to populate the test vectors
void FillVector(vector<BigTestStruct>& testVector)
{
  for (int i = 0; i < 10000; i++)
  {
    BigTestStruct bt;
    testVect
 2018-12-29 23:04:07 |  0 Comments  |  二分

BUPT大一上学期第三次机考E题核心部分题解 && 二分法讲解。

二分!二分!

引入背景

同学们有没有为上周第三次机考E题困扰呢?
大家都能读懂题目,但是很多同学就很苦恼了:明明我答案是对的,但是为什么我超出时间限制(TLE)了呢?
这是因为大家设计的程序的时间复杂度太高了,在碰到大数据的时候程序无法在规定时间内完成所有运算。
那么这一篇文章就来给大家介绍一种更优的搜索答案的方案————它就是二分查找!

疑惑&解惑

二分?是那个数学高中必修I上、高数上讲的那个二分法吗?
对~!没错就是它!
蛤?二分不是用来找函数近似零点的吗?怎么就成了查找答案了?
nope,二分的功能不只是那一个,它可强大了。在计算机上,我们目前的主要应用是用来二分查找答案。

正题

二分查找,是因为单个查找的时间复杂度太高,让程序查找答案的效率低下,而出现用来替代单步查找的一种方法。它是一种思想,而不能叫做一种算法。
对于二分查找的题目,一般都有一个明显的特征:判断这个解是否能满足所有的题目条件。同学们在设计第三次机考E题的时候,就是逐步判断每一个解是否能满足题意的。其实这种方法从理论上来说是正确的,但是它却做了一些不必要的工作。
我们就以E题来讲解一下二分查找的思路。
首先,我们能确定,最佳答案ans(给战士补充的最大能量)一定在范围1到max{ai}中,其中ai表示第i个能量瓶所含的能量值。
那么我们设答案左区间l = 1,右区间r = max{ai},然后我们用去检索答案区间的中间值mid = (l+r)/2是否能够满足题意。 如果mid能够满足题意,那么说明当前能量值是可行方案,我们就记录下当前的mid的

 2018-12-26 11:18:55 |  0 Comments  |  线段树

Codeforces Round#528 div2 F. Rock-Paper-Scissors Champion

Codeforces Round#528 div2

F. Rock-Paper-Scissors Champion

time limit:per test 2 seconds
memory limit:per test 256 megabytes
input:standard input
output:standard output

n players are going to play a rock-paper-scissors tournament. As you probably know, in a one-on-one match of rock-paper-scissors, two players choose their shapes independently. The outcome is then determined depending on the chosen shapes: "paper" beats "rock", "rock" beats "scissors", "scissors" beat "paper", and two equal shapes result in a draw.

At the start of the tournament all players will stand in a row, with their numbers increasing from 1 for the leftmost player, to n for the rightmost player. Each player has a pre-chosen shape that they will use in every game throughout the tournament. Here's how the tournament is conducted:

1.If there is only one player left, he is declared the champion.
2.Otherwise, two adjacent players in the row are chosen arbitrarily, and they play the next match. The losing player is eliminated fr

 2018-12-26 10:24:28 |  0 Comments  |  Link-Cut-Tree

BZOJ2002[HNOI2010] 弹飞绵羊 (LCT)

BZOJ2002[HNOI2010] 弹飞绵羊 (LCT)

Description

某天,Lostmonkey发明了一种超级弹力装置,为了在他的绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏。游戏一开始,Lostmonkey在地上沿着一条直线摆上n个装置,每个装置设定初始弹力系数ki,当绵羊达到第i个装置时,它会往后弹ki步,达到第i+ki个装置,若不存在第i+ki个装置,则绵羊被弹飞。绵羊想知道当它从第i个装置起步时,被弹几次后会被弹飞。为了使得游戏更有趣,Lostmonkey可以修改某个弹力装置的弹力系数,任何时候弹力系数均为正整数。

Input

第一行包含一个整数n,表示地上有n个装置,装置的编号从0到n-1,接下来一行有n个正整数,依次为那n个装置的初始弹力系数。第三行有一个正整数m,接下来m行每行至少有两个数i、j,若i=1,你要输出从j出发被弹几次后被弹飞,若i=2则还会再输入一个正整数k,表示第j个弹力装置的系数被修改成k。对于20%的数据n,m<=10000,对于100%的数据n<=200000,m<=100000

Output

对于每个i=1的情况,你都要输出一个需要的步数,占一行。

Sample Input

4  
1 2 1 1  
3  
1 1  
2 1 1  
1 1

Sample Output

2
3

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=2002

题解:

LCT基础板题,终于凑出了属于自己代码风格的一套LCT模板,以后终于不用百度别人的去改LCT了
只不过此题的link和cut操作可以叠在一起,由于题目性质,cut后的点一定是某个辅助树的根,所以不需要换根操作(evert),自然也就不用写pushdown。不过写上也没错,只是运行速度会稍慢一些。

代码(写了些多余的比如push_down):

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
int get_num(){
    int num = 0;
    char ch;
    bool flag = false;
    
 2018-12-26 10:18:42 |  0 Comments  |  网络流 tarjan 最大流

NOI2009 植物大战僵尸(最大权闭合子图、联通量处理)

题目描述


输入格式

输出格式

仅包含一个整数,表示可以获得的最大能源收入。注意,你也可以选择不进行任何攻击,这样能源收入为0。

样例输入

3 2
10 0
20 0
-10 0
-5 1 0 0
100 1 2 1
100 0​

样例输出

25​

数据范围及提示

在样例中, 植物P1,1可以攻击位置(0,0), P2, 0可以攻击位置(2,1)。
一个方案为,首先进攻P1,1, P0,1,此时可以攻击P0,0 。共得到能源收益为(-5)+20+10 = 25。注意, 位置(2,1)被植物P2,0保护,所以无法攻击第2行中的任何植物。

【大致数据规模】

约20%的数据满足1 ≤ N, M ≤ 5; 约40%的数据满足1 ≤ N, M ≤ 10; 约100%的数据满足1 ≤ N ≤ 20,1 ≤ M ≤ 30,-10000 ≤ Score ≤ 10000 。


题解

首先注意到,由于僵尸是从右侧开始走的,所以同一行内右侧植物可以认为是保护左侧一个植物的,在保护关系加边的时候可以加上这类边。
很好想,我们注意到如果把植物间的保护关系建出图,那么就可以发现,其实就是个最大权闭合子图(相当于最小割)的问题,不过形成环的植物们都是无敌的,所以可以用tarjan或者topsort求出环,然后把环上的点全部删掉,剩下的跑最大权闭合子图就行了。

网络流建图方式:

把剩下的点分为两类: score大于零的:从源点S向此点连边,流量为score
score小于零的:从此点向汇点T连边,流量为-score
然后每个点向自己保护的点连一条反向边,流量为INF
最大权闭合子图的求法:跟最小割一样,把剩下的点里面正的score全加起来,减去跑的dinic返回的值(最小割),就是答案。当然此处要和0取较大值。

代码


#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == '
 2017-05-18 22:38:05 |  2 Comments  |  OI祭

OI,来世再见

     看着标题忍不住想哭……索性不看标题写好了……
    2017年5月18日下午3:00,我的OI生涯永远定格于此,三年OI到此结束,因为我连D类队员的资格可能都拿不了。doc讲完题就走了,只剩下评测机仍然在运作。
    大概半小时左右,所有人的成绩就出来了。我依然是那个倒着数的名次,MagHsk(韩神)直接怒砍R2rank1,冲进A队。然后监考老师按照总成绩名次叫前13名面试,韩宇栋排在第二,直接成为省队副队长,我这种实力弱到不行的就只能背着包倚在墙边,默默看着省队队员们一个接一个地进入房间门去面试……
    人们常常跟我们说,运气也是实力的一部分,你不成功不过是这次运气不好就是了,不过,现在再想想,这是真的吗?这次R2带给我的无力感彻彻底底让我明白了,原来运气也不是凭空得来的啊,运气也是需要一定实力去做基础的。就像MagHsk,实力够强,于是这次直接就碰到了自己做过的结论题(当场只有两个人做出来了)。胜王败寇,弱肉强食,本身就是自然界和人类社会不变的真理呢……我只不过就是那种实力弱的,自然会被淘汰,也不用伤心过度了,坦然面对就好了。
    韩神面试完就直奔北京去参加PKUSC了,我和老师要和胜利一中的一起走,于是就在考场里面一直坐着,看着SLYZ的同学们打游戏,努力让自己忘记OI。毕竟自己已经和OI无缘了,为什么还要去想呢……目前比较期待的就是THU能不能给我THUSC的名额了。也有好多有一定实力的同学没能实现自己的目标,例如Menci大神、shallwe、stonepage等等,大家应该都在NOIP2017后就会彻底告别OI了吧。至于之后的规划,现在还是没有……不过我个人的话应该就上了大学去参加ACM竞赛吧……感觉自己也就考个上交的样子,清北的话现在连想都不敢想。
    不甘心,失望,这都是在所难免的情绪,学会放轻松,把心放平静就好了,不是还有文化课吗。如果努力不够的话,那就拼命好了。
    在各个奥赛中,联赛都是小打小闹,竞赛才是真正拿着自己的前途在赌博。其实如果给我像MagHSK那样多的时间去努力,去拼命,我现在应该也最少是个B类队员了吧。不过过去的事,谁都无法改变了,只有放眼于未来了。
    也没什么好说的了,祝韩副队长和各位省队爷NOI拿个好成绩吧。我自己,也终于退役了呢……没什么大不了的,这不过是早晚的事情。
    你好,高考;再见,OI,来世
 2017-04-12 20:56:17 |  3 Comments  |  OI祭

SDOI 2017 R1(这不是题解再说一遍)

去SDOI的时候梦想很好,但是后来发现,自己果真还是弱啊。

Day -1

最后一天刷题了。

早上依旧是7:30直奔机房,连教室都不回。已经一个周没有回教室看看了。

到机房想了想,哦,自己的字符串还是垃圾,LCT什么的根本不会……于是决定学LCT和字符串。

然后一天就只整了两道题,一道LCT板,一道KMP+DP矩阵快速幂优化。

然后就滚粗回家了。晚上颓废了一晚上,看了看LPL的比赛,然后就早早睡觉了。

Day 0

早上7:30从东营上东吕高速,大概在高速上跑了两个半小时,腿一直被卡着非常难受,最后下车的时候感觉自己左边大腿已经废了。

到了济南,在高架桥上被卡了半个多小时后,才得以到宾馆。到的时候发现MagHSK和Lyrance两位要去CTSC的dalao已经到了(我这种渣渣肯定是钦定去不了CTSC了呀)。然后被宾馆通知没有房间(MDZZ啊)。去到两年前来的时候的小店吃了一碗盖浇饭,然后才回到酒店安定下来。

然后在房间里准备Day1要考的,重新背了背板子,然后复习了下mobius反演,就已经晚上7:00了。出去吃完饭回来颓废了一会儿,然后去Menci的博客看了点东西就睡觉了。

Day 1

早上吃了一顿丰盛的早餐,就怀着忐(hua)忑(shui)的心态去了考场。我这种NOIP305的垃圾选手感觉根本不可能,我省选前才停了一周的课。

开考前20分钟试机(说好的8:00---13:00试机呢当然是开玩笑的了),现场打FFT的板子,发现自己忘记了,感觉非常方,祈祷不要考FFT。

然后监考老师发题了(我还以为那个人是出题人)

开始扫题目……

T1:gcd(i,j)?还nm <= 10^6?这是mobius反演吧……等等连乘?woc我只学过连加的mobius反演啊。。。算了先打暴力吧。

T2:woc好水的树链剖分!(开始写,然后180行后……)woc这个1操作什么玩意儿啊,根本不会维护怎么办啊喂。暴力也好难写啊,算了算了……

T3:这是啥东西?DP??欸不就是考虑在模数意义下的转移吗?嗯……好像不是很难的样子。什么神TM n<= 10^9?欸这不是我做的矩阵乘法优化?欸,容斥原理算两边?嗯模数才最大100,O(m+p^2 * logn)应该是没问题的复杂度啊。(推式子废了1个小时后)woc那里出错了啊。这TM是有顺序的还是没顺序的序列啊?(手玩样例半小时)欸这是有顺序的啊,我没做错啊。(又一个小时)woc我矩阵快速幂

 2017-04-06 00:00:14 |  0 Comments  |  splay 线段树 树套树

BZOJ 3196 二逼平衡树

引言

好久没写题解了,正好不怎么想写代码,还是来发波题解吧。

Description

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x,且最大的数)
5.查询k在区间内的后继(后继定义为大于x,且最小的数)

Input

第一行两个数 n,m 表示长度为n的有序序列和m个操作 第二行有n个数,表示有序序列
下面有m行,opt表示操作标号
若opt=1 则为操作1,之后有三个数l,r,k 表示查询k在区间[l,r]的排名
若opt=2 则为操作2,之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数
若opt=3 则为操作3,之后有两个数pos,k 表示将pos位置的数修改为k
若opt=4 则为操作4,之后有三个数l,r,k 表示查询区间[l,r]内k的前驱
若opt=5 则为操作5,之后有三个数l,r,k 表示查询区间[l,r]内k的后继

Output

对于操作1,2,4,5各输出一行,表示查询结果

Sample Input

9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5

Sample Output

2
4
3
4
9

HINT

1.n和m的数据范围:n,m<=50000
2.序列中每个数的数据范围:[0,1e8]
3.虽然原题没有,但事实上5操作的k可能为负数

题解

这是一道线段树套平衡树(就是每个线段树节点里面都存着一颗平衡树)的裸题。。。
用线段树维护下标区间,然后把平衡树节点套到线段树节点里面,注意此处的平衡树节点维护的是权值的大小。 修改操作可以转化成为找到当前这个数对应的区间,在splay里面删掉这个数,然后插入修改成的那个数就OK。
然后就是注意排名的话是比当前小的数的个数+1。
要求区间内排名为k的数的时候,我们就得注意了。因为我们是线段树套平衡树,所以说查询区间的时候,查询区间会分布在很多个线段树节点上。所以这样的话,这个操作就只能是二分答案,然后去看答案的排名是不是在这个查询区间中排k。(注意因为有重复的数,所以要求最大排名和最小排名,看k是不是在这个范围内)。
最后要注意的就是……为了保证空间,一律用内存池写。(可能我的代码里面的指针对某些读者不太友善。。。)

代码

#includ
 2017-04-01 10:00:46 |  0 Comments  |  FFT

FFT模板 【UOJ】模板题库 多项式乘法

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <complex>
using namespace std;
const int maxn = 3e5+5;
const double pi = acos(-1);
int n = 0;
int n1,n2;
int get_num(){
	int num = 0;
	char c;
	bool flag = false;
	while((c = getchar()) == ' ' || c == '\r' || c == '\n');
	if(c == '-')
		flag = true;
	else num = c - '0';
	while(isdigit(c = getchar()))
		num = num * 10 + c - '0';
	return (flag ? -1 : 1) * num;
}
struct FFT{
	complex<double>omega[maxn],iomega[maxn];
	void init(const int n){
		for(int i = 0;i < n;++i){
			omega[i] = complex<double>(cos(2*pi*i/n),sin(2*pi*i/n));
			iomega[i] = conj(omega[i]);
		}
	}
	void trans(complex<double> *a,const int n,const complex<double> *omega){
		int k = 0;
		while((1 << k) < n)k++;
		for(int i = 0;i < n;++i){
			int t = 0;
			for(int j = 0;j < k;j++)if(i&(1 << j))t |= (1 << (k-j-1));
			if(i < t)swap(a[i],a[t]);
		}
		for(int l = 2;l <= n;l *= 2){
			int m = l / 2;
			for(co
 2017-03-18 10:08:42 |  1 Comments  |  主席树

主席树模板

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
int get_num(){
	int num = 0;
	char c;
	bool flag = false;
	while((c = getchar()) == ' ' || c == '\r' || c == '\n');
	if(c == '-')
		flag = true;
	else num = c - '0';
	while(isdigit(c = getchar()))
		num = num * 10 + c - '0';
	return (flag ? -1 : 1) * num;
}
const int lim = 1e9; 
const int N = 100010; 
const int lg = 60; 
struct node{
	node *lc,*rc;
	int s;
}pool[N*lg],*rot[N],*null;
int cnt; 
int n, m, a[N], dc[N]; 
node* insert(node *u, int l, int r, int p) {
	node *ret = pool + ++cnt;
	*ret = *u; ret->s++;
	if(l == r) return ret;
	int mid = (l + r) >> 1; 
	if(p <= mid) ret->lc = insert(ret->lc,l,mid,p); 
	else ret->rc = insert(ret->rc,mid+1,r,p); 
	return ret;
}
int query(node *u, node *v, int l, int r, int k) {
	if(l == r) return dc[l]; 
	int mid = (l + r) >> 1; 
	int c = u->lc->s - v->lc-> s; 
	if(k <= c) return query(u->lc,v->lc,l,mid,k);
	return q
Title - Artist
0:00