Hunan institute of technology in 2022 ACM training sixth week antithesis

A题 函数

来源：AtCoder Beginner Contest 234 A - Weird Function

考察：语言基础

难度：红题

直接计算即可.

#include<bits/stdc++.h>
#define endl '\n'
typedef long long ll;
const ll mod = 1e9 + 7;
double eps = 1e-6;
using namespace std;
int cal(int x) {
	return x * x + 2 * x + 3;
}
int main() {
	int t;
	cin >> t;
	cout << cal(cal(cal(t) + t) + cal(cal(t)));
	return 0;
}

B题 选择恐惧症

来源：AtCoder Beginner Contest 252 B - Takahashi's Failure

考察：模拟

难度：红题

To pick out the highest rating of milk tea,只要有一个是kk不喜欢的,那么就不符合要求.Just loop through it in order.

#include<bits/stdc++.h>
#define endl '\n'
typedef long long ll;
const ll mod = 1e9 + 7;
double eps = 1e-6;
using namespace std;
struct ss {
	int id, val;
}a[202];
bool cmp(ss s1, ss s2) {
	return s1.val > s2.val;
}
int main() {
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].val;
		a[i].id = i;
	}
	sort(a + 1, a + 1 + n, cmp);
	int f = 0;
	for (int i = 1; i <= k; i++) {
		int x;
		cin >> x;
		for (int j = 1; j <= n; j++) {
			if (a[j].val != a[1].val) {
				break;
			}
			else {
				if (x == a[j].id) {
					f = 1;
				}
			}
		}
	}
	if (f) {
		cout << "Yes";
	}
	else {
		cout << "No";
	}
	return 0;
}

C题 跳房子

来源：AtCoder Beginner Contest 240 C - Jumping Takahashi

考察：DP

难度：橙题

对于每一次操作,He can only affect his current position by the actions in front of him,因此dpThe ineffectiveness of the,我们用dp[i][j]表示前 i Whether the operation reached the position j,If reached, the value is1,否则为0.So for each operation,He carried out by the location of the last operation can reach the transfer.因此动态转移方程为 dp[ i ][ j + a[ i ] ] |= dp[ i - 1 ][ j ],dp[ i ][ j + b[ i ] ] |= dp[ i - 1 ][ j ].Also for the first operation,We initialize both of its jump distances as1即可.

#include<bits/stdc++.h>
#define endl '\n'
typedef long long ll;
const ll mod = 1e9 + 7;
double eps = 1e-6;
using namespace std;
int dp[200][20000];
int a[200], b[200];
int main() {
	int n, x;
	cin >> n >> x;
	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i];
	}
	dp[1][a[1]] = dp[1][b[1]] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= x; j++) {
			if (dp[i - 1][j]) {
				dp[i][j + a[i]] = 1;
				dp[i][j + b[i]] = 1;
			}
		}
	}
	if (dp[n][x]) {
		cout << "Yes";
	}
	else {
		cout << "No";
	}
	return 0;
}

D题 选数 2.0

来源：AtCoder Beginner Contest 233 C - Product

考察：思维 + Dfs

难度：黄题

This question can actually start from the data range,Because the product of the number of banknotes is less than or equal to1e5,The minimum number of stacks is 2,因此,That is to say if the blast search most we search17层,所以我们可以dfs直接做即可.但是要注意一点,Because the value of banknotes is relatively large,Therefore likely to burstlonglong.And we can from division to begin,rather than multiplication,we remove the current value,just follow1Start multiplying is equivalent,And don't worry about exploding data range.因此直接dfs爆搜即可.

#include<bits/stdc++.h>
#define endl '\n'
typedef long long ll;
const ll mod = 1e9 + 7;
double eps = 1e-6;
using namespace std;
vector<ll> a[202020];
ll n, sum;
void dfs(ll x, ll y) {
	if (x == n + 1) {
		if (y == 1) { //当 y 等于 1 时,Description just finished,or has been removed before.
			sum++;
		}
		return;
	}
	for (int i = 0; i < a[x].size(); i++) {
		if (y % a[x][i] == 0) { // 如果能整除,we put itdfs,If it is not divisible, it cannot be multiplied in reverse..
			dfs(x + 1, y / a[x][i]);
		}
	}
}
int main() {
	ll x;
	cin >> n >> x;
	for (int i = 1; i <= n; i++) {
		int l;
		cin >> l;
		for (int j = 1; j <= l; j++) {
			ll t;
			cin >> t;
			a[i].push_back(t);
		}
	}
	dfs(1, x);
	cout << sum;
	return 0;
}

E题 棋子

来源：AtCoder Beginner Contest 243 C - Collision 2

考察：思维 + Map

难度：橙题

题目要求,We need to determine if there will be a collision between the pieces.

Since the direction given by the title is only left and right,Then we just need to judge whether there are pawns in each row that will collide.

Then there is only one case of collision.在同一y坐标中,pawn on the left（xpawn with small coordinates）朝向右,The pieces on the right（xChess pieces with large coordinates）朝向左.x[i] < x[j] && s[i] == 'R' && s[j] == 'L'

If we directly use the loop to judge whether they meet the above conditions one by one,So for O(n^2) ,当 N Obviously it will time out when taking the maximum value,and the data range arrives1e9,If you use the array directly, it will explode the space.

因此我们可以使用mapGo to save the minimum coordinates of the line to the right and the maximum coordinates of the left.,然后用mapto traverse the line to see if the maximum point to the left is greater than the minimum point to the right,如果满足,Then it means there will be a collision.

#include<bits/stdc++.h>
#define endl '\n'
typedef long long ll;
const ll mod = 1e9 + 7;
double eps = 1e-6;
using namespace std;
struct ss {
	int x, y;
}a[202020];
int main() {
	int n;
	cin >> n;
	map<int, int> left, right;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].x >> a[i].y;
	}
	string b;
	cin >> b;
	int f = 0;
	for (int i = 0; i < b.size(); i++) {
		if (b[i] == 'R') {
			if (right[a[i + 1].y] == 0) {
				right[a[i + 1].y] = a[i + 1].x;
			}
			else {
				right[a[i + 1].y] = min(right[a[i + 1].y], a[i + 1].x);
			}
		}
		else {
			left[a[i + 1].y] = max(left[a[i + 1].y], a[i + 1].x);
		}
	}
	for (auto& t : right) {
		if (left[t.first] > right[t.first]) {
			f = 1;
		}
	}
	if (f) {
		cout << "Yes";
	}
	else {
		cout << "No";
	}
	return 0;
}

F题 building blocks stacking

来源：AtCoder Beginner Contest 227 D - Project Planning

考察：贪心 + 二分

难度：黄题

First, imagine the topic as stacking buns,有 n different kinds of buns,

Then the query becomes different each time c Take one each from the buns,最多可以取 s 次.

Because each bun take at most s 个,So consider putting more than s of steamed buns s 个.

 

 So we try to put the rest of the steamed bread into high for construction s 的 c Stacked buns,Then take it from top to bottom layer by layer..

However, the title requires that the steamed buns taken each time cannot be of the same species.,也就是Each layer cannot have the same type of buns,So the above stacking method is not feasible..

Note that each steamed bread up s 个,So we stack each stack of steamed buns on top of the stack to the left of it,The rest are stacked on their own.

 

Therefore, each layer of steamed buns will not appear the same kind.,And every steamed bread can be used.

那么As long as there are enough buns c × s must be able to construct c stack height is s each layer of different steamed buns.

So the problem becomes s After the high portion of the bun,Is there enough left over? c × s 个.

So how to pray to the part of the higher the number of steamed bread？

Obviously, for each steamed bun that has a high rise, remove the bottom of it. s 个馒头,The sum of the remaining number of buns.

 

So as long as you know more than s The number and quantity of steamed buns should be summed up. 

---This problem is solved from Luogu usersBearBrine

#include<bits/stdc++.h>
#define endl '\n'
typedef long long ll;
const ll mod = 1e9 + 7;
double eps = 1e-6;
using namespace std;
ll a[202020];
ll n, k;
int check(ll x) {
	ll temp = 0;
	for (int i = 1; i <= n; i++) {
		temp += min(a[i], x);
	}
	return temp >= x * k;
}
int main() {
	cin >> n >> k;
	ll sum = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		sum += a[i];
	}
	ll l = 0, r = sum / k;
	while (l <= r) {
		ll mid = l + r >> 1;
		if (check(mid)) {
			l = mid + 1;
		}else{
			r = mid - 1;
		}
	}
	cout << r;
	return 0;
}