Codeforces Round #FF (Div. 2) 题解
- WBOYOriginal
- 2016-06-07 15:31:471056browse
比赛链接：http://codeforces.com/contest/447 A. DZY Loves Hash time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output DZY has a hash table with p buckets, numbered from 0 to p ?-?1 . He
比赛链接：http://codeforces.com/contest/447
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
DZY has a hash table with p buckets, numbered from 0 to p?-?1. He wants to insert n numbers, in the order they are given, into the hash table. For the i-th number xi, DZY will put it into the bucket numbered h(xi), where h(x) is the hash function. In this problem we will assume, that h(x)?=?x mod p. Operation a mod b denotes taking a remainder after division a by b.
However, each bucket can contain no more than one element. If DZY wants to insert an number into a bucket which is already filled, we say a "conflict" happens. Suppose the first conflict happens right after the i-th insertion, you should output i. If no conflict happens, just output -1.
Input
The first line contains two integers, p and n (2?≤?p,?n?≤?300). Then n lines follow. The i-th of them contains an integer xi (0?≤?xi?≤?109).
Output
Output a single integer — the answer to the problem.
Sample test(s)
input
10 5 0 21 53 41 53
output
4
input
5 5 0 1 2 3 4
output
-1
链接：http://codeforces.com/contest/447
题意:找出hash时第一次产生冲突的位置。
解题思路：用一个数组表示是否存放有hash之后的元素，0表示这个位置还没有使用过，1表示这个位置上有hash之后的元素（即产生了冲突）。
代码：
#include <cstdio>
#include <cstring>
const int MAXN = 305;
int a[MAXN], p, n, ans = -1;
int main()
{
bool flag = true;
scanf("%d%d", &p, &n);
for(int i = 0; i <br>
<p>
</p>
<p>
</p>
<p>
</p>
<p>
</p>
<p>
</p>
<p>
</p>
<p>
B. DZY Loves Strings</p>
<p>
</p>
<p>
time limit per test</p>
1 second
<p>
</p>
<p>
memory limit per test</p>
256 megabytes
<p>
</p>
<p>
input</p>
standard input
<p>
</p>
<p>
output</p>
standard output
<p>
</p>
<p>DZY loves collecting special strings which only contain lowercase letters. For each lowercase letter<span> </span><span><em>c</em></span><span> </span>DZY
knows its value<span> </span><span><em>w</em><sub><em>c</em></sub></span>.
For each special string<span> </span><span><em>s</em>?=?<em>s</em><sub>1</sub><em>s</em><sub>2</sub>...<span> </span><em>s</em><sub>|<em>s</em>|</sub></span><span> </span>(<span>|<em>s</em>|</span><span> </span>is
the length of the string) he represents its value with a function<span> </span><span><em>f</em>(<em>s</em>)</span>, where</p>
<center><img src="/inc/test.jsp?url=http%3A%2F%2Fespresso.codeforces.com%2F47c9783b69409ca6ade8e93f7d51bed11f430539.png&refer=http%3A%2F%2Fblog.csdn.net%2Fu010084308%2Farticle%2Fdetails%2F37758201" alt="Codeforces Round #FF (Div. 2) 题解" ></center>
<p>Now DZY has a string<span> </span><span><em>s</em></span>. He wants to
insert<span> </span><span><em>k</em></span><span> </span>lowercase letters into this string in order to get the largest possible value of the resulting
string. Can you help him calculate the largest possible value he could get?</p>
<p>
</p>
<p>
Input</p>
<p>The first line contains a single string<span> </span><span><em>s</em> (1?≤?|<em>s</em>|?≤?10<sup>3</sup>)</span>.</p>
<p>The second line contains a single integer<span> </span><span><em>k</em> (0?≤?<em>k</em>?≤?10<sup>3</sup>)</span>.</p>
<p>The third line contains twenty-six integers from<span> </span><span><em>w</em><sub><em>a</em></sub></span><span> </span>to<span> </span><span><em>w</em><sub><em>z</em></sub></span>.
Each such number is non-negative and doesn't exceed<span> </span><span>1000</span>.</p>
<p>
</p>
<p>
Output</p>
<p>Print a single integer — the largest possible value of the resulting string DZY could get.</p>
<p>
</p>
<p>
Sample test(s)</p>
<p>
</p>
<p>
</p>
<p>
input</p>
<pre class="brush:php;toolbar:false">abc
3
1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
output
41
Note
In the test sample DZY can obtain "abcbbc", value?=?1·1?+?2·2?+?3·2?+?4·2?+?5·2?+?6·2?=?41.
链接：http://codeforces.com/contest/447/problem/B
题意：在给出的字符串中增加k个字符，求可以得到的最大权值和。
解题思路：找出最大的位权，将k个有最大位权的字符放到原字符串的末尾，求权值和。ps：答案可能会超出int，要用long long
代码：
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s;
int k, a[27], imax = -1;
cin >> s >> k;
for(int i = 0; i > a[i];
if(a[i] > imax)
{
imax = a[i];
}
}
long long ans = 0;
int len = s.length();
for(int i = 0; i <br>
<p>
</p>
<p>
C. DZY Loves Sequences</p>
<p>
</p>
<p>
time limit per test</p>
1 second
<p>
</p>
<p>
memory limit per test</p>
256 megabytes
<p>
</p>
<p>
input</p>
standard input
<p>
</p>
<p>
output</p>
standard output
<p>
</p>
<p>DZY has a sequence<span> </span><span><em>a</em></span>, consisting of<span> </span><span><em>n</em></span><span> </span>integers.</p>
<p>We'll call a sequence<span> </span><span><em>a</em><sub><em>i</em></sub>,?<em>a</em><sub><em>i</em>?+?1</sub>,?...,?<em>a</em><sub><em>j</em></sub></span><span> </span><span>(1?≤?<em>i</em>?≤?<em>j</em>?≤?<em>n</em>)</span><span> </span>a
subsegment of the sequence<span> </span><span><em>a</em></span>. The value<span> </span><span>(<em>j</em>?-?<em>i</em>?+?1)</span><span> </span>denotes
the length of the subsegment.</p>
<p>Your task is to find the longest subsegment of<span> </span><span><em>a</em></span>,
such that it is possible to change at most one number (change one number to any integer you want) from the subsegment to make the subsegment strictly increasing.</p>
<p>You only need to output the length of the subsegment you find.</p>
<p>
</p>
<p>
Input</p>
<p>The first line contains integer<span> </span><span><em>n</em> (1?≤?<em>n</em>?≤?10<sup>5</sup>)</span>.
The next line contains<span> </span><span><em>n</em></span><span> </span>integers<span> </span><span><em>a</em><sub>1</sub>,?<em>a</em><sub>2</sub>,?...,?<em>a</em><sub><em>n</em></sub> (1?≤?<em>a</em><sub><em>i</em></sub>?≤?10<sup>9</sup>)</span>.</p>
<p>
</p>
<p>
Output</p>
<p>In a single line print the answer to the problem — the maximum length of the required subsegment.</p>
<p>
</p>
<p>
Sample test(s)</p>
<p>
</p>
<p>
</p>
<p>
input</p>
<pre class="brush:php;toolbar:false">6
7 2 3 1 5 6
output
5
Note
You can choose subsegment a2,?a3,?a4,?a5,?a6 and change its 3rd element (that is a4) to 4.
链接：http://codeforces.com/contest/447/problem/C题意：从一串数字中选出一个子串，可以改变子串中一个数字的值得到一个新的子串，求最大的递增新子串的长度。
解题思路：
将原数组分割成递增的子串，记录下每个子串的开始和结束位置，以及长度。接下来要分几种情况讨论：1.相邻的两个子串改变一个数字之后，可以合并形成新的递增子串，2.相邻的3个子串，中间子串长度为1，改变中间的数字后可以形成新的递增子串，3.相邻的子串不能合并形成新的递增子串，但是可以在原串的基础上，得到一个长度增加1的新的递增子串（在子串开头位置前有数字，或是结束位置后有数字）。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 100010;
int a[MAXN];
struct P
{
int l, len, r;
};
P p[MAXN];
int n;
int main()
{
memset(p, 0, sizeof(p));
scanf("%d", &n);
int t = 0;
for(int i = 0; i a[p[i - 1].r - 1] + 1 ||
a[p[i].l + 1] > a[p[i - 1].r] + 1)
{
ans = max(ans, p[i].len + p[i - 1].len);
}
if(i >= 2 && 1 == p[i - 1].len &&
a[p[i].l] > a[p[i - 2].r + 1])
{
ans = max(ans, p[i].len + p[i - 2].len + 1);
}
// printf("%d \n", p[i].len);
}
printf("%d\n", ans);
return 0;
}
</algorithm></cstring></cstdio>