111qqz的小窝

老年咸鱼冲锋!

C++ STL Algotithms 学习笔记

迫于拙劣的cpp水平,这次来记录一些关于STL算法部分的内容。

参考内容是CS106L的course reader

Iterator Categories

Iterators分为以下五种:

  • Output Iterators:可以使用”++”;可以用*myItr = value,不能用value = *myItr
  • Input Iterators:可以使用”++”;可以用value = *myItr,不能用*myItr = value
  • Forward Iterators: 可以使用”++”,可以同时用value = *myItr和*myItr = value
  • Bidirectional Iterators:比起Forward Iterator 对了”–“,但是不能+或者+=
  • Random-Access Iterators:比起Bidirectional Iterators多了+和+=

Algorithm Naming Conventions

一些关于STL Algorithm的命名规则

后缀_if表示只有当满足一定条件的时候该算法才会执行一定任务。

比如:

_n表示执行一个特定的操作n次。

比如:

Reordering Algorithms

  • sort: 传入的必须是Random-Access Iterators,记得定义<函数
  • random_shuffle:传入的必须是Random-Access Iterators,作用是将一个区间内的元素打乱重排。 可以在使用之前先使用srand函数。
  • rotate:作用是循环改变容器中元素的顺序。rotate(v.begin(), v.begin() + 2, v.end());会让(0, 1, 2, 3, 4, 5)变为(2, 3, 4, 5, 0, 1)

Searching Algorithms

  • find:三个参数,前面连个迭代器表示寻找的范围,第三个参数表示要找的值。返回第一个该值所在的位置的迭代器或者返回第二个迭代器(如果没找到)
  • binary_search:需要有序;返回某个值是否在一个范围内。
  • lower_bound:需要有序;返回大于等于某值的第一个位置的迭代器。

需要注意的是,如果某个容器本身有和STL algorithm同名的成员函数(比如set的find),那么优先使用该容器的成员函数。原因是STL Algorithm需要就有普适性,不会针对特定容易优化。因此对于set来说,其成员函数的find的复杂度是logn的,而STL alogithm的find是O(n)的复杂度。

Iterator Adaptors

具有Iterator的性质,但是比Iterator更强..

比如ostream_iterator

通过copy(myVector.begin(), myVector.end(), ostream_iterator<int>(cout, ” “)); 可以直接将一个容器中的元素输出。

比如insert_iterator,对于要从一个容器拷贝元素到另一个容器,但是在编写代码时不知道源容器的元素有多少个的问题,可以很好解决?

Removal Algorithms

需要注意的是并没有真的remove,而是将”remove”的元素放在了容器后面(?),原因是STL Algorithms接受的是Iterator,而不是Container.

Other Noteworthy Algorithms

  • transform:四个参数,前两个迭代器表示要变换的范围,第三个迭代器表示结果的开始位置,第四个参数为一个函数,表示将该范围的每个元素经过该函数的处理。不要求结果和原始的数据类型相同。
  • min_element:两个迭代器表示一个范围,返回该范围中最小元素的迭代器;可以有第三个参数来自定义小于关系。max_element与之类似。
  • accumulate:template< class InputIt, class T T accumulate( InputIt first, InputIt last, T init );
  • inner_product:求内积;T inner_product( InputIt1 first1, InputIt1 last1,
    InputIt2 first2, T value );
  • distance:连个参数,表示这两个迭代器之间元素的个数。

 

 

 

cuda c++ 基础算法库 thrust 学习笔记

可以了解成并行版的STL(?

过了一遍nvidia的官方网文档

发现如果熟悉STL的话,thrust没什么太多好说的,看起来很简单…

不过还是开一篇记录一下,一段时间内估计要和cuda c++ 打交道,就当记录使用过程中遇到的问题吧.

 

BZOJ 1653: [Usaco2006 Feb]Backward Digit Sums(暴力)

 

1653: [Usaco2006 Feb]Backward Digit Sums

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 349  Solved: 258
[Submit][Status][Discuss]

Description

FJ and his cows enjoy playing a mental game. They write down the numbers from 1 to N (1 <= N <= 10) in a certain order and then sum adjacent numbers to produce a new list with one fewer number. They repeat this until only a single number is left. For example, one instance of the game (when N=4) might go like this: 3 1 2 4 4 3 6 7 9 16 Behind FJ’s back, the cows have started playing a more difficult game, in which they try to determine the starting sequence from only the final total and the number N. Unfortunately, the game is a bit above FJ’s mental arithmetic capabilities. Write a program to help FJ play the game and keep up with the cows.

Input

* Line 1: Two space-separated integers: N and the final sum.

Output

* Line 1: An ordering of the integers 1..N that leads to the given sum. If there are multiple solutions, choose the one that is lexicographically least, i.e., that puts smaller numbers first.

Sample Input


4 16

Sample Output


3 1 2 4
OUTPUT DETAILS:

There are other possible sequences, such as 3 2 1 4, but 3 1 2 4
is the lexicographically smallest.

思路:n很小。。一开始做得时候把公式推错了。。3+3算成了4.我的内心是崩溃的。。
其实直接暴力就好。可以用next_permutation来生成全排列,然后判断是否合法。

 

uva 156 – Ananagrams

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=92
题意:给出一段文字,包含若干个单词,以’#’结束。按照字典序输出所有的ananagrams。所谓ananagram,是指经过任意的重排后,不能得到这段文字中的另一个单词(不区分大小写)
思路:首先是字符串的读入…可以整行读入然后用空格分隔单词。由于补区分大小写,所以要都转化成小写…但是输出的时候要输出原始,所以还记得保留一份。而且要能够通过新的找到原始的(我用了一个toori的map<string,string>来实现)
然后最关键的部分是如何判断两个单词经过重排是否能一样…

我的做法是构造一个hash函数…一个单词的hash值等于对应字母的顺序的平方和…效果还不错?

单词和hash值一一对应…最大也就9E5,可以存的下。然后统计每个hash值出现的次数。对于那些只出现一次的,就是我们要的答案。

还要注意的是输出要按照原始单词的字典序,而不是都变成小写以后的字典序。

所以找到之后可以先找到对应的原始单词存到set里,最后再输出。

 

 

 

codeforces 29 C. Mail Stamps

http://codeforces.com/contest/29/problem/C
题意:给出n个边的关系,保证可以构成一条链。正向或者反向输出这个链。
思路:由于下标很大(1E9),而关系个数只有1E5..需要离散化。。而且离散化的同时不能丢失边的关系。。。实际上。。直接用vector+map就好了。。。 map >e;即可。然后找到一个度为1的点。。做个dfs…

codeforces 12 C. Fruits

http://codeforces.com/contest/12/problem/C
题意:有n个价格价格,m个要买的东西(可能有相同的种类,设为k种),把n个标签中拿出k个给个贴上。。。问最大价钱和最少价钱分别是多少。
思路:贪心。不过要按照map的value排序。。然后发现其实不用排序。。因为map的key值其实不影响。

vector降序排列的话。。直接 sort(v.rbegin(),v.rend());就好。

 

 

 

codeforces #332 div 2 D. Spongebob and Squares

http://codeforces.com/contest/599/problem/D
题意:给出总的方格数x,问有多少种不同尺寸的矩形满足题意,输出方案数和长宽(3,5和5,3算两种)
思路:比赛的时候gg了。。其实稍微在纸上推一下。就会得到对于n,m的矩形,一共会有-n*n*n+3*n*n*m+n+3*n*m的方格。数量级是n3。
我们可以实际跑一遍。发现对于x1E18的数量级,n不会超过1442550,1E6,可以搞。

需要注意的是,一个是会爆int,所以记得用long long

另一个是如果两个数相等,记得只输入一组,并且方案数-1

我是用set +pair存的答案。。反向遍历set的时候要用reserve_iterator…

 

 

codeforces #333 div 2B. Approximating a Constant Range

http://codeforces.com/contest/602/problem/B
题意:给定n个数,问最大连续区间长度,满足这段区间内最大值和最小值的差的绝对值小于等于1.
思路:尺取+set。尺取法,由于要时刻得到一段区间的最大值和最小值,而且可能有重复元素,所以用multiset.

需要注意的是,set里最小值是*se.begin() ,最大值是*se.rbegin()这样比较好。。不要用se.end()之类。。。

另一个需要注意的是,multiset里用erase的时候。如果se.erase(x)会把集合里所有的x都删除掉。如果指向删除一个,那么应该写成se.erase(se.find(x))

 

poj 3687 Labeling Balls

http://poj.org/problem?id=3687
题意:给定几个标签球的重量大小关系,求每个球是第几重的(即每个球在所有球的重量中由小到大排名是多少)。
输出是每个球第几重,而不是几号球比几号球重!)。一开始理解错了QAQ
思路:反向拓扑+优先队列。因为正向不好用。。。所以我们连边的时候由重的指向轻的。。这样最先出队的就是最重的。。和上道题差不多?

 

hdoj4391 Paint The Wall

http://acm.hdu.edu.cn/showproblem.php?pid=4391
题意:有 n 个点,每个点有一种颜色(可能相同),两种操作:1、将区间 [a,b] 染成颜色 c ; 2、询问区间 [a,b] 中颜色为 c 的点有多少个。
思路:因为颜色种类很多。。。没办法通过建很多棵线段树解决。我们用分块的办法。。。

codeforces 567 E President and Roads (优先队列+迪杰斯特拉+tarjan)

题意是说,给定一个有向图,对于每一条边,问是否是s到t的最短路上一定会经过的边.

如果是就输出yes

如果不是,问能否通过减少这条边的权值(减少的权值就是修理费用),使得这条边成为新的最短路上的边.

对于一条边是否一定是最短路上的边,我们可以从s做一遍最短路,然后反响建边,从t再做一遍最短路.

得到两个d1,d2数组

如果一条边d1[u] + d2[v] + w(u, v) = 最短路,那这条边在最短路上的边.但是未必不能缺少.

我们还要判断这条边是否是不能缺少的.

不能缺少的意思是说,如果没有这条边,就不能构成最短路.

那么这条边一定是桥.

我们可以用tarjan算法求桥.

 

据说是水题,不过图论还没怎么刷,所以对我来说还是很有难度的.

只是基本懂了

下面的代码是我仿照其他人的代码写出来的….求不鄙视 ><

POJ 1028 Web Navigation

http://poj.org/problem?id=1028

poj 2643 election

题目链接:http://poj.org/problem?id=2643

 

在考stl的map…

我是定义了一个string 指向string的,表示参选人和党派的关系,和一个string 指向int的,表示某个党派被投票的次数。

需要注意的是!!!

需要注意的是!!!

需要注意的是!!!

 

字符串读入部分…

在输入n和m之后,会有一个回车符没读进去…(大概是这样?)

如果不处理一下的话,后面的字符串就会少读入一个…(sad)

解决的办法是在读完n和m之后写一个getchar(); 把回车符读掉。

 

poj 3481 double queues

http://acm.hdu.edu.cn/showproblem.php?pid=1908

看到有两个优先级,然后题目中又有queue。。。就想到了优先队列。。。

但是优先队列的cmp函数没搞懂,因为比较的是结构体,好像要重载< 什么的。

然而并不会。

其实用map就可以做。。。

map在插入的时候可以自动按关键字排序,简直好评如潮!

STL容器之优先队列

STL容器之优先队列

优先级队列,以前刷题的时候用的比较熟,现在竟然我只能记得它的关键字是priority_queue(太伤了)。在一些定义了权重的地方这个数据结构是很有用的。

先回顾队列的定义:队列(queue)维护了一组对象,进入队列的对象被放置在尾部,下一个被取出的元素则取自队列的首部。priority_queue特别之处在于,允许用户为队列中存储的元素设置优先级。这种队列不是直接将新元素放置在队列尾部,而是放在比它优先级低的元素前面。标准库默认使用<操作符来确定对象之间的优先级关系,所以如果要使用自定义对象,需要重载 < 操作符。

优先队列有两种,一种是最大优先队列;一种是最小优先队列;每次取自队列的第一个元素分别是优先级最大和优先级最小的元素。

1) 优先队列的定义

包含头文件:”queue.h”, “functional.h”

可以使用具有默认优先级的已有数据结构;也可以再定义优先队列的时候传入自定义的优先级比较对象;或者使用自定义对象(数据结构),但是必须重载好< 操作符。 

2) 优先队列的常用操作

优先级队列支持的操作

q.empty()         如果队列为空,则返回true,否则返回false

q.size()            返回队列中元素的个数

q.pop()             删除队首元素,但不返回其值

q.top()             返回具有最高优先级的元素值,但不删除该元素

q.push(item)     在基于优先级的适当位置插入新元素

其中q.top()为查找操作,在最小优先队列中搜索优先权最小的元素,在最大优先队列中搜索优先权最大的元素。q.pop()为删除该元素。优先队列插入和删除元素的复杂度都是O(lgn),所以很快

另外,在优先队列中,元素可以具有相同的优先权。

下面这个C例子,包含了几乎所有常见的优先队列用法。 

复制代码

复制代码