A - Registration system
A new e-mail service "Berlandesk" is going to be opened in Berland in the near future. The site administration wants to launch their project as soon as possible, that's why they ask you to help. You're suggested to implement the prototype of site registration system. The system should work on the following principle.
Each time a new user wants to register, he sends to the system a request with his name. If such a name does not exist in the system database, it is inserted into the database, and the user gets the response OK, confirming the successful registration. If the name already exists in the system database, the system makes up a new user name, sends it to the user as a prompt and also inserts the prompt into the database. The new name is formed by the following rule. Numbers, starting with 1, are appended one after another to name (name1, name2, ...), among these numbers the least i is found so that namei does not yet exist in the database.
Input
The first line contains number n (1 ≤ n ≤ 105). The following n lines contain the requests to the system. Each request is a non-empty line, and consists of not more than 32 characters, which are all lowercase Latin letters.
Output
Print n lines, which are system responses to the requests: OK in case of successful registration, or a prompt with a new name, if the requested name is already taken.
Examples
Input
4 abacaba acaba abacaba acab
Output
OK OK abacaba1 OK
Input
6 first first second second third third
Output
OK first1 OK second1 OK third1
题意：第一次出现的字符串输出OK，如果不是第一次出现的话输出此字符串并在最后加上之前出现的次数。
做法：这题使用STL里的map，可以说是几乎秒杀了。
#include<iostream>
#include<stdio.h>
#include<map>
using namespace std;
map<string,int> f;
int n;
int main()
{
ios::sync_with_stdio(false),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
string s;
cin>>s;
if(f[s]==0)
{
cout<<"OK";
f[s]++;
}
else
{
cout<<s<<f[s];
f[s]++;
}
cout<<'\n';
}
return 0;
}
B - Boredom
Alex doesn't like boredom. That's why whenever he gets bored, he comes up with games. One long winter evening he came up with a game and decided to play it.
Given a sequence a consisting of n integers. The player can make several steps. In a single step he can choose an element of the sequence (let's denote it ak) and delete it, at that all elements equal to ak + 1 and ak - 1 also must be deleted from the sequence. That step brings ak points to the player.
Alex is a perfectionist, so he decided to get as many points as possible. Help him.
Input
The first line contains integer n (1 ≤ n ≤ 105) that shows how many numbers are in Alex's sequence.
The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 105).
Output
Print a single integer — the maximum number of points that Alex can earn.
Examples
Input
2 1 2
Output
2
Input
3 1 2 3
Output
4
Input
9 1 2 1 3 2 2 2 2 3
Output
10
Note
Consider the third test example. At first step we need to choose any element equal to 2. After that step our sequence looks like this [2, 2, 2, 2]. Then we do 4 steps, on each step we choose any element equals to 2. In total we earn 10 points.
题意：给出一些数字，你可以选择删掉其中的a并且获得大小为a的回报，但此时需要同时消除a+1和a-1并不能获得这两者的回报。
求回报的最大值。
做法：DP。cnt[i]表示i这个数出现的次数，dp[i]表示在第i个数取完后的结果。假设在第i这个数，它可以选择这个数，选了这个数就不能选第i-1个，所以它的值为dp[i]=dp[i-2]+i*cnt[i].如果是不选这个数，当前的情况就为dp[i-1]，所以状态转移式为 dp[i]=max(dp[i-1],dp[i-2]+cnt[i]*i)
#include<iostream>
#include<stdio.h>
using namespace std;
int n,ai;
long long dp[100005],cnt[100005];
void read_in()
{
ios::sync_with_stdio(false),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
int a;
cin>>a;
ai=max(a,ai);
cnt[a]++;
}
}
void DP()
{
dp[1]=cnt[1];
for(int i=2;i<=ai;i++)
dp[i]=max(dp[i-1],dp[i-2]+cnt[i]*i);
cout<<dp[ai];
}
int main()
{
read_in();
DP();
return 0;
}
C - Number of Ways
You've got array a[1], a[2], ..., a[n], consisting of n integers. Count the number of ways to split all the elements of the array into three contiguous parts so that the sum of elements in each part is the same.
More formally, you need to find the number of such pairs of indices i, j (2 ≤ i ≤ j ≤ n - 1), that .
Input
The first line contains integer n (1 ≤ n ≤ 5·105), showing how many numbers are in the array. The second line contains n integers a[1], a[2], ..., a[n] (|a[i]| ≤ 109) — the elements of array a.
Output
Print a single integer — the number of ways to split the array into three parts with the same sum.
Examples
Input
5 1 2 3 0 3
Output
2
Input
4 0 1 -1 0
Output
1
Input
2 4 1
Output
0
题意：将一段长度为n的数字分成3份，每一份的和相同，求方案数。
做法：其实一开始真的没有什么思路，只想到一定要前缀和，但是后面却想着枚举两个长度的位置。
正解为从1扫到n-1，若扫到sum[i]为sum[n]/3，则说明i这个位置之前的可以是第一部分。
如果扫到sum[j]=sum[n]* 2/3，则说明j这个位置是第二个隔板。
但是要注意在循环内先判断第二条再判断第一条，因为当sum[n]等于0的时候会出错。
#include<iostream>
#include<stdio.h>
using namespace std;
int n;
long long sum[500005];
void read_in()
{
freopen("in.txt","r",stdin);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>sum[i];
sum[i]+=sum[i-1];
}
}
void DP()
{
long long ans=0,ansi=0;
for(int i=1;i<n;i++)
{
if(sum[i]*3==sum[n]*2)
ans+=ansi;
if(sum[i]*3==sum[n])
ansi++;
}
cout<<ans ;
}
int main()
{
read_in();
DP();
return 0;
}