题目分别出自：

poj1195，codeforces 482B，codeforces 591A。poj 2503，poj2442，codeforces 445B

A题：

A题题目链接

题目描写叙述：

Input

The input is read from standard input as integers and the answers to the queries are written to standard output as integers. The input is encoded as follows. Each input comes on a separate line, and consists of one instruction integer and a number of parameter integers according to the following table. 

The values will always be in range, so there is no need to check them. In particular, if A is negative, it can be assumed that it will not reduce the square value below zero. The indexing starts at 0, e.g. for a table of size 4 * 4, we have 0 <= X <= 3 and 0 <= Y <= 3. 

Table size: 1 * 1 <= S * S <= 1024 * 1024 
Cell value V at any time: 0 <= V <= 32767 
Update amount: -32768 <= A <= 32767 
No of instructions in input: 3 <= U <= 60002 
Maximum number of phones in the whole table: M= 2^30 

0 4
1 1 2 3
2 0 0 2 2 
1 1 1 2
1 1 2 -1
2 1 1 2 3 
3

3
4

解析：

A题先晾着。树状数组这一块还没有进行系统的学习。

有兴趣的能够自己做做或者百度一下相关知识学一学。

B题：

B题题目链接

题目描写叙述：

Interesting Array

3 1
1 3 3

YES
3 3 3

3 2
1 3 3
1 3 2

NO

题意：

给定n,m，分别表示数组a中元素的个数和"限制"的组数，接下来是m组限制，每组限制有三个数据。各自是l，r。p，表示要满

足条件数组a[l] & a[l+1] & ...a[r] = p，然后要求输出满足以上全部m组限制的数组a。假设有多组满足的话，输出随意一组就可以。

解析：

一開始拿到这道题的时候。看到区间问题。立即反应过来要用线段树。

但是想了非常久，依据自己掌握的知识，先要构建一棵线段树，但是题目中却是要输出这种一个数组，意思就是一開始并不提供构建线段树的条件(即数组元素)，而是给你一些查询，让你

通过这些查询来输出一棵满足全部查询的树。然后我就纳闷了，去翻了翻当时的官方题解，发现思路很巧妙。题解的思路也就是

将这些查询转换成对应的条件。然后通过这些条件先预处理一棵通过这些条件不断更新后得到的一棵线段树，然后最后再通过这

棵线段树来推断这些条件是否一一成立，若当中有不成立的，说明得到的这棵线段树与已知的查询矛盾。则输出NO。反之则一一

输出线段树中存储的数据元素。即数组元素。

官方题解出处:点击打开链接

完整代码实现：

#include<cstdio>
#include<cstring>

const int MAX_BIT = 29;        //表示最大的位数(二进制位)
const int MAX_NUM = (int)1e5 + 10;
const int INF = (1 << 30) - 1;       //注意这里的无穷大的取值,不能随便取值
int l[MAX_NUM],r[MAX_NUM],q[MAX_NUM],a[MAX_NUM],sum[MAX_NUM],n,m;
int tree[MAX_NUM * 4];

//数组建立线段树,v为当前遍历到的节点的下标,根节点为1,l,r分别为线段树节点存储的区间的左值和右值
void build(int v,int l,int r){
    //遍历到了叶节点
    if(l == r){
        tree[v] = a[l];
        return;
    }

    int lson = v << 1,rson = lson + 1,mid = (l+r) >> 1;

    build(lson,l,mid);
    build(rson,mid+1,r);

    //节点存储的值为其左右孩子存储的值相与后的结果
    tree[v] = tree[lson] & tree[rson];
}
/**v,l,r表示当前遍历到的节点的下标以及存储的左右区间值
 **ql,qr表示待查询的区间
 */
int Query(int v, int l, int r, int ql, int qr) {
    if (r < ql || l > qr)  return INF;

    if (ql <= l && r <= qr)  return tree[v];

    int lson = v<<1, rson = lson+1, mid = (l+r)>>1;

    return Query(lson, l, mid, ql, qr) & Query(rson, mid+1, r, ql, qr);
}

void Init(){
    scanf("%d %d",&n,&m);
    for(int i = 1;i <= m;++i){
        scanf("%d %d %d",&l[i],&r[i],&q[i]);
    }

    for(int i = 0;i <= MAX_BIT;++i){    //考虑q[i]的每一位,假设该位是1。那么数组a[l[i]] —— a[r[i]]相应位均要为1
        memset(sum,0,sizeof(sum));
        for(int j = 1;j <= m;++j){
            if((q[j] >> i) & 1){      
                ++sum[l[j]];
                --sum[r[j]+1];  //sum用来标记每次处理的区间
            }
        }
        for(int j = 1;j <= n;++j){
            sum[j] += sum[j-1];
            if(sum[j] > 0){     //表示处理到的这一位不为0
                a[j] |= 1 << i;
            }
        }
    }
    build(1,1,n);
}

void solve(){
    for(int i = 1;i <= m;++i){
        if(Query(1,1,n,l[i],r[i])!=q[i]){
            printf("NO
");
            return;
        }
    }
    printf("YES
");
    for(int i = 1;i <= n;++i){
        if(i-1){
            printf(" ");
        }
        printf("%d ",a[i]);
    }
    printf("
");
}
int main(){
    Init();
    solve();
    return 0;
}

这道题目是非常好的题目。感觉自己还不是非常懂，等到过段时间线段树这部分总结了之后一定要再来看看。

C题：

C题题目链接

题目描写叙述：

Wizards' Duel

100
50
50

50

199
60
40

119.4

 Note

In the first sample the speeds of the impulses are equal, so both of their meetings occur exactly in the middle of the corridor.

题意：

Harry 和 He-Who-Must-Not-Be-Named 分别在走廊末端，各发射自己的impulse，当中Harry 的 impulse 速度为 p 米/s。He-Who-

Must-Not-Be-Named为 q米/s。

然后相遇之后各自回到它们的主人身边。再发射。再发射时的速度保持不变。问第二次相遇的时候。

Harry的impulse 离他的位置距离是多少。

解析：

因为第二次再发射的时候速度保持不变。因此相遇点仍然是第一次相遇的那个点。

因此得出一元一次方程（p+q）* t = l;

然后再p*t则是全部答案。

完整代码实现：

#include<cstdio>
int main(){
    int l,p,q;
    scanf("%d %d %d",&l,&p,&q);
    printf("%.6f
",(double)l/(p+q)*p);
}

D题题目链接

题目描写叙述：

Babelfish

dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay

atcay
ittenkay
oopslay

cat
eh
loops

在词典中，给定一些翻译后的单词及翻译前的单词，然后空行隔开，再给定一些翻译前的单词。假设这些翻译前的单词存在词

典中，那么输出其翻译后的单词，否则的话，则输出字符串eh。

解析：

这道题因为数据量很大。词典中最多高达10^5组单词，并且查询次数也达到了10^5次方，因此暴力遍历的方法显然是不可行

的，因为这道题的时限比較宽松。因此用映射容器map也能过。注意空行的处理，在这里空行仅仅有一个' '字符。

完整代码实现：

#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<cstring>
#include<cstdio>
using namespace std;
map <string,string> mp;
int main(){
    char temp[50];
    string str,str1,str2;
    while(gets(temp) && strlen(temp)){
        for(int j = 0;;++j){
            if(temp[j]==' '){
                temp[j] = '