STL

迫于拙劣的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的命名规则

可以了解成并行版的STL(? 过了一遍nvidia的官方网文档 发现如果熟悉STL的话，thrust没什么太多好说的，看起来很简单… 不过还是开一篇记录一下，一段时间内估计要和cuda c++ 打交道，就当记录使用过程中遇到的问题吧.

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.

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

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

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

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

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

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

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

题意是说，给定一个有向图，对于每一条边，问是否是 s 到 t 的最短路上一定会经过的边。 如果是就输出 yes。 如果不是，问能否通过减少这条边的权值（减少的权值就是修理费用），使得这条边成为新的最短路上的边。

http://poj.org/problem?id=1028 代码实现 1 2 3 4 /* *********************************************** 5 Author :111qqz 6 Created Time :2016年02月19日 星期五 15时45分01秒 7 File Name :1028.cpp 8 ************************************************ */ 9 10 #include <algorithm> 11 #include <cstdio> 12 #include <iostream> 13 #include <cstring> 14 #include <string> 15 #include <cmath> 16 #include <map> 17 #include <stack> 18 #include <queue> 19 20 using namespace std; 21 typedef long long LL; 22 const int inf = 8E8; 23 stack<string> backstack; 24 stack<string> forwardstack; 25 string cur; 26 string cmd; 27 int main() 28 { 29 cur ="http://www.acm.org/"; 30 31 while (cin>>cmd) 32 { 33 if (cmd=="QUIT") 34 { 35 break; 36 } 37 if (cmd=="BACK") 38 { 39 if (backstack.empty()) 40 { 41 cout<<"Ignored"<<endl; 42 continue; 43 } 44 forwardstack.push(cur); 45 cur=backstack.top(); 46 backstack.pop(); 47 cout<<cur<<endl; 48 } 49 if (cmd=="FORWARD") 50 { 51 if (forwardstack.empty()) 52 { 53 cout<<"Ignored"<<endl; 54 continue; 55 } 56 backstack.push(cur); 57 cur=forwardstack.top(); 58 forwardstack.pop(); 59 cout<<cur<<endl; 60 } 61 if (cmd=="VISIT") 62 { 63 backstack.push(cur); 64 65 cin>>cur; 66 while (!forwardstack.empty()) forwardstack.pop(); 67 cout<<cur<<endl; 68 69 } 70 } 71 72 73 return 0; 74 }

题目链接：http://poj.org/problem?id=2643 在考stl的map… 我是定义了一个string 指向string的，表示参选人和党派的关系，和一个string 指向int的，表示某个党派被投票的次数。

http://acm.hdu.edu.cn/showproblem.php?pid=1908 看到有两个优先级，然后题目中又有queue。。。就想到了优先队列。。。 但是优先队列的cmp函数没搞懂，因为比较的是结构体，好像要重载< 什么的。 然而并不会。 其实用map就可以做。。。

http://poj.org/problem?id=1833 还是next_permutation. 这次是Int类型的 需要注意的是next_permutation是先判断时候有后继，返回一个bool值，如果为true，就转化到后继。

http://poj.org/problem?id=1256 题意是说求出一个字符串的全排列，按字典序 需要注意的是字典序和传统意义上的字典序不同 重新定义了，A 需要自己重写cmp函数。 next_permutation好神….直接求出全排列…..