A: One two five eight

Title Description

There is a tribe on Planet X that has been using an ancient set of coins. This set of coins has four denominations: 1 star, 2 stars, 5 stars and 8 stars. The x-star man decided to carry the currency with a total amount of N-star for a global trip, because he needed to carry too many items. He wanted to carry the least amount of currency.
Can you write a program to help star X people calculate the minimum amount of money they need to carry?

input

Single group input. Each group has a positive integer n, which represents the total amount carried by star X. (N<=10^3)

output

Output the minimum amount of money that star X people need to carry.

• greedy
• Use as many 8 stars as you can

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
int main(){
    int n;
    scanf("%d",&n);
    int ans=n/8;
    n%=8;
    if(n==1||n==2||n==5)ans++;
    else if(n)ans+=2;
    printf("%d\n",ans);
    return 0;
}

B: And is 1

Title Description

Give n positive integers, in which there may be some same numbers. Now select m positive integers from these n numbers and record them as X1, X2,..., Xm respectively, so that these m numbers meet the following formula:
1/X1 + 1/X2 + ... + 1/Xm = 1
How many different combinations of numbers can make the above formula true?

input

Single group input.
In line 1, enter a positive integer n, indicating the number of positive integers entered. (n<=100)
On line 2, enter n positive integers separated by spaces.

output

Output the number of combinations that meet the requirements. If none of the combinations exist, "No solution!" is output.

• search
• It's easy to find a group with a sum of 1. Search directly, but there are many duplicate groups, so it's necessary to increase the judgment
• Search: it is divided into numerator and denominator. The number selected each time and the currently selected denominator find the least common multiple to form a new denominator, and then find the numerator to continue the search
• Weight judgment: first sort the array from small to large, and connect the selected number of each group with the string s. when recording the answer, only the answer string that appears for the first time is recorded
• The last round was AC91%, which changed the judgment for a long time

#include<bits/stdc++.h>
using namespace std;
int a[105];
int ans,n;
map<string,bool>vis;
int gcd(int x,int y){//greatest common divisor
    return y==0 ? x:gcd(y,x%y);
}
int lcm(int x,int y){//Least common multiple
    return x*y/gcd(x,y);
}
void dfs(int fz,int fm,string s,int pos){

    if(fz==fm&&fz){
        if(!vis[s])//Weight judgment
            ans++;
        vis[s]=1;
        return ;
    }
    if(pos>n)return ;
    if(fz==0)dfs(1,a[pos],s+to_string(a[pos]),pos+1);
    else {
        int m=lcm(a[pos],fm);
        int z=(m/a[pos])+(m/fm)*fz;
        int g=gcd(m,z);
        dfs(z/g,m/g,s+to_string(a[pos]),pos+1);
    }
    dfs(fz,fm,s,pos+1);

}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    dfs(0,0,"",1);
    if(ans)printf("%d\n",ans);
    else printf("No solution!\n");
    return 0;
}

C: Prime split

Title Description

If a prime number with n (n > = 2) bits is divided into two parts, where the high m bit is a prime number and the low (n-m) bit is also a prime number, then this number is called a separable prime number.
For example, 113 can be split into two parts. The upper two bits 11 are a prime number, and the lower one bit 3 is also a prime number. Therefore, 113 is a separable prime number.
Now enter two positive integers m and n (m < n). Please write a program to calculate how many separable prime numbers are between M and n (M and N can be included).

input

Single group input.
Enter two positive integers (M < = 10 and M < = 10).

output

Output the number of separable prime numbers between M and n (including M and N).

• enumeration
• Firstly, the prime numbers between 2~m are obtained by screening method, and then the numbers between n-m are enumerated to judge whether they are separable prime numbers
• Judging whether a prime number can be split is also enumeration. How many numbers are there before and after enumeration
• The code may be easier to understand than I said

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
int n,m;
bool isprime[1000005];
void prime(){//Finding prime numbers by sieve method
 
    int i,j;
    isprime[0] = false;
    isprime[1] = false;
    isprime[2] = true;
 
    for(i=3; i<=m; i++) {
        isprime[i++] = true;
        isprime[i] = false;
    }
    int ma = sqrt(m);
    for(i=3; i<=ma; i++){
        if(isprime[i]) {
            for(j=i+i; j <= m; j+=i)
                isprime[j] = false;
        }
    }
}
bool check(int i){//Judge whether a prime number can be split
    int x=10;
    while(x<=i){
        if(isprime[i/x]&&isprime[i%x])
            return 1;
        x*=10;
    }
    return 0;
}
void cnt(){
    int ans=0;
    for(int i=n;i<=m;i++){
        if(isprime[i]&&check(i)){
            ans++;
        }
    }
    printf("%d\n",ans);
}
int main(){
 
    scanf("%d%d",&n,&m);
    prime();
    cnt();
    return 0;
}

D: Hollow cylinder

Title Description

Xiaomi rolled N small hollow columns with thin paper. He wanted to insert some small hollow columns into the large hollow columns.
Given the bottom radius of each hollow cylinder, how many layers can these hollow cylinders be nested at most without considering the thickness of the tissue itself?

input

Single group input.
On line 1, enter a positive integer n to indicate the total number of small hollow cylinders. (N<=10^3)
On the second line, enter N positive numbers (both integer and decimal, up to eight decimal places) to represent the bottom radius of N small hollow cylinders.

output

Outputs the maximum number of hollow cylinders that can be nested.

• Water question
• Just judge how many cylinders with different radii

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
int n;
double a[1005];
int main(){
 
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lf",&a[i]);
    }
    sort(a+1,a+1+n);
    int ans=0;
    for(int i=1;i<=n;i++){
        if(a[i]!=a[i-1])ans++;
    }
    printf("%d\n",ans);
    return 0;
}

E: Rescue operation

Title Description

The x-star guard received an urgent mission. The big BOSS is trapped in the hell maze of planet Y, and the guardian of Planet X must carry the "space-time transfer pill" to the rescue as soon as possible.
The hell maze of Y star is a rectangular structure composed of M*N small rooms. The small rooms in the maze have m rows, and each row has N columns.
The entrance of the maze is row 1 and column 1, marked as "S", and the trapped position of the big BOSS is marked as "B".
The time for the X-star guard to pass through each ordinary small room is 1 minute. However, in this maze, some rooms are equipped with mechanisms, including three different types of mechanisms: death trap, delay trap and directional trap. Death trap is a room that cannot be entered. Once entered, it will be doomed and the rescue will fail; The delay trap is full of death light, which takes 3 minutes to pass smoothly; A directional guidance device is set in the directional trap. Those who enter the room will lose the steering function (only in the room) and can only travel along a straight line. For example, entering from the left can only come out from the right, entering from above can only come out from below, but the passing time is still 1 minute.
For a given hell maze map, how much time (minutes) does it take to rescue the big BOSS (it doesn't take steps to enter the BOSS room)?

input

Single group input.
In the first row, enter two positive integers m and N to represent the rows and columns of the maze matrix respectively. (M<=103，N<=103)
From row 2 to row M+1, each row has N columns, corresponding to a two-dimensional character matrix, which is used to represent the hell maze.
In the character matrix, "S" represents the maze entrance, "B" represents the trapped position of the big BOSS, "0" represents the room that can pass normally (the passing time is 1 minute), "#" represents the death trap, "*" represents the delay trap, "and" @ "represents the directional trap.

output

The minimum time required for the X-star guard to rescue the big BOSS (unit: minutes); If the rescue is not successful, "Failure" is output.

• search
• Search on the matrix, about search, push my blog Search topic: DFS
• This is the shortest path template, so use bfs quickly. The only thing to pay attention to is @ situation. It is to go in the same direction until you reach a place that is not @

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
int d[][2]={0,1,1,0,0,-1,-1,0};
int dis[1005][1005];
char a[1005][1005];
struct node{
    int x,y;
    int ans;
    bool operator <(const node &q)const{
        return ans>q.ans;
    }
};
int ans;
bool check(int x,int y){
    if(x>=1&&x<=n&&y>=1&&y<=m&&a[x][y]!='#')
        return 1;
    return 0;
}
void bfs(){
    priority_queue<node>q;
    q.push({1,1,0});
    while(!q.empty()){
        node k=q.top();
        q.pop();
        if(a[k.x][k.y]=='B'){
            ans=k.ans-1;
            return ;
        }
        if(dis[k.x][k.y])continue;
        dis[k.x][k.y]=1;
        for(int i=0;i<4;i++){
            int x=k.x+d[i][0];
            int y=k.y+d[i][1];
            if(check(x,y)){
                if(a[x][y]=='0'||a[x][y]=='B')q.push({x,y,k.ans+1});
                else if(a[x][y]=='*')q.push({x,y,k.ans+3});
                else if(a[x][y]=='@'){
                    int res=k.ans;
                    while(check(x,y)&&a[x][y]=='@'){
                        dis[x][y]=1;
                        x+=d[i][0];
                        y+=d[i][1];
                        res++;
                    }
                    if(check(x,y)){
                        if(a[x][y]=='0'||a[x][y]=='B')
                            q.push({x,y,res+1});
                        else if(a[x][y]=='*')
                            q.push({x,y,res+3});
                    }
                }
            }
        }
    }
    return ;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%s",a[i]+1);
    }
    bfs();
    if(ans)printf("%d\n",ans);
    else puts("Failure");
    return 0;
}

F: a disc Microcomputer

Title Description

Disc a has just finished the microcomputer test recently. He felt that this course was too painful, so he came up with some Good questions. There is a section of data transmitted serially on the address line (decomposing the data into binary bits and transmitting it in sequence one signal line and one bit by one). A disc has a sudden whim (random thinking). Take 0 of the binary bit as "(", and 1 as "). If" 01 "in a string of data is completely matched (for example, 01, 0011, 001011), it will output" Good ". If it is not completely matched (for example, 001, 100111), it will output" Bad ".
Now I'll give you a string s with data length n (n < = 1E5). Please judge whether this data meets the above definition?

input

Enter a data string s, whose length is < = 1E5

output

If "01" in the data string exactly matches, "Good" is output; otherwise, "Bad" is output

• simulation
• It's just a bracket match. Just simulate the stack. It's also water

#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool cmp(string s){
    stack<char>st;
    for(int i=0;i<s.size();i++){
        if(s[i]=='1'){
            if(!st.empty())
                st.pop();
            else return 0;
        }else{
            st.push(s[i]);
        }
    }
    if(st.empty())return 1;
    else return 0;
}
int main(){
    string s;
    cin>>s;
    if(cmp(s))puts("Good");
    else puts("Bad");
    return 0;
}

G: a disc memo

Title Description

Disc a studied Android development this semester. His classmate ph often forgot things, so he wanted to make a simple memo to help ph.
He wants his memo to include the following functions:
1. Insert string s (English characters) into memo
2. Delete the last k characters of the memo (ensure that it is not an empty string)
3. Output the k th character of the memo (ensure that it is not an empty string)
4. Undo the latest 1 or 2 operation and return the memo to the state before the 1 (or 2) operation
But Disc a still can't do it after thinking for a long time. Smart, can you solve the problem of disc A and help ph?

input

On the first line, enter an integer t representing the total number of operations
The following t lines describe an operation, each line starting with an integer n (1 < = n < = 4).
n represents the type of operation in the above statement. If the operation requires parameters, they are followed by space delimited parameters.
Ensure that all operations are legal
1 <= t <= 10^6
1 < = k < = | Notepad content length|
Total length of s in each test data < = 10 ^ 6

output

Only operation 3 needs to output the result, and each line ends with a newline character.

• simulation
• Directly use string simulation (this is not difficult. Why is it that no one does it? Is it my opening order that affects everyone's problem-solving)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
string s2[1000005];
 
int main(){
 
     int n;
     cin>>n;
     int d,k;
     string s1,str="";
     int pos=1;
     for(int i=1;i<=n;i++){
        cin>>d;
        if(d==1){
            cin>>s1;
            s2[pos++]=str;
            str+=s1;
        }
        else if(d==2){
            cin>>k;
            s2[pos++]=str;
            str=str.substr(0,str.size()-k);
        }
        else if(d==3){
            cin>>k;
            cout<<str[k-1]<<endl;
        }
        else {
            str=s2[--pos];
        }
     }
     return 0;
 }

H: X star's password

Title Description

The smart Planet X man decided to send a very, very important file to his companions in outer space. The file needs to enter a special password to open it.
This special password is a string of numbers, which can only be obtained by parsing a file containing many positive integers.
The digital password consists of three parts, which correspond to three positive integers: the first part is the maximum positive integer contained in the file, the second part is the length of the longest monotonically decreasing subsequence contained in the positive integer sequence of the file, and the third part is the minimum positive integer contained in the file. If you get these three parts, they are connected to form a digital string, which is the password needed to crack the file.
Star X is looking for your help. You need to write a program to help him extract the password contained in the file.

input

Single group input.
On line 1, enter a positive integer n, which indicates the number of positive integers in the file. (N<=1000)
On line 2, enter N positive integers separated by spaces. The maximum positive integer shall not exceed 10 ^ 6.

output
The digital password contained in the output file.

• The length of the longest monotonically decreasing subsequence. Reversing the array is equivalent to the length of the longest ascending subsequence
• Stack simulation, because this is easy to remember

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
int a[1005];
int n;
int lis(){
    reverse(a+1,a+1+n);
    vector<int>stk;
    stk.push_back(a[1]);
    for (int i = 2; i<=n; ++i) {
        if (a[i] > stk.back())
            stk.push_back(a[i]);
        else
            *lower_bound(stk.begin(), stk.end(), a[i]) = a[i];
    }
    return stk.size();
}
int main(){
 
    while(~scanf("%d",&n)){
        int ma=-INF,mi=INF;
        for(int i=1;i<=n;i++){
             scanf("%d",&a[i]);
             if(a[i]>ma)ma=a[i];
             if(a[i]<mi)mi=a[i];
        }
 
        printf("%d%d%d\n",ma,lis(),mi);
    }
    return 0;
}

1: Repeat DNA fragment

Title Description

Given a DNA fragment composed of four characters: A, G, C and T.
Please write a program to calculate the length of the longest and non overlapping repeated DNA sub fragments contained in the DNA fragment.
For example, if the input is "AAAAA", the length of the longest and non overlapping repetitive DNA sub segment is 2, because the corresponding non overlapping longest repetitive sub segment is "AA".

input

Single group input.
Enter a DNA fragment composed of four characters: A, G, C and T. (1 < = length < = 3000)

output

Output the length of the longest and non overlapping repeated DNA fragments.

• String dp
• Note that duplicate strings cannot overlap

#include<bits/stdc++.h>
using namespace std;
int dp[3005][3005];
int main(){

    string s;
    int ans=0;
    cin>>s;
    for(int i=1;i<=s.size();i++){
        for(int j=1;j<=s.size();j++){
            if(i!=j&&s[i-1]==s[j-1]){
                dp[i][j] = dp[i-1][j-1]+1;
                if(dp[i][j]>ans&&ans<abs(i-j))
                       ans=dp[i][j];
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}