ACM竞赛常用STL(二)之STL–algorithm



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

下面列举出<algorithm>中的模板函数:

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

如果详细叙述每一个模板函数的使用,足够写一本书的了。还是来看几个简单

的示例程序吧。

示例程序之一,for_each 遍历容器:

#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

示例程序之二,min_element/max_element,找出容器中的最小/最大值:

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

示例程序之三,sort 对容器进行排序:

#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

示例程序之四,copy 在容器间复制元素:

#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

容器(container):

迭代器(iterator): 指针

内部实现: 数组 // 就是没有固定大小的数组,vector 直接翻译是向量vector // T 就是数据类型,Alloc 是关于内存的一个什么东西,一般是使用默认参数。

支持操作:

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;
}

 类似:双端队列,两头都支持进出

支持push_front()和pop_front()

是的精简版:) //栈,只支持从末尾进出
支持push(), pop(), top()
是的精简版 //单端队列,就是我们平时所说的队列,一头进,另一头出
支持push(), pop(), front(), back()
内部实现: 双向链表 //作用和vector 差不多,但内部是用链表实现
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
//不支持[ ]操作!
内部实现: 红黑树 //Red-Black Tree,一种平衡的二叉排序树
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
允许重复元素的
的用法及Compare 函数示例:
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;
…
}
内部实现: pair 组成的红黑树 //map 中文意思:映射!!
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 可以是任何类型的!允许重复元素, 没有[]运算符
内部实现: 堆 //优先队列,听RoBa 讲得,似乎知道原理了,但不明白干什么用的
priority_queue
支持操作:
push() O(n)
pop() O(n)
top() O(1)
See also: push_heap(), pop_heap() … in
用法举例:
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);
区间[first,last)
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);//部分排序
将前(middle-first)个元素放在[first,middle)中,其余元素位置不定
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);
在[first,last)中查找value,如果找到返回Ture,否则返回False
二分检索,复杂度O(log(last-first))
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 中专门用于排列的函数(可以处理存在重复数据集的排列问题)

头文件:#include <algorithm>

using namespace std;

调用: next_permutation(start, end);

注意:函数要求输入的是一个升序排列的序列的头指针和尾指针.

用法:

 

// 数组
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 需要两个参数,分别为元素对的首元素和尾元素。

在题1067–Ugly Numbers 中,就可以用pair 来表示推演树上的结点,用first 表示结点的值,用second 表示结点是由父结点乘以哪一个因子得到的。

#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 向量对象的方法示例:38

vector<int> s;

定义一个空的vector 对象,存储的是int 类型的元素。

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(迭代器)做一点简单的介绍。

简单地说,STL 中有以下几类iterator(迭代器)

输入iterator(迭代器),在容器的连续区间内向前移动,可以读取容器内任意值;输出iterator(迭代器),把值写进它所指向的容器中;前向iterator(迭代器),读取队列中的值,并可以向前移动到下一位置(++p,p++);双向iterator(迭代器),读取队列中的值,并可以向前向后遍历容器;随机访问iterator(迭代器), 可以直接以下标方式对容器进行访问,vector iterator(迭代器)就是这种iterator(迭代器);流iterator(迭代器),可以直接输出、输入流中的值;每种STL 容器都有自己的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;
}

这段代码中的copy 就是STL 中定义的一个模板函数,copy(s.begin(),s.end(), ostream_iterator<int>(cout, ” “));的意思是将由s.begin()s.end()(不含s.end())所指定的序列复制到标准输出流cout 中,用” “作为每个元素的间隔。也就是说,这句话的作用其实就是将表中的所有内容依次输出。iterator(迭代器)STL 容器和算法之间的“胶合剂”,几乎所有的STL 算法都是通过容器的iterator(迭代器)来访问容器内容的。只有通过有效地运用iterator(迭代器),才能够有效地运用STL 强大的算法功能。

ACM/ICPC 竞赛之STL–string

字符串是程序中经常要表达和处理的数据,我们通常是采用字符数组或字符指针来表示字符串。STL 为我们提供了另一种使用起来更为便捷的字符串的表达方式:stringstring 类的定义在头文件<string>中。string 类其实可以看作是一个字符的vectorvector 上的各种操作都可以适用于string,另外,string 类对象还支持字符串的拼合、转换等操作。下面先来看一个简单的例子:

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

再以题1064–Parencoding 为例,看一段用string 作为容器,实现由P

代码还原括号字符串的示例代码片段:

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 的实现细节,而是来了解一些他们的基本使用。

1stack

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

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

素类型是必要的,在不指定容器类型时,默认的容器类型为deque

定义stack 对象的示例代码如下:

stack<int> s1;

stack<string> s2;

stack 的基本操作有:

入栈,如例:s.push(x);

出栈,如例:s.pop();注意,出栈操作只是删除栈顶元素,并不返回该元素。

访问栈顶,如例:s.top()

判断栈空,如例:s.empty(),当栈空时,返回true

访问栈中的元素个数,如例:s.size()

下面是用string stack 写的解题1064–Parencoding 的程序。

#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;
}

2queue

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

定义queue 对象的示例代码如下:

queue<int> q1;

queue<double> q2;

queue 的基本操作有:

入队,如例:q.push(x); 接到队列的末端。

出队,如例:q.pop(); 弹出队列的第一个元素,注意,并不会返回被弹出元素的值。

访问队首元素,如例:q.front(),即最早被压入队列的元素。

访问队尾元素,如例:q.back(),即最后被压入队列的元素。

判断队列空,如例:q.empty(),当队列空时,返回true

访问队列中的元素个数,如例:q.size()

3priority_queue

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

定义priority_queue 对象的示例代码如下:

priority_queue<int> q1;

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

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

priority_queue 的基本操作与queue 相同。

初学者在使用priority_queue 时,最困难的可能就是如何定义比较算子了。如果是基本数据类型,或已定义了比较运算符的类,可以直接用STL less算子和greater 算子——默认为使用less 算子,即小的往前排,大的先出队。如果要定义自己的比较算子,方法有多种,这里介绍其中的一种:重载比较运算符。优先队列试图将两个元素代入比较运算符(less 算子,调用x<y,对greater 算子,调用x>y),若结果为真,则排在前面,将先于出队,反之,则将排在前面,将先出队。

看下面这个简单的示例:

#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 的顺序

}

则第一个例子的程序会得到和第二个例子的程序相同的输出结果。

再回顾一下用优先队列实现的题1067–Ugly Numbers 的代码:

#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 的元素对,

则返回该元素对的值域部分,否则将会创建一个键值为key 的元素对,值域为默认值。所以可以用该操作向map 中插入元素对或修改已经存在的元素对的值域部分。

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

也可以直接调用insert 方法插入元素对,insert 操作会返回一个pair,当map 中没有与key 相匹配的键值时,其first 是指向插入元素对的迭代器,其second true;若map 中已经存在与key 相等的键值时,其first 是指向该元素对的迭代器,second false

3、查找元素对,例如:

int i = m[key];

要注意的是,当与该键值相匹配的元素对不存在时,会创建键值为key 的元素对。map<string, int>::iterator it = m.find(key);如果map 中存在与key 相匹配的键值时,find 操作将返回指向该元素对的迭代器,否则,返回的迭代器等于map end()(参见vector 中提到的begin

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;
}

由于STL–algorithm较长  另加一篇详解


第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);
}

void add(int i,int v)
{
    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] == 'A') add(a,b);
            if (s[0] == 'S') add(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)改变某一个元素的值 (2)查询某一个区间内所有元素的和。在此基础上,经过简单的变形可以变成支持另一组操作:(1)把一个区间内所有元素都加上一个值 (2)查询某一个元素的值。这两个都是已经泛滥了的东西了,在此不赘述。

简单的树状数组模型是不支持这样一组操作的:(1)把某一个区间内所有元素都加上一个值 (2)查询某一个区间内所有元素的和。当然,这个东西可以用线段树完成,但是线段树占内存比较大,写起来也比较繁(对我这种不会数据结构的人而言)。下面我们用一个改进版的树状数组完成这个任务。

首先一个观察是区间操作总可以变成从最左端开始,比如把区间[3..6]都加10,可以变成[1..6]10, [1..2]10。查询也类似。于是下面只关心从最左端开始的情况。定义Insert(p, d)表示把区间[1..p]都加dQuery(p)表示查询区间[1..p]之和。

我们考虑调用一次Insert(p, d)对以后的某次查询Query(q)的影响:

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

也就是说,Query(q)的结果来源可分为两部分,一部分是Insert(p1,d) (p1<=q),一部分是Insert(p2,d) (p2 > q)。我们用两个数组B[], C[]分别维护这两部分信息,B[i]表示区间右端点恰好是i的所有区间的影响之和,C[i]表示区间右端点大于i的所有区间的影响之和。每当遇到 Insert时,考虑当前的Insert会对以后的Query产生什么影响,更新BC数组;当遇到Query时,把两部分的结果累加起来。

具体来说,当我们遇到Insert(p, d)时,把B[p]增加p*d,把C[1], C[2], , C[p-1]都增加d。当遇到Query(p)时,查询B[1]+B[2]++B[p]+C[p]*p即可。可以发现对B数组是修改单个元素,查询区间和;对C数组是修改区间,查询单个元素,这恰好对应于一开始说的树状数组支持的基本操作。于是我们用两个树状数组漂亮地完成了任务。🙂

示例代码:

#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线段树区间修改


传送门 

题目意思很简单,有N个数,Q个操作,  Q l  r 表示查询从l到r 的和,C  l  r  v 表示将从l到r 的值加上v,明显的线段树,不知道线段树的人肯定暴力,肯定超时,哈哈!!

解题方法我在代码注释中写的很详细了

#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的区别


这个星期开始学习Python了,因为看的书都是基于Python2.x,而且我安装的是Python3.1,所以书上写的地方好多都不适用于Python3.1,特意在Google上search了一下3.x和2.x的区别。特此在自己的空间中记录一下,以备以后查找方便,也可以分享给想学习Python的friends.

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

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

对象和seq是可迭代的。

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

另外,数值类型也被ABCs化。关于这两点,请参阅 PEP 3119和PEP 3141。

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

在Py3.0中:

    >>> 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’ ‘)来达到相同目的

3)zip()、map()和filter()都返回迭代器。而apply()、 callable()、coerce()、 execfile()、reduce()和reload


()函数都被去除了

现在可以使用hasattr()来替换 callable(). hasattr()的语法如:hasattr(string, ‘__name__’)

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

在Py3.X中:

    >>> file

    Traceback (most recent call last):

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

       file

    NameError: name ‘file’ is not defined  


interviewstreet pair


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

链接  https://www.hackerrank.com/challenges/pairs

       题意大概是输入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个物品,两个人轮流从这堆物品中取物,规

定每次至少取一个,最多取m个。最后取光者得胜。

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

后取者都能够一次拿走剩余的物品,后者取胜。因此我们发现了如何取胜的法则:如果
n=(m+1)r+s,(r为任意自然数,s≤m),那么先取者要拿走s个物品,如果后取者拿走

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

取法,那么先取者肯定获胜。总之,要保持给对手留下(m+1)的倍数,就能最后获胜。

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

个,谁能报到100者胜。

(二)威佐夫博奕(Wythoff Game):有两堆各若干个物品,两个人轮流从某一堆或同
时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。


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

两堆物品的数量并称其为局势,如果甲面对(0,0),那么甲已经输了,这种局势我们

称为奇异局势。前几个奇异局势是:(0,0)、(1,2)、(3,5)、(4,7)、(6,

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)的某一个分量,那么另一个分量不可能在其

他奇异局势中,所以必然是非奇异局势。如果使(ak,bk)的两个分量同时减少,则由

于其差不变,且不可能是其他奇异局势的差,因此也是非奇异局势。

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

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

奇异局势(0,0);如果a = ak ,b > bk,那么,取走b  – bk个物体,即变为奇异局

势;如果 a = ak ,  b < bk ,则同时从两堆中拿走 ak – ab + ak个物体,变为奇异局

势( ab – ak , ab – ak+ b – ak);如果a > ak ,b= ak + k,则从第一堆中拿走多余

的数量a – ak 即可;如果a < ak ,b= ak + k,分两种情况,第一种,a=aj (j < k)

,从第二堆里面拿走 b – bj 即可;第二种,a=bj (j < k),从第二堆里面拿走 b – a

j 即可。

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

;反之,则后拿者取胜。

    那么任给一个局势(a,b),怎样判断它是不是奇异局势呢?我们有如下公式:

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


奇妙的是其中出现了黄金分割数(1+√5)/2 = 1。618…,因此,由ak,bk组成的矩形近

似为黄金矩形,由于2/(1+√5)=(√5-1)/2,可以先求出j=[a(√5-1)/2],若a=[

j(1+√5)/2],那么a = aj,bj = aj + j,若不等于,那么a = aj+1,bj+1 = aj+1

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

局势。

(三)尼姆博奕(Nimm Game):有三堆各若干个物品,两个人轮流从某一堆取任意多的
物品,规定每次至少取一个,多者不限,最后取光者得胜。

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

先(0,0,0)显然是奇异局势,无论谁面对奇异局势,都必然失败。第二种奇异局势是

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

下,(1,2,3)也是奇异局势,无论对手如何拿,接下来都可以变为(0,n,n)的情

形。

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

这种运算。这种运算和一般加法不同的一点是1+1=0。先看(1,2,3)的按位模2加的结

果:

1 =二进制01

2 =二进制10

3 =二进制11 (+)

———————

0 =二进制00 (注意不进位)

    对于奇异局势(0,n,n)也一样,结果也是0。

    任何奇异局势(a,b,c)都有a(+)b(+)c =0。

如果我们面对的是一个非奇异局势(a,b,c),要如何变为奇异局势呢?假设 a < b

< 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个物体即可达

到奇异局势(14,21,27)。

    例2。(55,81,121),55(+)81=102,121-102=19,所以从121中拿走19个物品

就形成了奇异局势(55,81,102)。

    例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:今有若干堆火柴,两人依次从中拿取,规定每次只能从一堆中取若干根, 

可将一堆全取走,但不可不取,最后取完者为胜,求必胜的方法。 

题目2:今有若干堆火柴,两人依次从中拿取,规定每次只能从一堆中取若干根, 

可将一堆全取走,但不可不取,最后取完者为负,求必胜的方法。

嘿嘿,这个游戏我早就见识过了。小时候用珠算玩这个游戏:第一档拨一个,第二档拨两个,依次直到第五档拨五个。然后两个人就轮流再把棋子拨下来,谁要是最后一个拨谁就赢。有一次暑假看见两个小孩子在玩这个游戏,我就在想有没有一个定论呢。下面就来试着证明一下吧

先解决第一个问题吧。

定义:若所有火柴数异或为0,则该状态被称为利他态,用字母T表示;否则, 

为利己态,用S表示。

[定理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

这就是说从A(t)堆中取出 A(t) – x 根火柴后状态就会从S态变为T态。证毕

[定理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易得。 

接着来解决第二个问题。

定义:若一堆中仅有1根火柴,则被称为孤单堆。若大于1根,则称为充裕堆。

定义:T态中,若充裕堆的堆数大于等于2,则称为完全利他态,用T2表示;若充裕堆的堆数等于0,则称为部分利他态,用T0表示。

 

孤单堆的根数异或只会影响二进制的最后一位,但充裕堆会影响高位(非最后一位)。一个充裕堆,高位必有一位不为0,则所有根数异或不为0。故不会是T态。

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

证明:

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

方取,所以最后一根必己取。败。同理,  T0态必胜#

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

证明:

若此时孤单堆堆数为奇数,把充裕堆取完;否则,取成一根。这样,就变成奇数个孤单堆,由对方取。由定理5,对方必输。己必胜。  # 

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

证明:

充裕堆数不可能一次由2变为0。得证。  # 

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

证明:

由定理1,S态可转变为T态,态可一次转变为T态,又由定理6,S2态不可转一次变为T0态,所以转变的T态为T2态。  # 

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

证明:

由定理2,T态必然变为S态。由于充裕堆数不可能一次由2变为0,所以此时的S态不可能为S0态。命题得证。 

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

证明:

方法如下: 

      1)  S2态,就把它变为T2态。(由定理8) 

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

    若转变为S2,  转向1) 

    若转变为S1,  这己必胜。(定理5) 

[定理11]:T2态必输。 

证明:同10。 

综上所述,必输态有:  T2,S0 

          必胜态:    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) 

下划线表示胜利一方的取法。  是否发现了他们的惊人相似之处。 

我们不难发现(见加黑部分),S1态可以转变为S0态(第二题做法),也可以转变为 

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

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

  所以,抢夺S1是制胜的关键! 

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

 

推荐HDOJ题目
http://acm.hdu.edu.cn/showproblem.php?pid=1907
http://acm.hdu.edu.cn/showproblem.php?pid=2509

看完上面的结论,就能顺利解决上面2道了

 

 

S-Nim
http://acm.hdu.edu.cn/showproblem.php?pid=1536
http://acm.hdu.edu.cn/showproblem.php?pid=1944

 

 

 

博弈算法入门小节 1536 1517 1907

小子最近迷途于博弈之中。。。感触颇深。

为了让大家能够在学习博弈的时候少走弯路,最重要的也是为了加深自己的影响,温故而知新,特发此贴与大家共勉。

学博弈先从概念开始:

特别推荐LCY老师的课件:博弈入门。

下载地址:http://acm.hdu.edu.cn/forum/read.php?tid=6875

这个课件个人认为从博弈的基本思想,一直到解博弈的中心算法做了很好的诠释。但是特别要注意的是。课件后面一部分英语写的讲义是重中之重。小子英语很弱,在这困扰很久。现在为大家大概介绍一下。

主要是后继点和SG值的问题:

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

后继点:也就是按照题目要求的走法(比如取石子可以取的数量,方法)能够走一步达到的那个点。

具体的有关SG值是怎么运用的希望大家自己多想想。

课件后面有一个1536的代码。可以放在后面做做

看到这里推荐大家做几道题:1846(最简单的博弈水题)

1847(求SG值)

有了上面的知识接下来我们来看看组合博弈(n堆石子)

推荐大家看个资料:

博弈-取石子游戏(推荐等级五星级)
http://acm.hdu.edu.cn/forum/read.php?fid=20&tid=5748
http://hi.baidu.com/netnode/blog/item/30932c2edc7384514fc226ea.html

这里提出了一个奇异状态的问题。看了这篇文章你会发现异或运算在博弈中使用的妙处。当然这里指出的只是组合博弈中一种特殊情况。

王道还是对SG值的求解,但是知道这么一种思路无疑对思维的广度和深度扩展是很有帮助的。

ZZ博弈
http://acm.hdu.edu.cn/forum/read.php?fid=9&tid=10617

这里介绍了组和博弈的两种大的类型,一种是最后取的是N状态一种是最后取的是P状态,两个状态的解题方法能看懂很有帮助。当然,能够把推导过程理解,吃透无疑是大牛级的做法~小子也佩服的紧~   

    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
http://acm.hdu.edu.cn/forum/read.php?tid=11339&fpage=0&toread=&page=1

 

 

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()

{

    int i,t,n,s,bead,j;

    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–)

            {

                cin >> bead;//该堆的成员个数

                if(sg[bead]==-1)

                    sg[bead]=mex(bead);

                s=s^sg[bead];

            }

            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;

}

这里感谢shǎ崽同学的一段代码让小子学会了puts的妙用

 

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是否是2的N次方。


  方法之一是判断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?


这个题目的意思是输入n个数,m组询问,每组询问包含两个整数k,v,意思是询问整数v第k次出现的位置。

#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;
}

代码很好懂,主要是map和vector的用法。


《算法竞赛入门经典——训练指南》实用数据结构



基础数据结构


例题







例题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

hdoj 1711 KMP Number Sequence





Problem Description


Given two sequences of numbers : a[1], a[2], …… , a[N], and b[1], b[2], …… , b[M] (1 <= M <= 10000, 1 <= N <= 1000000). Your task is to find a number K which make a[K] = b[1], a[K + 1] = b[2], …… , a[K + M – 1] = b[M]. If there are more than one
K exist, output the smallest one.


 




Input


The first line of input is a number T which indicate the number of cases. Each case contains three lines. The first line is two numbers N and M (1 <= M <= 10000, 1 <= N <= 1000000). The second line contains N integers which indicate a[1], a[2], …… , a[N].
The third line contains M integers which indicate b[1], b[2], …… , b[M]. All integers are in the range of [-1000000, 1000000].


 




Output


For each test case, you should output one line which only contain K described above. If no such K exists, output -1 instead.


 




Sample Input

2 13 5 1 2 1 2 3 1 2 3 1 3 2 1 2 1 2 3 1 3 13 5 1 2 1 2 3 1 2 3 1 3 2 1 2 1 2 3 2 1


 




Sample Output

6 -1
#include <stdio.h>

int n, m;
int a[1000005];
int b[10005];
int f[10005];

void getfail()
{
    f[0] = 0;
    f[1] = 0;
    for (int i = 1; i < m; i++)
    {
        int j = f[i];
        while (j && b[i] != b[j])
            j = f[j];
        f[i+1] = b[j] == b[i] ? j + 1 : 0;
    }
}

int main()
{
    int flag, i, j, t;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d %d",&n,&m);
        for (i = 0; i < n; i++)
            scanf("%d",&a[i]);
        for (i = 0; i < m; i++)
            scanf("%d",&b[i]);
        getfail();
        for (i = 0;i <= m; i++) printf("%d ",f[i]);  puts("");
        flag = 1;
        j = 0;
        for (i = 0;i < n;i++)
        {
            while (j && b[j] != a[i])
                j = f[j];
            if (b[j] == a[i])
                j++;
            if (j == m)
            {
                flag = 0;
                printf("%d\n",i - m + 1);
            }
        }
        if (flag)
            puts("-1");
    }
    return 0;
}


hdoj 1230 火星A+B


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

int a[150],b[150],t[150];
int pr[150];

void prime()
{
    int i, j, f, cnt = 1;
    pr[0] = 2;
    for(i = 3; ;i++)
    {
        f = 1;
        for(j = 2;j * j <= i; j++)
        {
            if(i % j == 0)
            {
                f = 0;
                break;
            }
        }
        if(f)
            pr[cnt++] = i;
        if(cnt > 120)
            break;
    }
}

void change(int l,int *p)
{
    int cnt = 0;
    for(int i = l;i >= 0;i--)
    {
        p[cnt++] = t[i];
    }
}

int main()
{
    int i, j;
    prime();
    while(1)
    {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        i = 0;j = 0;
        while(1)
        {
            scanf("%d",&t[i++]);
            if(getchar() == ' ')
            {
                change(i - 1,a);
                break;
            }
        }
        while(1)
        {
            scanf("%d",&t[j++]);
            if(getchar() == '\n')
            {
                change(j - 1,b);
                break;
            }
        }
        if(i == 1 && j == 1 && !a[0] && !b[0])
            break;
        int temp = 0;
        for(i = 0; i < 120 ;i++ )
        {
            a[i] = a[i] + b[i] + temp;
            temp = a[i] / pr[i];
            a[i] = a[i] % pr[i];
        }
        for(i = 120; i >= 0;i--)
        {
            if(a[i] != 0)
                break;
        }
        for(;i >= 0;i--)
        {
            printf("%d",a[i]);
            if(i)
                putchar(',');
            else
                putchar('\n');
        }
    }
    return 0;
}

hdoj 1202 水水更健康


传送门

没写的了 就随便写写,这是一道大大的水题,wa了两次 ,太丢人了!!!!

#include<stdio.h>

double fun(double x)
{
	if(x >= 90 && x <= 100)
		return 4;
	else if(x >= 80 && x <90)
		return 3;
	else if(x >= 70 && x < 80)
		return 2;
	else if(x >= 60 && x < 70)
		return 1;
	else
		return 0;
}

int main()
{
	int n,i;
	double s,p,ss,sp;
	while(scanf("%d",&n) != EOF)
	{
		ss = 0;
		sp = 0;
		int f = 1;
		for(i = 0;i < n;i++)
		{
			scanf("%lf %lf",&s,&p);
			if(p == -1.0)
				continue;
			f = 0;
			ss += s;
			sp += fun(p) * s;
		}
		if(f || ss == 0.0)     // 注意当ss为0的时候是没办法出结果的(除数不能为0),我就在这wa了一次
			printf("-1\n");
		else
			printf("%.2lf\n",sp / ss);
	}
	return 0;
}

至于另外一次wa就更丢人了,就不说了,弱爆了。


HackerRank网站,为编码程序员们提供一个以编码谜题和现实生活中遇到的编码难题为基础的新兴的社交平台



       https://www.hackerrank.com/


       HackerRank网站,为编码程序员们提供一个以编码谜题和现实生活中遇到的编码难题为基础的新兴的社交平台。

       HackerRank网站是一个为编码程序员们提供的新型社交平台。HackerRank 公司受风险投资公司Y Combinator 的资金支持,该公司的创始人与招聘工作网站InterviewStreet 的创始人是同一个团队,他们想要创建一个专为黑客们服务的在线社区,在这个社区中,他们提供了各种编码谜题、游戏病毒和现实中的编码难题及挑战,让黑客们在该社区中进行交流讨论,接受挑战。HackerRank,就如这个名字所暗示的一样,它同时还提供了在线排行榜和其他的竞争元素。

        HackerRank 公司的联合创始人Vivek Ravisankar 上周说到,创建HackerRank 网站的初衷是为潜在雇主们提供程序员招聘服务,以及对每一次成功的程序员推荐收取相应的费用。然而,随着时间的推移,该网站最初的运营模式逐渐发生改变,到现在HackerRank 网站已经成为了一个由公司赞助发起的社区网站,黑客们在该网站上解决编程方面遇到的挑战,以及公司目前面临的难题,并且实行竞争机制。如果公司决定雇佣其中最好的程序员,那么该他就会得到奖金。

        HackerRank网站上为提供很多的谜像问题,这些谜像问题都是从各种领先的编程语言社区网站上收集到的,但是Ravisankar介绍说,大部分的编码程序员们都比较喜欢解决现实中的编程难题及挑战。

对于HackerRank团队来说,HackerRank网站这个新的风投企业是InterviewStreet产物的自然演化物。InterviewStreet在今年年初组织了一次CodeSprint比赛,这是在硅谷举办的一次非常成功的编码挑战赛。参与这次挑战赛的公司都期待能够聘用到最棒的程序员,这些公司其中就包括脸谱(Facebook), Skype, 爱本卜(Airbnb), Box 和亚马逊(Amazon)。

        HackerRank网站的另外一个有趣的地方就是网站的排名系统。网站上的编程难题不是按照等级发布排列的,而是与网站会员的排名相关的,会员等级从一级排到十级,编程任务急难题就是按照会员的等级发送的,还有的是看那个任务需要多少人一起完成,然后再决定怎么发送难题。Ravisankar说,有些编程挑战并没有一个准确的解决方案,更多的是使编程的现有算法更加有效率。

Ravisankar还表示,该网站最重要的目的还是吸引那些已经在各自领域非常精通的编码程序员。网站上发布的挑战解决方案也会及时在线发布,然而,HackerRank希望发布的这些解决方案能够让程序员们从中学习到新的技术和知识。

为了推销其产品,HackerRank还为大学生们设置了一系列适合他们程度的挑战,而且还计划在这个月主持一个校际之间的编程马拉松比赛。

由于之前InterviewStreet这个典型的成功,HackerRank在2011年募集到了科斯拉风险投资公司(Khosla Ventures)300万美元的投资,而且,很明显的,HackerRank接收到了Y Combinator风投公司的投资。


2012年9月12日


poj 3298 数状数组


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

题目大意是一条大街上住着n个乒乓球爱好者,他们的水平高低用一个数值表示,他们经常举办比赛,比赛要三个人,一人当裁判。对裁判是有一定要求的,裁判的水平必须介于两选手之间且必须住他们中间,计算可以举办多少场比赛

#include<stdio.h>
#include<string.h>
#define maxn 100005
int c[20050];                  //存放比比第i个人技能值低的人数 
int xt[200050];                //树状数组
int a[10050];                  //存放每个人的技能值
int n;

int lowbit(int x)
{
	return x & (-x);
}
//一看到这个函数就知道是树状数组

void update(int x)
{
	while(x <= maxn)
	{
		xt[x] += 1;
		x += lowbit(x);
	}
}
//每次更新节点的时候只增加1

int sum(int x)
{
	int s = 0;
	while(x > 0)
	{
		s += xt[x];
		x -= lowbit(x);
	}
	return s;
} 
//因为更新的时候数组元素的值只增加了1,所以返回的值是小于等于x的数的个数


int main()
{
	int i, j, t;
	__int64  ans;
	//结果的可能值超出1<<32, 开始wa了一次

	scanf("%d",&t);
	while(t--)
	{
		memset(c,0,sizeof(c));
		memset(xt,0,sizeof(xt));
		scanf("%d",&n);
		for(i = 1;i <= n;i++)
		{
			scanf("%d",&a[i]);
			update(a[i]);
			c[i] = sum(a[i] - 1);                          
			//因为可能有多个人的技能值是相同的,所以不能在最后计算i的左边比a[i]小的人数

		}
		ans = 0;
		//别忘了初始化

		//我考虑第i个人做裁判的时候可能的比赛,累加得结果
		for(i = 2;i < n;i++)
		{
			ans += (c[i]) * ((n - i) - (sum(a[i]) - c[i] - 1));
			//当i做裁判时i左边有c[i]人小于a[i](前面已经计算出来了),sum(a[i]) - c[i] - 1)是i的右边比a[i]大的人数  

			ans += (i - 1 - c[i]) * (sum(a[i]) - c[i] - 1);
			//在i 的左边比a[i]大的有i - 1 - c[i]人,(sum(a[i]) - c[i] - 1)是i右边比a[i]大的人数

		}
		printf("%I64d\n",ans);
	}
	return 0;
}


线段树区间修改和点修改 hdoj 1698(区间修改)、hdoj 1754(点修改)



        这两题我都在之前做过,但并未通过,那次做的时候是刚开始接触线段树,现在有了一点点的了解,翻出以前的代码稍作修改就AC了。之前1698错误的原因是没有注意到位运算的优先级。

//hdoj 1698
#include<stdio.h>
#include<string.h>
#define maxn 100010
struct node
{
    int l;
    int r;
    int mid;
    int val;
}tree[maxn<<2];

void buildtree(int o,int l,int r)
{
    tree[o].val = 1;
    tree[o].l = l;
    tree[o].r = r;
    tree[o].mid = (l + r)>>1;
    if(l == r)
        return ;
    else
    {
        buildtree(o<<1, l, tree[o].mid);
        buildtree((o<<1)+1, tree[o].mid + 1, r);
    }
}

void update(int o, int l, int r, int val)
{
    if(l == tree[o].l && r == tree[o].r)
    {
        tree[o].val = val;
        return ;
    }
    //递归边界,如果更新的边界和节点边界相同则返回

    if(tree[o].val != 0)
    {
        tree[o<<1].val = tree[o].val;
        tree[(o<<1)+1].val = tree[o].val;
        tree[o].val = 0;
    }
    //这个地方是为了表示tree[o]的两个节点的val值是不一样的

    //要更新的段无非三种情况,要么在l-mid段,要么在mid-r段,再么就是两端都存在的,分情况递归
    if(r <= tree[o].mid)
        update(o<<1, l, r, val);
    //这个是位于l-mid段的

    else if(l > tree[o].mid)
        update((o<<1)+1, l, r, val);
    //这个是位于mid-r段的

    else
    {
        update(o<<1, l, tree[o].mid, val);
        update((o<<1)+1, tree[o].mid + 1, r, val);
    }
    //两段都有的情况
}

int getsum(int o,int l,int r)
{
    if(tree[o].val > 0)
        return tree[o].val * (tree[o].r - tree[o].l + 1);
    //tree[o].val > 0 证明在tree[o].l到tree[o].r区间里面的val都是一样的,要获取的区间也属于该区间

    if(r <= tree[o].mid)
        return getsum(o * 2, l, r);
    //同 update() 也是分三种情况

    else if (l > tree[o].mid)
        return getsum((o<<1)+1, l, r);

    else
        return getsum(o<<1, l, tree[o].mid) + getsum((o<<1)+1, tree[o].mid, r);
}

int main()
{
    int t, n, i, j, op, x, y, z;
    scanf("%d",&t);
    for(i = 1;i <= t;i++)
    {
        scanf("%d",&n);
        buildtree(1, 1, n);
        scanf("%d",&op);
        while(op--)
        {
            scanf("%d%d%d",&x,&y,&z);
            update(1, x, y, z);
        }
        int ans = getsum(1,1,n);
        printf("Case %d: The total value of the hook is %d.\n",i,ans);
    }
    return 0;
}

//hdoj 1754
#include<stdio.h>
#include<string.h>
#define maxn 200005

struct node
{
	int l;
	int r;
	int mid;
	int max;
}tree[maxn<<2];
int arr[maxn];

int max(int a,int b)
{
	return a > b ? a : b;
}

void build(int o, int l, int r)
{
	tree[o].l = l;
	tree[o].r = r;
	tree[o].mid = (l + r)>>1;
	if(l == r)
    {
        tree[o].max = arr[l];
		return ;
    }
	build(o<<1, l, tree[o].mid);
	build((o<<1)+1, tree[o].mid + 1, r);
	tree[o].max = max(tree[o<<1].max, tree[(o<<1)+1].max);
}

void update(int o, int l, int r,int a, int val)
{
    tree[o].max = max(tree[o].max, val);
	if(tree[o].l == tree[o].r)
	{
		return ;
	}
	if(a <= tree[o].mid)
		update(o<<1,l,tree[o].mid,a,val);
	else
		update((o<<1)+1, tree[o].mid + 1, r, a, val);
}

int query(int o,int l,int r)
{
	if(l == tree[o].l && r == tree[o].r)
		return tree[o].max;
	if(r <= tree[o].mid)
		return query(o*2,l,r);
	if(l > tree[o].mid)
		return query((o<<1)+1, l, r);
	return max(query(o<<1, l, tree[o].mid),query((o<<1)+1, tree[o].mid+1, r));
}

int main()
{
	int n, m, i, t, a, b;
	char c;
	while(scanf("%d%d",&n,&m) != EOF)
	{
		for(i = 1;i <= n;i++)
		{
			scanf("%d",&arr[i]);
		}
		build(1,1,n);
		while(m--)
		{
		    getchar();
			scanf("%c%d%d",&c,&a,&b);
			if(c == 'U')
				update(1,1,n,a,b);
			else
				printf("%d\n",query(1,a,b));
		}
	}
	return 0;
}