当前位置:网站首页>Blue Bridge Cup software provincial competition in April 2021: title + analysis (full version)

Blue Bridge Cup software provincial competition in April 2021: title + analysis (full version)

2021-09-15 04:10:40 AI bacteria


Related articles :


The first question is : card

 Insert picture description here
analysis :

First of all, we should clarify the problem : from 1 Start , Spell from small to large , So there will always be one number used up first ( Every number is limited ). According to the example in the title , It's not enough to spell 11, It's easy to see 1 Is the first to use up , And so it is . So the key to this question is : Find out that you happen to use the 2021 individual 1 Of cards !

Reference code :

#include<iostream>
#include<sstream>
#include<algorithm>
using namespace std;

// Integer to string  
string int_str(int i)
{
    
	string output;
	stringstream Convert;
	Convert<<i;
	Convert>>output;
	return output;
}

int main()
{
    
	int i=1;
	int nOne=0;
	while(1)
	{
    
		string s = int_str(i);
		nOne += count(s.begin(), s.end(), '1');// Record 1 Number of occurrences  
		if(nOne>=2021)
			break;
		else
			i += 1; 
	}
	cout<<i<<endl;
	return 0;
} 

The code run output is :3181. It should be noted that ,3181 There are two 1, At this time, you need to make sure , Which one? 1 It's No 2021 individual 1. Through judgment, we know ,3181 The one in front of the 1 It's No 2020 individual 1, The one in the back 1 It's No 2021 individual 1. therefore 3181 It's just something you can put together , and 3182 Can't spell . So the final answer is :3181


The second question is : A straight line

 Insert picture description here
analysis : Total straight line = Oblique line + Horizontal straight line + Vertical straight line . Horizontal and vertical lines are easy to count , Namely 21 and 20 individual , Therefore, focus on the statistics of the number of different oblique lines . Each line can be used :y=kx+b Express , That is, a different set of {k, b} Represent different lines . So the key point of this problem is to use the set to store and count the number of different oblique lines .

Refer to the answer : 40257

#include <iostream>
#include <vector>
#include <set>
using namespace std;

struct point
{
    
	int x; // Abscissa 
	int y; // Ordinate 
};

int main()
{
    
	vector<point> p;// Store all points 
	for (int i = 0; i <= 19; ++i)
		for (int j = 0; j <= 20; ++j)
			p.push_back({
    i, j});

	int len = p.size();
	set<pair<double, double>> lines; // Store oblique lines y=kx+b
	for (int i = 0; i < len; ++i)
	{
    
		for (int j = 0; j < len; ++j)
		{
    
			if (p[i].x != p[j].x && p[i].y != p[j].y) //  Statistics of all oblique lines 
			{
    
				double k = (p[j].y - p[i].y) * 1.0 / (p[j].x - p[i].x);
				double b = (p[j].y * (p[j].x - p[i].x) - (p[j].y - p[i].y) * p[j].x) * 1.0 / (p[j].x - p[i].x);
				//double b = p[j].y - k * p[j].x;  Not in this way , avoid k Cause precision explosion 
				lines.insert(pair<double, double>(k, b));
			}

		}
	}
	cout << lines.size() + 20 + 21 << endl; //  Total straight line = Oblique line + Horizontal straight line + Vertical straight line 
	return 0;
}

Third question : Goods placement

 Insert picture description here
analysis : Find out first n All the factors of , Then judge the total number of schemes according to the factor .

Refer to the answer : 2430

#include <iostream>
#include <vector>
using namespace std;
const long long n = 2021041820210418;

int main()
{
    
	vector<long long> factor; // Store all factors 
	
	for (int i = 1; i < sqrt(n); ++i)
	{
    
		if (n%i == 0)
		{
    
			factor.push_back(i);
			factor.push_back(n / i);
		}
	}

	// Enumerate the situations 
	int ans = 0;
	int len = factor.size(); // The total number of factors 
	for (int i = 0; i < len; ++i)
		for (int j = 0; j < len; ++j)
		{
    
			if(n%(factor[i]*factor[j])==0)
				ans += 1;
		}
	cout << ans << endl;
	return 0;
}

Fourth question : route

 Insert picture description here
Answer key : The test point of this question is to find the least common multiple and the shortest path algorithm dijstra, But this question can also be used dp do .

Refer to the answer : 10266837

#include <iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
const ll inf = 1e12;
int vis[2050];
ll e[2050][2050], dis[2050];

ll gcd(ll a, ll b)   // Find the greatest common factor 
{
    
	return a % b == 0 ? b : gcd(b, a % b);
}

ll lcm(ll a, ll b)	// Find the least common multiple 
{
    
	return a * b / gcd(a, b);
}

int main()
{
    
	fill(dis, dis + 2050, inf);
	fill(e[0], e[0] + 2050 * 2050, inf);
	for (int i = 1; i <= 2021;i++)
	{
    
		for (int j = 1; j <= 21;j++)    //21 Valid within steps 
		{
    
			int k = i + j;  //i As a starting point ,k End point 
			if (k > 2021)
				break;
			e[i][k] = e[k][i] = lcm(i, k);
		}
	}
	dis[1] = 0;
	// Shortest path template  dijstra Algorithm 
	for (int i = 1; i <= 2021;i++)
	{
    
		ll u = -1, minn = inf;
		for (int j = 1; j <= 2021;j++)// Find the starting point 
		{
    
			if (!vis[j] && dis[j] < minn)
			{
    
				minn = dis[j];
				u = j;
			}
		}
		if (u == -1)
			break;
		vis[u] = 1;
		for (int v = 1; v <= 2021;v++)
		{
    
			if (!vis[v])
				dis[v] = min(dis[v], e[u][v] + dis[u]);
		}
	}
	cout << dis[2021];
	return 0;
}

Fifth question : Loop count

 Insert picture description here


Sixth question : Time to show

 Insert picture description here
analysis :

This question is relatively simple , You need to pay attention to two points to complete :

  • Note the unit conversion ,1 God = 24h = 24x60min = 24x60x60s = 24x60x60x1000ms
  • Show problems ,0-9 To display as 00-09

Reference code :

#include<iostream>
#include<sstream>
#include<algorithm>
using namespace std;

int main()
{
    
	long long num;
	cin >> num;
	long long time = num % (24 * 60 * 60 * 1000);
	// The clock  
	int HH = time / (60 * 60 * 1000);
	// minute  
	int MM = time % (60 * 60 * 1000);
	MM = MM / 60000;
	// Second 
	int SS = (time / 1000) % 60;
	printf("%02d:%02d:%02d", HH, MM, SS);
	return 0;
}

Question seven : Weighing with weights

 Insert picture description here  Insert picture description here
Answer key : Adopt dynamic planning ,dp[i][j] Before presentation i Items , If you can weigh j Then for 1 , Instead of 0

#include <iostream>
#define N 102
#define MAX_WEIGHT 100005
using namespace std;

int n, m, k, w[N], sum_weight, ans;
bool dp[N][MAX_WEIGHT << 2];

int main() {
    
	cin >> n;
	for (int i = 1; i <= n; ++i) {
    
		cin >> w[i];
		sum_weight += w[i];
	}
	dp[0][sum_weight * 2] = true;
	for (int i = 1; i <= n; ++i) {
    
		for (int j = sum_weight; j <= sum_weight * 3; ++j) {
    
			dp[i][j] = dp[i][j] || dp[i - 1][j] || dp[i - 1][j - w[i]] || dp[i - 1][j + w[i]];
		}
	}
	for (int i = 1; i <= sum_weight; ++i) {
    
		if (dp[n][sum_weight + i] || dp[n][sum_weight - i]) {
    
			++ans;
		}
	}
	cout << ans;
	return 0;
}


The eighth question : Yanghui triangle

 Insert picture description here
Answer key :

#include <iostream>
#include <algorithm>
#define ll long long
#define N 100005
using namespace std;

ll n, c[N], p, q;
bool flag;

int main() {
    
	cin >> n;
	if (n == 1) {
     // Special judgement  1
		cout << 1 << endl;
		return 0;
	}
	c[0] = c[1] = 1;
	p = 1;
	while (c[2] < n) {
    
		++p;
		for (int i = p / 2 + 1; i > 0; --i) {
    
			c[i] += c[i - 1];
		}
		c[p] = 1;
		q = lower_bound(c, c + p / 2, n) - c;
		if (c[q] == n) {
    
			flag = true;
			break;
		}
	}
	if (flag) {
    
		cout<<(1 + p) * p / 2ll + q + 1ll;
	}
	else {
    
		cout<<(1 + n) * n / 2ll + 2ll;
	}
	return 0;
}

Question 9 : Two way sorting

 Insert picture description here
Answer key : This question is relatively simple , The key is to apply array sorting flexibly , Here we can use STL In the algorithm sort() function , Sort in ascending and descending order , Very convenient !

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

//  Custom descending sort predicate 
bool cmp(int a, int b)
{
    
	return a > b;
}

int main()
{
    
	int n = 0; // Sequence length 
	int m = 0; // Operating frequency 
	cin >> n >> m; // Input sequence length 、 Operating frequency 
	vector<int> a;
	for (int i = 1; i <= n; i++)
		a.push_back(i); //  The original sequence 
	for (int i = 0; i < m; i++)
	{
    
		int p, q;
		cin >> p >> q; //  Enter sort type 、 Parameters ( Sort critical point )
		if (p == 0)
			sort(a.begin(), a.begin() + q, cmp); // Descending 
		else
			sort(a.begin() + q - 1, a.end()); // Ascending 
	}
	for (int i = 0; i < n;i++)
	{
    
		cout << a[i] << " ";
	}
	return 0;
}

Question 10 : Bracket sequence

 Insert picture description here


Due to limited level , There are some mistakes in blogs , If there is any mistake, please give me your advice !

 Insert picture description here
The follow-up is stepping up the update , I wish you all the best !

版权声明
本文为[AI bacteria]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/09/20210909111002687K.html

随机推荐