- 2021-04-18 15:08
*views 2*- Blue Bridge Cup

On the whole , It was fine in the middle of the game , That is to say, filling in the blanks takes a lot of time , I think the amount of code is very large , Maybe I'm too complicated ? But when we get to the back, it's very explosive , My head is in a mess , I can't concentrate , Maybe it's because I haven't done much recently , Wuwuwu , In the end, I left two questions and didn't do them . Recall the topic , No questions or codes in hand , I can only think about the way of thinking in the game by memory , Code and title , Code to do , The answer may also be wrong , Anyway, it's just for reference .

Updated questions

Save one !

<>A card

<> Title Description

Respectively 2021 individual 0-9, How many words can you spell from the beginning .

<> Brief introduction of thinking

Simple simulation

<> code

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

unsigned long long uLL; const int inf=0x3f3f3f3f; const int maxn=1e5+5; const

int N=6e6+5; const LL mod=998244353; const double pi=acos(-1); int n,ans,cnt[15]

,f=1; int main() // 3181 { scanf("%d",&n); //2021 for(int i=0;i<=9;i++) cnt[i]=n

; for(int i=1;i<=inf&&f;i++) { int now=i; while(now) { if(cnt[now%10]) cnt[now%

10]--; else f=0; now/=10; } if(f) ans=i; } printf("%d\n",ans); return 0; }

<> Reference results

3181

<>B straight line

<> Title Description

Two dimensional plane is given 20*21 A point , The number of straight lines formed by questions .

<> Brief introduction of thinking

I'm a couple , Reuse set De duplication record y=kx+b,x=a, These are two straight lines , The end result is s.size();

Code output after the game 48953; In the competition 57561…

I feel as like as two peas . Maybe it's all wrong ? I guess it's too accurate .

<> code

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

unsigned long long uLL; const int inf=0x3f3f3f3f; const int maxn=5e6+5; const

int N=1e7+15; const LL mod=998244353; const double eps=1e-7; const double pi=

acos(-1); int n,m; struct node{ double k,b; node(double kk,double bb) { k=kk,b=

bb; } friend bool operator < (node x,node y){ if(fabs(x.k-y.k)<eps) return x.b<y

.b; return x.k<y.k; } }; set<node>s; void solve(int a,int b,int c,int d) { if(a

==c&&b==d) return; if(a==c)//x=a; { if(s.find(node(1.0*inf,1.0*a))!=s.end())

return; s.insert(node(1.0*inf,1.0*a)); } else //y=kx-ka+b; { double kk=1.0*(d-b)

/(c-a); double bb=1.0*kk*a-b; if(s.find(node(kk,bb))!=s.end()) return; s.insert(

node(kk,bb)); } } int main() //20 21 { scanf("%d%d",&n,&m); for(int a=0;a<n;a++)

for(int b=0;b<m;b++) for(int c=0;c<n;c++) for(int d=0;d<m;d++) solve(a,b,c,d);

printf("%d\n",s.size()); return 0; }

<> Reference results

48953 ? It should be wrong

<>C Goods placement

<> Title Description

given n=2021041820210418（ It's the date only when the teammate reminds me ）, Divide a ∗ b ∗ c a*b*c a∗b∗c Number of Solutions

such as n=4 When I was young

1 1 4;1 4 1;1 1 4;1 2 2;2 1 2;2 2 1 Six methods of classification

<> Brief introduction of thinking

I just got this question , I think it's a big number , But after thinking about the decomposition, there should be no big prime number , I wrote factorization , After the decomposition is

2021041820210418

2 3 3 3 17 131 2857 5882353

After that is to write search , I need to write another one set duplicate removal .

<> code

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

unsigned long long uLL; const int inf=0x3f3f3f3f; const int maxn=5e6+5; const

int N=1e7+15; const LL mod=998244353; const double pi=acos(-1); struct node{ int

a,b,c; node(int aa,int bb,int cc) { a=aa,b=bb,c=cc; } friend bool operator < (

node x,node y){ if(x.a==y.a) { if(x.b==y.b) return x.c<y.c; return x.b<y.b; }

return x.a<y.a; } }; set<node>s; LL n,x[5]; int cnt,prime[maxn],res; bool

is_prime[N],f[maxn]; vector<LL>mid; void __prime() { for(int i=1;i<=N-5;i++)

is_prime[i]=1; is_prime[1]=0; for(int i=2;i<=N-5;i++) if(is_prime[i]) { prime[++

cnt]=i; for(int j=i;j<=N-5;j+=i) is_prime[j]=0; } } /* 2021041820210418 2 3 3 3

17 131 2857 5882353 */ void fen(){ LL now=n; for(int i=1;i<=cnt;i++) while(n%

prime[i]==0) n/=prime[i],mid.push_back(1LL*prime[i]); } void dfs(int ff,int now,

LL mul) { if(now==mid.size()) { x[ff]=mul; if(ff==1) { x[2]=n/x[1]/x[0]; if(s.

find(node(x[0],x[1],x[2]))!=s.end()) return; s.insert(node(x[0],x[1],x[2])); res

++; } else dfs(ff+1,0,1); return; } if(f[now]==0) { f[now]=1; dfs(ff,now+1,mul*

mid[now]); f[now]=0; dfs(ff,now+1,mul); } else dfs(ff,now+1,mul); } int main() {

__prime(); scanf("%lld",&n); fen(); for(int i=0;i<mid.size();i++) printf("%d ",

mid[i]); printf("\n"); dfs(0,0,1); printf("%d\n",res); return 0; }

<> Reference results

2430

<>D route

<> Problem description

The difference between the absolute values of two numbers is less than or equal to 21 Edge , The border right is lcm(i,j);

All in all 2021 One point

Ask from 1 reach 2021 The shortest path of

<> Brief introduction of thinking

Simulation mapping , The shortest path is OK .

My teammates told me before the game Bellon-Ford Here we go

And he wrote Freud. Haha

It's amazing

<> code

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

unsigned long long uLL; const int inf=0x3f3f3f3f; const int maxn=1e5+5; const

int N=6e6+5; const LL mod=998244353; const double pi=acos(-1); int gcd(int a,int

b){ if(b==0) return a; return gcd(b,a%b); } struct node{ int u,v,w; node(int uu

,int vv,int ww) { u=uu,v=vv,w=ww; } }; int n,dis[maxn]; vector<node>g; int main(

) { scanf("%d",&n); for(int i=1;i<=n;i++) dis[i]=inf; dis[1]=0; for(int i=1;i<=n

;i++) for(int j=i+1;j<=n;j++) { if(j-i>21) continue; g.push_back( node( i , j ,

i*j/gcd(i,j) ) ); } for(int i=1;i<=n-1;i++) { bool f=0; for(int j=0;j<g.size();j

++) { int u=g[j].u,v=g[j].v,w=g[j].w; if(dis[v]>dis[u]+w) f=1,dis[v]=dis[u]+w; }

if(f==0) break; } printf("%d\n",dis[n]); return 0; }

<> Reference results

10266837

<>E Loop count

I didn't do it , I thought I could do it , I want to do a big problem , It blew up in the back , gone for ever .

Now more, now more , I'm writing. I'm writing

When writing big questions, the mentality is a bit broken , I feel that there may be problems in reading .

I don't seem to remember the meaning ...

I can only think of ideas and codes in general , I don't know if I read it right

<>F Weighing with weights

<> Problem description

There is a balance and a pile of weights , Weights can be placed on the left or right . He now knows the weight of each weight . According to the above conditions , How many groups of different weights can be measured .

<> Brief introduction of thinking

dynamic programming ?

The feeling is to write a simple recursion , Just look at the code

The important thing is to survive -sum reach sum bar , So all subscripts are added sum.

<> code

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

unsigned long long uLL; const int inf=0x3f3f3f3f; const int maxn=1e3+5; const

int N=3e5+5; const LL mod=998244353; const double pi=acos(-1); vector<int>mid;

int n,res,a[maxn],sum,f[N]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++)

scanf("%d",&a[i]),sum+=a[i]; for(int i=1;i<=n;i++) { mid.clear(); mid.push_back(

sum+a[i]); mid.push_back(sum-a[i]); for(int j=0;j<=2*sum;j++) if(f[j]) { if(j-a[

i]>=0) mid.push_back(j-a[i]); mid.push_back(j+a[i]); } for(int j=0;j<mid.size();

j++) f[mid[j]]=1; } for(int i=sum+1;i<=2*sum;i++) if(f[i]) res++; printf("%d\n",

res); return 0; }

<>G XOR sequence

<> Problem description

Don't hit me if you're wrong , That means I read it wrong, too

A and B Two people are playing games , In the beginning, they each have a number a,b, Give an array x, The person whose turn is in each round can do two operations , Choose an XOR a Or XOR b, Each number can only be used once .A First hand , Multiple input and output .

Under the optimal strategy , Select all the numbers , Who has the biggest number wins , Otherwise it's a draw .

<> Brief introduction of thinking

All numbers are represented in binary , Count by bit . If there's only one at the top , I'm sure it's the first A I won , If there are two at the top , We should go to the next high position . So it's only about the parity of the digits , But that's the way to start A You won't lose at all , I don't know if it's too simple .. Abba, Abba, Abba , It's too delicious .

Wrong

First hand must lose 2 2 2 1

There's nothing left to save

<> code

#include<bits/stdc++.h> // None of the samples were tested using namespace std; typedef long long LL;

typedef unsigned long long uLL; const int inf=0x3f3f3f3f; const int maxn=1e5+5;

const int N=6e6+5; const LL mod=998244353; const double pi=acos(-1); int cnt[30]

,bit[30],n,t,x; int solve() { for(int i=25;i>=0;i--) if(cnt[i]%2) return 0*

printf("1\n"); return 0*printf("0\n"); } int main() { scanf("%d",&t); for(int i=

0;i<=25;i++) bit[i]=1<<i; while(t--) { scanf("%d",&n); memset(cnt,0,sizeof(cnt))

; for(int i=1;i<=n;i++) { scanf("%d",&x); for(int i=25;i>=0;i--) if(x>=bit[i]) x

-=bit[i],cnt[i]++; } solve(); } return 0; }

<>H Left child right brother

<> Problem description

Turn a tree into a binary tree according to left son and right brother . The root height of the tree is 0, Find the highest height of binary tree after transformation .

<> Brief introduction of thinking

structure , Recursive traversal of trees

<> code

Data range , I can't remember the examples and the details of the title , The code is for reference only

#include<bits/stdc++.h> using namespace std; typedef long long LL; const int

inf=0x3f3f3f3f; const int maxn=2e5+5; int n; vector<int>g[maxn]; int dfs(int u)

{ int mx=0,sz=g[u].size(); for(int i=0;i<sz;i++) mx=max(mx,dfs(g[u][i])+sz-1);

return mx+1; } int main() { scanf("%d",&n); for(int i=2,u;i<=n;i++) { scanf("%d"

,&u); g[u].push_back(i); } printf("%d\n",dfs(1)-1); return 0; }

<>I Bracket sequence

The most angry question , I always feel like I can do it , For more than an hour , I still didn't write it , At last, it is simplified to the problem of many line segments and points .

Examples ((()

The last thing that comes out is from [1,2],[1,3] The number of schemes to take two points on two line segments , namely (1,1),(1,2),(1,3),(2,2),(2,3) Five .

Another example (((()

It's from [1,2],[1,3],[1,4] Pick up point , namely (1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2),(1,2,3),(1,2,4),(1,3,3),(1,3,4),(2,2,2),(2,2,3),(2,2,4),(2,3,3),(2,3,4) Fourteen kinds .

But I just don't know how to deduce the formula , In the end, I didn't push out my watch , great , Finally, I wrote a pop search . There's less than half an hour left to finish this , also J and E I didn't touch it .

I don't want to write this question …

<>J Split fruit

<> Problem description

Divide candy

n Grow candy ,m personal , Each candy can be divided up to two times , At least once , Everyone's got to get it , And can only be divided into continuous candy .

<> Brief introduction of thinking

There's no time , There are about ten minutes left after reading the question , Wrote the most violent violence

Explosive search

initialization cnt Arrays are all arrays 2

Enumerate the start and end points when searching , Let's look at the starting point and the ending point , appear cnt[i]=0 This set of starting and ending points is illegal , If it's legal, keep searching , All the way back m personal , From 1 reach n Judge cnt[i]==2 It's not legal , Search for all the information res=min(res,mx-mn)

The time complexity is beyond imagination

probably n=10 It's hard to get out , But there's no time …

<> code

I don't want to write such violent code again

Wait for time to think about it .

Technology

- Java407 articles
- Python218 articles
- Linux114 articles
- Vue106 articles
- MySQL91 articles
- SpringBoot70 articles
- javascript70 articles
- Spring63 articles
- more...

Daily Recommendation

©2019-2020 Toolsou All rights reserved,

Hikvision - Embedded software written test questions C Language application 0 The length of array in memory and structure is 0 In depth analysis data structure --- The preorder of binary tree , Middle order , Subsequent traversal How to do it ipad Transfer of medium and super large files to computer elementui Shuttle box el-transfer Display list content text too long 2019 The 10th Blue Bridge Cup C/C++ A Summary after the National Games （ Beijing Tourism summary ）unity Shooting games , Implementation of first person camera python of numpy Module detailed explanation and application case Study notes 【STM32】 Digital steering gear Horizontal and vertical linkage pan tilt Vue Used in Element Open for the first time el-dialog Solution for not getting element