完了,这次做扯了,做的时候有点发烧,居然只做出来一道题,差点被绿.
| # | When | Who | Problem | Lang | Verdict | Time | Memory |
|---|---|---|---|---|---|---|---|
| 4434550 | Sep 9, 2013 11:57:20 AM | OIer | E - Xenia and Tree | GNU C++ | Accepted | 842 ms | 4260 KB |
| 4434547 | Sep 9, 2013 11:56:11 AM | OIer | E - Xenia and Tree | GNU C++ | Wrong answer on test 4 | 280 ms | 3400 KB |
| 4434544 | Sep 9, 2013 11:54:50 AM | OIer | E - Xenia and Tree | GNU C++ | Memory limit exceeded on test 4 | 966 ms | 262100 KB |
| 4434534 | Sep 9, 2013 11:50:15 AM | OIer | E - Xenia and Tree | GNU C++ | Memory limit exceeded on test 4 | 748 ms | 262100 KB |
| 4434506 | Sep 9, 2013 11:33:28 AM | OIer | E - Xenia and Tree | GNU C++ | Time limit exceeded on test 19 | 5000 ms | 4200 KB |
| 4434474 | Sep 9, 2013 11:15:59 AM | OIer | E - Xenia and Tree | GNU C++ | Accepted | 748 ms | 3600 KB |
| 4434179 | Sep 9, 2013 8:45:13 AM | OIer | D - Xenia and Dominoes | GNU C++ | Accepted | 30 ms | 600 KB |
| 4431354 | Sep 8, 2013 1:42:22 PM | OIer | C - Cupboard and Balloons | GNU C++ | Accepted | 30 ms | 0 KB |
| 4431256 | Sep 8, 2013 1:16:19 PM | OIer | C - Cupboard and Balloons | GNU C++ | Wrong answer on test 17 | 30 ms | 0 KB |
| 4431247 | Sep 8, 2013 1:14:03 PM | OIer | B - Xenia and Spies | GNU C++ | Accepted | 124 ms | 1200 KB |
| 4431244 | Sep 8, 2013 1:13:33 PM | OIer | B - Xenia and Spies | GNU C++ | Wrong answer on test 1 | 0 ms | 1300 KB |
| 4431210 | Sep 8, 2013 1:00:11 PM | OIer | B - Xenia and Spies | GNU C++ | Wrong answer on test 3 | 30 ms | 1100 KB |
| # | When | Who | Problem | Lang | Verdict | Time | Memory |
|---|---|---|---|---|---|---|---|
| 4424854 | Sep 7, 2013 1:53:25 PM | OIer | B - Xenia and Spies | GNU C++ | Wrong answer on pretest 2 | 30 ms | 1100 KB |
| 4424797 | Sep 7, 2013 1:52:36 PM | OIer | B - Xenia and Spies | GNU C++ | Wrong answer on pretest 1 | 0 ms | 1300 KB |
| 4422952 | Sep 7, 2013 1:21:08 PM | OIer | A - Xenia and Divisors | GNU C++ | Accepted | 30 ms | 400 KB |
| 4422863 | Sep 7, 2013 1:19:32 PM | OIer | C - Cupboard and Balloons | GNU C++ | Hacked | 30 ms | 0 KB |
| 4422366 | Sep 7, 2013 1:11:51 PM | OIer | C - Cupboard and Balloons | GNU C++ | Wrong answer on pretest 6 | 30 ms | 0 KB |
| 4420785 | Sep 7, 2013 12:50:12 PM | OIer | C - Cupboard and Balloons | GNU C++ | Wrong answer on pretest 6 | 30 ms | 0 KB |
| 4417237 | Sep 7, 2013 12:10:37 PM | OIer | A - Xenia and Divisors | GNU C++ | Hacked | 30 ms | 400 KB |
Xenia the mathematician has a sequence consisting of n ( n is divisible by 3) positive integers, each of them is at most 7. She wants to split the sequence into groups of three so that for each group of three a , b , c the following conditions held:
- a < b < c ;
- a divides b , b divides c .
Naturally, Xenia wants each element of the sequence to belong to exactly one group of three. Thus, if the required partition exists, then it has
groups of three.
Help Xenia, find the required partition or else say that it doesn't exist.
The first line contains integer n (3 ≤ n ≤ 99999) — the number of elements in the sequence. The next line contains n positive integers, each of them is at most 7.
It is guaranteed that n is divisible by 3.
If the required partition exists, print
groups of three. Print each group as values of the elements it contains. You should print values in increasing order. Separate the groups and integers in groups by whitespaces. If there are multiple solutions, you can print any of them.
If there is no solution, print -1.
/*
1 2 4
1 2 6
1 3 6
*/
#include
<stdio.h>
#include
<
string
.h>
int
a[
100010
],w[
8
];
int
N;
int
main()
{
//
freopen("input.txt","r",stdin);
while
(scanf(
"
%d
"
,&N)!=
EOF)
{
memset(w,
0
,
sizeof
(w));
for
(
int
i=
1
;i<=N;i++
)
{
scanf(
"
%d
"
,&
a[i]);
w[a[i]]
++
;
}
if
(w[
1
]!=(N/
3
) || w[
2
]+w[
3
]!=w[
4
]+w[
6
] || w[
2
]<w[
4
] || w[
6
]<w[
3
] || w[
5
] || w[
7
])
{
printf(
"
-1\n
"
);
continue
;
}
for
(
int
i=
1
;i<=w[
4
];i++) printf(
"
1 2 4\n
"
);
for
(
int
i=
1
;i<=w[
2
]-w[
4
];i++) printf(
"
1 2 6\n
"
);
for
(
int
i=
1
;i<=w[
3
];i++) printf(
"
1 3 6\n
"
);
}
return
0
;
}
Xenia the vigorous detective faced n ( n ≥ 2) foreign spies lined up in a row. We'll consider the spies numbered from 1 to n from left to right.
Spy s has an important note. He has to pass the note to spy f . Xenia interrogates the spies in several steps. During one step the spy keeping the important note can pass the note to one of his neighbours in the row. In other words, if this spy's number is x , he can pass the note to another spy, either x - 1 or x + 1 (if x = 1 or x = n , then the spy has only one neighbour). Also during a step the spy can keep a note and not pass it to anyone.
But nothing is that easy. During m steps Xenia watches some spies attentively. Specifically, during step t i (steps are numbered from 1) Xenia watches spies numbers l i , l i + 1, l i + 2, ..., r i (1 ≤ l i ≤ r i ≤ n ) . Of course, if during some step a spy is watched, he can't do anything: neither give the note nor take it from some other spy. Otherwise, Xenia reveals the spies' cunning plot. Nevertheless, if the spy at the current step keeps the note, Xenia sees nothing suspicious even if she watches him.
You've got s and f . Also, you have the steps during which Xenia watches spies and which spies she is going to watch during each step. Find the best way the spies should act in order to pass the note from spy s to spy f as quickly as possible (in the minimum number of steps).
The first line contains four integers n , m , s and f (1 ≤ n , m ≤ 10 5 ; 1 ≤ s , f ≤ n ; s ≠ f ; n ≥ 2) . Each of the following m lines contains three integers t i , l i , r i (1 ≤ t i ≤ 10 9 , 1 ≤ l i ≤ r i ≤ n ) . It is guaranteed that t 1 < t 2 < t 3 < ... < t m .
Print k characters in a line: the i -th character in the line must represent the spies' actions on step i . If on step i the spy with the note must pass the note to the spy with a lesser number, the i -th character should equal " L ". If on step i the spy with the note must pass it to the spy with a larger number, the i -th character must equal " R ". If the spy must keep the note at the i -th step, the i -th character must equal " X ".
As a result of applying the printed sequence of actions spy s must pass the note to spy f . The number of printed characters k must be as small as possible. Xenia must not catch the spies passing the note.
If there are miltiple optimal solutions, you can print any of them. It is guaranteed that the answer exists.
#include<stdio.h>
#include
<
string
.h>
int
cur,dir,CT;
int
T[
100010
],L[
100010
],R[
100010
];
void
go()
{
if
(dir==
1
) putchar(
'
R
'
);
else
putchar(
'
L
'
);
cur
+=
dir;
}
int
main()
{
int
N,M,S,F;
while
(scanf(
"
%d%d%d%d
"
,&N,&M,&S,&F)!=
EOF)
{
memset(T,
0
,
sizeof
(T));
for
(
int
i=
1
;i<=M;i++) scanf(
"
%d%d%d
"
,&T[i],&L[i],&
R[i]);
cur
=S,dir=S<F ?
1
:-
1
,CT=
1
;
for
(
int
i=
1
;i<=
0x7FFFFFFF
;i++
)
{
if
(cur==F)
break
;
if
(i==
T[CT])
{
if
((L[CT]<=cur && cur<=R[CT]) || (L[CT]<=cur+dir && cur+dir<=R[CT])) putchar(
'
X
'
);
else
go();
CT
++
;
}
else
go();
}
printf(
"
\n
"
);
}
return
0
;
}
A girl named Xenia has a cupboard that looks like an arc from ahead. The arc is made of a semicircle with radius r (the cupboard's top) and two walls of height h (the cupboard's sides). The cupboard's depth is r , that is, it looks like a rectangle with base r and height h + r from the sides. The figure below shows what the cupboard looks like (the front view is on the left, the side view is on the right).
Xenia got lots of balloons for her birthday. The girl hates the mess, so she wants to store the balloons in the cupboard. Luckily, each balloon is a sphere with radius . Help Xenia calculate the maximum number of balloons she can put in her cupboard.
You can say that a balloon is in the cupboard if you can't see any part of the balloon on the left or right view. The balloons in the cupboard can touch each other. It is not allowed to squeeze the balloons or deform them in any way. You can assume that the cupboard's walls are negligibly thin.
The single line contains two integers r , h (1 ≤ r , h ≤ 10 7 ) .
Print a single integer — the maximum number of balloons Xenia can put in the cupboard.
#include<math.h>
#include
<stdio.h>
int
main()
{
int
R,H;
while
(scanf(
"
%d%d
"
,&R,&H)!=
EOF)
{
int
ans=H/R*
2
;
H
-=ans*R/
2
;
if
(H*
2
<R) ans++
;
else
{
if
((
double
)(
2
*H)<sqrt(
3.0
)*(
double
)R) ans+=
2
;
else
ans+=
3
;
}
printf(
"
%d\n
"
,ans);
}
return
0
;
}
Xenia likes puzzles very much. She is especially fond of the puzzles that consist of domino pieces. Look at the picture that shows one of such puzzles.
A puzzle is a 3 × n table with forbidden cells (black squares) containing dominoes (colored rectangles on the picture). A puzzle is called correct if it meets the following conditions:
- each domino occupies exactly two non-forbidden cells of the table;
- no two dominoes occupy the same table cell;
- exactly one non-forbidden cell of the table is unoccupied by any domino (it is marked by a circle in the picture).
To solve the puzzle, you need multiple steps to transport an empty cell from the starting position to some specified position. A move is transporting a domino to the empty cell, provided that the puzzle stays correct. The horizontal dominoes can be moved only horizontally, and vertical dominoes can be moved only vertically. You can't rotate dominoes. The picture shows a probable move.
Xenia has a 3 × n table with forbidden cells and a cell marked with a circle. Also, Xenia has very many identical dominoes. Now Xenia is wondering, how many distinct correct puzzles she can make if she puts dominoes on the existing table. Also, Xenia wants the circle-marked cell to be empty in the resulting puzzle. The puzzle must contain at least one move.
Help Xenia, count the described number of puzzles. As the described number can be rather large, print the remainder after dividing it by 1000000007 (10 9 + 7) .
The first line contains integer n (3 ≤ n ≤ 10 4 ) — the puzzle's size. Each of the following three lines contains n characters — the description of the table. The j -th character of the i -th line equals " X " if the corresponding cell is forbidden; it equals " . ", if the corresponding cell is non-forbidden and " O ", if the corresponding cell is marked with a circle.
It is guaranteed that exactly one cell in the table is marked with a circle. It is guaranteed that all cells of a given table having at least one common point with the marked cell is non-forbidden.
Print a single number — the answer to the problem modulo 1000000007 (10 9 + 7) .
题意:有一个3*n的矩形,除其中标为X或O的点之外的点用1*2的矩形覆盖,求有多少种发难.要求标为O的点周围存在可以移动的1*2矩形.
思路:位DP?还是状态压缩?我不太清楚这分类.f[i][j]表示填充到第i列,状态为j的方案数.其中j∈[0,7],其二进制表示第k行是否被占用.因为O点周围必须有能移动的小矩形,所以枚举小矩形的位置,分别有可能在左右或下.然后用容斥原理排除多余解.
#include<stdio.h>
#include
<
string
.h>
const
__int64 MOD=
1000000007
;
__int64 dp[
10025
][
8
];
char
ch[
3
][
10025
];
int
N;
__int64 DP()
{
memset(dp,
0
,
sizeof
(dp));
dp[
0
][
0
]=
1
;
for
(
int
i=
0
;i<N;i++
)
for
(
int
j=
0
;j<
8
;j++
)
{
bool
v[
3
];
for
(
int
k=
0
;k<
3
;k++
)
{
v[k]
=j >> k &
1
^
1
;
if
(ch[k][i]==
'
X
'
)
{
if
(v[k]==
false
) dp[i][j]=
0
;
v[k]
=
false
;
}
}
if
(dp[i][j]==
0
)
continue
;
if
(v[
0
])
{
if
(v[
1
])
{
if
(v[
2
])
{
(dp[i
+
1
][
7
]+=dp[i][j])%=
MOD;
(dp[i
+
1
][
1
]+=dp[i][j])%=
MOD;
(dp[i
+
1
][
4
]+=dp[i][j])%=
MOD;
}
else
{
(dp[i
+
1
][
3
]+=dp[i][j])%=
MOD;
(dp[i
+
1
][
0
]+=dp[i][j])%=
MOD;
}
}
else
{
if
(v[
2
])
{
(dp[i
+
1
][
5
]+=dp[i][j])%=
MOD;
}
else
{
(dp[i
+
1
][
1
]+=dp[i][j])%=
MOD;
}
}
}
else
{
if
(v[
1
])
{
if
(v[
2
])
{
(dp[i
+
1
][
6
]+=dp[i][j])%=
MOD;
(dp[i
+
1
][
0
]+=dp[i][j])%=
MOD;
}
else
{
(dp[i
+
1
][
2
]+=dp[i][j])%=
MOD;
}
}
else
{
if
(v[
2
])
{
(dp[i
+
1
][
4
]+=dp[i][j])%=
MOD;
}
else
{
(dp[i
+
1
][
0
]+=dp[i][j])%=
MOD;
}
}
}
}
return
(dp[N][
0
]);
}
int
main()
{
int
sx,sy;
while
(scanf(
"
%d
"
,&N)!=
EOF)
{
for
(
int
i=
0
;i<
3
;i++) scanf(
"
%s
"
,ch[i]);
for
(
int
i=
0
;i<
3
;i++
)
for
(
int
j=
0
;j<N;j++
)
if
(ch[i][j]==
'
O
'
)
{
sx
=
i;
sy
=
j;
ch[i][j]
=
'
X
'
;
}
if
(sx==
2
)
{
for
(
int
i=
0
;i<N;i++
)
{
char
tmp=ch[
0
][i];
ch[
0
][i]=ch[
2
][i];
ch[
2
][i]=
tmp;
}
sx
=
0
;
}
ch[
0
][N]=ch[
1
][N]=ch[
2
][N]=
'
X
'
;
bool
f1=
false
,f2=
false
,f3=
false
;
__int64 ans
=
0
;
if
(sy>
1
&& ch[sx][sy-
1
]==
'
.
'
&& ch[sx][sy-
2
]==
'
.
'
)
{
f1
=
true
;
ch[sx][sy
-
1
]=ch[sx][sy-
2
]=
'
X
'
;
ans
=(ans+DP())%
MOD;
ch[sx][sy
-
1
]=ch[sx][sy-
2
]=
'
.
'
;
}
if
(sy<N-
2
&& ch[sx][sy+
1
]==
'
.
'
&& ch[sx][sy+
2
]==
'
.
'
)
{
f2
=
true
;
ch[sx][sy
+
1
]=ch[sx][sy+
2
]=
'
X
'
;
ans
=(ans+DP())%
MOD;
ch[sx][sy
+
1
]=ch[sx][sy+
2
]=
'
.
'
;
}
if
(sx==
0
&& ch[sx+
1
][sy]==
'
.
'
&& ch[sx+
2
][sy]==
'
.
'
)
{
f3
=
true
;
ch[sx
+
1
][sy]=ch[sx+
2
][sy]=
'
X
'
;
ans
=(ans+DP())%
MOD;
ch[sx
+
1
][sy]=ch[sx+
2
][sy]=
'
.
'
;
}
if
(f1 &&
f2)
{
ch[sx][sy
-
1
]=ch[sx][sy-
2
]=ch[sx][sy+
1
]=ch[sx][sy+
2
]=
'
X
'
;
ans
=(ans+MOD-DP())%
MOD;
ch[sx][sy
-
1
]=ch[sx][sy-
2
]=ch[sx][sy+
1
]=ch[sx][sy+
2
]=
'
.
'
;
}
if
(f1 &&
f3)
{
ch[sx][sy
-
1
]=ch[sx][sy-
2
]=ch[sx+
1
][sy]=ch[sx+
2
][sy]=
'
X
'
;
ans
=(ans+MOD-DP())%
MOD;
ch[sx][sy
-
1
]=ch[sx][sy-
2
]=ch[sx+
1
][sy]=ch[sx+
2
][sy]=
'
.
'
;
}
if
(f2 &&
f3)
{
ch[sx][sy
+
1
]=ch[sx][sy+
2
]=ch[sx+
1
][sy]=ch[sx+
2
][sy]=
'
X
'
;
ans
=(ans+MOD-DP())%
MOD;
ch[sx][sy
+
1
]=ch[sx][sy+
2
]=ch[sx+
1
][sy]=ch[sx+
2
][sy]=
'
.
'
;
}
if
(f1 && f2 &&
f3)
{
ch[sx][sy
-
1
]=ch[sx][sy-
2
]=ch[sx][sy+
1
]=ch[sx][sy+
2
]=ch[sx+
1
][sy]=ch[sx+
2
][sy]=
'
X
'
;
ans
=(ans+DP())%
MOD;
ch[sx][sy
-
1
]=ch[sx][sy-
2
]=ch[sx][sy+
1
]=ch[sx][sy+
2
]=ch[sx+
1
][sy]=ch[sx+
2
][sy]=
'
.
'
;
}
printf(
"
%I64d\n
"
,ans);
}
return
0
;
}
Xenia the programmer has a tree consisting of n nodes. We will consider the tree nodes indexed from 1 to n . We will also consider the first node to be initially painted red, and the other nodes — to be painted blue.
The distance between two tree nodes v and u is the number of edges in the shortest path between v and u .
Xenia needs to learn how to quickly execute queries of two types:
- paint a specified blue node in red;
- calculate which red node is the closest to the given one and print the shortest distance to the closest red node.
Your task is to write a program which will execute the described queries.
The first line contains two integers n and m (2 ≤ n ≤ 10 5 , 1 ≤ m ≤ 10 5 ) — the number of nodes in the tree and the number of queries. Next n - 1 lines contain the tree edges, the i -th line contains a pair of integers a i , b i (1 ≤ a i , b i ≤ n , a i ≠ b i ) — an edge of the tree.
Next m lines contain queries. Each query is specified as a pair of integers t i , v i (1 ≤ t i ≤ 2, 1 ≤ v i ≤ n ) . If t i = 1 , then as a reply to the query we need to paint a blue node v i in red. If t i = 2 , then we should reply to the query by printing the shortest distance from some red node to node v i .
It is guaranteed that the given graph is a tree and that all queries are correct.
For each second type query print the reply in a single line.
1 2
2 3
2 4
4 5
2 1
2 5
1 2
2 5
#include<stdio.h>
#include
<
string
.h>
#include
<queue>
using
namespace
std;
struct
node
{
int
x,step,pre;
};
int
d[
100010
];
vector
<
int
> G[
100010
];
bool
col[
100010
];
void
bfs(
int
s)
{
queue
<
int
>
q;
while
(!
q.empty()) q.pop();
q.push(s);
d[s]
=
0
;
col[s]
=
true
;
while
(!
q.empty())
{
int
x=
q.front();
q.pop();
for
(
int
i=
0
;i<G[x].size();i++
)
{
int
v=
G[x][i];
if
(d[v]>d[x]+
1
)
{
d[v]
=d[x]+
1
;
q.push(v);
}
}
}
}
int
BFS(
int
s)
{
if
(col[s])
return
0
;
queue
<node>
q;
while
(!
q.empty()) q.pop();
node S;
S.x
=
s;
S.step
=
0
;
S.pre
=
0
;
q.push(S);
while
(!
q.empty())
{
S
=
q.front();
q.pop();
for
(
int
i=
0
;i<G[S.x].size();i++
)
{
int
v=
G[S.x][i];
if
(v==S.pre)
continue
;
if
(col[v])
return
S.step+
1
;
else
{
node tmp;
tmp.x
=
v;
tmp.step
=S.step+
1
;
tmp.pre
=
S.x;
q.push(tmp);
}
}
}
}
int
main()
{
int
N,M;
while
(scanf(
"
%d%d
"
,&N,&M)!=
EOF)
{
for
(
int
i=
1
;i<=N;i++
) G[i].clear();
for
(
int
i=
1
;i<N;i++
)
{
int
x,y;
scanf(
"
%d%d
"
,&x,&
y);
G[x].push_back(y);
G[y].push_back(x);
}
for
(
int
i=
1
;i<=N;i++) d[i]=
0x7FFFFFFF
;
memset(col,
false
,
sizeof
(col));
col[
1
]=
true
;
bfs(
1
);
int
cnt=
0
;
for
(
int
i=
1
;i<=M;i++
)
{
int
Q,P;
scanf(
"
%d%d
"
,&Q,&
P);
if
(Q==
1
)
{
cnt
++
;
if
(cnt<
500
) bfs(P);
else
col[P]=
true
;
}
else
{
if
(cnt<
500
) printf(
"
%d\n
"
,d[P]);
else
printf(
"
%d\n
"
,BFS(P));
}
}
}
return
0
;
}
