浪在ACM集训队寒假集训第二场部分题解

本场发挥整体还行,剩下的那四个题是真的不会做。等待慢慢补题吧。


A - Generous Kefa(CodeForces841A)

One day Kefa found n baloons. For convenience, we denote color of i-th baloon as si — lowercase letter of the Latin alphabet. Also Kefa has k friends. Friend will be upset, If he get two baloons of the same color. Kefa want to give out all baloons to his friends. Help Kefa to find out, can he give out all his baloons, such that no one of his friens will be upset — print «YES», if he can, and «NO», otherwise. Note, that Kefa’s friend will not upset, if he doesn’t get baloons at all.

Input

The first line contains two integers n and k (1 ≤ n, k ≤ 100) — the number of baloons and friends.

Next line contains string s — colors of baloons.

Output

Answer to the task — «YES» or «NO» in a single line.
You can choose the case (lower or upper) for each letter arbitrary.

Examples

Input
4 2
aabb
Output
YES

Input
6 3
aacaab
Output
NO

Note

In the first sample Kefa can give 1-st and 3-rd baloon to the first friend, and 2-nd and 4-th to the second.

In the second sample Kefa needs to give to all his friends baloons of color a, but one baloon will stay, thats why answer is «NO».

题目大意:

某人有n个气球,这些气球分别有不同的颜色,现在他要把这些气球送给k个朋友,但是他的朋友不希望得到两个相同颜色的气球,也就是说每个朋友拿到的气球颜色应该都是互不相同的。他的气球应该全部送完,问当前状况能不能完成要求。

稍加分析不难得出一个结论,如果此人某个颜色的气球的数量多余朋友的数量,那么这个情况下是一定不可行的,因为这样的话至少会有一个朋友得到两个相同颜色的气球。这其实就是这个题的突破点。统计一下每种颜色气球的数量与k比较,如果比k小或者与k相等则可以,如果比k大就不行。

槽点:没有拿到气球的朋友竟然会比拿到相同颜色气球的朋友高兴(请自行思考为什么可能出现有人拿不到气球)

我的实现方式与其他人略有不同,统计数量的时候我使用了map的迭代器,这样的写法也许看起来更cooooooool(误

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <cstdio>
#include <string>
#include <map>
#include <cmath>
#define maxn 23333
using namespace std;
int n, k;
string s;
map <char, int> ma;

int max(int a, int b) {
if (a > b)
return a;
else
return b;
}

int main() {
cin >> n >> k;
cin >> s;
ma.clear();
int l = s.length();
for (int i = 0; i < l; i++) {
ma[s[i]]++;
}
int maxx = -1;
for (map <char, int>::iterator iter = ma.begin(); iter != ma.end(); iter++) {
maxx = max(maxx, iter->second);
}
if (maxx > k)
cout << "NO";
else
cout << "YES";
return 0;
}

B - Godsend(CodeForces841B)

Leha somehow found an array consisting of n integers. Looking at it, he came up with a task. Two players play the game on the array. Players move one by one. The first player can choose for his move a subsegment of non-zero length with an odd sum of numbers and remove it from the array, after that the remaining parts are glued together into one array and the game continues. The second player can choose a subsegment of non-zero length with an even sum and remove it. Loses the one who can not make a move. Who will win if both play optimally?

Input

First line of input data contains single integer n (1 ≤ n ≤ 106) — length of the array.

Next line contains n integers a1, a2, …, an (0 ≤ ai ≤ 109).

Output

Output answer in single line. “First”, if first player wins, and “Second” otherwise (without quotes).

Examples

Input
4
1 3 2 3
Output
First

Input
2
2 2
Output
Second

Note

In first sample first player remove whole array in one move and win.

In second sample first player can’t make a move and lose.

题目大意:有一个长度为n的序列,每一项都有一个值,现在两个人玩一个游戏,第一个玩家先动,他可以取走序列中的一段,但是只能是序列和为奇数的,第二个玩家后动,他可以取走序列中的一段,但是只能是序列和为偶数的。谁先没法动谁先输,问给定的情况是谁赢了。

这是一个很显然的博弈论问题。刚开始拿到这题的时候粗读题发现牵扯到博弈论和序列和,感觉可能是难题就暂时扔了,所有题读过一遍来看榜发现已经有两人A了这题了。。。这群大佬也太恐怖了。。。

但是这个题真的有这么难吗?不见得。想一下,如果你是第一个玩家,你应该怎么才能最快的赢?

显然,如果整段序列的总和就是奇数,那么第一个玩家直接把整个序列都取走,显然就赢了。那么如果整段序列的总和是偶数呢?这里分两种情况。第一种情况是总和的偶数全都是由偶数组成,第二种情况是总和的偶数由奇数的项参与。如果是第一种情况,那第一个玩家上来就没法动,也就是没有赢的可能。因为所有的项都是偶数,任意子段和必定是偶数。但是如果是第二种情况呢?第二种情况必然有奇数参与,则必然有偶数个奇数参与(想一想,为什么)。所以第一个玩家的必胜策略很简单,留下一个奇数,剩下的序列全拿走,这样最后就剩下一个奇数让第二个玩家拿,第二个玩家根本没法动,还是第一个玩家赢。

吐槽:这题卡我cin,明明算法没问题,大概是常数大了。lyj的cin是1800ms擦边过,我直接就T了。。。以后用cin要加关闭流同步了。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <cstdio>
#include <string>
#include <map>
#include <cmath>
#define maxn 2333333
using namespace std;
int n;
int a;
bool exist = false;
long long int sum;
int main() {
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a;
if (a % 2 == 1)
exist = true;
sum += a;
}

if (sum % 2 == 1)
cout << "First";
else {
if (exist) {
cout << "First";
}
else {
cout << "Second";
}
}
//system("pause");
return 0;
}

F - New Year and Days(CodeForces611A)

Today is Wednesday, the third day of the week. What’s more interesting is that tomorrow is the last day of the year 2015.

Limak is a little polar bear. He enjoyed this year a lot. Now, he is so eager to the coming year 2016.

Limak wants to prove how responsible a bear he is. He is going to regularly save candies for the entire year 2016! He considers various saving plans. He can save one candy either on some fixed day of the week or on some fixed day of the month.

Limak chose one particular plan. He isn’t sure how many candies he will save in the 2016 with his plan. Please, calculate it and tell him.

Input

The only line of the input is in one of the following two formats:

“x of week” where x (1 ≤ x ≤ 7) denotes the day of the week. The 1-st day is Monday and the 7-th one is Sunday.
“x of month” where x (1 ≤ x ≤ 31) denotes the day of the month.

Output

Print one integer — the number of candies Limak will save in the year 2016.

Examples

Input
4 of week
Output
52

Input
30 of month
Output
11

Note

Polar bears use the Gregorian calendar. It is the most common calendar and you likely use it too. You can read about it on Wikipedia if you want to – https://en.wikipedia.org/wiki/Gregorian_calendar. The week starts with Monday.

In the first sample Limak wants to save one candy on each Thursday (the 4-th day of the week). There are 52 Thursdays in the 2016. Thus, he will save 52 candies in total.

In the second sample Limak wants to save one candy on the 30-th day of each month. There is the 30-th day in exactly 11 months in the 2016 — all months but February. It means that Limak will save 11 candies in total.

题目大意:

某人打算在即将到来的2016年进行节省糖果的计划,一种方案是一星期中的某一天节省一块,另一种方案是在一月中的某一天节省某一块,给出他想采用的方案和具体在一星期的哪一天/一月的哪一天节省一颗糖,问一年能节省多少糖。

可不要小看这个题,这题可不算简单题(滑稽)。由于我不知道怎么推算某年的星期几多一天,我就只能无奈的查日历了QAQ,然后这题是打表出来的。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cstdio>
#include <string>
#include <map>
#include <cmath>
#include <algorithm>
#define maxn 2333333
using namespace std;
int a;
string s;

int main() {
cin >> a;
getline(cin, s);
if (s == " of week") {
if (a == 5 || a == 6)
cout << "53";
else
cout << "52";
}
else {
if (a == 31) {
cout << "7";
}
else if (a == 30)
cout << "11";
else
cout << "12";
}
//system("pause");
return 0;
}

H - New Year and Old Property(CodeForces611B)

(唉算了实在懒得拉题目了直接给链接吧,改格式太麻烦了:https://vjudge.net/contest/279816#problem/H

大意:给出一个区间[l,r](可能很大),问这个区间内的二进制数里, 有多少个二进制数里面只有一个0。

解法有两个,第一个是wsb大佬提供的数位dp解法,他成功的用此解法拿到了本题的FB。这我实在是不会233333

第二个解法就是暴力模拟找。原本我是用Python过了这题的,然后赛后被怼,因为正式比赛不让用Python。

我的思路和lyj大佬的类似,emmmm目前来看暂时没有需要补充的,基于不重复造轮子原则,给出传送门:https://blog.csdn.net/weixin_43537190/article/details/86561402?tdsourcetag=s_pcqq_aiomsg

槽点:数据非常大,甚至C++的long long int都难以满足要求。刚才试图用java写了一下,这个只能过不是很大的数据。。

基于不重复造轮子原则,这里给出不完善的Java代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Long l = in.nextLong();
Long r = in.nextLong();
Long ans = (long) 0;
String binl = Long.toBinaryString(l);
String binr = Long.toBinaryString(r);
Long st = (long)binl.length();
Long ed = (long)binr.length();
for (Long i = st; i <= ed; i++) {
for (Long j = (long) 0;j <= i - 1; j++) {
Long temp = (long) (1 << i) - 1 - (1 << j);
if (temp >= l && temp <= r)
ans++;
}
}
System.out.print(ans);
in.close();
}
}

-------------本文结束,感谢您的阅读转载请注明原作者及出处-------------


本文标题:浪在ACM集训队寒假集训第二场部分题解

文章作者:Shawn Zhou

发布时间:2019年01月20日 - 20:01

最后更新:2019年01月22日 - 16:01

原始链接:http://shawnzhou.xyz/2019/01/20/19-01-20-01/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

知识无价,码字不易。对您有用,敬请打赏。金额随意,感谢关心。
0%