当前位置:网站首页>2020 "Lenovo Cup" National College programming online Invitational Competition and the third Shanghai University of technology programming competition
2020 "Lenovo Cup" National College programming online Invitational Competition and the third Shanghai University of technology programming competition
2022-07-05 08:51:00 【Qizi K】
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
边栏推荐
- Business modeling of software model | object modeling
- Hello everyone, welcome to my CSDN blog!
- Bit operation related operations
- Run menu analysis
- Install the CPU version of tensorflow+cuda+cudnn (ultra detailed)
- Digital analog 2: integer programming
- Programming implementation of ROS learning 2 publisher node
- Business modeling of software model | vision
- Halcon shape_ trans
- Solutions of ordinary differential equations (2) examples
猜你喜欢
随机推荐
猜谜语啦(8)
Basic number theory - fast power
C#【必备技能篇】ConfigurationManager 类的使用(文件App.config的使用)
Confusing basic concepts member variables local variables global variables
Several problems to be considered and solved in the design of multi tenant architecture
猜谜语啦(3)
ABC#237 C
JS asynchronous error handling
猜谜语啦(7)
Mathematical modeling: factor analysis
location search 属性获取登录用户名
猜谜语啦(142)
特征工程
[formation quotidienne - Tencent Selection 50] 557. Inverser le mot III dans la chaîne
猜谜语啦(5)
Halcon Chinese character recognition
我从技术到产品经理的几点体会
ECMAScript6介绍及环境搭建
Halcon blob analysis (ball.hdev)
Yolov4 target detection backbone