Codeforces Round #FF (Div. 2) 题解

比赛链接：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

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 wants to insert n numbers, in the order they are given, into the hash table. For the i-th number x_i, DZY will put it into the bucket numbered h(x_i), 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 x_i (0?≤?x_i?≤?10⁹).

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="/static/imghw/default1.png" data-src="/inc/test.jsp?url=http%3A%2F%2Fespresso.codeforces.com%2F47c9783b69409ca6ade8e93f7d51bed11f430539.png&refer=http%3A%2F%2Fblog.csdn.net%2Fu010084308%2Farticle%2Fdetails%2F37758201" class="lazy" 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 a₂,?a₃,?a₄,?a₅,?a₆ and change its 3rd element (that is a₄) 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>