A - Weird Flecks, But OK(未做)

算法标签

数学(最小圆覆盖问题)

B - Code Names(未做)

算法标签

二分图最大匹配问题

C - New Maths(未做)

算法标签

DFS搜索

D - Some Sum

算法标签

数论

题目描述

Your friend has secretly picked N consecutive positive integers between 1 and 100, and wants you to guess if their sum is even or odd.
If the sum must be even, output Even. If the sum must be odd, output Odd. If the sum could be even or could be odd, output Either.

输入

The input is a single integer N with 1≤N≤10.

输出

Output a single word. The word should be Even, Odd, or
Either, according to the rules given earlier.

样例

Input

1
1

Output

1
Either

Input

1
2

Output

1
Odd

解题思路

从1到100的数字中取出N个数字,给定整数N,求这些数字和一定是偶数、一定是奇数、还是都有可能。比赛的时候直接暴力判断所有可能的情况成功AC。

奇数+奇数 = 偶数、偶数+偶数=偶数、奇数+偶数=奇数

给出N个连续数字,一定是三种情况:

1.奇数的个数=偶数的个数=n,此时相当于n/2个奇数相加。

2.奇数的个数=偶数的个数+1,按上述情况考虑并加一个奇数。

3.偶数的个数=奇数的个数+1,按上述情况考虑并加一个偶数。

而2、3根据起始数字的不同有不同的情况,所以都有可能。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>

using namespace std;

int main()
{
int N;
cin >> N;

if (N % 2 == 0)
{
if ((N / 2) % 2 == 0) cout << "Even" << endl;
else cout << "Odd" << endl;
}
else
{
cout << "Either" << endl;
}

return 0;
}

English单词积累

Odd—奇数

Even—偶数

E - Early Orders(未做)

算法标签

单调栈

F - Pulling Their Weight

算法标签

二分

题目描述

To save money, Santa Claus has started hiring other animals besides reindeer to pull his sleigh via short term ‘gig’ contracts. As a result, the actual animals that show up to pull his sleigh for any given trip can vary greatly in size.

Last week he had 2 buffalo, 37 voles and a schnauzer. Unfortunately, both buffalo were hitched on the left side and the entire sleigh flipped over in mid-flight due to the weight imbalance.

To prevent such accidents in the future, Santa needs to divide the animals for a given trip into two groups such that the sum of the weights of all animals in one group equals the sum of the weights of all animals in the other. To make the hitching process efficient, Santa is seeking an integer target weight t such that all animals that are lighter than t go in one group and those
heavier than t go into the other. If there are multiple such t, he wants the smallest one. There’s one small wrinkle: what should be done if there some animals have weight exactly equal to t? Santa solves the problem this way: if there are an even number of such animals, he divides them equally among the two groups (thus distributing the weight evenly). But if there are an odd number of such animals, then one of those animals is sent to work with the elves to make
toys (it is not put in either group), and the remaining (now an even number) are divided evenly among the two groups.

输入

Input describes a list of animals’ weights. The first line contains an integer m (2≤m≤10^5^), indicating the number of animals. The next m lines each have a positive integer. These are the weights of the animals (in ounces).

Animals weighing more than 20000 ounces are too big to pull the sleigh so no given weight will exceed this maximum.

输出

Output the smallest integer target weight t, as described above. It’s
guaranteed that it is possible to find such an integer.

样例

Input

1
2
3
4
5
4
3
6
1
2

Output

1
4

Input

1
2
3
4
5
4
11
8
3
10

Output

1
10

Input

1
2
3
2
99
99

Output

1
99

解题思路

圣诞老人要雇佣一些动物,要求求出一个整数t。

凡是重量小于t的动物放在A组,重量大于t的动物放在B组。

如果重量等于t两组平均分配。如果是奇数,就扔掉一只。(可以不考虑等于t的情况,因为对相等的两组无影响)。

如果存在多个满足题意的t,求最小的t。

可以使用二分答案,t左边的均小于t,右边均大于等于t。

AC代码

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
38
39
40
41
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;
int n;
int w[N];

bool check(int t)
{
int w1 = 0, w2 = 0;
for (int i = 0; i < n; i++)
{
if (w[i] < t) w1 += w[i];
if (w[i] > t) w2 += w[i];
}

if (w1 >= w2) return true;
else return false;
}

int main()
{
cin >> n;
for (int i = 0; i < n; i++) cin >> w[i];

sort(w, w + n);

int l = 1, r = w[n - 1];
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}

cout << l << endl;

return 0;
}

English单词积累

reindeer—驯鹿

sleigh—雪橇

buffalo—水牛

voles—田鼠

schnauze—髯狗

elves—精灵

ounces—盎司

G - Birthday Paradox(未做)

算法标签

概率

H - On Average They’re Purple(未做)

算法标签

BFS最短路

I - Full Depth Morning Show(未做)

算法标签

树形DP

J - This Ain’t Your Grandpa’s Checkerboard

算法标签

模拟

题目描述

brid

You are given an n−by−n grid where each square is colored either black or white. A grid is correct if all of the following conditions are satisfied:

  • ​ Every row has the same number of black squares as it has white squares.

  • ​ Every column has the same number of black squares as it has white squares.

  • ​ No row or column has 3 or more consecutive squares of the same color.

    Given a grid, determine whether it is correct.

输入

The first line contains an integer n(2≤n≤24; n is even) . Each of the next n lines contains a string of length n consisting solely of the characters ‘B’ and ‘W’, representing the colors of the grid squares.

输出

If the grid iscorrect, print the number 1 on a single line. Otherwise, print the number 0 on a single line.

样例

Input

1
2
3
4
5
4
WBBW
WBWB
BWWB
BWBW

Output

1
1

Input

1
2
3
4
5
4
BWWB
BWBB
WBBW
WBWW

Output

1
0

Input

1
2
3
4
5
6
7
6
BWBWWB
WBWBWB
WBBWBW
BBWBWW
BWWBBW
WWBWBB

Output

1
0

Input

1
2
3
4
5
6
7
6
WWBBWB
BBWWBW
WBWBWB
BWBWBW
BWBBWW
WBWWBB

Output

1
1

解题思路

题目数据范围不大,给定一个n*n的方块。

要求每行每列的黑色块数等于白色块数,并且每行每列相同颜色的连续快数小于3。

直接使用二维数组模拟即可。

AC代码

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 24;
char grid[N][N];

int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++) //输入
for (int j = 0; j < n; j++)
cin >> grid[i][j];

for (int i = 0; i < n; i++) //统计白色格数==黑色格数
{
int cnt = 0, cnt2 = 0;
for (int j = 0; j < n; j++)
{
if (grid[i][j] == 'B') cnt++;
if (grid[j][i] == 'B') cnt2++;
}
if (cnt * 2 != n || cnt2 * 2 != n)
{
cout << 0 << endl;
return 0;
}
}

for(int i = 0; i < n; i++) //统计行列是否连续格数<3
for (int j = 2; j < n; j++)
{
if (grid[i][j - 2] == grid[i][j - 1] && grid[i][j - 1] == grid[i][j])
{
cout << 0 << endl;
return 0;
}

if (grid[j - 2][i] == grid[j - 1][i] && grid[j - 1][i] == grid[j][i])
{
cout << 0 << endl;
return 0;
}
}

cout << 1 << endl;

return 0;
}

English单词积累

K - Solar Energy(未做)

算法标签

模拟退火