250PProblem Statement |
|||||||||||||
| Manao has N cards arranged in a sequence. He numbered them from left
to right with numbers from 0 to N-1. Each card is colored black on
one side and white on the other. Initially, each of the cards may
lie on a different side. That is, some of the cards (possibly none
or all of them) will be black side up and others will be white side
up. Manao wants to flip some cards over to obtain an alternating
configuration: every pair of successive cards must be of different
colors. You are given a string cardFront consisting of N characters. For each i, character i of cardFront is 'B' if card i lies black side up, and 'W' otherwise. Count and return the minimum number of cards which must be flipped to obtain an alternating configuration. |
|||||||||||||
Definition |
|||||||||||||
|
|||||||||||||
Constraints |
|||||||||||||
| - | cardFront will be between 3 and 50 characters long, inclusive. | ||||||||||||
| - | Each character in cardFront will be either 'B' or 'W'. | ||||||||||||
Examples |
|||||||||||||
| 0) | |||||||||||||
|
|||||||||||||
| 1) | |||||||||||||
|
|||||||||||||
| 2) | |||||||||||||
|
|||||||||||||
| 3) | |||||||||||||
|
|||||||||||||
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
[Thought]
很简单，题目只有两种模式“BWBWBW..."或者“WBWBWB....”,对于两种模式各做一次统计，然后取最小值即可。
[Code]
1: #include <string>
2: using namespace std;
3: class BlackAndWhiteSolitaire
4: {
5: public:
6: int minimumTurns(string cardFront);
7: };
8: int BlackAndWhiteSolitaire::minimumTurns(string cardFront)
9: {
10: int len = cardFront.size();
11: int turn1 =0, turn2 =0;
12: string sample1 = "BW";
13: string sample2 = "WB";
14: for(int i =0; i< len; i++)
15: {
16: if(sample1[i%2] != cardFront[i])
17: turn1++;
18: if(sample2[i%2] != cardFront[i])
19: turn2++;
20: }
21: return min(turn1, turn2);
22: }
500P
Problem Statement |
|||||||||||||
| There is a long narrow storehouse. The storehouse is divided into a
sequence of N identical sectors, labeled 0 through N-1. Each sector
is large enough to contain a single container. Currently, some
sectors are empty and some sectors are filled by containers. The
storehouse also contains a surveillance system that is described
below. We are going to break into the storehouse. As a part of preparation for the heist, we already found out some information about the warehouse. In particular, we know exactly how the containers are currently placed in the warehouse. You are given a String containers consisting of N characters. For each i, character i of containers is 'X' if sector i contains a container, and it is '-' if sector i is empty. We also discovered some information about the surveillance system. The system consists of several hidden cameras. You are given a int L with the following meaning: Each of the cameras monitors exactly L consecutive sectors. The segments of sectors monitored by different cameras might overlap, but no two cameras watch exactly the same segment. (In other words, each sector may be monitored by multiple cameras, but each camera monitors a different set of consecutive sectors.) Finally, we know something about what the cameras currently see. You are given a int[] reports. Each element of reports corresponds to one of the cameras (in no particular order). More precisely, reports[i] is the number of containers stored in the sectors monitored by the corresponding camera. It is guaranteed that all our information is correct and consistent. Your task is to use the provided information to deduce which sectors are monitored by at least one surveillance camera. Return a String containing N characters. For each i, character i of the return value should be one of '+', '?', and '-'. Character '+' represents that sector i is certainly monitored by at least one camera. Character '-' represents that sector i is certainly not monitored by any of the cameras. Character '?' represents the remaining case: given the information we have, it is possible that sector i is monitored, but it is also possible that it is not monitored. |
|||||||||||||
Definition |
|||||||||||||
|
|||||||||||||
Constraints |
|||||||||||||
| - | containers will contain N elements, where N is between 1 and 50, inclusive. | ||||||||||||
| - | Each character in containers will be either 'X' or '-'. | ||||||||||||
| - | L will be between 1 and N, inclusive. | ||||||||||||
| - | reports will contain between 1 and N-L+1 elements, inclusive. | ||||||||||||
| - | Each element of reports will be between 0 and L, inclusive. | ||||||||||||
| - | The given information will be consistent. | ||||||||||||
Examples |
|||||||||||||
| 0) | |||||||||||||
|
|||||||||||||
| 1) | |||||||||||||
|
|||||||||||||
| 2) | |||||||||||||
|
|||||||||||||
| 3) | |||||||||||||
|
|||||||||||||
| 4) | |||||||||||||
|
|||||||||||||
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
[Thoughts]
这道500分的题挺直观。其实就是一个概率覆盖的问题。
首先对于输入字符串，进行一次预处理。统计下来，对于任意[i, i+L)区间内，有多少container。
然后处理camera信息，统计对于每一个监控数量i的出现次数。以测试用例3 为例，监控数量为1的camera共有两个，这就意味这，有两个不相同的区间只包含一个container， 那么在输入字符串中，我们可以发现有如下四个区间只包含一个container，我们将每个区间值都标识为1，表示出现一次。
- X X X X X - - - X - -
1 1 1
1 1 1
1 1 1
1 1 1
-------------------------------
1 1 2 2 3 2 1
在此，将出现概率加和，可以发现，如果四个区间里面选两个出来的话，只有出现概率>(4-2) (抽屉原理)的container才会必然被监控到。
假设D[K]表示，输入字符串中包含K个container的区间数量，那么处理camera的条件只有两个， 对于任意监控数量K
1. 如果K>= D[K], 那么将所有包含K个container的区间置为‘+’
2. 如果K<D[K],即如上例，那么将所有出现概率>(D[K]-K)的位置置为‘+’，其余位置置为'?'
[Code]
1: #include <vector>
2: #include <string>
3: #include <map>
4: #include <bitset>
5: using namespace std;
6: class SurveillanceSystem
7: {
8: public:
9: string getContainerInfo(string containers, vector <int> reports, int L)
10: {
11: sort(reports.begin(), reports.end());
12: string target(containers.size(), '-');
13: map<int, vector<int> > lengthDir;
14: int pre=0, cur = 0, count=0; //two-pointer scan
15: for(int i =0; i<L; i++)
16: {
17: if(containers[i] =='X')
18: count++;
19: pre++;
20: }
21: vector<int>* dir = &lengthDir[count];
22: dir->push_back(cur);
23: while(pre< containers.size())
24: {
25: if(containers[pre] == 'X')
26: count++;
27: if(containers[cur] == 'X')
28: count--;
29: pre++;
30: cur++;
31: vector<int>* dir = &lengthDir[count];
32: dir->push_back(cur);
33: }
34: bitset<51> doubtless, doubt;
35: int expectCount;
36: int report;
37: for(int length =0; length<reports.size(); length++)
38: {
39: expectCount=1;
40: report = reports[length];
41: while(length<reports.size()-1 && reports[length] == reports[length+1])
42: {
43: expectCount++;
44: length++;
45: }
46: if(expectCount < lengthDir[report].size())// for exmple, expect 1 camera watching 3 storages, but there are muiltiple choice
47: {
48: int counter[51];
49: memset(counter, 0, sizeof(counter));
50: for(int k =0; k< lengthDir[report].size(); k++ )
51: {
52: for(int j =0; j<L; j++)
53: {
54: counter[lengthDir[report][k] +j] ++;
55: }
56: }
57: for(int k =0; k< target.size(); k++)
58: {
59: if(counter[k] ==0) continue;
60: if(expectCount > lengthDir[report].size() - counter[k])
61: doubtless.set(k,1);
62: else
63: doubt.set(k,1);
64: }
65: }
66: else
67: {
68: for(int k =0; k< lengthDir[report].size(); k++ )
69: {
70: for(int j =0; j<L; j++)
71: {
72: doubtless.set(lengthDir[report][k]+j,1);
73: }
74: }
75: }
76: }
77: for(int i =0; i< target.size();i++)
78: {
79: if(doubtless[i] ==1)
80: target[i] ='+';
81: else if(doubt[i] ==1)
82: target[i] ='?';
83: }
84: return target;
85: }
86: };
1000P
Problem Statement |
|||||||||||||
|
This problem statement contains superscripts and/or subscripts.
These may not display properly outside the applet. Manao is studying graph theory and simple cycles in particular. A simple cycle of length L ≥ 3 in graph G is a sequence of vertices (v0, v1, ..., vL-1) such that all v0, v1, ..., vL-1 are pairwise distinct and for each i=0..L-1, an edge between vi and v(i+1) mod L exists in G. Manao is interested in graphs formed by connecting two trees. The connection process is as follows. Manao takes two trees composed of N vertices each. The vertices in each tree are labeled from 0 to N - 1. Then, he generates some permutation P of numbers from 0 to N - 1. Finally, the graph is formed by connecting vertex i of the first tree to vertex P[i] of the second tree, for each i from 0 to N - 1. To remove ambiguity, the vertices of the first tree within the graph are referred to as A0, A1, ..., AN-1 and the vertices of the second graph are referred to as B0, B1, ..., BN-1. Manao wants to know the maximum number of simple cycles of length K which the resulting graph could contain if he chooses P optimally. You are given two String[]s, tree1 and tree2. Both contain N elements, each of them N characters long. The j-th character in the i-th element of tree1 is 'X' if vertices i and j in the first tree are connected and '-' otherwise. tree2 describes the second tree in the same fashion. Compute and return the maximum possible number of simple cycles of length K in the graph formed by connecting the two given trees as described above. Two simple cycles are equal if one of them can be cyclically shifted, or reversed and cyclically shifted, to coincide with the second. According to this definition, (1, 2, 3, 4), (2, 3, 4, 1) and (3, 2, 1, 4) are all equal. |
|||||||||||||
Definition |
|||||||||||||
|
|||||||||||||
Constraints |
|||||||||||||
| - | tree1 and tree2 will each contain N elements, where N is between 1 and 9, inclusive. | ||||||||||||
| - | Each element of tree1 and tree2 will be N characters long. | ||||||||||||
| - | Each element of tree1 and tree2 will consist of 'X' and '-' characters only. | ||||||||||||
| - | tree1[i][i] and tree2[i][i] will be '-' for each i between 0 and N-1. | ||||||||||||
| - | tree1[i][j] will be equal to tree1[j][i] for each i, j between 0 and N-1. | ||||||||||||
| - | tree2[i][j] will be equal to tree2[j][i] for each i, j between 0 and N-1. | ||||||||||||
| - | Both tree1 and tree2 will describe a graph which is a tree. | ||||||||||||
| - | K will be between 3 and 7, inclusive. | ||||||||||||
Examples |
|||||||||||||
| 0) | |||||||||||||
|
|||||||||||||
| 1) | |||||||||||||
|
|||||||||||||
| 2) | |||||||||||||
|
|||||||||||||
| 3) | |||||||||||||
|
|||||||||||||
| 4) | |||||||||||||
|
|||||||||||||
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
[Thoughts]
还没做
No comments:
Post a Comment