训练联盟热身训练赛（三）题解报告

A - Circuit Math

算法标签

后缀表达式

题目描述

You are enrolled in the Computer Organization and Architecture course at your university. You decide to write a program to help check your work by computing the output value of a combinational digital circuit, given its inputs.

Consider the circuit shown in Figure A.1, which we use for illustration. This circuit has four inputs (letters A through D on the left), each of which is either true or false. There are four ‘gates’ each of which is one of three types: AND, OR, or NOT. Each gate produces either a true or false value, depending on its inputs. The last gate (the OR on the right) produces the output of the entire circuit. We can write these three types of gates in text by their equivalent logical operators: *** for **AND, + for OR, and - for NOT. In what follows, we’ll use the operators rather than gates to describe circuits.

Here is how these operators work. Given an assignment of true (T) or false (F) for each input, the operators produce the truth value indicated in the following tables:

Notice that AND and OR take two inputs, whereas NOT operates on only one input. Also, we use postfix notation to write expressions involving operators (like A B *), where the operator comes after its input(s) (just as how in Figure A.1, each gate in the circuit diagram comes after its inputs).

When we describe a valid circuit in postfix notation, we use the following syntax.

• ​ An uppercase letter (A through Z) is a valid circuit. In other words, an input alone (without any gates) is a valid circuit (which produces as output its own input value).

• ​ If and are valid circuits, then ‘ *‘ is a valid circuit that produces the AND of the outputs of the two subcircuits.

• ​ If and are valid circuits, then ‘ +‘ is a valid circuit that produces the OR of the outputs of the two subcircuits.

• ​ If is a valid circuit, then ‘ -‘ is a valid circuit that produces the NOT of ‘s output.

  No other description is a valid circuit.

Thus, one of the ways the circuit in Figure A.1 could be described using postfix notation is as the string:

​ A B * C D + - +

Given a truth value (T or F) for each of the inputs (A, B, C, and D in this example), their values propagate through the gates of the circuit, and the truth value produced by the last gate is the output of the circuit. For example, when the above circuit is given inputs A = T, B = F, C = T, D = F, the output of the circuit is F.

Given an assignment to variables and a circuit description, your software should print the output of the circuit.

输入

The first line of the input consists of a single integer n, satisfying 1≤n≤26, denoting the number of input variables. Then follows a line with n space-separated characters. Each character is either T or F, with the i-th such character indicating the truth value of the input that is labeled with the i-th letter of the alphabet.

The last line of input contains a circuit description, which obeys the syntax described above. Each circuit is valid, uses only the first n letters of the alphabet as input labels, and contains at least 1 and at most 250 total non-space characters.

Note that while each variable is provided only one truth value, a variable may appear multiple times in the circuit description and serve as input to more than one gate.

输出

Print a single character, the output of the circuit (either T or F), when evaluated using the given input values.

样例

Input

4
T F T F
A B * C D + - +

Output

F

解题思路

数字电路题目，要求解析后缀表达式。

运算符号有与、或、非，与和或计算前两个变量，非计算前一个变量。

可以使用栈进行运算。运算后的结果压回栈中。

AC代码

#include <iostream>
#include <stack>

using namespace std;

int main()
{
	int n;
	bool truth[26] = { false };
	stack<bool> s;

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		char tmp;

		cin >> tmp;
		if (tmp == 'T')	truth[i] = true;
		else truth[i] = false;
	}

	char tmp;
	while (cin >> tmp)
	{
		
		bool a, b;

		if (tmp == '+')
		{
			a = s.top();
			s.pop();
			b = s.top();
			s.pop();

			s.push(a || b);
		}
		else if (tmp == '*')
		{
			a = s.top();
			s.pop();
			b = s.top();
			s.pop();

			s.push(a && b);
		}
		else if(tmp == '-')
		{
			a = s.top();
			s.pop();

			s.push(!a);
		}
		else
		{
			s.push(truth[tmp - 'A']);
		}
	}

	if (s.top())	cout << 'T' << endl;
	else cout << 'F' << endl;

	return 0;
}

English单词积累

enrolled in—报名参加

circuit—电路

postfix notation—后缀表达式

propagate—传播

assignment—赋值

B - Diagonal Cut

算法标签

数论

题目描述

Quido and Hugo are making a chocolate cake. The central ingredient of the cake is a large chocolate bar, lying unwrapped on the kitchen table. The bar is an M×N rectangular grid of chocolate blocks. All of the M N blocks are rectangles of identical shape and size. The chocolate bar is of top quality and the friends want to eat part of it, before the rest is used in the cake.

“OK,” says Quido, “let’s divide the whole bar into two triangular chunks by a straight diagonal cut from its upper-left corner to its lower-right corner. We will then eat all of the blocks which have been cut exactly in half, into two equal-area pieces. You will eat one half and I will eat the other half of each such block. All other blocks, that is, the blocks which are either uncut or cut into two parts of different sizes, will go directly into the cake. Of course, we will make sure the cut is perfectly precise.

Let’s see how much chocolate we get to eat!”

输入

The input consists of two space-separated integers M and N given on a single line, (where 1≤M,N≤10^18^). The numbers M and N denote the number of blocks in one column and in one row, respectively, in the chocolate bar.

输出

Print the number of blocks of the chocolate bar which are cut into exactly two pieces of equal area.

样例

Input

6 10

Output

2

Input

75206452536745713 10322579177493903

Output

40318322589

解题思路

题目大意是给出M*N的矩形巧克力。

从左上角到右下角切开巧克力。

如果某块巧克力恰好被切掉一半，就吃掉。

剩下的没被切到的或者切开不均匀的做蛋糕。

求有多少块巧克力恰好被切成两半。

1.如果是正方形，恰好切成两半的块数即边长。

2.如果是长方形，答案是M和N的最大公约数。

（证明过程待补充）

大致思路：M和N同为奇数只有一块，M和N一个是偶数则有零块。

其余M、N可以通过求最大公约数划分为小的m和n，然后判断个数。

AC代码

#include <iostream>
#include <algorithm>

using namespace std;

long long gcd(long long a, long long b)
{
	return b ? gcd(b, a % b) : a;
}

int main()
{
	long long m, n;
	long long ans;

	cin >> m >> n;

	ans = gcd(m, n);

	if (m / ans % 2 == 0 || n / ans % 2 == 0)
	{
		cout << 0 << endl;
	}
	else
	{
		if (m == n)	cout << m << endl;
		else cout << gcd(m, n) << endl;
	}

	return 0;
}

English单词积累

identical—完全相同

C - Gerrymandering（未做）

算法标签

模拟

D - Missing Numbers

算法标签

思维

题目描述

You enjoy your new job as a teacher of young children. It’s fun to see them learning to count, recognize letters, draw, and interact with the world.

One common problem you’ve noticed is that children often forget numbers when counting. For example, early on they might count “one, two, three, five, six.” You have to remind them about that “four” that they didn’t say. And as they get more proficient and clever, they may use the “quick” way of counting: “one, two, skip a few, ninety-nine, one hundred!”

Please write a program that can help you (and your students) identify the missing numbers when they are counting.

输入

The first line of input contains a single integer n, where 1 ≤ n ≤ 100. Each of the next n lines contains

one number that the child recited. Each recited number is an integer between 1 and 200 (inclusive). They

are listed in increasing order, and there are no duplicates.

输出

If the child recited all the numbers between 1 and the last number they recited, then print good job.

If the child missed any numbers between 1 and the last number they recited, then print those missing

numbers in increasing numeric order, one per line.

样例

Input

9
2
4
5
7
8
9
10
11
13

Output

1
3
6
12

Input

5
1
2
3
4
5

Output

good job

解题思路

水题，给出整数n，下面n行顺序递增的数字。

请输出遗漏的数字，如果没有遗漏的数字输出good job。

AC代码

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	bool flag = true;
	int first = 1, last;
	bool cnt[201] = { false };

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int tmp;

		cin >> tmp;
		cnt[tmp] = true;
		last = tmp;
	}

	for (int i = first; i <= last; i++)
	{
		if (cnt[i] == false)
		{
			flag = false;
			cout << i << endl;
		}
	}

	if (flag)	cout << "good job" << endl;

	return 0;
}

English单词积累

proficient—熟练

duplicates—完全一样的，副本

E - NVWLS（未做）

算法标签

AC自动机last优化 + dp

F - Prospecting（未做）

算法标签

防AK

G - Research Productivity Index（未做）

算法标签

期望DP

H - Running Routes（未做）

算法标签

区间DP

I - Slow Leak（未做）

算法标签

最短路

J - Stop Counting!（未做）

算法标签

前缀和

K - Summer Trip（未做）

算法标签

前缀和

L - Traveling Merchant（未做）

算法标签

线段树

M - Zipline（未做）

算法标签

几何