Codeforces Round #297 (Div. 2) (ABCDE题解)
- WBOY원래의
- 2016-06-07 15:26:051360검색
比赛链接：http://codeforces.com/contest/525 算是比较简单的一场了，拖了好久现在才补 A. Vitaliy and Pie time limit per test：2 seconds memory limit per test：256 megabytes After a hard day Vitaly got very hungry and he wants to eat his favor
比赛链接：http://codeforces.com/contest/525
算是比较简单的一场了，拖了好久现在才补
A. Vitaliy and Pie
time limit per test：2 seconds
memory limit per test：256 megabytes
After a hard day Vitaly got very hungry and he wants to eat his favorite potato pie. But it's not that simple. Vitaly is in the first room of the house with n room located in a line and numbered starting from one from left to right. You can go from the first room to the second room, from the second room to the third room and so on — you can go from the (n?-?1)-th room to the n-th room. Thus, you can go to room x only from room x?-?1.
The potato pie is located in the n-th room and Vitaly needs to go there.
Each pair of consecutive rooms has a door between them. In order to go to room x from room x?-?1, you need to open the door between the rooms with the corresponding key.
In total the house has several types of doors (represented by uppercase Latin letters) and several types of keys (represented by lowercase Latin letters). The key of type t can open the door of type T if and only if t and T are the same letter, written in different cases. For example, key f can open door F.
Each of the first n?-?1 rooms contains exactly one key of some type that Vitaly can use to get to next rooms. Once the door is open with some key, Vitaly won't get the key from the keyhole but he will immediately run into the next room. In other words, each key can open no more than one door.
Vitaly realizes that he may end up in some room without the key that opens the door to the next room. Before the start his run for the potato pie Vitaly can buy any number of keys of any type that is guaranteed to get to room n.
Given the plan of the house, Vitaly wants to know what is the minimum number of keys he needs to buy to surely get to the room n, which has a delicious potato pie. Write a program that will help Vitaly find out this number.
Input
The first line of the input contains a positive integer n (2?≤?n?≤?105) — the number of rooms in the house.
The second line of the input contains string s of length 2·n?-?2. Let's number the elements of the string from left to right, starting from one.
The odd positions in the given string s contain lowercase Latin letters — the types of the keys that lie in the corresponding rooms. Thus, each odd position i of the given string s contains a lowercase Latin letter — the type of the key that lies in room number (i?+?1)?/?2.
The even positions in the given string contain uppercase Latin letters — the types of doors between the rooms. Thus, each even position i of the given string s contains an uppercase letter — the type of the door that leads from room i?/?2 to room i?/?2?+?1.
Output
Print the only integer — the minimum number of keys that Vitaly needs to buy to surely get from room one to room n.
Sample test(s)
Input
<span>3 aAbB </span>
Output
<span>0 </span>
Input
<span>4 aBaCaB </span>
Output
<span>3 </span>
Input
<span>5 xYyXzZaZ </span>
Output
<span>2 </span>
题目大意：有n－1个门大写字母表示，n－1把钥匙小写字母表示，大小写相对应的钥匙能开相对应的门，每次遇到一个钥匙可以将它收起来或者直接使用，用过一次就没了，问最少还要买多少钥匙才能通过所有的门
题目分析：hash存一下，简单模拟
#include <cstdio>
#include <cstring>
int const MAX = 1e6;
char s[MAX];
int hash[60];
int main()
{
int n, ans = 0;
scanf("%d %s", &n, s);
int len = strlen(s);
memset(hash, 0, sizeof(hash));
for(int i = 0; i = 'a' && s[i] <br>
<br>
<p><br>
</p>
<p><br>
</p>
<p>
</p>
<p>
</p>
<p>
</p>
<p>
</p>
<p><span>B. Pasha and String</span></p>
<p>
</p>
<p><span>time limit per test：2 seconds</span></p>
<p>
</p>
<p><span>memory limit per test：256 megabytes</span></p>
<span><br>
</span>
<p>
</p>
<p><span>Pasha got a very beautiful string <span>
<em>s</em></span> for his birthday, the string consists of lowercase Latin letters. The letters in the string are numbered from 1 to
<span>|<em>s</em>|</span> from left to right, where <span>
|<em>s</em>|</span> is the length of the given string.</span></p>
<p><span>Pasha didn't like his present very much so he decided to change it. After his birthday Pasha spent
<span><em>m</em></span> days performing the following transformations on his string — each day he chose integer
<span><em>a</em><sub><em>i</em></sub></span> and
<span>reversed</span> a piece of string (a segment) from position
<span><em>a</em><sub><em>i</em></sub></span> to position
<span>|<em>s</em>|?-?<em>a</em><sub><em>i</em></sub>?+?1</span>. It is guaranteed that
<span>2·<em>a</em><sub><em>i</em></sub>?≤?|<em>s</em>|</span>.</span></p>
<p><span>You face the following task: determine what Pasha's string will look like after
<span><em>m</em></span> days.</span></p>
<p>
</p>
<p><span>Input</span></p>
<p><span>The first line of the input contains Pasha's string
<span><em>s</em></span> of length from <span>2</span> to
<span>2·10<sup>5</sup></span> characters, consisting of lowercase Latin letters.</span></p>
<p><span>The second line contains a single integer <span>
<em>m</em></span> (<span>1?≤?<em>m</em>?≤?10<sup>5</sup></span>) — the number of days when Pasha changed his string.</span></p>
<p><span>The third line contains <span><em>m</em></span> space-separated elements
<span><em>a</em><sub><em>i</em></sub></span> (<span>1?≤?<em>a</em><sub><em>i</em></sub></span>;
<span>2·<em>a</em><sub><em>i</em></sub>?≤?|<em>s</em>|</span>) — the position from which Pasha started transforming the string on the
<span><em>i</em></span>-th day.</span></p>
<p>
</p>
<p><span>Output</span></p>
<p><span>In the first line of the output print what Pasha's string
<span><em>s</em></span> will look like after <span>
<em>m</em></span> days.</span></p>
<p>
</p>
<p><span>Sample test(s)</span></p>
<p>
</p>
<p>
</p>
<p><span>Input</span></p>
<pre class="brush:php;toolbar:false"><span>abcdef
1
2
</span>
Output
<span>aedcbf </span>
Input
<span>vwxyz 2 2 2 </span>
Output
<span>vwxyz </span>
Input
<span>abcdef 3 1 2 3 </span>
Output
<span>fbdcea</span>
题目大意：给1个字符串长度为len，要操作m次，每次将第a[i]到第len-a[i]+1这段子串逆置，问最终字符串成什么样
题目分析：用reverse函数肯定T，同一个数操作偶数次相当于没动，所以算出要变换奇数次个数的数，交换即可
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char s[200005];
int a[100005];
int main()
{
scanf("%s", s + 1);
int len = strlen(s + 1), m, get;
scanf("%d", &m);
while(m--)
{
scanf("%d", &get);
a[get] ++;
}
for(int i = 1; i <br>
<br>
<p><br>
</p>
<p>
</p>
<p>
</p>
<p>
</p>
<p>
</p>
<p><span>C. Ilya and Sticks</span></p>
<p>
</p>
<p><span>time limit per test：2 seconds</span></p>
<p>
</p>
<p><span>memory limit per test：256 megabytes</span></p>
<span><br>
</span>
<p>
</p>
<p><span>In the evening, after the contest Ilya was bored, and he really felt like maximizing. He remembered that he had a set of
<span><em>n</em></span> sticks and an instrument. Each stick is characterized by its length
<span><em>l</em><sub><em>i</em></sub></span>.</span></p>
<p><span>Ilya decided to make a rectangle from the sticks. And due to his whim, he decided to make rectangles in such a way that maximizes their total area. Each stick is used in making at most one rectangle, it is possible that some
of sticks remain unused. Bending sticks is not allowed.</span></p>
<p><span>Sticks with lengths <span><em>a</em><sub>1</sub></span>,
<span><em>a</em><sub>2</sub></span>, <span>
<em>a</em><sub>3</sub></span> and <span><em>a</em><sub>4</sub></span> can make a rectangle if the following properties are observed:</span></p>
<ul>
<li>
<span><span><em>a</em><sub>1</sub>?≤?<em>a</em><sub>2</sub>?≤?<em>a</em><sub>3</sub>?≤?<em>a</em><sub>4</sub></span></span>
</li>
<li>
<span><span><em>a</em><sub>1</sub>?=?<em>a</em><sub>2</sub></span></span>
</li>
<li>
<span><span><em>a</em><sub>3</sub>?=?<em>a</em><sub>4</sub></span></span>
</li>
</ul>
<p><span>A rectangle can be made of sticks with lengths of, for example,
<span>3 3 3 3</span> or <span>2 2 4 4</span>. A rectangle cannot be made of, for example, sticks
<span>5 5 5 7</span>.</span></p>
<p><span>Ilya also has an instrument which can reduce the length of the sticks. The sticks are made of a special material, so the length of each stick can be reduced by at most one. For example, a stick with length
<span>5</span> can either stay at this length or be transformed into a stick of length
<span>4</span>.</span></p>
<p><span>You have to answer the question — what maximum total area of the rectangles can Ilya get with a file if makes rectangles from the available sticks?</span></p>
<p>
</p>
<p><span>Input</span></p>
<p><span>The first line of the input contains a positive integer
<span><em>n</em></span> (<span>1?≤?<em>n</em>?≤?10<sup>5</sup></span>) — the number of the available sticks.</span></p>
<p><span>The second line of the input contains <span>
<em>n</em></span> positive integers <span><em>l</em><sub><em>i</em></sub></span> (<span>2?≤?<em>l</em><sub><em>i</em></sub>?≤?10<sup>6</sup></span>) — the lengths
of the sticks.</span></p>
<p>
</p>
<p><span>Output</span></p>
<p><span>The first line of the output must contain a single non-negative integer — the maximum total area of the rectangles that Ilya can make from the available sticks.</span></p>
<p>
</p>
<p><span>Sample test(s)</span></p>
<p>
</p>
<p>
</p>
<p><span>Input</span></p>
<pre class="brush:php;toolbar:false"><span>4
2 4 4 2
</span>
Output
<span>8 </span>
Input
<span>4 2 2 3 5 </span>
Output
<span>0 </span>
Input
<span>4 100003 100004 100005 100006 </span>
Output
<span>10000800015</span>
题目大意：给n个木条，求从中选择4个出来组成长方形，能组成长方形的四个边满足a1
题目分析：从大到小排序，从大的开始选，选的时候注意减1的情况，开始看错题了，以为只拼一个，其实是可以拼多个
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
int const MAX = 1e5;
ll l[MAX];
bool cmp(ll a, ll b)
{
return a > b;
}
int main()
{
int n;
scanf("%d", &n);
if(n <br>
<br>
<p><br>
</p>
<p>
</p>
<p><span>D. Arthur and Walls</span></p>
<p>
</p>
<p><span>time limit per test：2 seconds</span></p>
<p>
</p>
<p><span>memory limit per test：512 megabytes<br>
</span></p>
<span><br>
</span>
<p>
</p>
<p><span>Finally it is a day when Arthur has enough money for buying an apartment. He found a great option close to the center of the city with a nice price.</span></p>
<p><span>Plan of the apartment found by Arthur looks like a rectangle
<span><em>n</em>?×?<em>m</em></span> consisting of squares of size
<span>1?×?1</span>. Each of those squares contains either a wall (such square is denoted by a symbol "<span>*</span>" on the plan) or a free space (such square is denoted on the plan by a symbol "<span>.</span>").</span></p>
<p><span>Room in an apartment is a maximal connected area consisting of free squares. Squares are considered adjacent if they share a common side.</span></p>
<p><span>The old Arthur dream is to live in an apartment where all rooms are rectangles. He asks you to calculate minimum number of walls you need to remove in order to achieve this goal. After removing a wall from a square it becomes
a free square. While removing the walls it is possible that some rooms unite into a single one.</span></p>
<p>
</p>
<p><span>Input</span></p>
<p><span>The first line of the input contains two integers
<span><em>n</em>,?<em>m</em></span> (<span>1?≤?<em>n</em>,?<em>m</em>?≤?2000</span>) denoting the size of the Arthur apartments.</span></p>
<p><span>Following <span><em>n</em></span> lines each contain
<span><em>m</em></span> symbols — the plan of the apartment.</span></p>
<p><span>If the cell is denoted by a symbol "<span>*</span>" then it contains a wall.</span></p>
<p><span>If the cell is denoted by a symbol "<span>.</span>" then it this cell is free from walls and also this cell is contained in some of the rooms.</span></p>
<p>
</p>
<p><span>Output</span></p>
<p><span>Output <span><em>n</em></span> rows each consisting of
<span><em>m</em></span> symbols that show how the Arthur apartment plan should look like after deleting the minimum number of walls in order to make each room (maximum connected area free from walls) be a rectangle.
</span></p>
<p><span>If there are several possible answers, output any of them.</span></p>
<p><span>Sample test(s)</span></p>
<p>
</p>
<p><span>Input</span></p>
<pre class="brush:php;toolbar:false"><span>5 5
.*.*.
*****
.*.*.
*****
.*.*.
</span>
Output
<span>.*.*. ***** .*.*. ***** .*.*. </span>
Input
<span>6 7 ***.*.* ..*.*.* *.*.*.* *.*.*.* ..*...* ******* </span>
Output
<span>***...* ..*...* ..*...* ..*...* ..*...* ******* </span>
Input
<span>4 5 ..... ..... ..*** ..*.. </span>
Output
<span>..... ..... ..... .....</span>
题目大意：给一个n*m的矩阵，'' * “表示墙 " . "表示空地，被" * "围起来的是房间现在求删去最少的" * "使得每个房间空地的形状都是一个矩形，输出删除后的矩阵
题目分析：YY一下发现类似下面这种形状的(其他可由它翻转或旋转得到)2*2的子矩阵的" * "都要被改成" . "
<span>*. .. </span>
然后就是预处理一下这种形状BFS搜一下，用队列维护，每次删去一个" * "分别向周围8个方向扩展，注意要用vis数组标记防止未更新的点重复入队列！
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int const MAX = 2005;
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
char map[MAX][MAX];
bool vis[MAX][MAX];
int n, m;
queue <pair int> > q;
bool judge(int i, int j)
{
if(map[i][j] == '.' || i == 0 || j == 0 || i == n + 1 || j == m + 1)
return false;
if(map[i - 1][j - 1] == '.' && map[i - 1][j] == '.' && map[i][j - 1] == '.')
return true;
if(map[i + 1][j + 1] == '.' && map[i + 1][j] == '.' && map[i][j + 1] == '.')
return true;
if(map[i + 1][j - 1] == '.' && map[i][j - 1] == '.' && map[i + 1][j] == '.')
return true;
if(map[i - 1][j + 1] == '.' && map[i - 1][j] == '.' && map[i][j + 1] == '.')
return true;
return false;
}
void BFS()
{
while(!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
map[x][y] = '.';
for(int i = 0; i <br>
<p><br>
</p>
<p><br>
</p>
<p>
</p><p>
</p><p>
</p><p>
</p><p><span>E. Anya and Cubes</span></p>
<p>
</p><p><span>time limit per test：2 seconds</span></p>
<p>
</p><p><span>memory limit per test：256 megabytes</span></p>
<span><br>
</span>
<p>
</p><p><span>Anya loves to fold and stick. Today she decided to do just that.</span></p>
<p><span>Anya has <span><em>n</em></span> cubes lying in a line and numbered from
<span>1</span> to <span><em>n</em></span> from left to right, with natural numbers written on them. She also has
<span><em>k</em></span> stickers with exclamation marks. We know that the number of stickers does not exceed the number of cubes.</span></p>
<p><span>Anya can stick an exclamation mark on the cube and get the factorial of the number written on the cube. For example, if a cube reads
<span>5</span>, then after the sticking it reads <span>
5!</span>, which equals <span>120</span>.</span></p>
<p><span>You need to help Anya count how many ways there are to choose some of the cubes and stick on some of the chosen cubes at most
<span><em>k</em></span> exclamation marks so that the sum of the numbers written on the chosen cubes after the sticking becomes equal to
<span><em>S</em></span>. Anya can stick at most one exclamation mark on each cube. Can you do it?</span></p>
<p><span>Two ways are considered the same if they have the same set of chosen cubes and the same set of cubes with exclamation marks.</span></p>
<p>
</p><p><span>Input</span></p>
<p><span>The first line of the input contains three space-separated integers
<span><em>n</em></span>, <span><em>k</em></span> and
<span><em>S</em></span> (<span>1?≤?<em>n</em>?≤?25</span>,
<span>0?≤?<em>k</em>?≤?<em>n</em></span>, <span>
1?≤?<em>S</em>?≤?10<sup>16</sup></span>) — the number of cubes and the number of stickers that Anya has, and the sum that she needs to get.
</span></p>
<p><span>The second line contains <span><em>n</em></span> positive integers
<span><em>a</em><sub><em>i</em></sub></span> (<span>1?≤?<em>a</em><sub><em>i</em></sub>?≤?10<sup>9</sup></span>) — the numbers, written on the cubes. The cubes in
the input are described in the order from left to right, starting from the first one.
</span></p>
<p><span>Multiple cubes can contain the same numbers.</span></p>
<p>
</p><p><span>Output</span></p>
<p><span>Output the number of ways to choose some number of cubes and stick exclamation marks on some of them so that the sum of the numbers became equal to the given number
<span><em>S</em></span>.</span></p>
<p>
</p><p><span>Sample test(s)</span></p>
<p>
</p><p>
</p><p><span>Input</span></p>
<pre class="brush:php;toolbar:false"><span>2 2 30
4 3
</span>
Output
<span>1 </span>
Input
<span>2 2 7 4 3 </span>
Output
<span>1 </span>
Input
<span>3 1 1 1 1 1 </span>
Output
<span>6 </span>
Note
In the first sample the only way is to choose both cubes and stick an exclamation mark on each of them.
In the second sample the only way is to choose both cubes but don't stick an exclamation mark on any of them.
In the third sample it is possible to choose any of the cubes in three ways, and also we may choose to stick or not to stick the exclamation mark on it. So, the total number of ways is six.
题目大意：给n个数a[i]，其中可以选出k个将它变成自己的阶乘，问有多少种方案取出的数的和为s
题目分析：由于n＝25，对每个数有3种情况，不选，选，选它的阶乘，因此3^25肯定T，由此想到类似poj 1840这样的题，我们可以先算前n/2个数然后用map存储下来，再算后n/2个数，在后n/2个数中算出来的数架设为sum2如果s-sum2在前n/2个数的和中出现过，则我们找到相应个数的解，这样将复杂度降到2 * 3^12 约等于1e6的数量级，注意s的范围是10^16，而18! ＝ 6*10^15因此18以后的阶乘我们都不用去算了，搜索的时候当然也不用搜，本地跑了好久，交到cf上才500+ms。。。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#define ll long long
using namespace std;
ll fac[20] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880,
3628800, 39916800, 479001600, 6227020800 ,87178291200 ,1307674368000
,20922789888000 ,355687428096000 ,6402373705728000};
ll a[30], s, ans;
int n, k;
map <ll ll> mp[30];
void DFS1(int i, int cnt, ll sum)
{
if(sum > s || cnt > k)
return;
if(i == n / 2)
{
mp[cnt][sum] ++;
return;
}
DFS1(i + 1, cnt, sum);
DFS1(i + 1, cnt, sum + a[i]);
if(a[i] s || cnt > k)
return;
if(i == n)
{
for(int j = 0; j + cnt <br>
<br>
<p><br>
</p>
<p><span><br>
</span></p>
<p><br>
</p>
</ll></map></algorithm></cstring></cstdio>