©2020-2024 ioDraw All rights reserved
@author：xuanzo（icpc Iron player , A weak chicken ）
If there is an error , Welcome comments that , thank .
<>A, space
【 Problem description 】
Xiaolan is ready to use 256MB Open an array in the memory space of , Every element of the array is 32 position
Binary integer , If the space occupied by the program and the auxiliary space required to maintain memory are not considered , Excuse me?
256MB How many can you store in your space 32 Bit binary integer ?
256MB Convert into B namely 256*1024*1024 Convert to bit yes 256*1024*1024*8 32 Bit integer is 256*1024*1024*8/32 #
include<bits/stdc++.h> #define ll long long using namespace std; int main(){
//MB KB B bit ll ans=256; cout<<ans*1024*1024*8/32<<endl; } //671008864
<>B, card
【 Problem description 】
Xiaolan has many digital cards , There are numbers on every card 0 reach 9.
Xiao Lan is going to spell some numbers with these cards , From him 1 Start spelling positive integers , Each spell one ,
Just keep it , Cards can't be used to spell other numbers .
Xiaolan wants to know what she can do from 1 How much do you spell .
for example , When Xiaolan has 30 Card , among 0 reach 9 various 3 Zhang , Then little blue can spell 1 reach 10,
But spell 11 Time card 1 There's only one , Not enough to spell 11.
Now Xiaolan has it in her hand 0 reach 9 Each card 2021 Zhang , common 20210 Zhang , Can Xiaolan go from 1
How much do you spell ?
prompt ： It is recommended to use computer programming to solve the problem .
Open an array and save it 0-9 Number of cards , Then from 1 Start traversing back Decompose the current traversal number each time If the number of cards is zero Indicates that the current number cannot be spelled out Directly output the previous number #include
<bits/stdc++.h> #define ll long long using namespace std; int a[11]; int main(){
for(int i=0;i<10;i++) a[i]=2021; int cnt=1; while(1){ int x=cnt; while(x){ if(a[
x%10]==0){ cout<<cnt-1<<endl; return 0; } a[x%10]--; x/=10; } cnt++; } } //3181
<>C, straight line
【 Problem description 】
In plane rectangular coordinate system , Two points can determine a straight line . If there are many points in a straight line ,
Then the straight line determined by any two of these points is the same .
On a given plane 2 × 3 Whole point {(x, y)|0 ≤ x < 2, 0 ≤ y < 3, x ∈ Z, y ∈ Z}, Abscissa
yes 0 reach 1 ( contain 0 and 1) Integer between , The ordinate is 0 reach 2 ( contain 0 and 2) Integer between
Point of . These points have been determined 11 Different lines .
On a given plane 20 × 21 A whole point {(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z}, Namely horizontal
The coordinates are 0 reach 19 ( contain 0 and 19) Integer between , The ordinate is 0 reach 20 ( contain 0 and 20) of
Point of integer between . How many different straight lines are determined by these points .
Open a map perhaps set Save each line A slope k And intercept b Determine a straight line k=(y2-y1)/(x2-x1) b=-k*x1+y1=(x2*y1-x1*y2)/(
x2-x1) Then add horizontal and vertical lines . It's all straight lines #include<bits/stdc++.h> #define ll long long using
namespace std; struct Point{ double x,y; }point[25*25];// Save every point map<pair<double,
double>,int> m;// Storage slope k And intercept b int main(){ int cnt=0; for(int i=0;i<20;i++){ for(int
j=0;j<21;j++){ point[cnt].x=i; point[cnt].y=j; cnt++; } } int ans=20+21; for(int
i=0;i<cnt;i++){ for(int j=0;j<cnt;j++){ // The straight line of two points is parallel to or Co located with the coordinate axis if(point[i].x==point[j
].x||point[i].y==point[j].y) continue; // Slope and intercept double k=(point[j].y-point[i].y)/
(point[j].x-point[i].x); double b=(point[j].x*point[i].y-point[j].y*point[i].x)/
(point[j].x-point[i].x); if(m[{k,b}]==0){ m[{k,b}]=1; ans++; } } } cout<<ans<<
endl; } //40257
<>D, Cargo placement
【 Problem description 】
Xiaolan has a huge warehouse , Can put a lot of goods .
Now? , Xiao Lanyou n Boxes of goods shall be placed in the warehouse , Each box of goods is a regular cube . Blue
The length is specified , wide , Three directions perpendicular to each other , The sides of each case must be strictly parallel to the length ,
wide , high .
Xiaolan hopes that all the goods will eventually be placed into a big cube . That is, in the long , wide , High direction
Separate heap L,W,H Goods , satisfy n = L × W × H.
given n, How many schemes for stacking goods meet the requirements .
for example , When n = 4 Time , Have the following 6 Kinds of schemes ：1×1×4,1×2×2,1×4×1,2×1×2, 2 × 2 × 1,4 × 1 × 1.
Excuse me? , When n = 2021041820210418 （ Attention yes 16 Digit number ） Time , How many are there altogether
programme ?
prompt ： It is recommended to use computer programming to solve the problem .
Obtained by decomposition of prime factor 2 1 3 3 17 1 131 1 2857 1 5882353 1 about 2,17,131,2857,5882353, have 3^5=
243 Kinds of schemes about 3, 3,3,3 happen now and then 1 species ,1,3,9 have 6 species ,1,1,27 have 3 species , total 10 species So the total number of schemes is 243*10=2430 #include
<bits/stdc++.h> #define ll long long using namespace std; vector<int> prime; int
num[10000005]; bool vis[10000005]; void shai(){ memset(vis,0,sizeof(vis)); for(
int i=2;i<=10000000;i++){ if(!vis[i]){ prime.push_back(i); for(int j=i+i;j<=
10000000;j+=i){ vis[j]=1; } } } return; } vector<int> v; int main(){ shai(); ll
n=2021041820210418; for(int i=0;i<prime.size();i++){ num[i]=0; while(n%prime[i]
==0){ n/=prime[i]; num[i]++; } if(num[i]!=0) v.push_back(i); } //ll check=1; for
(int i=0;i<v.size();i++){ cout<<prime[v[i]]<<' '<<num[v[i]]<<endl; //for(int
j=1;j<=num[v[i]];j++) //check*=prime[v[i]]; } //cout<<check<<endl; } //2430
<>E, route
【 Problem description 】
Xiaolan is very happy after learning the shortest path , He defined a special graph , Hope to find the map
Shortest path in .
Little blue's picture is by 2021 Composed of nodes , Serial number 1 to 2021.
For two different nodes a, b, If a and b The absolute value of the difference is greater than 21, Then there are two nodes
There is no edge connection between them ; If a and b The absolute value of the difference is less than or equal to 21, Then there is a line between the two points
Count Reg a and b The undirected edge of the least common multiple of .
for example ： node 1 And node 23 There is no edge connection between them ; node 3 And node 24 There is a none between
To the side , Count Reg 24; node 15 And node 25 There is an undirected edge between , Count Reg 75.
Please calculate , node 1 And node 2021 What is the shortest path length between .
prompt ： It is recommended to use computer programming to solve the problem .
First calculate the weight of the edge , Then run the single source shortest circuit dijkstra #include<bits/stdc++.h> #define ll long long using
namespace std; int d[2025]; int edges[2025][2025]; int gcd(int x,int y){ return
x%y?gcd(y,x%y):y; } bool vis[2025]; int main(){ memset(edges,0x3f3f3f3f,sizeof(
edges)); for(int i=1;i<=2021;i++) edges[i][i]=0; for(int i=1;i<=2021;i++){ for(
int j=i+1;j<=2021&&j<=i+21;j++){ int w=i*j/gcd(i,j); edges[i][j]=edges[j][i]=w;
} } memset(d,0x3f3f3f3f,sizeof(d)); d[1]=0; for(int i=1;i<=2021;i++){ int x=0;
for(int j=1;j<=2021;j++){ if(!vis[j]&&d[j]<d[x]){ x=j; } } vis[x]=1; for(int j=
max(1,x-21);j<=min(2021,x+21);j++){// Shear value , Only these points have edges d[j]=min(d[j],d[x]+edges[x][j]);
} } cout<<d[2021]<<endl; } //10266837
<>F, Time display
【 Problem description 】
Xiaolan wants to cooperate with her friends to develop a time display website . On the server , Friends have obtained
The current time has been , Expressed as an integer , Value is from 1970 year 1 month 1 day 00:00:00 To current time
Milliseconds elapsed .
Now? , Xiaolan wants to display this time on the client . Little blue doesn't need to show the date , It only needs
Display the hour, minute and second , Milliseconds are not displayed , Just throw it away .
Given a time expressed as an integer , Please output the hour, minute and second corresponding to this time .
【 Input format 】
The input line contains an integer , Represent time .
【 Output format 】
Output the current time represented by hours, minutes and seconds , Format as HH:MM:SS, among HH Representation time , value
by 0 reach 23,MM Expressed score , Value is 0 reach 59,SS Indicates seconds , Value is 0 reach 59. Time , branch , second
Fill in the leading when it is less than two digits 0.
【 sample input 1】
46800999
【 sample output 1】
13:00:00
【 sample input 2】
1618708103123
【 sample output 2】
01:08:23
【 Scale and agreement of evaluation cases 】
For all profiling cases , The given time is no more than 1018 Positive integer of .
What is the time of the day 86400000ms Pair the input data 86400000 Take mold , Then divide by 1000 From that day 00:00:00 The number of seconds elapsed until now .
each 3600 A second is an hour , Then the rest of the time 60 Second is one minute , The last remaining is seconds . #include<bits/stdc++.h> #define ll long
long using namespace std; int main(){ ll a; cin>>a; a%=86400000; a/=1000; int h=
a/3600,m=(a%3600)/60,s=a%60; if(h>=10) cout<<h<<':'; else cout<<'0'<<h<<':'; if(
m>=10) cout<<m<<':'; else cout<<'0'<<m<<':'; if(s>=10) cout<<s; else cout<<'0'<<
s; }
<>G, Weight weighing
【 Problem description 】
You have a balance and N Weights , this N The weights of the weights are W1, W2, · · · , WN.
Please calculate how many different weights you can weigh ?
Note that the weight can be placed on both sides of the balance .
【 Input format 】
The first line of input contains an integer N.
The second line contains N Integer ：W1, W2, W3, · · · , WN.
【 Output format 】
Output an integer representing the answer .
【 sample input 】
3
1 4 6
【 sample output 】
10
【 Example description 】
Can weigh 10 The weight is ：1,2,3,4,5,6,7,9,10,11.
1 = 1;
2 = 6 − 4 ( Put the balance aside 6, On the other side 4);
3 = 4 − 1;
4 = 4;
5 = 6 − 1;
6 = 6;
7 = 1 + 6;
9 = 4 + 6 − 1;
10 = 4 + 6;
11 = 1 + 4 + 6.
【 Scale and agreement of evaluation cases 】
about 50% Evaluation cases for ,1 ≤ N ≤ 15.
For all profiling cases ,1 ≤ N ≤ 100,N The total weight of each weight does not exceed 100000.
Run twice 01 knapsack , The first time is to add weights , The second time is to reduce the weight . （ For weight reduction If the current weight has been added , It's equivalent to taking down the weight
If the current weight is not added , It is equivalent to putting the weight on the other side of the balance Therefore, there will be no conflict ） #include<bits/stdc++.h> #define ll long long
using namespace std; int dp[100005]; int w[105]; int main(){ int n; cin>>n; for(
int i=1;i<=n;i++){ cin>>w[i]; } memset(dp,0,sizeof(dp)); dp[0]=1; for(int i=1;i
<=n;i++){ for(int j=100000;j>=w[i];j--){ dp[j]=max(dp[j],dp[j-w[i]]); } } for(
int i=1;i<=n;i++){ int siz=100000-w[i]; for(int j=1;j<=siz;j++){ dp[j]=max(dp[j]
,dp[j+w[i]]); } } int ans=0; for(int i=1;i<=100000;i++){ ans+=dp[i]; } cout<<ans
<<endl; }
<>H, Yang Hui triangle
【 Problem description 】
The following figure is the famous Yang Hui triangle ：
If we press from top to bottom , Arrange all the numbers in a row from left to right , You can get the following
series ：
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, …
Given a positive integer N, Please output the first time in the sequence N What number is it ?
【 Input format 】
Enter an integer N.
【 Output format 】
Output an integer representing the answer .
【 sample input 】
6
【 sample output 】
13
【 Scale and agreement of evaluation cases 】
about 20% Evaluation cases for ,1 ≤ N ≤ 10;
For all profiling cases ,1 ≤ N ≤ 1000000000.
binomial theorem , about C(3,n), When n be equal to 2000 Time ,C(3,2000)＞1e9 So you only need to count to the third 2000 All right , Count the rest C(1,n) and C(2,n) Just fine .
#include<bits/stdc++.h> #define ll long long using namespace std; int a[2005][
2005]; int main(){ ll N; cin>>N; memset(a,0,sizeof(a)); a[0][0]=1; for(int i=1;i
<2005;i++){ for(int j=1;j<=i;j++){ a[i][j]=a[i-1][j]+a[i-1][j-1]; if(a[i][j]==N)
{ cout<<i*(i-1)/2+j<<endl; return 0; } } } // If the one above is not found , Explain only C(1,n) and C(2,n) Satisfied
//n*(n-1)/2==N ll n=sqrt(N*2)+1; if(n*(n-1)/2==N){ //C(2,n) cout<<n*(n+1)/2+3<<
endl; }else{ //C(1,n) cout<<N*(N+1)/2+2<<endl; } }
<>I, Bidirectional sorting
【 Problem description 】
Given sequence (a1, a2, · · · , an) = (1, 2, · · · , n), Namely ai = i.
Xiaolan will test this sequence m Secondary operation , Every time it may be a1, a2, · · · , aqi Descending order ,
Or will aqi , aqi+1, · · · , an Ascending arrangement .
Request the sequence after the operation is completed .
【 Input format 】
The first line of input contains two integers n, m, Represents the length of the sequence and the number of operations, respectively .
next m Line describes the operation on the sequence , Among them i The row contains two integers pi, qi Indicates the operation
Types and parameters . When pi = 0 Time , Indicates that it will a1, a2, · · · , aqi Descending order ; When pi = 1 Time , express
take aqi , aqi+1, · · · , an Ascending arrangement .
【 Output format 】
Output one line , contain n Integer , Adjacent integers are separated by a space , Indicates the operation
Sequence after completion .
【 sample input 】
3 3
0 3
1 2
0 2
【 sample output 】
3 1 2
【 Example description 】
The original sequence is (1, 2, 3). The first 1 After step (3, 2, 1). The first 2 After step (3, 1, 2). The first 3 After step (3, 1, 2). And the first 2
Same after step operation , Because the first two numbers are in descending order .
【 Scale and agreement of evaluation cases 】
about 30% Evaluation cases for ,n, m ≤ 1000;
about 60% Evaluation cases for ,n, m ≤ 5000;
For all profiling cases ,1 ≤ n, m ≤ 100000,0 ≤ ai ≤ 1,1 ≤ bi ≤ n.
can't , violence sort Cheat points #include<bits/stdc++.h> #define ll long long using namespace std;
/* int main(){ } */ // Violence score n*n*logn bool cmp(int x,int y){ return x>y; } int a[
100005]; int main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++) a[i]=i; while(m--
){//1e5 int p,q; cin>>p>>q; //nlogn if(p==0){ sort(a+1,a+q+1,cmp); }else{ sort(a
+q,a+n+1); } for(int i=1;i<=n;i++) cout<<a[i]<<' '; cout<<endl; } for(int i=1;i
<=n;i++) cout<<a[i]<<' '; }
<>J, Bracket sequence
【 Problem description 】
Given a sequence of parentheses , It is required to add as few parentheses as possible to make the sequence of parentheses legal ,
When the addition is complete , Different addition results will be produced , How many adding results are essentially different .
The two results are essentially different, which means that there is a certain position, and one result is the left parenthesis , And the other is right
number .
for example , For bracket sequences (((), Just add two parentheses to make it legal , There are the following
Different addition results ：()()(),()(()),(())(),(()()) and ((())).
【 Input format 】
The input line contains a string s, Represents the given sequence of parentheses , There are only left parentheses and in the sequence
Right bracket .
【 Output format 】
Output an integer to represent the answer , The answer may be big , Please output the answer divided by 1000000007 ( Namely
109 + 7) Remainder .
【 sample input 】
((()
【 sample output 】
5
【 Scale and agreement of evaluation cases 】
about 40% Evaluation cases for ,|s| ≤ 200.
For all profiling cases ,1 ≤ |s| ≤ 5000.
Divide the brackets into several parts , You only need to add one kind of parenthesis to each part ,dp Calculate the placement of each part , Then multiply it . dp I used prefixes and reduced complexity , Otherwise, it will probably time out #include
<bits/stdc++.h> #define ll long long using namespace std; //int
pre[5005],suf[5005]; //int dp[5005][5005]; const int mod=1e9+7; ll cal(string s)
{ int dp[s.size()+1][s.size()+1]; int suf[s.size()+1]; suf[s.size()]=0; memset(
dp,0,sizeof(dp)); dp[s.size()][0]=1; for(int i=s.size()-1;i>=0;i--){ suf[i]=suf[
i+1]+(s[i]==')'?1:0); if(s[i]==')'){ dp[i][0]=1; for(int j=1;j<=suf[i];j++){ dp[
i][j]=(dp[i+1][j]+dp[i][j-1])%mod; } }else{ for(int j=0;j<=suf[i];j++){ dp[i][j]
=dp[i+1][j]; } } } return dp[0][suf[0]]; } ll cal2(string s){ s="0"+s; int dp[s.
size()+1][s.size()+1]; int pre[s.size()+1]; pre[0]=0; memset(dp,0,sizeof(dp));
dp[0][0]=1; for(int i=1;i<s.size();i++){ pre[i]=pre[i-1]+(s[i]=='('?1:0); if(s[i
]=='('){ dp[i][0]=1; for(int j=1;j<=pre[i];j++){ dp[i][j]=(dp[i-1][j]+dp[i][j-1]
)%mod; } }else{ for(int j=0;j<=pre[i];j++){ dp[i][j]=dp[i-1][j]; } } } return dp
[s.size()-1][pre[s.size()-1]]; } int main(){ string s; cin>>s; int now=0;
string ss=""; ll ans=1; for(int i=0;i<s.size();i++){ if(s[i]=='(') now++; else
now--; ss+=s[i]; if(now<0){ while(i+1<s.size()&&s[i+1]==')'){ ss+=s[i+1]; i++; }
//cout<<ss<<' '<<cal(ss)<<endl; ans=(ans*cal(ss))%mod; ss=""; now=0; } } if(now
!=0){ //cout<<ss<<' '<<cal2(ss)<<endl; ans=(ans*cal2(ss))%mod; } cout<<ans%mod<<
endl; }
Technology