# poj 1961 Period(kmp最短循环节)

Description

For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know
the largest K > 1 (if there is one) such that the prefix of S with length i can be written as AK ,that is A concatenated K times, for some string A. Of course, we also want to know the period K.……………………

给定一个长度为n的字符串s，求他每个前缀的最短循环节。换句话说，对于每个i（2<=i<=n），求一个最大的整数k（如果k存在），使得s的前i个字符可以组成的前缀是某个字符串重复k次得到的。输出所有存在K的i和对应的k。

这是刘汝佳《算法竞赛入门经典训练指南》上的原题（p213），用KMP构造状态转移表。

//poj 1961
#include <stdio.h>
const int maxn = 1000000 + 10;

char p[maxn];
int f[maxn];

int main()
{
int n, t = 1;
while (scanf("%d",&n) && n)
{
scanf("%s",p);
f[0] = 0;
f[1] = 0;
for (int i = 1; i < n; i++)
{
int j = f[i];
while (p[i] != p[j] && j)
j = f[j];
f[i+1] = (p[i] == p[j] ? j+1 : 0);
}/*这段代码就是KMP里面核心的代码,这里没有文本串，
我们只需要处理模板即可*/
printf("Test case #%d\n",t++);
for (int i = 2; i <= n; i++)
{
if (f[i] > 0 && i % (i-f[i]) == 0)
printf("%d %d\n",i, i / (i-f[i]));
}
puts("");
}
return 0;
}


# poj 2352 Stars 树状数组

Description

Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given
star. Astronomers want to know the distribution of the levels of the stars.………………

#include<stdio.h>
#include<string.h>

int a[32002];
int level[15002];

int lowbit(int x)
{
return x&(-x);
}

void insert(int x)
{
while(x<32002)
{
a[x]++;
x += lowbit(x);
}
}

int sum(int x)
{
int s=0;
while(x)
{
s += a[x];
x -= lowbit(x);
}
return s;
}

int main()
{
int n, i, x, y;
scanf("%d",&n);
memset(a,0,sizeof(level));
memset(level,0,sizeof(level));
for(i = 0; i < n; i++)
{
scanf("%d%d",&x,&y);
x++;
level[sum(x)]++;
insert(x);
}
for(i= 0; i < n; i++)
printf("%d\n",level[i]);
return 0;
}


# poj 2182 Lost Cows（树状数组）

Description

N (2 <= N <= 8,000) cows have unique brands in the range 1..N. In a spectacular display of poor judgment, they visited the neighborhood ‘watering hole’ and drank a few too many beers before dinner. When it was time to line up for
their evening meal, they did not line up in the required ascending numerical order of their brands.

Regrettably, FJ does not have a way to sort them. Furthermore, he’s not very good at observing problems. Instead of writing down each cow’s brand, he determined a rather silly statistic: For each cow in line, he knows the number of cows that precede that cow
in line that do, in fact, have smaller brands than that cow.

Given this data, tell FJ the exact ordering of the cows. ……………………

FJ有n头牛，现在它们排成一排，每一头牛都有一个不同的编号（1-n），现在知道从第二头牛开始每头牛左边比自己编号小的牛的数目，让你确定每头牛的编号。

我用一个树状数组来表示第i头牛的左边有多少比自己标号小的，树状数组必须初始化，每个节点必须加1。每次我们可以知道最后一头牛的编号x，然后然后更新x以后的区间使其都减1（这里也可以使用线段树，不过感觉比较麻烦，因为树状数组的特性，只需要更新x就好了），然后求倒数第二头的编号，我们只需要找到一个x，使得sum(x) 为该牛左边小于其编号牛的数量，使用二分查找可以提高查找速率，然后是倒数第三头的………………………………

因为是倒着来的，为了熟悉stl，我使用了其封装的stack 栈。

下面是解题代码：

#include <stdio.h>
#include <string.h>
#include <stack>
#define maxn 8005

using namespace std;

int a[maxn];
int ans[maxn];
int n;

int lowbit(int x)
{
return x&(-x);
}

{
while (x <= n)
{
a[x] += v;
x += lowbit(x);
}
}

int sum(int x)
{
int s = 0;
while (x > 0)
{
s += a[x];
x -= lowbit(x);
}
return s;
}

int binarysearch(int l, int r, int x)
{
if (l == r)
return l;
int mid = (l + r) >> 1;
if (x <= sum(mid))
return binarysearch(l, mid, x);
else
return binarysearch(mid+1, r, x);
}
/*二分查找也可以写成非递归的形式，避免了函数的调用和栈的开销，节约时间空间，

stack <int> s;
int main()
{
int t;
while (scanf("%d",&n) != EOF)
{
memset(a, 0, sizeof(a));
//因为每次使用s后s必定为空，就不用初始化了

int i;
for (i = 1; i < n; i++)
{
scanf("%d",&t);
s.push(t);
}
while (i > 1)
{
int x = binarysearch(1, n, s.top());
ans[i--] = x;
s.pop();
}
ans[1] = binarysearch(1, n, 0);
//while循环只循环n-1次（如果循环n次栈会出错），所以要加这行

for (i = 1; i <= n; i++)
{
printf("%d\n",ans[i]);
}
}
return 0;
}


# ZOJ1117 POJ1521 HDU1053 Huffman编码

Description

An entropy encoder is a data encoding method that achieves lossless data compression by encoding a message with “wasted” or “extra” information removed. In other words, entropy encoding removes information that was not necessary
in the first place to accurately encode the message. A high degree of entropy implies a message with a great deal of wasted information; english text encoded in ASCII is an example of a message type that has very high entropy. Already compressed messages,
such as JPEG graphics or ZIP archives, have very little entropy and do not benefit from further attempts at entropy encoding. …………………………

题意是输入一字符串，然后进行Huffman编码，输出原字符串所占的长度，编码后所占的长度，以及两个长度之间的比值。

Huffman编码的思想就是贪心，我们这里使用stl里的优先队列，priority_queue使用堆进行优化，虽然自己也可以写一个堆，但我感觉对于这道题有点主次不分了，再次感觉到stl确实是一个很强大的东西。

解题代码

//ZOJ1117 POJ1521 HDU1053  Huffman编码
#include <stdio.h>
#include <queue>
#include <string.h>
#include <vector>

using namespace std;
char str[500];
int cnt[260];

struct cmp
{
bool operator()(int a, int b)
{
return a > b;
}
};
/*我们可以直接priority_queue<int>  这样它默认的是使用vector<int> 并且是大的优先

class cmp
{
public:
bool operator() (int a, int b)
{
return a > b;
}
};
*/
priority_queue <int, vector<int>, cmp> q;

int main()
{
while (scanf("%s",str) && strcmp(str,"END"))
{
int l = strlen(str);
memset(cnt, 0, sizeof(cnt));
//我们不需要清空队列，因为每次操作完后它都被清空了
for (int i = 0; i < l; i++)
{
cnt[str[i]]++;
}
for (int i = 0; i < 260; i++)
{
if (cnt[i])
{
q.push(cnt[i]);
}
}
int nl = 0;
if (q.size() == 1)
nl = l;
while (q.size() > 1)
{
int a = q.top(); q.pop();
int b = q.top(); q.pop();
q.push(a+b);
nl += (a+b);
//我想看到这也许会有些疑惑，为什么要加（a+b），稍微思考一下就明白了
}
q.pop();
printf("%d %d %.1lf\n",8*l, nl, (double)(8*l)/(double)nl);
}
return 0;
}


# POJ 1195 Mobile phones (二维树状树组)

由于英语极差，看了半天也没看懂题目，最后参考了其他人的题解才搞懂题目，我就直接把题意贴过来了

这是我做的第一道二维树状树组的题目，感觉和一维的差不多，下面是题解。

//poj 1195
#include <stdio.h>
#include <string.h>
const int maxn = 1030;

int n, a[maxn][maxn];

int lowbit(int x)
{
return x & (-x);
}

void update(int i, int j, int v)
{
int t;
while(i <= n)
{
t = j;                        //不能改变j的值，因为每次循环都要用到
while (t <= n)
{
a[i][t] += v;
t += lowbit(t);
}
i += lowbit(i);
}
}

int getsum(int i, int j)
{
int sum = 0, t;
while (i > 0)
{
t = j;                          //不能改变j的值，因为每次循环都要用到
while (t > 0)
{
sum += a[i][t];
t -= lowbit(t);
}
i -= lowbit(i);
}
return sum;
}

int main()
{
int op, x, y, v, xx, yy;
while (scanf("%d%d",&op,&n) != EOF)
{
memset(a, 0, sizeof(a));
while (scanf("%d",&op) && op != 3)
{
if (op == 1)
{
scanf("%d%d%d",&x, &y, &v);
x++; y++;                         //树状数组坐标是从1开始的，以此要加1
update(x, y, v);
}
else
{
scanf("%d%d%d%d", &x, &y, &xx, &yy);
x ++, y ++, xx ++, yy ++;
int ans = getsum(xx, yy) - getsum(x-1, yy) - getsum(xx, y-1) + getsum(x-1, y-1);
// 每次getsum(i, j); 得到的结果是（i，j）前面所有数的和
printf("%d\n", ans);
}
}
}
return 0;
}


# 计算机科学中的树

## 自平衡二叉查找树

▪ AA树 ▪ AVL树 ▪ 红黑树 ▪ 伸展树 ▪ 树堆 ▪ 节点大小平衡树

## Trie

▪ 前缀树 ▪ 后缀树 ▪ 基数树

## 空间划分树

▪ 四叉树 ▪ 八叉树 ▪ k-d树 ▪ vp-树 ▪ R树 ▪ R*树 ▪ R+树 ▪ X树 ▪ M树 ▪ 线段树 ▪ 希尔伯特R树 ▪ 优先R树

# POJ数据结构专辑（含部分题解）

1195 Mobile phones 树状数组

1455 Crazy tea party
题解

1521 Entropy huffman                                                               题解

1703 Find them, Catch them 并查集

1785 Binary Search Heap Construction

1794 Castle Walls 逆序对

1961 Period KMP重复因子                                                        题解

1986* Distance Queries LCA

1988* Cube Stacking 并查集应用

1990* MooFest 线段树

2010* Moo University – Financial Aid 最大堆-最小堆

2182 Lost Cows 线段树                                                              题解

2183 Bovine Math Geniuses hash

2188 Cow Laundry 逆序对

2227 The Wedding Juicer 堆+floodfill

2236 Wireless Network 并查集

2269* Friends 表达式

2270 Quadtree II or: Florida Jones strikes back 将2266反之

2299 Ultra-QuickSort 归并排序

2352 Stars 树状数组                                                                   题解

2395 Out of Hay 并查集

2482 Stars in Your Window 静态2叉树

2513 Colored Sticks 并查集

2524 Ubiquitous Religions 并查集

2528 Mayor’s posters 线段树

2567 Code the Tree

2750* Potted Flower 线段树

2777 Count Color 线段树

2796 Feel Good RMQ

2823 Sliding Window 堆或双端队列

2886* Who Gets the Most Candies? 线段树

2892* Tunnel Warfare 树状数组

3214* Heap 后序遍历，每个节点减去相应sub保证属性，然后对遍历结果求最长不下降序列

3253 Fence Repair huffman

3263 Tallest Cow 线段树

3274* Gold Balanced Lineup hash

3277 City Horizon 线段树

3321* Apple Tree 树状数组

3332 Parsing Real Numbers DFA

3344 Chessboard Dance 队列模拟

3349 Snowflake Snow Snowflakes hash(or 暴力)

3437 Tree Grafting dfs树构造

3461 Oulipo KMP

3468 A Simple Problem with Integers 线段树区间更新，懒操作

3631 Cuckoo Hashing 并查集

3667 Hotel 线段树

3690 Constellations trie匹配

3695 Rectangles 矩阵切割

# ACM竞赛常用STL（二）之STL–algorithm

<algorithm>无疑是STL 中最大的一个头文件，它是由一大堆模板函数组成的。

adjacent_find / binary_search / copy / copy_backward / count

/ count_if / equal / equal_range / fill / fill_n / find /

find_end / find_first_of / find_if / for_each / generate /

generate_n / includes / inplace_merge / iter_swap /

lexicographical_compare / lower_bound / make_heap / max /

max_element / merge / min / min_element / mismatch /

next_permutation / nth_element / partial_sort /

partial_sort_copy / partition / pop_heap / prev_permutation

/ push_heap / random_shuffle / remove / remove_copy /

remove_copy_if / remove_if / replace / replace_copy /

replace_copy_if / replace_if / reverse / reverse_copy /

rotate / rotate_copy / search / search_n / set_difference /

set_intersection / set_symmetric_difference / set_union /

sort / sort_heap / stable_partition / stable_sort / swap /

swap_ranges / transform / unique / unique_copy / upper_bound

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int Visit(int v) // 遍历算子函数
{
cout << v << " ";
return 1;
}
class MultInt // 定义遍历算子类
{
private:
int factor;
public:
MultInt(int f) : factor(f){}
void operator()(int &elem) const
{
elem *= factor;
}
};
int main()
{
vector<int> L;
for (int i=0; i<10; i++)
L.push_back(i);
for_each(L.begin(), L.end(), Visit);
cout << endl;
for_each(L.begin(), L.end(), MultInt(2));
for_each(L.begin(), L.end(), Visit);
cout << endl;
return 0;
}

0 1 2 3 4 5 6 7 8 9

0 2 4 6 8 10 12 14 16 18

using namespace std;
int main()
{
vector<int> L;
for (int i=0; i<10; i++)
L.push_back(i);
vector<int>::iterator min_it = min_element(L.begin(),L.end());
vector<int>::iterator max_it = max_element(L.begin(),L.end());
cout << "Min is " << *min_it << endl;
cout << "Max is " << *max_it << endl;
return 1;
}

Min is 0

Max is 9

#include <iostream>
#include <vector>
#include <algorithm>

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void Print(vector<int> &L)
{
for (vector<int>::iterator it=L.begin(); it!=L.end();it++)
cout << *it << " ";
cout << endl;
}
int main()
{
vector<int> L;
for (int i=0; i<5; i++)
L.push_back(i);
for (int i=9; i>=5; i--)
L.push_back(i);
Print(L);
sort(L.begin(), L.end());
Print(L);
sort(L.begin(), L.end(), greater<int>()); // 按降序排序
Print(L);
return 0;
}

0 1 2 3 4 9 8 7 6 5

0 1 2 3 4 5 6 7 8 9

9 8 7 6 5 4 3 2 1 0

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
// 先初始化两个向量v1 和v2
vector <int> v1, v2;
for (int i=0; i<=5; i++)
v1.push_back(10*i);
for (int i=0; i<=10; i++)
v2.push_back(3*i);
cout << "v1 = ( " ;
for (vector <int>::iterator it=v1.begin(); it!=v1.end();it++)
cout << *it << " ";
cout << ")" << endl;
cout << "v2 = ( " ;
for (vector <int>::iterator it=v2.begin(); it!=v2.end();it++)
cout << *it << " ";
cout << ")" << endl;
// 将v1 的前三个元素复制到v2 的中间
copy(v1.begin(), v1.begin()+3, v2.begin()+4);
cout << "v2 with v1 insert = ( " ;
for (vector <int>::iterator it=v2.begin(); it!=v2.end();it++)
cout << *it << " ";
cout << ")" << endl;
// 在v2 内部进行复制，注意参数2 表示结束位置，结束位置不参与复制
copy(v2.begin()+4, v2.begin()+7, v2.begin()+2);
cout << "v2 with shifted insert = ( " ;
for (vector <int>::iterator it=v2.begin(); it!=v2.end();it++)
cout << *it << " ";
cout << ")" << endl;
return 1;
}

v1 = ( 0 10 20 30 40 50 )

v2 = ( 0 3 6 9 12 15 18 21 24 27 30 )

v2 with v1 insert = ( 0 3 6 9 0 10 20 21 24 27 30 )

v2 with shifted insert = ( 0 3 0 10 20 10 20 21 24 27 30 )

STL in ACM

begin(), //取首个元素，返回一个iterator
end(), //取末尾（最后一个元素的下一个存储空间的地址）
size(), //就是数组大小的意思
clear(), //清空
empty(), //判断vector 是否为空
[ ] //很神奇的东东，可以和数组一样操作
//举例： vector a; //定义了一个vector
//然后我们就可以用a[i]来直接访问a 中的第i + 1 个元素！和数组的下标一模一样！
push_back(), pop_back() //从末尾插入或弹出
insert() O(N) //插入元素，O(n)的复杂度
erase() O(N) //删除某个元素，O(n)的复杂度

Iterator 用法举例:

int main()
{
int n,i;
vector vi; //类似于我们定义一个数组，同 int vi[1000]; 但vector的大小是自动调整的
vector ::iterator itr; //两个冒号
while (scanf("%d",&n) != EOF)
vi.push_back(n);
for (i = 0 ; i < vi.size() ; i++)
printf("%d\n",vi[i]);
for (itr = vi.begin() ; itr != vi.end() ; itr++)
printf("%d\n",*itr);
return 0;
}

类似：双端队列，两头都支持进出

是的精简版:) //栈，只支持从末尾进出

list

begin(), end(), size(), clear(), empty()
push_back(), pop_back() //从末尾插入或删除元素
push_front(), pop_front()
insert() O(1) //链表实现，所以插入和删除的复杂度的O(1)
erase() O(1)
sort() O(nlogn),不同于中的sort
//不支持[ ]操作！

set //又是一个Compare 函数，类似于qsort 函数里的那个Compare 函数，

insert() O(logn)
erase() O(logn)
find() O(logn) 找不到返回a.end()
lower_bound() O(logn) 查找第一个不小于k 的元素
upper_bound() O(logn) 查找第一个大于k 的元素
equal_range() O(logn) 返回pair
42

struct SS {int x,y;};
struct ltstr {
bool operator() (SS a, SS b)
{return a.x < b.x;} //注意，按C 语言习惯，double 型要写成这样：
return a.x < b.x ? 1 : 0;
};
int main() {
set st;
…
}

map //就是很多pair 组成一个红黑树
insert() O(logn)
erase() O(logn)
find() O(logn) 找不到返回a.end()
lower_bound() O(logn) 查找第一个不小于k 的元素
upper_bound() O(logn) 查找第一个大于k 的元素
equal_range() O(logn) 返回pair
[key]运算符 O(logn) *** //这个..太猛了，怎么说呢，数组有一个下标，如a[i],这里i 是int 型的。数组可以认为是从int 印射到另一个类型的印射，而map 是一个任意的印射，所以i 可以是任何类型的！允许重复元素, 没有[]运算符

priority_queue

push() O(n)
pop() O(n)
top() O(1)

priority_queue maxheap; //int 最大堆
struct ltstr { //又是这么个Compare 函数，重载运算符？？？不明白为什么要这么写...反正这个Compare 函数对我来说是相当之神奇。RoBa

bool operator()(int a,int b)
{return a > b;}
};
priority_queue <INT,VECTOR,ltstr> minheap; //int 最小堆
1.sort()
void sort(RandomAccessIterator first, RandomAccessIterator
last);
void sort(RandomAccessIterator first, RandomAccessIterator
last, StrictWeakOrdering comp);

Quicksort,复杂度O(nlogn)
(n=last-first,平均情况和最坏情况)

1.从小到大排序(int, double, char, string, etc)
const int N = 5;
int main()
{
int a[N] = {4,3,2,6,1};
string str[N] = {“TJU”,”ACM”,”ICPC”,”abc”,”kkkkk”};
sort(a,a+N);
sort(str,str+N);
return 0;
}
2.从大到小排序（需要自己写comp 函数)
const int N = 5;
int cmp(int a,int b)
{
return a > b;
}
int main()
{
int a[N] = {4,3,2,6,1};
sort(a,a+N,cmp);
return 0;
}
3. 对结构体排序
struct SS {int first,second;};
int cmp(SS a,SS b)
{
if (a.first != b.first)
return a.first < b.first;
return a.second < b.second;
}
v.s. qsort() in C (平均情况O(nlogn)，最坏情况
O(n^2)) //qsort 中的cmp 函数写起来就麻烦多了！
int cmp(const void *a,const void *b) {
if (((SS*)a)->first != ((SS*)b)->first)
return ((SS*)a)->first – ((SS*)b)->first;
return ((SS*)a)->second – ((SS*)b)->second;
}
qsort(array,n,sizeof(array[0]),cmp);
sort()系列:
stable_sort(first,last,cmp); //稳定排序
partial_sort(first,middle,last,cmp);//部分排序

e.g.
int A[12] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};
partial_sort(A, A + 5, A + 12);
// 结果是 "1 2 3 4 5 11 12 10 9 8 7 6".
Detail: Heapsort ,
O((last-first)*log(middle-first))
sort()系列:
partial_sort_copy(first, last, result_first, result_last,
cmp);
//输入到另一个容器，不破坏原有序列
bool is_sorted(first, last, cmp);
//判断是否已经有序
nth_element(first, nth, last, cmp);
//使[first,nth)的元素不大于[nth,last), O(N)
e.g. input: 7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5
nth_element(A,A+6,A+12);
Output: 5 2 6 1 4 3 7 8 9 10 11 12
2. binary_search()
bool binary_search(ForwardIterator first, ForwardIterator
last, const LessThanComparable& value);
bool binary_search(ForwardIterator first, ForwardIterator
last, const T& value, StrictWeakOrdering comp);

v.s. bsearch() in C
Binary_search()系列
itr upper_bound(first, last, value, cmp);
//itr 指向大于value 的第一个值(或容器末尾)
itr lower_bound(first, last, value, cmp);
//itr 指向不小于valude 的第一个值(或容器末尾)
pair equal_range(first, last, value, cmp);
//找出等于value 的值的范围 O(2*log(last – first))
int A[N] = {1,2,3,3,3,5,8}
*upper_bound(A,A+N,3) == 5
*lower_bound(A,A+N,3) == 3
make_heap(first,last,cmp) O(n)
push_heap(first,last,cmp) O(logn)
pop_heap(first,last,cmp) O(logn)
is_heap(first,last,cmp) O(n)
e.g:
vector vi;
while (scanf(“%d”,&n) != EOF)
{
vi.push_back(n);
push_heap(vi.begin(),vi.end());
}
Others interesting:
next_permutation(first, last, cmp)
prev_permutation(first, last, cmp)
//both O(N)
min(a,b);
max(a,b);
min_element(first, last, cmp);
max_element(first, last, cmp);
Others interesting:
fill(first, last, value)
reverse(first, last)
rotate(first,middle,last);
itr unique(first, last);
//返回指针指向合并后的末尾处
random_shuffle(first, last, rand)
//头文件
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;

# ACM竞赛常用STL（一）

## 全排列函数next_permutation

STL 中专门用于排列的函数（可以处理存在重复数据集的排列问题）

using namespace std;

// 数组
int a[N];
sort(a, a+N);
next_permutation(a, a+N);
// 向量
vector<int> ivec;
sort(ivec.begin(), ivec.end());
next_permutation(ivec.begin(), ivec.end());

vector<int> myVec;
// 初始化代码
sort(myVec.begin(),myVec.end());
do{
for (i = 0 ;i < size;i ++ ) cout << myVec[i] << " \t " ;
cout << endl;
}while (next_permutation(myVec.begin(), myVec.end()));

## ACM/ICPC 竞赛之STL–pair

STL <utility>头文件中描述了一个看上去非常简单的模板类pair，用来表示一个二元组或元素对，并提供了按照字典序对元素对进行大小比较的比较运算符模板函数。

pair<double, double> p1;cin >> p1.first >> p1.second;pair 模板类需要两个参数：首元素的数据类型和尾元素的数据类型。pair 模板类对象有两个成员：first second，分别表示首元素和尾元素。

<utility>中已经定义了pair 上的六个比较运算符：<><=>===!=，其规则是先比较firstfirst 相等时再比较second，这符合大多数应用的逻辑。当然，也可以通过重载这几个运算符来重新指定自己的比较逻辑。除了直接定义一个pair 对象外，如果需要即时生成一个pair 对象，也可以调用在<utility>中定义的一个模板函数：make_pairmake_pair 需要两个参数，分别为元素对的首元素和尾元素。

#include <iostream>
#include <queue>
using namespace std;
typedef pair<unsigned long, int> node_type;
int main()
{
unsigned long result[1500];
priority_queue< node_type, vector<node_type>,
greater<node_type> > Q;
Q.push( make_pair(1, 2) );
for (int i=0; i<1500; i++)
{
node_type node = Q.top(); Q.pop();
switch(node.second)
{
case 2: Q.push( make_pair(node.first*2, 2) );
case 3: Q.push( make_pair(node.first*3, 3) );
case 5: Q.push( make_pair(node.first*5, 5) );
}
result[i] = node.first;
}
int n;
cin >> n;
while (n>0)
{
cout << result[n-1] << endl;
cin >> n;
}
return 0;
}

## ACM/ICPC 竞赛之STL–vector

STL <vector>头文件中定义了vector（向量容器模板类），vector容器以连续数组的方式存储元素序列，可以将vector 看作是以顺序结构实现的线性表。当我们在程序中需要使用动态数组时，vector 将会是理想的选择，vector 可以在使用过程中动态地增长存储空间。

vector 模板类需要两个模板参数，第一个参数是存储元素的数据类型，第二个参数是存储分配器的类型，其中第二个参数是可选的，如果不给出第二个参数，将使用默认的分配器。

vector<int> s;

vector<int> s(n);定义一个含有int 元素的vector 对象。

vector<int> s(first, last);定义一个vector 对象，并从由迭代器first last 定义的序列[first,last)中复制初值。

vector 的基本操作有：

s[i]直接以下标方式访问容器中的元素。

s.front() 返回首元素。

s.back() 返回尾元素。

s.push_back(x)向表尾插入元素x

s.size() 返回表长。

s.empty() 当表空时，返回真，否则返回假。

s.pop_back() 删除表尾元素。

s.begin() 返回指向首元素的随机存取迭代器。

s.end() 返回指向尾元素的下一个位置的随机存取迭代器。

s.insert(it, x) 向迭代器it 指向的元素前插入新元素val

s.insert(it, n, x)向迭代器it 指向的元素前插入x

s.insert(it, first, last)将由迭代器first last 所指定的序列[first, last)插入到迭代器it

s.erase(it)删除由迭代器it 所指向的元素。

s.erase(first, last)删除由迭代器first last 所指定的序列[first, last)

s.reserve(n)预分配缓冲空间，使存储空间至少可容纳个元素。

s.resize(n)改变序列的长度，超出的元素将会被删除，如果序列需要扩展（原空间小于n），元素默认值将填满扩展出的空间。

s.resize(n, val)改变序列的长度，超出的元素将会被删除，如果序列需要扩展（原空间小于n），将用val 填满扩展出的空间。

s.clear()删除容器中的所有的元素。

s.swap(v)将与另一个vector 对象进行交换。

s.assign(first, last)将序列替换成由迭代器first last 所指定的序列[first, last)[first, last)不能是原序列中的一部分。要注意的是，resize 操作和clear 操作都是对表的有效元素进行的操作，但并不一定会改变缓冲空间的大小。另外，vector 还有其他一些操作如反转、取反等，不再一下列举。vector 上还定义了序列之间的比较操作运算符(>, <, >=, <=, ==, !=)

#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> L;
int x;
while (cin>>x) L.push_back(x);
for (int i=L.size()-1; i>=0; i--)
cout << L[i] << " ";
cout << endl;
return 0;
}

## ACM/ICPC 竞赛之STL–iterator 简介

iterator(迭代器)是用于访问容器中元素的指示器，从这个意义上说，iterator(迭代器)相当于数据结构中所说的“遍历指针”，也可以把iterator(迭代器)看作是一种泛化的指针。STL 中关于iterator(迭代器)的实现是相当复杂的，这里我们暂时不去详细讨论关于iterator(迭代器)的实现和使用，而只对iterator(迭代器)做一点简单的介绍。

#include <iostream>
#include <vector>
using namespace std;
main()
{
vector<int> s;
for (int i=0; i<10; i++)
s.push_back(i);
for (vector<int>::iterator it=s.begin(); it!=s.end();it++)
cout << *it << " ";
cout << endl;
return 1;
}

vector begin()end()方法都会返回一个vector::iterator 对象，分别指向vector 的首元素位置和尾元素的下一个位置（我们可以称之为结束标志位置）。对一个iterator(迭代器)对象的使用与一个指针变量的使用极为相似，或者可以这样说，指针就是一个非常标准的iterator(迭代器)。再来看一段稍微特别一点的代码：

#include <iostream>
#include <vector>
using namespace std;
main()
{
vector<int> s;
s.push_back(1);
s.push_back(2);
s.push_back(3);
copy(s.begin(), s.end(), ostream_iterator<int>(cout, ""));
cout <<endl;
return 1;
}

## ACM/ICPC 竞赛之STL–string

#include <iostream>
#include <string>
using namespace std;
int main()
{
string s = "Hello! ", name;
cin >> name;
s += name;
s += '!';
cout << s << endl;
return 0;
}

int m;

cin >> m; // P 编码的长度

string str; // 用来存放还原出来的括号字符串

int leftpa = 0; // 记录已出现的左括号的总数

for (int j=0; j<m; j++){

int p;

cin >> p;

for (int k=0; k<p-leftpa; k++) str += ‘(‘;

str += ‘)’;

leftpa = p;

}

## ACM/ICPC 竞赛之STL–stack/queue

stack()queue(队列)也是在程序设计中经常会用到的数据容器，STL为我们提供了方便的stack()queue(队列)的实现。39准确地说，STL 中的stack queue 不同于vectorlist 等容器，而是对这些容器的重新包装。这里我们不去深入讨论STL stack queue 的实现细节，而是来了解一些他们的基本使用。

### 1、stack

stack 模板类的定义在<stack>头文件中。

stack 模板类需要两个模板参数，一个是元素类型，一个容器类型，但只有元

stack<int> s1;

stack<string> s2;

stack 的基本操作有：

#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main()
{
int n;
cin >> n;
for (int i=0; i<n; i++)
{
int m;
cin >> m;
string str;
int leftpa = 0;
for (int j=0; j<m; j++) // 读入P 编码，构造括号字符串
{
int p;
cin >> p;
for (int k=0; k<p-leftpa; k++)
str += '(';
str += ')';
leftpa = p;
}
stack<int> s;
for (string::iterator it=str.begin();it!=str.end(); it++)
{ // 构造M 编码
if (*it=='(') s.push(1);
else
{
int p = s.top(); s.pop();
cout << p << " ";
if (!s.empty()) s.top() += p;
}
}
cout << endl;
}
return 0;
}

### 2、queue

queue 模板类的定义在<queue>头文件中。stack 模板类很相似，queue 模板类也需要两个模板参数，一个是元素类型，一个容器类型，元素类型是必要的，容器类型是可选的，默认为deque 类型。

queue<int> q1;

queue<double> q2;

queue 的基本操作有：

### 3、priority_queue

<queue>头文件中，还定义了另一个非常有用的模板类priority_queue(优先队列）。优先队列与队列的差别在于优先队列不是按照入队的顺序出队，而是按照队列中元素的优先权顺序出队（默认为大者优先，也可以通过指定算子来指定自己的优先顺序）。priority_queue 模板类有三个模板参数，第一个是元素类型，第二个容器类型，第三个是比较算子。其中后两个都可以省略，默认容器为vector，默认算子为less，即小的往前排，大的往后排（出队时序列尾的元素出队）。

priority_queue<int> q1;

priority_queue< pair<int, int> > q2; // 注意在两个尖括号之间一定要留空格。

priority_queue<int, vector<int>, greater<int> > q3; // 定义小的先出队

priority_queue 的基本操作与queue 相同。

#include <iostream>
#include <queue>
using namespace std;
class T
{
public:
int x, y, z;
T(int a, int b, int c):x(a), y(b), z(c){}
};
bool operator < (const T &t1, const T &t2)
{
return t1.z < t2.z; // 按照z 的顺序来决定t1 和t2 的顺序
}
int main()
{
priority_queue<T> q;
q.push(T(4,4,3));
q.push(T(2,2,5));
q.push(T(1,5,4));
q.push(T(3,3,6));
while (!q.empty())
{
T t = q.top(); q.pop();
cout << t.x << " " << t.y << " " << t.z << endl;
}
return 0;
}
/*输出结果为(注意是按照z 的顺序从大到小出队的)：
3 3 6
2 2 5
1 5 4
4 4 3*/

//再看一个按照z 的顺序从小到大出队的例子：
#include <iostream>
#include <queue>
using namespace std;
class T
{
public:
int x, y, z;
T(int a, int b, int c):x(a), y(b), z(c)
{
}
};
bool operator > (const T &t1, const T &t2)
{
return t1.z > t2.z;
}
int main()
{
priority_queue<T, vector<T>, greater<T> > q;
q.push(T(4,4,3));
q.push(T(2,2,5));
q.push(T(1,5,4));
q.push(T(3,3,6));
while (!q.empty())
{
T t = q.top(); q.pop();
cout << t.x << " " << t.y << " " << t.z << endl;
}
return 0;
}

4 4 3

1 5 4

2 2 5

3 3 6

bool operator < (const T &t1, const T &t2){

return t1.z > t2.z; // 按照的顺序来决定t1 t2 的顺序

}

#include <iostream>
#include <queue>
using namespace std;
typedef pair<unsigned long int, int> node_type;
int main( int argc, char *argv[] )
{
unsigned long int result[1500];
priority_queue< node_type, vector<node_type>,
greater<node_type> > Q;
Q.push( make_pair(1, 3) );
for (int i=0; i<1500; i++)
{
node_type node = Q.top();
Q.pop();
switch(node.second)
{
case 3: Q.push( make_pair(node.first*2, 3) );
case 2: Q.push( make_pair(node.first*3, 2) );
case 1: Q.push( make_pair(node.first*5, 1) );
}
result[i] = node.first;
}
int n;
cin >> n;
while (n>0)
{
cout << result[n-1] << endl;
cin >> n;
}
return 1;
}

## ACM/ICPC 竞赛之STL–map

STL 的头文件<map>中定义了模板类map multimap，用有序二叉树来存贮类型为pair<const Key, T>的元素对序列。序列中的元素以const Key部分作为标识，map 中所有元素的Key 值都必须是唯一的，multimap 则允许有重复的Key 值。可以将map 看作是由Key 标识元素的元素集合，这类容器也被称为“关联容器”，可以通过一个Key 值来快速确定一个元素，因此非常适合于需要按照Key值查找元素的容器。map 模板类需要四个模板参数，第一个是键值类型，第二个是元素类型，第三个是比较算子，第四个是分配器类型。其中键值类型和元素类型是必要的。map 的基本操作有：

1、定义map 对象，例如：

map<string, int> m;

2、向map 中插入元素对，有多种方法，例如：

m[key] = value;

[key]操作是map 很有特色的操作，如果在map 中存在键值为key 的元素对，

m.insert( make_pair(key, value) );

3、查找元素对，例如：

int i = m[key];

end 操作）。

4、删除元素对，例如：

m.erase(key);删除与指定key 键值相匹配的元素对，并返回被删除的元素的个数。

m.erase(it);删除由迭代器it 所指定的元素对，并返回指向下一个元素对的迭代器。

#include<map>
#include<iostream>
using namespace std;
typedef map<int, string, less<int> > M_TYPE;
typedef M_TYPE::iterator M_IT;
typedef M_TYPE::const_iterator M_CIT;
int main()
{
M_TYPE MyTestMap;
MyTestMap[3] = "No.3";
MyTestMap[5] = "No.5";
MyTestMap[1] = "No.1";
MyTestMap[2] = "No.2";
MyTestMap[4] = "No.4";
M_IT it_stop = MyTestMap.find(2);
cout << "MyTestMap[2] = " << it_stop->second << endl;
it_stop->second = "No.2 After modification";
cout << "MyTestMap[2] = " << it_stop->second << endl;
cout << "Map contents : " << endl;
for(M_CIT it = MyTestMap.begin(); it != MyTestMap.end();it++)
{
cout << it->second << endl;
}
return 0;
}
/*程序执行的输出结果为：
MyTestMap[2] = No.2
MyTestMap[2] = No.2 After modification
Map contents :
No.1
No.2 After modification
No.3
No.4
No.5*/

#include <iostream>
#include <map>
using namespace std;
int main()
{
map<string, int> m;
m["one"] = 1;
m["two"] = 2;
// 几种不同的insert 调用方法
m.insert(make_pair("three", 3));
m.insert(map<string, int>::value_type("four", 4));
m.insert(pair<string, int>("five", 5));
string key;
while (cin>>key)
{
map<string, int>::iterator it = m.find(key);
if (it==m.end())
{
cout << "No such key!" << endl;
}
else
{
cout << key << " is " << it->second << endl;
cout << "Erased " << m.erase(key) << endl;
}
}
return 0;
}

# 第K小数 uva 10041 – Vito’s Family poj 2388 Who’s in the Middle

很容易理解题目的意思，就是求某个点到其他点的距离之和，而且要让这个和最小，很明显是求中位数了。

关于求中位数，一般的方法是我们先将整个数组进行排序，然后直接取出中位数，采用不同的排序方法可能有不同的时间复杂度，一般我们使用快排，时间复杂度为O(nlogn)，有没有更快的方法？ 答案是肯定的。

这里有一种时间复杂度为O(n)的算法，下面是此题的解题代码。

//uva 10041 - Vito's Family
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;

int a[40000];

int partition(int l, int r)
{
int x = a[r];
int i = l-1;
for (int j = l; j < r; j++)
{
if (x >= a[j])
{
i++;
swap(a[i], a[j]);
}
}
++i;
swap(a[i],a[r]);
return i;
}

int select(int l, int r, int k)
{
if (l >= r)
return a[l];
int p = partition(l, r);
if (k == p)
return a[k];
else if(k > p)
return select(p + 1, r, k);
else
return select(l, p - 1, k);
}

int main()
{
int t, n;
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
for (int i = 0; i < n; i++)
scanf("%d",&a[i]);
int x = select(0, n-1, n/2);
int s = 0;
for (int i = 0; i < n; i++)
{
s += abs(a[i] - x);
}
printf("%d\n",s);
}
return 0;
}


了解快排的人对int (int l, int r) 这个函数很熟悉，因为这是在快排中用到的，它的作用是对数组的某一段选一个分界点，使得该点左边的数都不大于该点的数，右边的点不小于该点的数，也就是说我们通过一次调用这个函数确定一个数的位置，快排是将该点两边分别进行递归操作，时间复杂度为O(nlogn)，而select只是对一边进行递归操作（有点像二分的递归形式），所以时间复杂度仅为O(n)。

其实还有时间复杂度更低的算法，划分树。。。   时间复杂度为log(n) 。。。。。   划分树的优点是可以对某个区间进行多次的查询，并不改变原序。

poj 2388

//poj 2388
#include <stdio.h>
#include <algorithm>
using namespace std;

const int maxn = 10005;

int a[maxn];

int partition(int l, int r)
{
int x = a[r];
int ol = l;
for (int i = l; i < r; i++)
{
if (a[i] < x)
{
swap(a[ol], a[i]);
ol++;
}
}
swap(a[r], a[ol]);
return ol;
}

int search(int l, int r, int k)
{
int pos = partition(l, r);
if (l == r)
return a[l];
if (k == pos)
return a[k];
else if (pos < k)
return search(pos+1, r, k);
else if (pos > k)
return search(l, pos-1, k);
}

int main()
{
int n;
while (scanf("%d", &n) != EOF)
{
for (int i = 0; i < n; i++)
scanf("%d",&a[i]);
printf("%d\n",search(0, n-1, n/2));
}
return 0;
}


# hdoj 1166 敌兵布阵

暴力超时，这道题可以用线段树做，因为更新的是单个节点，我们也可以用数组数组来做，我将两种方法的代码都给出

数组数组最适宜的用途就是区间求和和点的更新，但树状数组并不适用于区间的更新问题，也不是做不到，比较麻烦且难理解，有兴趣的可以看看这个http://blog.csdn.net/xindoo/article/details/8748410

//树状数组
#include<stdio.h>

int n,ans[50005],f[50005];

int lowbit(int n)
{
return n&(-n);
}

{
while(i <= n)
{
ans[i] += v;
i += lowbit(i);
}
}

int query(int n)
{
int s = 0;
while(n)
{
s += ans[n];
n -= lowbit(n);
}
return s;
}

int main()
{
int t;
scanf("%d",&t);
for(int j = 1;j <= t; j++)
{
scanf("%d",&n);
for(int l = 1; l <= n;l++)
{
scanf("%d",&f[l]);
f[l] += f[l-1];
}
for(int l = 1; l <= n; l++)
ans[l] = f[l]-f[l-lowbit(l)];
printf("Case %d:\n",j);
while(1)
{
char s[20];
int a,b;
scanf("%s",s);
if (s[0] == 'E') break;
scanf("%d%d",&a,&b);
if (s[0] == 'Q') printf("%d\n",query(b)-query(a-1));
}
}
return 0;
}


//线段树解法
#include <stdio.h>
#include <string.h>
#define maxn 50005

struct node
{
int l, r, m;
int sum;
}tree[maxn<<2];

int a[maxn];

void build(int l, int r, int o)
{
tree[o].l = l;
tree[o].r = r;
int m = (l+r)>>1;
tree[o].m = m;
if (l == r)
{
tree[o].sum = a[l];
return;
}
build(l, m, o<<1);
build(m+1, r, (o<<1)+1);
tree[o].sum = tree[o<<1].sum + tree[(o<<1)+1].sum;
}

void update(int l, int v, int o)
{
tree[o].sum += v;
if (tree[o].l == l && tree[o].r == l)
return;
if (l <= tree[o].m)
update(l, v, o<<1);
else
update(l, v, (o<<1)+1);
}

int query(int l, int r, int o)
{
if (tree[o].l == r && tree[o].r == r)
return tree[o].sum;
if (tree[o].m >= r)
return query(l, r, o<<1);
else if (tree[o].m <l)
return query(l, r, (o<<1)+1);
else
return query(l, tree[o].m, o<<1) + query(tree[o].m+1, r, (o<<1)+1);
}

int main()
{
int t, n;
scanf("%d",&t);
for (int j = 1; j <= t; j++)
{
scanf("%d",&n);
for (int i = 1; i <= n; i++)
scanf("%d",&a[i]);
build(1, n, 1);
printf("Case %d:\n",j);
while(1)
{
char s[20];
int l, r;
scanf("%s",s);
if (s[0] == 'E')
break;
scanf("%d%d",&l,&r);
if (s[0] == 'A')
update(l, r, 1);
else if (s[0] == 'S')
update(l, -r, 1);
if (s[0] == 'Q')
printf("%d\n",query(l, r, 1));
}
}
return 0;
}


# 用树状数组解决区间查询问题

本文扩写自郭神的《树状数组新应用》，在此表示膜拜。树状数组的学名貌似叫做Binary Index Tree，关于它的基本应用可参考Topcoder上的这篇Tutorial.

(1) 如果p<=q，总的结果会加上p*d (2) 如果p>q，总的结果会加上q*d

#include <cstdio>

const int MAXN = 1024;
int B[MAXN], C[MAXN];

#define LOWBIT(x) ((x)&(-(x)))

void bit_update(int *a, int p, int d)
{
for ( ; p && p < MAXN ; p += LOWBIT(p))
a[p] += d;
}

int bit_query(int *a, int p)
{
int s = 0;
for ( ; p ; p -= LOWBIT(p))
s += a[p];
return s;
}

void bit_update2(int *a, int p, int d)
{
for ( ; p ; p -= LOWBIT(p))
a[p] += d;
}

int bit_query2(int *a, int p)
{
int s = 0;
for ( ; p && p < MAXN ; p += LOWBIT(p))
s += a[p];
return s;
}

inline void _insert(int p, int d)
{
bit_update(B, p, p*d);
bit_update2(C, p-1, d);
}

inline int _query(int p)
{
return bit_query(B, p) + bit_query2(C, p) * p;
}

inline void insert_seg(int a, int b, int d)
{
_insert(a-1, -d);
_insert(b, d);
}

inline int query_seg(int a, int b)
{
return _query(b) - _query(a-1);
}

int main()
{
int com, a, b, c;
while (scanf("%d%d%d",&com,&a,&b) != EOF)
{
a += 2; b += 2;		//防止出现负数
if (com == 0)
{		//更新
scanf("%d",&c);
insert_seg(a, b, c);
}
else
{			//查询
printf("%d\n",query_seg(a,b));
}
}
return 0;
}


# poj 3468 A Simple Problem with Integers线段树区间修改

#include <stdio.h>
const int maxn = 100005;
typedef __int64 ll;                           //Hint  The sums may exceed the range of 32-bit integers.
int a[maxn];

struct node                                   //比较复杂的线段树都需要保存一个节点的多个信息，虽然
{                                             //可以使用多个数组来存储，但我个人不推荐这种做法
int l, r, m;
ll sum, mark;
}tree[maxn<<2];                               // << 这里使用位运算，位运算的效率要比* /运算的效率高
//推荐大家在乘除2或2的某次方的时候使用位运算，

void build(int l, int r, int o)               //建树比较好理解，确定每个节点的各项，然后递归创建左右子树
{
tree[o].l = l;
tree[o].r = r;
int m = (l+r)>>1;
tree[o].m = m;
tree[o].mark = 0;                         //mark的值一定要初始化为0，很重要
if (l == r)                               //递归边界
{
tree[o].sum = a[l];
return;
}
build(l, m, o<<1);
build(m+1, r, (o<<1)+1);
tree[o].sum = tree[o<<1].sum + tree[(o<<1)+1].sum;  //这里tree[(o<<1)+1] （o<<1） 我打了括号，以为位运算的优先级比+低
}                                                      //不注意很容易出问题的

void update(int l, int r, int v, int o)
{
if (tree[o].l == l && tree[o].r == r)
{
tree[o].mark += v;                              //在每次更新某段的时候我们还要我们标记这一段被加了v
return;
}
tree[o].sum += (ll)(r-l+1)*v;
if (tree[o].m >= r)                                //递归更新，无外乎三种情况
update(l, r, v, o<<1);
else if (l > tree[o].m)
update(l, r, v, (o<<1)+1);
else
{
update(l, tree[o].m, v, o<<1);
update(tree[o].m+1, r, v, (o<<1)+1);
}
}

ll query(int l, int r, int o)
{
if (tree[o].l == l && tree[o].r == r)                           //我们也使用递归的方式查询，这是递归边界
return tree[o].sum + tree[o].mark*(r-l+1);
if (tree[o].mark != 0)
{
tree[o<<1].mark += tree[o].mark;                            //在查询的时候我将节点的mark值传递给子节点
tree[(o<<1)+1].mark += tree[o].mark;
tree[o].sum += (ll)(tree[o].r -tree[o].l +1)*tree[o].mark;  //并更新sum的值
tree[o].mark = 0;
}
if (tree[o].m >= r)                                             //查询的三种情况
return query(l, r, o<<1);
else if (tree[o].m <l)
return query(l, r, (o<<1)+1);
else
return query(l, tree[o].m, o<<1) + query(tree[o].m+1, r, (o<<1)+1);
}

int main()
{
int n, q;
while (scanf("%d%d",&n,&q) != EOF)
{
for(int i = 1; i <= n; i++)
scanf("%d",&a[i]);
build(1, n, 1);
char com;
int l, r, v;
while (q--)
{
getchar();
scanf("%c",&com);
if (com == 'Q')
{
scanf("%d%d",&l, &r);
printf("%I64d\n",query(l,r,1));
}
else
{
scanf("%d%d%d",&l ,&r ,&v);
update(l, r, v, 1);
}
}
}
return 0;
}


# python 学习体会

这段时间，做ACM的状态特别不好，经人推荐，了解了一下python，发现python确实很强大，而且语法简洁清晰，感觉用起来很方便（虽然还不会）。

在看刘汝佳的白书的时候，在最后附录，他也推荐python，并不是因为可以使用python做比赛（据我所知，貌似只有codeforces上可以使用python），只是用他可以快速的生成测试数据、对拍器什么的，帮助我们完成比赛。

下面简单谈谈我目前对python的了解（我最近要准备省赛，python学学得搁置会了），因为目前只会c，就拿c来对比了。

python 支持一些c所不支持的类型，比如复数和大整数，而且省去了变量的定义，也就是说我们可以随时使用一个变量，这无疑减少了代码量，实现相同的功能，python的代码量仅是c/c++的五分之一。这当然有很多好处，提高开发效率、减少代码维护成本…………

待续。。。。。。。。。

# Python3.x和Python2.x的区别

1.性能

Py3.0运行 pystone benchmark的速度比Py2.5慢30%。Guido认为Py3.0有极大的优化空间，在字符串和整形操作上可

Py3.1性能比Py2.5慢15%，还有很大的提升空间。
2.编码
Py3.X源码文件默认使用utf-8编码，这就使得以下代码是合法的：

>>> 中国 = ‘china’

>>>print(中国)

china
3. 语法

1）去除了<>，全部改用!=

2）去除“，全部改用repr()

3）关键词加入as 和with，还有True,False,None

4）整型除法返回浮点数，要得到整型结果，请使用//

5）加入nonlocal语句。使用noclocal x可以直接指派外围（非全局）变量

6）去除print语句，加入print()函数实现相同的功能。同样的还有 exec语句，已经改为exec()函数

例如：

2.X: print “The answer is”, 2*2

2.X: print x,                              # 使用逗号结尾禁止换行

3.X: print(x, end=” “)                     # 使用空格代替换行

2.X: print                                 # 输出新行

3.X: print()                               # 输出新行

2.X: print >>sys.stderr, “fatal error”

3.X: print(“fatal error”, file=sys.stderr)

2.X: print (x, y)                          # 输出repr((x, y))

3.X: print((x, y))                         # 不同于print(x, y)!

7）改变了顺序操作符的行为，例如x<y，当x和y类型不匹配时抛出TypeError而不是返回随即的 bool值

8）输入函数改变了，删除了raw_input，用input代替：

2.X:guess = int(raw_input(‘Enter an integer : ‘)) # 读取键盘输入的方法

3.X:guess = int(input(‘Enter an integer : ‘))

9）去除元组参数解包。不能def(a, (b, c)):pass这样定义函数了

10）新式的8进制字变量，相应地修改了oct()函数。

2.X的方式如下：

>>> 0666

438

>>> oct(438)

‘0666’

3.X这样：

>>> 0666

SyntaxError: invalid token (<pyshell#63>, line 1)

>>> 0o666

438

>>> oct(438)

‘0o666’

11）增加了 2进制字面量和bin()函数

>>> bin(438)

‘0b110110110’

>>> _438 = ‘0b110110110’

>>> _438

‘0b110110110’

12）扩展的可迭代解包。在Py3.X 里，a, b, *rest = seq和 *rest, a = seq都是合法的，只要求两点：rest是list

13）新的super()，可以不再给super()传参数，

>>> class C(object):

def __init__(self, a):

print(‘C’, a)

>>> class D(C):

def __init(self, a):

super().__init__(a) # 无参数调用super()

>>> D(8)

C 8

<__main__.D object at 0x00D7ED90>

14）新的metaclass语法：

class Foo(*bases, **kwds):

pass

15）支持class decorator。用法与函数decorator一样：

>>> def foo(cls_a):

def print_func(self):

print(‘Hello, world!’)

cls_a.print = print_func

return cls_a

>>> @foo

class C(object):

pass

>>> C().print()

Hello, world!

class decorator可以用来玩玩狸猫换太子的大把戏。更多请参阅PEP 3129
4. 字符串和字节串

1）现在字符串只有str一种类型，但它跟2.x版本的unicode几乎一样。

2）关于字节串，请参阅“数据类型”的第2条目
5.数据类型

1）Py3.X去除了long类型，现在只有一种整型——int，但它的行为就像2.X版本的long

2）新增了bytes类型，对应于2.X版本的八位串，定义一个bytes字面量的方法如下：

>>> b = b’china’

>>> type(b)

<type ‘bytes’>

str对象和bytes对象可以使用.encode() (str -> bytes) or .decode() (bytes -> str)方法相互转化。

>>> s = b.decode()

>>> s

‘china’

>>> b1 = s.encode()

>>> b1

b’china’

3）dict的.keys()、.items 和.values()方法返回迭代器，而之前的iterkeys()等函数都被废弃。同时去掉的还有

dict.has_key()，用 in替代它吧
6.面向对象
1）引入抽象基类（Abstraact Base Classes，ABCs）。

2）容器类和迭代器类被ABCs化，所以cellections模块里的类型比Py2.5多了很多。

>>> import collections

>>> print(‘\n’.join(dir(collections)))

Callable

Container

Hashable

ItemsView

Iterable

Iterator

KeysView

Mapping

MappingView

MutableMapping

MutableSequence

MutableSet

NamedTuple

Sequence

Set

Sized

ValuesView

__all__

__builtins__

__doc__

__file__

__name__

_abcoll

_itemgetter

_sys

defaultdict

deque

3）迭代器的next()方法改名为__next__()，并增加内置函数next()，用以调用迭代器的__next__()方法

4）增加了@abstractmethod和 @abstractproperty两个 decorator，编写抽象方法（属性）更加方便。
7.异常

1）所以异常都从 BaseException继承，并删除了StardardError

2）去除了异常类的序列行为和.message属性

3）用 raise Exception(args)代替 raise Exception, args语法

4）捕获异常的语法改变，引入了as关键字来标识异常实例，在Py2.5中：

>>> try:

…    raise NotImplementedError(‘Error’)

… except NotImplementedError, error:

…    print error.message

…

Error

>>> try:

raise NotImplementedError(‘Error’)

except NotImplementedError as error: #注意这个 as

print(str(error))

Error

5）异常链，因为__context__在3.0a1版本中没有实现
8.模块变动

1）移除了cPickle模块，可以使用pickle模块代替。最终我们将会有一个透明高效的模块。

2）移除了imageop模块

3）移除了 audiodev, Bastion, bsddb185, exceptions, linuxaudiodev, md5, MimeWriter, mimify, popen2,

rexec, sets, sha, stringold, strop, sunaudiodev, timing和xmllib模块

4）移除了bsddb模块(单独发布，可以从http://www.jcea.es/programacion/pybsddb.htm获取)

5）移除了new模块

6）os.tmpnam()和os.tmpfile()函数被移动到tmpfile模块下

7）tokenize模块现在使用bytes工作。主要的入口点不再是generate_tokens，而是 tokenize.tokenize()
9.其它
1）xrange() 改名为range()，要想使用range()获得一个list，必须显式调用：

>>> list(range(10))

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

2）bytes对象不能hash，也不支持 b.lower()、b.strip()和b.split()方法，但对于后两者可以使用 b.strip(b’

\n\t\r \f’)和b.split(b’ ‘)来达到相同目的

()函数都被去除了

4）string.letters和相关的.lowercase和.uppercase被去除，请改用string.ascii_letters 等

5）如果x < y的不能比较，抛出TypeError异常。2.x版本是返回伪随机布尔值的

6）__getslice__系列成员被废弃。a[i:j]根据上下文转换为a.__getitem__(slice(I, j))或 __setitem__和

__delitem__调用

7）file类被废弃，在Py2.5中：

>>> file

<type ‘file’>

>>> file

Traceback (most recent call last):

File “<pyshell#120>”, line 1, in <module>

file

NameError: name ‘file’ is not defined

# interviewstreet pair

今天突然想起interviewstreet这个网站，这个网站和其他oj有些不同，每题只要通过一组测试样例就会获得一定的分数，然后按分数的高低进行排名，刚刚看到一题。

题意大概是输入n和k，然后是n个数每个数在10^9范围内，计算出有多少对a[i]和a[j]使得a[i]+k = a[j]。

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
int N, K;
cin >> N >> K;
long long *key = new long long[N];

for (int i = 0; i < N; i++)
{
cin >> key[i];
}
sort (key, key+N);                     //对数组进行排序
int k = 0;
for (int i = 0; i < N; i++)
{
int begin = i+1;
int end = N-1;
int value = key[i] + K;
while(begin <= end)                //用二分查找有没有满足条件的
{
int mid = (begin+end)/2;
if (key[mid] < value)
begin = mid + 1;
else if (key[mid] > value)
end = mid - 1;
else
{
k++;
break;
}
}
}
cout << k << endl;
}

# ACM博弈知识汇总

，别看这游戏极其简单，却蕴含着深刻的数学原理。下面我们来分析一下要如何才能够

（一）巴什博奕（Bash Game）：只有一堆n个物品，两个人轮流从这堆物品中取物，规

显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，

n=（m+1）r+s，（r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后取者拿走

k（≤m)个，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的

这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报一个，最多报十

（二）威佐夫博奕（Wythoff Game）：有两堆各若干个物品，两个人轮流从某一堆或同

这种情况下是颇为复杂的。我们用（ak，bk）（ak ≤ bk ,k=0，1，2，…,n)表示

10）、（8，13）、（9，15）、（11，18）、（12，20）。

可以看出,a0=b0=0,ak是未在前面出现过的最小自然数,而 bk= ak + k，奇异局势有

1。任何自然数都包含在一个且仅有一个奇异局势中。

由于ak是未在前面出现过的最小自然数，所以有ak > ak-1 ，而 bk= ak + k > ak

-1 + k-1 = bk-1 > ak-1 。所以性质1。成立。

2。任意操作都可将奇异局势变为非奇异局势。

事实上，若只改变奇异局势（ak，bk）的某一个分量，那么另一个分量不可能在其

3。采用适当的方法，可以将非奇异局势变为奇异局势。

假设面对的局势是（a,b），若 b = a，则同时从两堆中取走 a 个物体，就变为了

,从第二堆里面拿走 b – bj 即可；第二种，a=bj （j < k）,从第二堆里面拿走 b – a

j 即可。

从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜

；反之，则后拿者取胜。

那么任给一个局势（a，b），怎样判断它是不是奇异局势呢？我们有如下公式：

ak =[k（1+√5）/2]，bk= ak + k  （k=0，1，2，…,n 方括号表示取整函数)

j（1+√5）/2]，那么a = aj，bj = aj + j，若不等于，那么a = aj+1，bj+1 = aj+1

+ j + 1，若都不是，那么就不是奇异局势。然后再按照上述法则进行，一定会遇到奇异

（三）尼姆博奕（Nimm Game）：有三堆各若干个物品，两个人轮流从某一堆取任意多的

这种情况最有意思，它与二进制有密切关系，我们用（a，b，c）表示某种局势，首

（0，n，n），只要与对手拿走一样多的物品，最后都将导致（0，0，0）。仔细分析一

计算机算法里面有一种叫做按位模2加，也叫做异或的运算，我们用符号（+）表示

1 =二进制01

2 =二进制10

3 =二进制11 （+）

———————

0 =二进制00 （注意不进位）

对于奇异局势（0，n，n）也一样，结果也是0。

任何奇异局势（a，b，c）都有a（+）b（+）c =0。

< c,我们只要将 c 变为 a（+）b,即可,因为有如下的运算结果: a（+）b（+）(a（+）

b)=(a（+）a)（+）(b（+）b)=0（+）0=0。要将c 变为a（+）b，只要从 c中减去 c-（

a（+）b）即可。

例1。（14，21，39），14（+）21=27，39-27=12，所以从39中拿走12个物体即可达

例2。（55，81，121），55（+）81=102，121-102=19，所以从121中拿走19个物品

例3。（29，45，58），29（+）45=48，58-48=10，从58中拿走10个，变为（29，4

5，48）。

例4。我们来实际进行一盘比赛看看：

甲:(7,8,9)->(1,8,9)奇异局势

乙:(1,8,9)->(1,8,4)

甲:(1,8,4)->(1,5,4)奇异局势

乙:(1,5,4)->(1,4,4)

甲:(1,4,4)->(0,4,4)奇异局势

乙:(0,4,4)->(0,4,2)

甲:(0.4,2)->(0,2,2)奇异局势

乙:(0,2,2)->(0,2,1)

甲:(0,2,1)->(0,1,1)奇异局势

乙:(0,1,1)->(0,1,0)

甲:(0,1,0)->(0,0,0)奇异局势

甲胜。

[定理1]：对于任何一个S态，总能从一堆火柴中取出若干个使之成为T态。

若有n堆火柴，每堆火柴有A(i)根火柴数，那么既然现在处于S态，

c = A(1) xor A(2) xor … xor A(n) > 0;

把c表示成二进制，记它的二进制数的最高位为第p位，则必然存在一个A(t),它二进制的第p位也是1。（否则，若所有的A(i)的第p位都是0，这与c的第p位就也为0矛盾）。

那么我们把x = A(t) xor c,则得到x < A(t).这是因为既然A(t)的第p位与c的第p位同为1,那么x的第p位变为0,而高于p的位并没有改变。所以x < A(t).而

A(1) xor A(2) xor … xor x xor … xor A(n)

= A(1) xor A(2) xor … xor A(t) xor c xor … xor A(n)

= A(1) xor A(2) xor… xor A(n) xor A(1) xor A(2) xor … xor A(n)

= 0

[定理2]：T态，取任何一堆的若干根，都将成为S态。

若

c = A(1) xor A(2) xor … xor A(i) xor … xor A(n) = 0；

c’ = A(1) xor A(2) xor … xor A(i’) xor c xor … xor A(n) = 0;

则有

c xor c’ = A(1) xor A(2) xor … xor A(i) xor … xor A(n) xor A(1) xor A(2) xor … xor A(i’) xor c xor … xor A(n) = A(i) xor A(i’) =0

进而推出A(i) = A(i’)，这与已知矛盾。所以命题得证。

[定理 3]：S态，只要方法正确，必赢。

最终胜利即由S态转变为T态，任何一个S态，只要把它变为T态，（由定理1，可以把它变成T态。）对方只能把T态转变为S态(定理2)。这样，所有S态向T态的转变都可以有己方控制，对方只能被动地实现由T态转变为S态。故S态必赢。

[定理4]：T态，只要对方法正确，必败。

由定理3易得。

[定理5]：S0态，即仅有奇数个孤单堆，必败。T0态必胜。

S0态，其实就是每次只能取一根。每次第奇数根都由己取，第偶数根都由对

[定理6]：S1态，只要方法正确，必胜。

[定理7]：S2态不可转一次变为T0态。

[定理8]：S2态可一次转变为T2态。

[定理9]：T2态，只能转变为S2态或S1态。

[定理10]：S2态，只要方法正确，必胜.

1）  S2态，就把它变为T2态。（由定理8）

2）  对方只能T2转变成S2态或S1态（定理9）

若转变为S2,  转向1）

若转变为S1,  这己必胜。（定理5）

[定理11]：T2态必输。

必胜态：    S2,S1,T0.

S2->T2->S2->T2->  ……  ->T2->S1->T0->S0->T0->……->S0->T0(全0)

S2->T2->S2->T2->  ……  ->T2->S1->S0->T0->S0->……->S0->T0(全0)

T0（第一题做法）。哪一方控制了S1态，他即可以有办法使自己得到最后一根（转变为

T0）,也可以使对方得到最后一根（转变为S0）。

所以，抢夺S1是制胜的关键！

为此，始终把T2态让给对方，将使对方处于被动状态，他早晚将把状态变为S1.

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

SG值：一个点的SG值就是一个不等于它的后继点的SG的且大于等于零的最小整数。

1847（求SG值）

http://hi.baidu.com/netnode/blog/item/30932c2edc7384514fc226ea.html

ZZ博弈

1536题推荐做做这题，这题前面提醒大家是一个求SG值的题目，题目前面是对异或运算运用在组合博弈问题中的很好的解释。当然题目本身是有所不同的。因为在这里面对取法有所要求。那么这样就回归到了解决博弈问题的王道算法——求SG值上。

有关运用求SG值的博弈题目有： 1850（也可基于奇异状态异或）

1848（中和的大斐波那契数列的典型求SG值题）

1517（个人认为有点猥琐的题目。。。。在此题上困扰很久。当然搞出来很开心。小子是用比较规矩的求SG值的方法求出来的，但是论坛有人对其推出来了规律，这里佩服一下，大家可以学习一下）

1079（更猥琐的题目，对新手要求较高，因为按传统方法需要比较细致的模拟加对边角状态的考虑，同样有人推出来了公式）

这里小子告诉大家。博弈很强大。学习要耐心~谢谢

Current System Time : 2008-12-11 19:16:03

ACM课作业：

1001 Brave Game

1002 Good Luck in CET-4 Everybody!

1003 Fibonacci again and again

1004 Rabbit and Grass

1005 Being a Good Boy in Spring Festival

1006 Public Sale

1007 悼念512汶川大地震遇难同胞——选拔志愿者

1008 kiki’s game

1009 Calendar Game

1010 A Multiplication Game

1011 Digital Deletions

1012 S-Nim

1536的参考代码

Copy code

//博弈-基于求SG值

//Accepted 1536 578MS 416K 904 B

#include”iostream”

using namespace std;

int f[101],sg[10001],k;

int mex(int b)

{

int a[101]={0},i;

for(i=0;i<k;i++)

{

if(b-f<0)//b-f后继点

break;

if(sg[b-f]==-1)

{

sg[b-f]=mex(b-f);

}

a[sg[b-f]]=1;

}

for(i=0;i<k;i++)

if(!a)

{

return i;

}

}

int main()

{

while(cin >> k,k)

{

for(i=0;i<k;i++)

{

cin >> f;

}

memset(sg,-1,sizeof(sg));

for(i=0;i<k;i++)

for(j=i+1;j<k;j++)

if(f>f[j])

{

f+=f[j];

f[j]=f-f[j];

f-=f[j];

}

sg[0]=0;

cin >> t;

while(t–)

{

cin >> n;

s=0;

while(n–)

{

}

if(s==0)

cout << “L”;

else

cout << “W”;

}

cout << endl;

}

return 0;

}

1517参考代码

Copy code

//博弈-基于求SG值

//Accepted 1517 234MS 0K 837 B

#include”iostream”

using namespace std;

int main()

{

__int64 a[7000]={1},min,n;

int p[10],sg[7000],i,j,k;

for(i=2;i<10;p=0,i++);

for(i=1;i<7000;i++)

{

for(j=2,min=-1;j<10;j++)

if(min==-1||a[p[j]]*j<a[p[min]]*min)

min=j;

a=a[p[min]]*min;

min=a[p[min]]*min;

if(a>=5000000000)

break;

for(j=2;j<10;j++)

if(a[p[j]]*j==min)

p[j]++;

}//从小到大求出所有乘积

while(scanf(“%I64d”,&n)!=EOF)

{

for(i=0;i<7000;i++)

{

sg=0;

if(a>=n)

break;

}

for(j=i-1;a[j]*9>=n&&j>=0;j–)

sg[j]=1;

while(j>=0)

{

for(k=j+1;k<i&&a[j]*9>=a[k];k++)

if(a[k]%a[j]==0&&sg[k]==0)

{

sg[j]=1;

break;

}

j–;

}

puts(sg[0]?”Stan wins.”:”Ollie wins.”);

}

return 0;

}

1907参考代码

#include”iostream”

using namespace std;

int main()

{

int temp,t,n,s,x,i;

cin >> t;

while(t–)

{

cin >> n;

for(i=s=temp=0;i<n;i++)

{

cin >> x;

if(x>1)    temp=1;

s^=x;

}

if((s&&temp)||(!s&&!temp))

cout << “John” << endl;

else

cout << “Brother” << endl;

}

return 0;

}

# x & (x – 1)==0

方法之一是判断x & (x – 1)==0。若为True，则x是2的N次方；若为False，则x不是2的N次方。

有人质疑，他证明了“2的n次方一定符合这个条件”， 却并没有证明“符合这个条件的一定是2的n次方”呀！更没有证明“不符合条件的一定不是2的n次方”呀。

现在，从两个方面来证明这个方法的正确性

证明之前，先给出一些定义

&运算的定义：A & B 表示将A和B转化为二进制，然后按照对位&运算。

例如：17 & 9

100012　　=1710

&　    1012　　 =910

————————

000012　　 =110

而对位&运算的定义如下：

1 & 1=1　　；　　1 & 0=0　　；　　0 & 1=0　　；　　0 & 0=0

对位&运算还有如下性质：

A & 1=A　　；　　A & 0=0　　；　　A & A=A　　；　　A & B=B & A　　此时：A，B=0或1

定义：

X=x1x2……xn-1xn，其中xi=1或0，1≤i≤n，n>0。显然X>0（当X≤0，没有讨论的意义）

给定正整数X，X是2的N次方的充要条件是X转化成二进制后，有且只能有一个1，其余的都是0

也就是说，若X是2的N次方，则x1=1，x2=……=xn-1=xn=0

若X不是2的N次方，则至少存在一个j，xj=1，1<j≤n

先证明“2的N次方符合X & (X – 1)==0条件”

当X=1时，1 & 0 =0，满足条件

当X>1时，且X是2的N次方

如定义：X=100……0　　（n-1个0，n>1）

X-1=11……1　　（n-1个1，n>1）

则X & X-1是

100……02　　=X10

&　   　11……12　　=X-110

————————

00……02　　=010

满足条件

再证明“不是2的N次方不符合X & (X – 1)==0条件”

分两种情况，

1、X是奇数，则X=x1x2……xn-1xn，x1=xn=1，故X=1x1x2……xn-11

则X-1=1x2……xn-10

则X & X-1是

1x2x3……xn-112　　=X10

&　    1x2x3……xn-102　　=X-110

————————————

1x2x3……xn-102　　 ≠010

不满足X & (X – 1)==0的条件

2、X是偶数，则X=x1x2……xn-1xn，x1=1，xn=0

由于X不是2的N次方，因此x1，x2……xn-1中至少有两个为1。设xj是最右边的1

则X=1x2……xj-1xj0……0=1x2……xj-110……0 　　1<j<n，最右边有n-j个0

则X-1=1x2……xj-101……1　　　　　　　　　　　1<j<n，最右边有n-j个1

则X & X-1

1x2……xj-110……02　　=X10

&　    1x2……xj-101……12　　=X-110

————————————–

1x2……xj-100……02　　 ≠010

不满足X & (X – 1)==0的条件

综上所述，当X不是2的N次方的时候，是不满足X & (X – 1)==0的条件的

因此，当X是2的N次方的时候X & (X – 1)==0成立，当X不是2的N次方的时候X & (X – 1)==0不成立。

故判断X（X>0）是否是2的N次方的方法，判断X & (X – 1)==0是否成立，是可行的。

# 算法的强大——快速计算一个正二进制整数中包含多少个1

原题：一个正整数，转成二进制后，这个二进制数包含多少个1？

这个问题在网上看过多次，几番思考，也没有什么好的办法。采用最基本的办法，逐位判断，是1的统计加1，最后将统计数返回。

以下是这个思路的VB2008代码，不失一般性，将正整数的范围控制在（1~231-1）

Private Function GetCount1OfValue(ByVal Value As
Integer
As Integer
Dim i As
Integer
, Count As Integer =
0

For i
= 0
To 30
If (Value And 2
^ i) = 2 ^ i
Then Count += 1
Next
Return Count
End Function

但是近日，在网上发现一个很巧妙的算法，能够快速实现上述的计算功能。代码贴于下方

Private Function GetCount1OfValue(ByVal Value As
Integer
As Integer

Dim Count As
Integer
= 0

Do While Value
> 0

Value = Value And (Value
– 1)

Count +=1

Loop

Return Count

End Function

这段代码的精髓就是在这一句：Value = Value And (Value – 1)

曾经用过类似语句的在我的博客“判断是否是2的N次方——证明x &
(x – 1)==0的正确性

那么这句语句到底起到什么作用呢？看下面的分析

假设Value=X1X2……Xn-1Xn，其中Xi(1≤i≤n)为1或0

不妨设Xi是最右边的1，那么Value就可以写成如下的形式

Value=X1X2……Xi-1Xi0……0，其中(1≤i≤n)，Xi后面有n-i个0

因为Xi=1，所以Value=X1X2……Xi-110……0，其中(1≤i≤n)，1后面有n-i个0

则Value-1=X1X2……Xi-101……1，其中(1≤i≤n)，0后面有n-i个1

则Value And (Value-1)=X1X2……Xi-100……0，其中(1≤i≤n)，Xi-1后面有n-i+1个0

因此，Value And (Value-1)的效果把最右边的1变成0

在上面的代码中，每把最右边的1变成0，则统计数加1，直到所有的1变成0为止。

这两个算法，第一个算法的循环次数是固定的，是31次，无论数值是多少（必须在范围之内）。而第二个算法和Value中的1的个数有关，循环的次数就是1的个数，可见该算法之妙。

# uva 11991 – Easy Problem from Rujia Liu?

#include <cstdio>
#include <map>
#include <vector>

using namespace std;

int main()
{
map<int,vector<int> > mm;            //我们这里使用了STL里的map和vector
int n, m, k, v, i, a;
while (scanf("%d%d",&n,&m) != EOF)
{
mm.clear();
for (i = 1;i <= n;i++)
{
scanf("%d",&a);
mm[a].push_back(i);
}
while (m--)
{
scanf("%d%d",&k,&v);
if(mm[v].size() < k)
printf("0\n");
else
printf("%d\n",mm[v][k-1]);
}
}
return 0;
}


# 基础数据结构

## 例题

 例题1 UVa11995    AC I Can Guess the Data Structure! ADT  题解 例题2 UVa11991    AC Easy Problem from Rujia Liu 排序或者善用STL  题解 例题3 LA3135      AC Argus 优先队列；模拟    题解 例题4 UVa11997   AC K Smallest Sums 优先队列；有序表合并 题解 例题5 LA3644      AC X-Plosives 并查集                        题解 例题6 LA3027     AC Corporative Network 加权并查集                 题解

## 习题

 UVa11988      AC Broken Keyboard (a.k.a. Beiju Text) 模拟；链表               题解 UVa11645 Hoax or what 最大-最小堆或者STL的set LA4487 Exclusive-OR 加权并查集 UVa11987 Almost Union-Find 并查集；需要一点技巧 LA5908 Tracking RFIDs 规模不大，不用高级数据结构 LA3977 Summits 用数据结构加速算法 LA3634 The SetStack Computer 模拟；数据结构

# 区间信息维护

## 例题

 例题7 LA4329      AC Ping pong Fenwick树；类似逆序对  题解 例题8 UVa11235  AC Frequent Values RMQ         题解 例题9 LA3938      AC Ray, pass me the dishes 线段树；区间查询  题解 例题10 UVa11992  AC Fast Matrix Operations 线段树；区间修改；懒标记传递   题解

## 习题

 LA2191 Potentiometers      AC Fenwick树                   题解 LA5902 Movie collection    AC Fenwick树                   题解 UVa12299 RMQ with shifts     AC 线段树；单点修改，区间查询  题解 LA4108 Skyline 线段树 UVa11525 Permutations 递推；线段树（或二分+Fenwick树） LA4730 Kingdom 并查集；线段树 LA5694 Adding New Machine 线段树；组合计数 LA5698 Draw a Mess 线段树可以做，但并查集更好 LA4013 A Sequence of Numbers 转化为区间问题；预处理 LA5915 Flights

# 字符串算法

## 例题

 例题11 LA3942 Remember the Word 用Trie加速动态规划 例题12 UVa11732 strcmp() Anyone? Trie的性质 例题13 LA3026 Period KMP算法的失配函数 例题14 LA4670 Dominating Patterns AC自动机 例题15 UVa11468 Substring AC自动机上的算法 例题16 UVa11019 Matrix Matcher 二维匹配；AC自动机 例题17 UVa11107 Life Forms 后缀数组+height数组 例题18 LA4513 Stammering Aliens LCP；hash函数

## 习题

 UVa11488 Hyper Prefix Sets Trie的应用 LA5913 Dictionary Size 前缀；后缀；字符串集合 LA3703 Billing Tables Trie的应用 LA2755 Hidden Password 求字符串的最小表示 LA3907 Puzzle 给s个禁止子串，求不含它们的最长串 LA4126 Password Suspects 字符串的动态规划 UVa10829 L-Gap Substrings 后缀数组 LA3490 Generator 自动机；数学期望；数学推导 LA4769 Fuzzy Google Suggest 模糊查找 LA4975 Casting Spells 有难度；需要配合其他数据结构 LA5766 GRE Words 用串算法加速动态规划 LA4619 Accountant notes AC自动机的应用。有难度

# 排序二叉树

## 例题

 例题19 UVa11020 Efficient Solutions 维护点集；单调性 例题20 LA5031 Graph and Queries 名次树；并查集；时光倒流 例题21 UVa11922 Permutation Transformer 伸展树；和分裂合并的序列 例题22 UVa11996 Jewel Magic 字符串；Hash函数；伸展树

## 习题

 LA4847 Binary Search Tree 和BST有关的计数问题 LA5705 Very Boring Homework BST快速模拟；递归。注意栈溢出 LA3525 Wild West 扫描法；维护点集；单调性（或线段树） LA3961 Robotic Sorting 伸展树 LA4976 Defense Line 维护点集；单调性 UVa12419 Heap Manager