Codeforces Round #197 (Div. 二)

Codeforces Round #197 (Div. 2)
A. Helpful Mathstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Xenia the beginner mathematician is a third year student at elementary school. She is now learning the addition operation.

The teacher has written down the sum of multiple numbers. Pupils should calculate the sum. To make the calculation easier, the sum only contains numbers 1, 2 and 3. Still, that isn't enough for Xenia. She is only beginning to count, so she can calculate a sum only if the summands follow in non-decreasing order. For example, she can't calculate sum 1+3+2+1 but she can calculate sums 1+1+2 and 3+3.

You've got the sum that was written on the board. Rearrange the summans and print the sum in such a way that Xenia can calculate the sum.

The first line contains a non-empty string s — the sum Xenia needs to count. String s contains no spaces. It only contains digits and characters "+". Besides, string s is a correct sum of numbers 1, 2 and 3. String s is at most 100 characters long.

Print the new sum that Xenia can count.

3+2+1

1+2+3

1+1+3+1+3

1+1+1+3+3

2

2

水题就不说了

B. Xenia and Ringroadtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output
Xenia lives in a city that has n houses built along the main ringroad. The ringroad houses are numbered 1 through n in the clockwise order. The ringroad traffic is one way and also is clockwise.
Xenia has recently moved into the ringroad house number 1. As a result, she's got m things to do. In order to complete the i-th task, she needs to be in the house number ai and complete all tasks with numbers less than i. Initially, Xenia is in the house number 1, find the minimum time she needs to complete all her tasks if moving from a house to a neighboring one along the ringroad takes one unit of time.
Input
The first line contains two integers n and m (2?≤?n?≤?105,?1?≤?m?≤?105). The second line contains m integers a1,?a2,?...,?am (1?≤?ai?≤?n). Note that Xenia can have multiple consecutive tasks in one house.
Output
Print a single integer — the time Xenia needs to complete all tasks.
Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64dspecifier.
Sample test(s)input
4 33 2 3
output
6
input
4 32 3 3
output
2
Note
In the first test example the sequence of Xenia's moves along the ringroad looks as follows: 1?→?2?→?3?→?4?→?1?→?2?→?3. This is optimal sequence. So, she needs 6 time units.

题目不好懂。读懂了就是水题。就是一个人只能朝着一个方向走。问按这题目给定顺序走完全程需要的时间。注意只能朝一个方向走。
详细见代码：
C. Xenia and Weightstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output
Xenia has a set of weights and pan scales. Each weight has an integer weight from 1 to 10 kilos. Xenia is going to play with scales and weights a little. For this, she puts weights on the scalepans, one by one. The first weight goes on the left scalepan, the second weight goes on the right scalepan, the third one goes on the left scalepan, the fourth one goes on the right scalepan and so on. Xenia wants to put the total of m weights on the scalepans.
Simply putting weights on the scales is not interesting, so Xenia has set some rules. First, she does not put on the scales two consecutive weights of the same weight. That is, the weight that goes i-th should be different from the (i?+?1)-th weight for any i (1?≤?i?<?m). Second, every time Xenia puts a weight on some scalepan, she wants this scalepan to outweigh the other one. That is, the sum of the weights on the corresponding scalepan must be strictly greater than the sum on the other pan.
You are given all types of weights available for Xenia. You can assume that the girl has an infinite number of weights of each specified type. Your task is to help Xenia lay m weights on ??the scales or to say that it can't be done.
Input
The first line contains a string consisting of exactly ten zeroes and ones: the i-th (i?≥?1) character in the line equals "1" if Xenia has i kilo weights, otherwise the character equals "0". The second line contains integer m (1?≤?m?≤?1000).
Output
In the first line print "YES", if there is a way to put m weights on the scales by all rules. Otherwise, print in the first line "NO". If you can putm weights on the scales, then print in the next line m integers — the weights' weights in the order you put them on the scales.
If there are multiple solutions, you can print any of them.
Sample test(s)input
00000001013
output
YES8 10 8
input
10000000002
output
NO


开始犹豫了下。没敢写。抱着试一试的态度暴力写了下就过了。。看来深搜的时间复杂度真不好估计。
详细见代码：
D. Xenia and Bit Operationstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output
Xenia the beginner programmer has a sequence a, consisting of 2n non-negative integers: a1,?a2,?...,?a2n. Xenia is currently studying bit operations. To better understand how they work, Xenia decided to calculate some value v for a.
Namely, it takes several iterations to calculate value v. At the first iteration, Xenia writes a new sequence a1 or a2,?a3 or a4,?...,?a2n?-?1 or a2n, consisting of 2n?-?1 elements. In other words, she writes down the bit-wise OR of adjacent elements of sequence a. At the second iteration, Xenia writes the bitwise exclusive OR of adjacent elements of the sequence obtained after the first iteration. At the third iteration Xenia writes the bitwise OR of the adjacent elements of the sequence obtained after the second iteration. And so on; the operations of bitwise exclusive OR and bitwise OR alternate. In the end, she obtains a sequence consisting of one element, and that element is v.
Let's consider an example. Suppose that sequence a?=?(1,?2,?3,?4). Then let's write down all the transformations (1,?2,?3,?4) ?→?(1 or 2?=?3,?3 or 4?=?7) ?→? (3 xor 7?=?4). The result is v?=?4.
You are given Xenia's initial sequence. But to calculate value v for a given sequence would be too easy, so you are given additional mqueries. Each query is a pair of integers p,?b. Query p,?b means that you need to perform the assignment ap?=?b. After each query, you need to print the new value v for the new sequence a.
Input
The first line contains two integers n and m (1?≤?n?≤?17,?1?≤?m?≤?105). The next line contains 2n integers a1,?a2,?...,?a2n (0?≤?ai?<?230). Each of the next m lines contains queries. The i-th line contains integers pi,?bi (1?≤?pi?≤?2n,?0?≤?bi?<?230) — the i-th query.
Output
Print m integers — the i-th integer denotes value v for sequence a after the i-th query.
Sample test(s)input
2 41 6 3 51 43 41 21 2
output
1333
Note
For more information on the bit operations, you can follow this link: http://en.wikipedia.org/wiki/Bitwise_operation

简单线段树。
详细见代码：
#include <iostream>#include<stdio.h>using namespace std;int val[1<<20],op[1<<20];void btree(int L,int R,int k){    int mid,ls,rs;    if(L==R)    {        scanf("%d",&val[k]);        op[k]=1;        return ;    }    ls=k<<1;    rs=ls|1;    mid=(L+R)>>1;    btree(L,mid,ls);    btree(mid+1,R,rs);    op[k]=op[ls]^1;    if(op[k])        val[k]=val[ls]^val[rs];    else        val[k]=val[ls]|val[rs];}void update(int L,int R,int p,int b,int k){    int mid,ls,rs;    if(L==R)    {        val[k]=b;        return;    }    ls=k<<1;    rs=ls|1;    mid=(L+R)>>1;    if(p>mid)        update(mid+1,R,p,b,rs);    else        update(L,mid,p,b,ls);    if(op[k])        val[k]=val[ls]^val[rs];    else        val[k]=val[ls]|val[rs];}int main(){    int n,m,p,b,i,lim;    while(~scanf("%d%d",&n,&m))    {        lim=1<<n;        btree(1,lim,1);        for(i=0;i<m;i++)        {            scanf("%d%d",&p,&b);            update(1,lim,p,b,1);            printf("%d\n",val[1]);        }    }    return 0;}

那次比赛没打。是下来写的，下来感觉蛮简单的。不过如果当时打了。第二题估计写不出来。因为题目我下来确实没读懂。