??? 這次出的題水爆了,借著這個機會終于把CF的號變藍了.
A. Helpful Maths
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard 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.
Input
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.
Output
Print the new sum that Xenia can count.
Sample test(s)
Input
3+2+1
Output
1+2+3
Input
1+1+3+1+3
Output
1+1+1+3+3
Input
2
Output
2
題意:輸入一個加法算式,把其中的加數按從小到大的順序排序后輸出算式.
思路:如題.
#include<stdio.h>
#include
<
string
.h>
int
main()
{
char
str[
200
];
int
s[
200
],i,j;
scanf(
"
%s
"
,&str[
1
]);
int
len=strlen(&str[
1
]);
int
T=(len+
1
)/
2
;
for
(i=
1
;i<=T;i++) s[i]=str[
2
*i-
1
]-
48
;
for
(i=
1
;i<=T-
1
;i++
)
for
(j=i+
1
;j<=T;j++
)
if
(s[i]>
s[j])
{
int
tmp=
s[i];
s[i]
=
s[j];
s[j]
=
tmp;
}
putchar(s[
1
]+
48
);
for
(i=
2
;i<=T;i++) printf(
"
+%c
"
,s[i]+
48
);
printf(
"
\n
"
);
return
0
;
}
B. Xenia and Ringroad
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard 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 %I64d specifier.
Sample test(s)
Input
4 33 2 3
Output
6Input
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.
題意:城市里有一條環形公路,一開始在1號位置,共需辦n件事,其中第i件要在a[i]位置完成,而且辦i時,前i-1件事必須已經完成,求需要花多長時間.
思路:直接模擬.
#include<stdio.h>
int
a[
100010
];
int
abs(
int
x)
{
if
(x<
0
)
return
-
1
*
x;
return
x;
}
int
main()
{
int
n,m;
scanf(
"
%d%d
"
,&n,&
m);
for
(
int
i=
1
;i<=m;i++
)
{
scanf(
"
%d
"
,&
a[i]);
a[i]
--
;
}
int
cur=
0
;
__int64 ans
=
0
;
for
(
int
i=
1
;i<=m;i++
)
{
if
(a[i]>=cur) ans+=a[i]-
cur;
else
ans+=n-(cur-
a[i]);
cur
=
a[i];
}
printf(
"
%I64d\n
"
,ans);
return
0
;
}
C. Xenia and Weights
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard 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 put m 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
0000000101
3
Output
YES
8 10 8
Input
1000000000
2
Output
NO
題意:有n種砝碼,每次取一個放在秤盤一端,下一次則放在另一端.要求:1.每次放完后,放置砝碼的一端質量應超過另一端,2.不連續兩次放同樣質量的砝碼.求是否能進行m次放置操作.
思路:直接dfs,枚舉每次如何操作.之前有想過貪心:在滿足條件的情況下優先選質量小的.但這種想法似乎不太對,目前還沒想明白.不過比賽時抱著試一試的想法直接dfs了,沒想到居然A了,而且只用了30ms.后來仔細想想,我搜索時是按從小質量到大質量的順序枚舉的,所以構造一組可行解所需的時間其實并不多.
#include<stdio.h>
#include
<
string
.h>
bool
find=
false
,f[
20
];
int
s[
1025
];
int
m;
void
dfs(
int
ax,
int
bx,
int
dep,
int
tar)
{
if
(find)
return
;
if
(dep==m+
1
)
{
printf(
"
YES\n%d
"
,s[
1
]);
for
(
int
i=
2
;i<dep;i++) printf(
"
%d
"
,s[i]);
printf(
"
\n
"
);
find
=
true
;
return
;
}
if
(tar==
0
)
{
for
(
int
i=
1
;i<=
10
;i++
)
if
(f[i] && i!=s[dep-
1
] && ax+i>
bx)
{
s[dep]
=
i;
dfs(ax
+i,bx,dep+
1
,
1
);
}
}
else
{
for
(
int
i=
1
;i<=
10
;i++
)
if
(f[i] && i!=s[dep-
1
] && bx+i>
ax)
{
s[dep]
=
i;
dfs(ax,bx
+i,dep+
1
,
0
);
}
}
}
int
main()
{
char
str[
20
];
scanf(
"
%s
"
,&str[
1
]);
memset(f,
false
,
sizeof
(f));
for
(
int
i=
1
;i<=
10
;i++
)
if
(str[i]==
'
1
'
) f[i]=
true
;
memset(s,
0
,
sizeof
(s));
scanf(
"
%d
"
,&
m);
dfs(
0
,
0
,
1
,
0
);
if
(!find) printf(
"
NO\n
"
);
return
0
;
}
D. Xenia and Bit Operations
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard 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 m queries. 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 4
1 6 3 5
1 4
3 4
1 2
1 2
Output
1
3
3
3
Note
For more information on the bit operations, you can follow this link:
http://en.wikipedia.org/wiki/Bitwise_operation
題意:給出2^n個數,第一次鄰項求OR,得到2^(n-1)個數,第二次鄰項求XOR,得到2^(n-2)個數.以此類推,直到只剩一個數v.給出序列的初始狀態,每次改變序列中的一個數,求出改變后的v(更新是累計的).
思路:沒什么可說的,線段樹.
#include<stdio.h>
struct
tnode
{
int
p,r;
int
m;
int
lid,rid;
int
K;
int
sty;
};
tnode tree[
400040
];
int
a[
200000
],top=
1
;
void
build(
int
u,
int
col
/*
0->XOR,1->OR
*/
)
{
tree[u].sty
=
col;
if
(tree[u].p+
1
==
tree[u].r)
{
tree[u].K
=
a[tree[u].p];
return
;
}
tree[u].m
=(tree[u].p+tree[u].r)>>
1
;
top
++
;
tree[u].lid
=
top;
tree[tree[u].lid].p
=
tree[u].p;
tree[tree[u].lid].r
=
tree[u].m;
build(tree[u].lid,
1
-
col);
top
++
;
tree[u].rid
=
top;
tree[tree[u].rid].p
=
tree[u].m;
tree[tree[u].rid].r
=
tree[u].r;
build(tree[u].rid,
1
-
col);
if
(col) tree[u].K=tree[tree[u].lid].K |
tree[tree[u].rid].K;
else
tree[u].K=tree[tree[u].lid].K ^
tree[tree[u].rid].K;
}
void
modify(
int
u,
int
p,
int
b)
{
if
(tree[u].p>p || tree[u].r-
1
<p)
return
;
if
(tree[u].p+
1
==
tree[u].r)
{
a[p]
=
b;
tree[u].K
=
b;
return
;
}
if
(p<
tree[u].m) modify(tree[u].lid,p,b);
else
modify(tree[u].rid,p,b);
if
(tree[u].sty) tree[u].K=tree[tree[u].lid].K |
tree[tree[u].rid].K;
else
tree[u].K=tree[tree[u].lid].K ^
tree[tree[u].rid].K;
}
int
main()
{
int
n=
1
,m,t;
scanf(
"
%d%d
"
,&t,&
m);
for
(
int
i=
1
;i<=t;i++) n <<=
1
;
for
(
int
i=
1
;i<=n;i++) scanf(
"
%d
"
,&
a[i]);
tree[
1
].p=
1
;
tree[
1
].r=n+
1
;
build(
1
,t&
1
);
while
(m--
)
{
int
p,b;
scanf(
"
%d%d
"
,&p,&
b);
modify(
1
,p,b);
printf(
"
%d\n
"
,tree[
1
].K);
}
return
0
;
}
E. Three Swaps
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Xenia the horse breeder has n (n?>?1) horses that stand in a row. Each horse has its own unique number. Initially, the i-th left horse has number i. That is, the sequence of numbers of horses in a row looks as follows (from left to right): 1, 2, 3, ..., n.
Xenia trains horses before the performance. During the practice sessions, she consistently gives them commands. Each command is a pair of numbers l,?r (1?≤?l?<?r?≤?n). The command l,?r means that the horses that are on the l-th, (l?+?1)-th, (l?+?2)-th, ..., r-th places from the left must be rearranged. The horses that initially stand on the l-th and r-th places will swap. The horses on the (l?+?1)-th and (r?-?1)-th places will swap. The horses on the (l?+?2)-th and (r?-?2)-th places will swap and so on. In other words, the horses that were on the segment [l,?r] change their order to the reverse one.
For example, if Xenia commanded l?=?2,?r?=?5, and the sequence of numbers of horses before the command looked as (2, 1, 3, 4, 5, 6), then after the command the sequence will be (2, 5, 4, 3, 1, 6).
We know that during the practice Xenia gave at most three commands of the described form. You have got the final sequence of numbers of horses by the end of the practice. Find what commands Xenia gave during the practice. Note that you do not need to minimize the number of commands in the solution, find any valid sequence of at most three commands.
Input
The first line contains an integer n (2?≤?n?≤?1000) — the number of horses in the row. The second line contains n distinct integers a1,?a2,?...,?an (1?≤?ai?≤?n), where ai is the number of the i-th left horse in the row after the practice.
Output
The first line should contain integer k (0?≤?k?≤?3) — the number of commads Xenia gave during the practice. In each of the next k lines print two integers. In the i-th line print numbers li,?ri (1?≤?li?<?ri?≤?n) — Xenia's i-th command during the practice.
It is guaranteed that a solution exists. If there are several solutions, you are allowed to print any of them.
Sample test(s)
Input
5
1 4 3 2 5
Output
1
2 4
Input
6
2 1 4 3 6 5
Output
3
1 2
3 4
5 6
題意:給出一個序列,經過不超過3次區間翻轉操作變成遞增數列,輸出一種可行解.
?
#include <iostream>
#include
<cstring>
#include
<cstdio>
#include
<algorithm>
using
namespace
std;
const
int
N=
10005
;
struct
node {
int
s, t;
void
init(
int
a,
int
b) {
s
=a, t=
b;
}
} ans[
10
];
int
A[
10
][N], n;
int
checkL(
int
dep) {
if
(A[dep][
1
]!=
1
)
return
1
;
for
(
int
i=
2
; i<=n; i++)
if
(A[dep][i]!=A[dep][i-
1
]+
1
)
return
i;
return
-
1
;
}
int
checkR(
int
dep) {
if
(A[dep][n]!=n)
return
n;
for
(
int
i=n-
1
; i>=
1
; i--)
if
(A[dep][i]!=A[dep][i+
1
]-
1
)
return
i;
return
-
1
;
}
int
findpos(
int
dep,
int
val) {
for
(
int
i=
1
; i<=n; i++)
if
(A[dep][i]==val)
return
i;
}
bool
DFS(
int
dep) {
if
(dep==
3
)
if
(checkL(dep)!=-
1
)
return
false
;
else
{
printf(
"
%d\n
"
, dep);
for
(
int
i=dep-
1
; i>=
0
; i--) printf(
"
%d %d\n
"
, ans[i].s, ans[i].t);
return
true
;
}
int
L=checkL(dep), R=
checkR(dep);
if
(L==-
1
|| R==-
1
) {
printf(
"
%d\n
"
, dep);
for
(
int
i=dep-
1
; i>=
0
; i--) printf(
"
%d %d\n
"
, ans[i].s, ans[i].t);
return
true
;
}
for
(
int
i=
1
; i<=n; i++) A[dep+
1
][i]=
A[dep][i];
int
Lpos=findpos(dep+
1
, L), Rpos=findpos(dep+
1
, R);
reverse(A[dep
+
1
]+L, A[dep+
1
]+Lpos+
1
);
ans[dep].init(L, Lpos);
if
(DFS(dep+
1
))
return
true
;
reverse(A[dep
+
1
]+L, A[dep+
1
]+Lpos+
1
);
ans[dep].init(Rpos, R);
reverse(A[dep
+
1
]+Rpos, A[dep+
1
]+R+
1
);
if
(DFS(dep+
1
))
return
true
;
reverse(A[dep
+
1
]+Rpos, A[dep+
1
]+R+
1
);
return
false
;
}
int
main() {
scanf(
"
%d
"
, &
n);
for
(
int
i=
1
; i<=n; i++) scanf(
"
%d
"
, &A[
0
][i]);
DFS(
0
);
return
0
;
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
