2020 "Lenovo Cup" National College programming online Invitational Competition and the third Shanghai University of technology programming competition

2020 year “ Lenovo cup ” Solution to the National College programming online Invitational Competition and the third Shanghai University of technology programming competition

Mengxin has come to write a solution
Original link

( Not in the order of question numbers QWQ）

L. Lottery Tickets
The question ： to 0-9 How many cards are there , It is required to form a number , This number can be 4 Divisible and maximal . Cards can not be used completely .

tips： Can be 4 Divisible numbers , The last two digits must be 4 to be divisible by .
Pay attention to the classified discussion （ Special judgement ） The situation is a little more qwq:
A. Only 0( The difference in B） Output 0
B. There is one 0 But no 2468 Output 0 （ Only 13579 and 0 Cannot form a two digit quilt 4 to be divisible by ）
C. There is one 4 But no 0268 Output 4
D. There is one 8 But no 0246 Output 8
E. other
E1. There are more than 1 A zero , And there are other numbers , Zero last .（ A hundred can be 4 to be divisible by ）
E2. Output in the following order .
{20,12,32,40,24,44,52,60,16,36,64,56,72,76,80,28,84,48,68,88,92,96};
Sort rule ： According to the maximum number, the minimum , If the largest number is the same, the order of the smallest number is the smallest .（ It's just greed ）

Code ：（ It's a mess , But it is these kinds of classification discussions ）

#include<bits/stdc++.h>
using namespace std;

int book[25] = {
    20,12,32,40,24,44,52,60,16,36,64,56,72,76,80,28,84,48,68,88,92,96};
int card[15],t;

bool judge(int x){
    
	if(x == 44)		return (card[4] >= 2) ? true : false; 
	if(x == 88)		return (card[8] >= 2) ? true : false; 
	else	return (card[x % 10] >= 1 && card[x / 10] >= 1)	? true : false; 
}

int main(){
    
	scanf("%d",&t);
	while(t--){
    
		string s = "";
		for(int i = 0; i <= 9; ++i)
			scanf("%d",&card[i]);
		if(card[0] == 1 && !card[2] && !card[4] && !card[6] && !card[8] && (card[1] || card[3] || card[5] || card[7] || card[9]))	s = "0";//A
		else if(card[0] > 0 && !card[2] && !card[4] && !card[6] && !card[8] && !card[1] && !card[3] && !card[5] && !card[7] && !card[9])	s = "0";		//B
		else if(card[4] == 1 && !card[2] && !card[8] && !card[6] && !card[0])	s = "4";		//C
		else if(card[8] == 1 && !card[2] && !card[4] && !card[6] && !card[0])	s = "8";		//D
		else if(card[0] >= 2 && (card[1] || card[2] || card[3] || card[5] || card[6] || card[7] || card[4] || card[9] || card[8])){
    		//E1
			s += "00";
			card[0] -= 2;
			for(int i = 0; i <= 9; ++i){
    
				for(int j = card[i]; j > 0; --j)
					s += i + '0';
			}
			reverse(s.begin(),s.end());
		}else{
    			//E2
			int idx;
			for(idx = 0; idx < 22; ++idx){
    
				if(judge(book[idx])){
    
					s += book[idx] % 10 + '0', card[book[idx] % 10]--;
					s += book[idx] / 10 + '0', card[book[idx] / 10]--;
					break;
				}
			}
			if(idx == 22){
    
				printf("-1\n");
				continue;
			}	
			for(int i = 0; i <= 9; ++i){
    
				for(int j = card[i]; j > 0; --j)
					s += i + '0';
			}
			reverse(s.begin(),s.end());
		}
		cout << s << endl;
	}
	return 0;
}

D. Disaster Recovery
The question ：n spot m Edge undirected connectivity graph , The first i The point weight of a point is the number of Fibonacci i
term , The edge right is the sum of the points at both ends , Find a minimum spanning tree of the original graph so that the degree is the most
The degree of the big point is the smallest .
Look at the picture qwq. The city number is fib The sequence , The weight is the sum of two numbers . Ask how to build roads , It can connect cities ！

tips: Almost naked kruskal Minimum spanning tree . utilize fib The nature of the sequence , according to pair<max(u,v),min(u,v)> Sort , You can get the arrangement of edge weights from small to large .（pair Sort in descending order ,fib The sequence ,max Big ones must be big . Because even if the other one is max-1 term ,max-2 term , Also have max-1 term +max-2 term = max term .)
Then calculate directly kruskal.

Use it carefully vector Write , Otherwise mle……

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> p;
const int maxn = 200005;
int n,m,cnt,f[100005],degree[100005],ans,x,y;
int find(int x){
    return f[x] == x ? x : f[x] = find(f[x]);}
int unite(int x, int y){
    
	int fa = find(x), fb = find(y);
	if(fa == fb)	return 0;
	else	f[fb] = f[fa];
	return 1;
} 
void init(){
    
	for(int i = 1; i <= n; ++i)	f[i] = i;
	ans = cnt = 0;
}
vector<p> edge;

int cmp(p r1, p r2){
    
	//return r1.second == r2.second ? r1.first < r2.first : r1.second < r2.second;  The same way 
	if(r1.second != r2.second)
		return r1.second < r2.second;
	else	return r1.first < r2.first;
}

int main(){
    
	scanf("%d%d",&n,&m);
	init();
	for(int i = 1; i <= m; ++i){
    
		scanf("%d%d",&x, &y);
		if (x > y) swap(x, y);
		edge.push_back(make_pair(x, y));
	}
	sort(edge.begin(), edge.end(), cmp);
	for(int i = 0; i < m; ++i){
    
		int u = edge[i].first, v = edge[i].second;
		if(unite(u,v))
			degree[u]++, degree[v]++;
	}
	int res = 0;
    for (int i = 1; i <= n; i++) res = max(res, degree[i]);
	printf("%d\n",res);
	return 0;
}
 

however ！！ This question has a kind of greed that seems to be correct but actually wrong ！ It is worth accumulating .
“ Greedy first 1 End in a row Reconnection 2 And so on , Because one point is connected with other points , The smaller the number, the better ”. The code implementation is the above cmp Change the function first/second The location of .
This will WA!!!
The conclusion is that , You can't be so greedy ！！
1-4,1-5,2-3,2-5,3-4
Press 1-5 The order of greed :1-4,1-5,2-3,2-5
According to the edge power greed ：2-3,1-4,3-4,1-5

Take the above example ,5 Connected 1 After that, it has been connected , Not necessarily with 2 Direct connection .（ It can be reached indirectly through other points 2 Number point ）. So greed is wrong qwqqqq

secondly ！！ To deepen the kruskal The understanding of the , Why? Use and check the collection , Instead of using set.
Get rid of this question , If the edge weights are in the order from small to large 1-3,2-4,2-3. If you use set,2-3 This side can't be connected qwq……

D. Disaster Recovery
t The question ： Cursive question .n × m Grid , The grass in each grid increases every second ai,j, continue with
Come on k Operations , Each operation will mow the grass of a column or row at a certain time ,
Find the sum of the grass finally cut .

tips: The contribution of each lattice depends only on it The last time I was cut . Just record it with a mark . Note that if you loop through each line / The grid mark of the column , Meeting TLE. Direct pair a line / A column is marked as a whole , For Compare the size of row and column tags that will do .
Be careful （a % mod) * ( b % mod) % mod, Direct ride will explode .

#include<bits/stdc++.h> 
#define ll long long 
#define mod 998244353
using namespace std;
int n,m,k,idx;
ll ans,ttime,mp[505][505],lie[505],hang[505],book[505][505];
char c;

int main(){
    
	scanf("%d%d%d",&n,&m,&k);
	for(int i = 1; i <= n; ++i){
    
		for(int j = 1; j <= m; ++j)
			scanf("%lld",&mp[i][j]);
	}
	for(int i = 1; i <= k; ++i){
    
		getchar();
		scanf("%c%d%lld",&c,&idx,&ttime);
		if(c == 'r'){
    
			for(int i = 1; i <= m; ++i){
    
				ll tmp = (ttime - max(hang[idx],lie[i]));
				book[idx][i] = (book[idx][i] % mod + tmp % mod) % mod;
			}
			hang[idx] = ttime;
		}else{
    
			for(int i = 1; i <= n; ++i){
    
				ll tmp = (ttime - max(lie[idx],hang[i]));
				book[i][idx] = (book[i][idx] % mod + tmp % mod) % mod;
			}
			lie[idx] = ttime;
		}
	}
	for(int i = 1; i <= n; ++i){
    
		for(int j = 1; j <= m; ++j){
    
			ll tmp = (mp[i][j] % mod * book[i][j] % mod ) % mod;
			ans = (ans % mod + tmp % mod) % mod;
		}
	}
	printf("%lld",ans);
	return 0;
}

A. Archmage
The question ： The maximum amount of mage's blue is n , Can spend per second x Release a skill , Per second
It will automatically return to blue y spot , After settlement, return to blue , ask m You can play skills at most several times in a second .
tips: A formula （ See the code ）.
A. If there is x ≤ y, Then it is obvious that he can release skills every second
B. If there is x > y, Before m - 1 The magic value restored in seconds can be used .

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll n,m,x,y,t;

int main(){
    
	scanf("%d",&t);
    while(t--){
    
        scanf("%lld%lld%lld%lld",&n,&m,&x,&y);
        printf("%lld\n",min(m, (n + (m - 1) * y) / x));
    }
    return 0;
}

B/C A little Sign in problem qwq