A house plate making

Title Description

Calculate the number of characters 2 from 1 to 2020.

thinking

The amount of data is very small, direct violence, and the number of 2 can be counted for each number.

code

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int ans = 0;
	for (int i = 1; i <= 2020; i++) {
		int x = i;
		while (x) {
			if (x % 10 == 2)ans++;
			x /= 10;
		}
	}
	cout << ans << endl;
    return 0;
}

answer

624

B reduced fraction

Title Description

Definition of reduced fraction: the maximum common divisor of the numerator and denominator of a fraction is 1.
Calculate how many reduced fractions have numerators and denominators that are integers between 1 and 2020.

thinking

The amount of data is very small, with direct violence. The numerator is from 1 to 2020 and the denominator is from 1 to 2020. Judge the combination of numerator and denominator into 2020 × How many of the 2020 numbers meet the molecular denominator coprime.

code

#include<iostream>
#include<algorithm>
using namespace std;
int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a%b);
}
int main()
{
	int ans = 0;
	for (int i = 1; i <= 2020; i++) {
		for (int j = 1; j <= 2020; j++) {
			if (gcd(i, j) == 1)ans++;
		}
	}
	cout << ans << endl;
    return 0;
}

answer

2481215

C serpentine filling number

Title Description

Start with the positive integer of "infinite", as shown in the figure below.
1 2 6 7 15 ...
3 5 8 14 ...
4 9 13 ...
10 12 ...
11 ...
...
It is easy to see that the number in the second row and second column of the matrix is 5. Please calculate the number of row 20 and column 20 in the matrix?

thinking

Rotate the serpentine matrix 45 degrees clockwise:
1
3 2
4 5 6
10 9 8 7
11 12 13 14 15
......
The number of numbers in each row is equal to the number of rows in the current row. Odd rows are filled from left to right, and even rows are filled from right to left. The original (1, 1) corresponds to the present (1, 1), the original (2, 2) corresponds to the present (3, 2), the original (3, 3) corresponds to the present (5, 3),..., and it is deduced that the original (x, X) corresponds to the present (2x-1, x).
Therefore, the original line 20 and column 20 correspond to the current line 39 and column 20.

code

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 40;
int a[maxn][maxn];
int main()
{
	int cur = 1;
	for (int i = 1; i <= 40; i++) {
		int cnt = 0;
		if (i & 1) {
			for (int j = cur + i - 1; j >= cur; j--)a[i][++cnt] = j;
		}
		else {
			for (int j = cur; j < cur + i; j++)a[i][++cnt] = j;
		}
		cur += i;
	}
	cout << a[39][20] << endl;
    return 0;
}

answer

761

D seven segment code

Title Description

thinking

When building a simulation map, pay attention to the common connection points of three transistors when building a map. One transistor in the vertical needs to occupy two grids, and when using dfs search, search in eight directions before the connection relationship between the three can be expressed. There are 127 cases in which seven transistors are selected or not. Each case can be compressed into a binary number, which can be decoded to obtain the corresponding state according to a certain way. In this way, the amount of code can be saved.

code

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 1 << 7;
bool mp[6][4], vis[6][4];
int dir[8][2] = { {1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1} };
void build(int x) {
	memset(mp, 0, sizeof(mp));
	memset(vis, 0, sizeof(vis));
	for (int i = 1; i <= 5; i++) {
		if (i & 1)mp[i][2] = x & 1;
		else{
			mp[i][1] = mp[i + 1][1] = x & 1;
			x = x >> 1;
			mp[i][3] = mp[i + 1][3] = x & 1;
		}
		x = x >> 1;
	}
}
void dfs(int x, int y) {
	vis[x][y] = 1;
	for (int i = 0; i < 8; i++) {
		int nx = x + dir[i][0];
		int ny = y + dir[i][1];
		if (nx >= 1 && nx <= 5 && ny >= 1 && ny <= 3) {
			if (mp[nx][ny] && !vis[nx][ny])dfs(nx, ny);
		}
	}
}
int main()
{
	int ans = 0;
	for (int i = 1; i < maxn; i++) {
		build(i);
		int num = 0;
		for (int j = 1; j <= 5; j++) {
			for (int k = 1; k <= 3; k++) {
				if (mp[j][k] && !vis[j][k])dfs(j, k), num++;
			}
		}
		if (num == 1)ans++;
	}
	cout << ans << endl;
    return 0;
}

answer

80

E-plane segmentation

Title Description

How many parts can a plane be divided into by 20 circles and 20 straight lines?

thinking

① Since circle and straight line have their own properties, they are considered separately. It is easy to find the maximum segmentation field of a straight line. A straight line must intersect all existing straight lines once. A total of N times, the original n+1 region can be divided into 2 × (n+1) regions, that is, the number of regions plus n+1. Therefore, we only need to consider how many lines there are at present each time we divide the plane.
② A circle must intersect with all existing lines and circles twice, because the circle has the characteristics of closed curve. Every two times, the original n regions can be divided into 2 × N regions, that is, the number of regions is doubled. Therefore, it is only necessary to consider how many circles and straight lines there are at present each time the plane is divided.

deduction

① 1 straight line, divided into 1 + 1 areas
(1) 1 circle intersecting straight line, divided into 2 + 2 × 1 area
(2) Two circles intersect straight lines, divided into 2 + 2 × 1+2 × (1 + 1) areas
(3) 3 circles intersecting straight lines, divided into 2 + 2 × 1+2 × (1+1)+2 × (1 + 2) areas
......
② Two straight lines intersect and are divided into 1 + 1 + 2 areas
(1) 1 circle intersecting straight line, divided into 4 + 2 × 2 areas
(2) 2 circles intersecting straight lines, divided into 4 + 2 × 2+2 × (1 + 2) areas
......
③ Three straight lines intersect each other and are divided into 1 + 1 + 2 + 3 areas
......
④ Four straight lines intersect each other and are divided into 1 + 1 + 2 + 3 + 4 areas
......
To sum up, n straight lines intersect each other, divided into 1 + 1 + 2 + 3 + 4 +... + n=1+(1+n) × n/2 areas
M circles intersect straight lines, divided into 1 + (1 + n) × n/2+2 × n+2 × (n+1)+2 × (n+2)+……+2 × (n+m-1)= 1+(1+n) × n/2+2 × n × m+2 × (1+2+……+m-1)= 1+(1+n) × n/2+2 × n × m+m × (m-1)= 1+(1+n) × n/2+2 × n × m+m × (m-1) regions, substituting n=m=20, the maximum score is 1 + 21 × 10+2 × twenty × 20+20 × 19 = 1391 areas.

answer

1391

F performance analysis

Title Description

In an exam, each student's score is an integer from 0 to 100. Please calculate the highest score, lowest score and average score of this exam.

thinking

Note that when calculating the average share, open float, keep two decimal places, and other simulations can be done.

code

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int main()
{
	ll n;
	cin >> n;
	ll x;
	ll maxn = -1, minn = 1e9, sum = 0;
	for (ll i = 1; i <= n; i++) {
		cin >> x;
		maxn = max(maxn, x), minn = min(minn, x);
		sum += x;
	}
	cout << maxn << endl << minn << endl;
	double ans = sum*1.0 / n;
	ans *= 1000;
	if (ll(ans) % 10 >= 5) {
		ll y = 10 - (ll(ans) % 10);
		ans += y;
	}
	double a = ans*1.0 / 1000;
	printf("%.2lf\n", a);
    return 0;
}

G reply date

Title Description

Give a date and find out what is the nearest palindrome date and abbaba date after the date.

thinking

For convenience, since the amount of data is not so large, directly traverse all possible dates between the given date + 1 and 99991231 to judge whether they are legal one by one. Note that leap years are multiples of 4 and not multiples of 100, or multiples of 400.

code

#include<iostream>
using namespace std;
bool ishuiwen(int year, int month, int day) {
	if (year / 1000 != day % 10)return false;
	if ((year % 1000) / 100 != day / 10)return false;
	if ((year % 100) / 10 != month % 10)return false;
	if (year % 10 != month / 10)return false;
	return true;
}
bool isABABBABA(int year, int month, int day) {
	if (year / 1000 != (year % 100) / 10)return false;
	if (year / 1000 != month % 10)return false;
	if (year / 1000 != day % 10)return false;
	if (day / 10 != month / 10)return false;
	if (day / 10 != year % 10)return false;
	if (day / 10 != (year % 1000) / 100)return false;
	return true;
}
int get_year(int cal) {
	int st = cal / 10000000;
	int nd = (cal % 10000000) / 1000000;
	int rd = (cal % 1000000) / 100000;
	int th = (cal % 100000) / 10000;
	int year = st * 1000 + nd * 100 + rd * 10 + th;
	return year;
}
int get_month(int cal) {
	int st = (cal % 10000) / 1000;
	int nd = (cal % 1000) / 100;
	int month = st * 10 + nd;
	return month;
}
int get_day(int cal) {
	int st = (cal % 100) / 10;
	int nd = cal % 10;
	int day = st * 10 + nd;
	return day;
}
bool islegal(int year, int month, int day) {
	if (month >= 13 || month <= 0)return false;
	if (day <= 0)return false;
	if (month == 4 || month == 6 || month == 9 || month == 11) {
		if (day >= 31)return false;
	}
	else if (month != 2) {
		if (day >= 32)return false;
	}
	else {
		if (year % 4 == 0 && year % 100 || year % 400 == 0) {
			if (day >= 30)return false;
		}
		else {
			if (day >= 29)return false;
		}
	}
	return true;
}
int main()
{
	int cal;
	cin >> cal;
	int st = 0, nd = 0;
	for (int cur = cal + 1; cur <= 99991231; cur++) {
		int year = get_year(cur);
		int month = get_month(cur);
		int day = get_day(cur);
		if (!islegal(year, month, day))continue;
		if (ishuiwen(year, month, day) && !st)st = cur;
		if (isABABBABA(year, month, day) && !nd)nd = cur;
		if (st&&nd)break;
	}
	cout << st << endl << nd << endl;
    return 0;
}

H substring score

Title Description

For a string s, define the score f(S) of s as the number of characters that occur exactly once in S. Let the string length be n and calculate the sum of f(S[i... j]) for all non empty substrings S[i... j] (0 < = I < = j < = n).

thinking

To find the answer only by traversing once, the breakthrough is that there are only 26 characters, which can contribute to each character. Substrings can be divided into n classes, and each class ends with element i.
Let the required character be a. if there is no a in element i and before, the contribution of a to this kind of substring is 0; If element i and a appear once before, the contribution of a to such substring is equal to the position where a appears; If element i and previous a have appeared twice or more, the contribution of a to such substring is equal to the difference between the positions of the last two occurrences of a from element i. Therefore, we need to record the position of each element in the last two times before element i. Finally, the contributions of various characters are added to get the result.

code

#include<iostream>
#include<string>
using namespace std;
int main()
{
	string s;
	cin >> s;
	int ans = 0;
	for (int i = 0; i < 26; i++) {
		char x = 'a' + i;
		int last = -1, cur = -1;
		for (int j = 0; j < s.size(); j++) {
			if (s[j] == x) {
				if (cur == -1 && last == -1)cur = j + 1;
				else if (cur != -1 && last == -1)last = cur, cur = j + 1;
				else if (cur != -1 && last != -1)last = cur, cur = j + 1;
			}
			if (cur != -1 && last != -1)ans += (cur - last);
			else if (cur != -1 && last == -1)ans += cur;
		}
	}
	cout << ans << endl;
    return 0;
}

1. Two questions J

The difficulty is too high. I don't understand it without research. I won't give a problem solution here.