Codeforces Round 903 (Div. 3)

D. Divide and Equalize

Example

input

Copy

7

5

100 2 50 10 1

3

1 1 1

4

8 2 4 2

4

30 50 27 20

2

75 40

2

4 4

3

2 3 1

output

Copy

YES
YES
NO
YES
NO
YES
NO

Note

The first test case is explained in the problem statement.

很重要很重要的知识点！！！

1）

一个数的因数，且这个因数是素数，则这个因数被称为质因数

2）

任何合数都可以被分解成其质因数2，3，4的乘积。也可以说，当一个数被分解成最小因数的时候，这些因数是质因数（具体指的是2，3，5这三个质因数）

如果不是合数的话，就是质数，只能分解成1乘本身了

例如：

6可以分解为2 * 3，其中2和3都是质数，是6的素因子，也是它的最小因数

72可以分解为2 * 2 * 2 * 3 * 3。然而，它也可以分解为2 * 6 * 6或3 * 4 * 6等

3）

分解成质因子的乘积则是唯一的

例如：

通常，我们会将一个数分解成质因子的乘积，这是因为，每个数都可以唯一地分解成质因数的乘积。

例如，72可以分解为2 * 2 * 2 * 3 * 3。分解成质因子的乘积则是唯一的。

分析：知道以上知识点，这道题就很容易了。我们采用逆推的思维。

从答案入手，如果每个数都相等，那么每种质因数的数量一定能被n整除，这样才能保证每种质数被平均分，从而保证每个数都相等。

map<int, int> mp;
 
void Devide(int x) {
	for (int i = 2; i <= x / i; i++) {
		while (x % i == 0) {
			mp[i]++;
			x /= i;
		}
	}
	mp[x]++;
}
 
signed main() {
	int T; cin >> T;
	while (T--) {
		mp.clear();
		int n; cin >> n;
		for (int i = 0; i < n; i++) {
			int b; cin >> b;
			Devide(b);
		}
 
		int f = 0;
		for (auto it = mp.begin(); it != mp.end(); it++) {
			if (it->first <= 1) continue;
			if (it->second % n != 0) {
				cout << "NO" << endl;
				f = 1;
				break;
			}
		}
		if (!f) cout << "YES" << endl;
	}
 
 
	return 0;
}

E. Block Sequence

Example

input

Copy

7

7

3 3 4 5 2 6 1

4

5 6 3 2

6

3 4 1 6 7 7

3

1 4 3

5

1 2 3 4 5

5

1 2 3 1 2

5

4 5 5 1 5

output

Copy

0
4
1
1
2
1
0

Note

In the first test case of the example, the given sequence is already beautiful, as shown in the statement.

In the second test case of the example, the sequence can only be made beautiful by removing all elements from it.

In the fifth test case of the example, the sequence can be made beautiful by removing the first and last elements. Then the sequence will become [2, 3, 42, 3, 4].

分析：删与不删，容易想到是dp。我的惯性思维是从前往后dp，但有个问题，就是无法判断当前序列是否beautiful。

观察到每一块的第一个元素代表这一块接下来的长度，有一种向后延伸的感觉，但dp从前往后，显然无法顾及到后面的部分（例如在dp[i]时，不知道dp[i+n]的情况）。

因此要想到从后往前dp，这样就可以顾及到dp[i]后面的部分，然而dp[i]前面的部分是什么样子，其实可以不用关心。

接下来考虑删和不删

删：dp[i] = dp[i+1]+1

不删：有前提条件的！如果n-i

int a[N], dp[N];
signed main() {
	int T; cin >> T;
	while (T--) {
		memset(dp, 0, sizeof(dp));
		int n; cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
		}
 
		for (int i = n; i >= 1; i--) {
			dp[i] = dp[i + 1] + 1;//删
			if (n - i >= a[i]) {
				dp[i] = min(dp[i], dp[i + a[i] + 1]);
			}
		}
		//cout << "答案:";
		cout << dp[1] << endl;
	}
 
 
	return 0;
}