A: Color overlay

Title Description
Kimi, who loves science, has been studying various colors. Today he plans to do a small experiment on color superposition.
Kimi has many blue and yellow rectangular transparent plastic cards. As we all know, if blue and yellow are mixed together, they will turn green. Therefore, Kimi can see green by looking at the superposition of blue transparent card and yellow transparent card against the light.
Suppose that in a two-dimensional plane, a blue transparent card and a yellow transparent card are placed parallel to the coordinate axis, that is, the horizontal edge of the card is parallel to the X axis and the vertical edge is parallel to the Y axis.
Now give the coordinates of the upper left corner of a blue card and a yellow card (both integers) and the length and width of the two cards (both positive integers).
[Note: here, the group of edges parallel to the X axis is defined as the long edge, and the group of edges parallel to the Y axis is defined as the wide edge]
Please write a program to calculate the area of the green area formed by the superposition of these two cards.
input
Single group input.
In the first line, enter four integers to represent the upper left corner coordinates (X and Y coordinates), length and width of the blue rectangular transparent card respectively. The two are separated by English spaces.
On the second line, enter four integers to represent the upper left corner coordinates (X and Y coordinates), length and width of the Yellow rectangular transparent card. The two are separated by English spaces.
The value range of X coordinate and Y coordinate of two rectangular transparent cards is [- 1000, 1000], and the value range of length and width is [1200].
output
Output a non negative integer indicating the area of the green area formed by the superposition of two cards.
sample input
0 100 200 100
100 150 75 75
sample output
1875

Analysis: simulate the meaning of the question and construct structural variables to store the highest horizontal line, lowest horizontal line, leftmost vertical line and rightmost vertical line of the rectangle. According to the input, you can know the coordinates and relative positions of the four points of the two rectangles. Judge by yourself when the area does not exist, otherwise push the formula to get the width and height of the overlapping part, and multiply it to be the area.
The code is as follows:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct Node{
    int u,d,l,r;
};
int fun(Node a,Node b){
    if(a.r<=b.l)return 0;
    if(a.u<=b.d||a.d>=b.u)return 0;
    int width=min(a.r,b.r)-max(a.l,b.l);
    int length=min(a.u,b.u)-max(a.d,b.d);
    return width*length;
}
int main(){
    Node a,b;
    int length1,width1,length2,width2;
    scanf("%d%d%d%d",&a.l,&a.u,&width1,&length1);
    a.d=a.u-length1,a.r=a.l+width1;
    scanf("%d%d%d%d",&b.l,&b.u,&width2,&length2);
    b.d=b.u-length2,b.r=b.l+width2;
    if(a.l<b.l)cout<<fun(a,b)<<endl;
    else cout<<fun(b,a)<<endl;
}

B: Hardworking Lao Yang

Title Description
Hardworking Lao Yang recently received a task list with N different work tasks. For each task, two times [X, Y] are given, where X represents the start time of the task (the task starts on day x and includes day x), and Y represents the end time of the task (the task ends on day y and includes day y).
Serious Lao Yang treats every task wholeheartedly. Once he decides to do a task, he will not do another task at the same time until the task is completed, that is, Lao Yang has only one task at most at any time.
It is assumed that the reward for completing each task is equal. So, how should Lao Yang arrange his time to get the most pay?
Please write a program to help Lao Yang calculate the maximum number of tasks he can complete. Ensure that at least one task can be completed.
input
Single group input.
In line 1, enter a positive integer n to represent the total number of tasks on the task list. (N<=1000)
From line 2 to line N, each line contains two positive integers, which respectively represent the start time and end time of each task. The two positive integers are separated by spaces.
output
Output the maximum number of tasks Lao Yang can complete.
sample input
7
1 4
1 3
2 7
3 4
4 6
5 10
7 8
sample output
3
Tips
For the input sample, the maximum number of tasks that can be completed is 3, corresponding to [1,3] (the second task), [4,6] (the fifth task) and [7,8] (the seventh task).

Analysis: in fact, it is a greedy idea to sort all tasks directly. The earlier the tasks are completed, the higher the task is ranked (the earliest end time), and then the for loop is traversed to meet the start time of node[i] after the end time of node[i-1].

#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct Node{
    int s,d;
}node[1005];
bool cmp(Node a,Node b){
    return a.d<b.d;
}
int main(){
    int n,num=0,t=0;
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%d %d",&node[i].s,&node[i].d);
    }
    sort(node,node+n,cmp);
    int i=0;
    while(i<n){
        if(node[i].s>t)
            num++,t=node[i].d;
        i++;
    }
    printf("%d\n",num);
}

C: Visitors to the secret building

Title Description
Kimi was recently in charge of the security of a secret building. His job was to record the visitors to the building.
Each visitor has a unique number corresponding to it, and the visitor's number is recorded in each visit record.
Now Kimi needs to count the number of visitors to the secret building in each record.
input
Single group input, two lines per group.
The first line contains a positive integer n, which indicates the number of records, and N does not exceed 1000;
The second line contains n positive integers, which in turn represent the number of each visitor in Kimi's record, separated by a space.
output
Output 1 line, containing n positive integers, separated by spaces, indicating the number of visitors in each record in turn.
sample input
6
1 1 2 2 3 1
sample output
1 2 1 2 1 3

Analysis: for the simulation problem, you can open up another array p, and the size of p[i] represents the number of visitors numbered I (1 at the beginning and + 1 after one visit). The following code directly uses the STL map container

The code is as follows:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    int n,num;
    scanf("%d",&n);
    map<int,int>m;
    while(n--){
        scanf("%d",&num);
        m[num]++;
        printf("%d ",m[num]);
    }
    printf("\n");
}

D: Maximum energy

Title Description
The annual cosmic super games were grandly held in the cosmic Ott hero stadium. Star X has prepared for the sports meeting for a long time, and the time for him to show his skill has finally come!
In order to maintain a good competitive state and abundant physical fitness, the X-star people have prepared N different energy packs.
Although there are an infinite number of energy packs for each kind of energy pack, because using too many of the same energy packs will bring side effects, you can't use more than two of the same energy packs at the same time, that is, you can use up to two of the same energy packs at the same time.
Each energy package has a weight value and an energy value. Due to the particularity of these energy packages, one energy package must be used completely to play its role, otherwise the corresponding energy value will be lost.
Considering the fairness of the competition, the competition organizing committee stipulates that the total weight of each person's supplementary energy package before the competition shall not exceed W.
Now you need to write a program to calculate the maximum energy that star X people can have?

input
Single group input.
Line 1 contains two positive integers N and W, where N < = 103 and W < = 103.
From line 2 to line N+1, each line contains two positive integers, which respectively represent the weight and energy value of each energy package. The two positive integers are separated by spaces. The weight and energy value of each energy package are positive integers less than or equal to 100.
output
Output the maximum energy that star X can have.
sample input
3 12
4 20
3 10
6 20
sample output
50

Analysis: in fact, this problem is the problem of multiple backpacks... But! Because I didn't remember the multiple knapsack cycle, there was another problem in the derivation during the game.. (I love scrolling arrays so much that I didn't expect to forget the critical moment directly. I've been wrong too many times).
Fortunately, the maximum range of k is 2... I directly expand the array by 2 times and do it as the board problem of 01 backpack.. Fortunately, luck favoured me.
Here is a direct analysis and understanding of several major knapsack problems, which may still take a lot of time to ponder:
Backpack nine lectures

The code is as follows (using the idea of one dimension to save space):

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int f[1005],c[2005],w[2005];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d%d",&c[i],&w[i]);
        c[n+i]=c[i],w[n+i]=w[i];
    }
    for(int i=1;i<=2*n;++i)
        for(int j=m;j>=c[i];--j)
            f[j]=max(f[j],f[j-c[i]]+w[i]);
    printf("%d\n",f[m]);
}

E: Maximum prime

Title Description
Enter a numeric string and delete several (including 0) numbers from it to get a prime number. Please write a program to solve the maximum prime number that can be obtained after deleting some numbers.
For example, if you enter "1234" and delete 1 and 4, the maximum prime number you can get is 23.
input
Single group input.
Enter a numeric string with a length of no more than 10.
output
Output the maximum prime number that can be obtained after deleting 0 or more numbers. If the prime number cannot be obtained after deletion, then "No result." will be output.
sample input
1234
sample output
23

Analysis: this problem can be solved by direct dfs violent search. The best pruning is to make the string from long to short. If you find this prime, you will find it. A faster way to judge prime numbers: Six prime method

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll maxn=0;
bool judge(ll n){
    if(n==1||n==0)return false;
    if(n==2||n==3||n==5)return true;
    if(n%2==0||n%3==0)return false;
    for(ll i=5;i<=sqrt(n);i+=6)
        if(n%i==0||n%(i+2)==0)return false;
    return true;
}
ll turn(string s){
    ll num=0;
    for(int i=0;i<s.size();++i)num=num*10+s[i]-'0';
    return num;
}
void fun(string s,int x){
    if(!x){
        ll num=turn(s);
        if(num>maxn&&judge(num))maxn=num;
        return;
    }
    for(int i=0;i<s.size();++i){
        string s1=s;s1.erase(i,1);
        fun(s1,x-1);
    }
}
int main(){
    string s;
    cin>>s;
    for(int i=0;i<s.size();++i){
        fun(s,i);
        if(maxn)break;
    }
    printf("%lld\n",maxn);
}

F: Maximum score

Title Description
Xiaomi and Xiaohua are playing a game of deleting numbers.
The rules of the game are as follows:
First, write down N positive integers randomly, and then choose any number as the starting point. One number can be deleted from left to right from the starting point, but the next deleted number must be less than the last deleted number. 1 point will be given for each number successfully deleted.
For a given N positive integers, what is the maximum score you can get after a game?
input
Single group input.
In line 1, enter a positive integer N to indicate the number of numbers (N < = 10 ^ 3).
On line 2, enter N positive integers separated by spaces.
output
For a given N positive integers, the maximum score you can get after a game.
sample input
6
3 4 3 5 2 1
sample output
4

Analysis: take a closer look at this problem is to find a continuous descending subsequence... But I have to read good questions. I use the binary one. This efficiency is much faster, that is, the inverse application of continuous ascending subsequence.

The code is as follows:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,cnt;
    scanf("%d",&N);
    cnt=0;
    int* num=new int[N];
    int* dp=new int[N];
    for(int i=0;i<N;i++)scanf("%d",&num[i]);
    dp[cnt++]=num[0];
    for(int i=1;i<N;i++){
        if(num[i]<dp[cnt-1])dp[cnt++]=num[i];
        else{
            int l=0,r=cnt-1;
            while(l<r){
                int mid=(l+r)>>1;
                if(dp[mid]<=num[i])r=mid;
                else l=mid+1;
            }
            dp[r]=num[i];
        }
    }
    printf("%d\n",cnt);
}

G: Key

Title Description
The X-star intercepted another ciphertext from the Y-star.
Cracking this ciphertext requires a key, which exists in a positive integer N.
The smart star X finally found a way to get the key: the last bit of this positive integer is a non-zero number k (k > = 2). You need to cut the positive integer N into k small integers and maximize the product of these K small integers. The maximum product obtained is the key required to crack the ciphertext.
Can you write a program for star X to get the key?
input
Single group input. Enter a positive integer N (the length of N is less than or equal to 15), and the last digit of N is K, K > = 2.
output
The maximum product of dividing N into K integers.
sample input
2342
sample output
966

Analysis: Unfortunately, there is not enough time when there is an idea. In fact, it is to search and use recursion to find the regression conditions (return directly when k=1 and recursion directly when k=2, which is still very fast). In other times, it is necessary to avoid some unnecessary recursion steps in the for loop.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll turn(string s){
    ll num=0;
    for(int i=0;i<s.size();++i)num=num*10+s[i]-'0';
    return num;
}
ll fun(string s,int k){
    if(k==1)return turn(s);
    if(k==2){
        ll res=1;
        for(int i=0;i<s.size();++i){
            string s1=s.substr(0,i+1),s2=s.substr(i+1,s.size()-i-1);
            ll num=turn(s1)*turn(s2);
            if(num>res)res=num;
        }
        return res;
    }
    ll res,maxn=1;
    for(int i=0;i<s.size();++i){
        string s1=s.substr(0,i+1),s2=s.substr(i+1,s.size()-i-1);
        //cout<<s1<<" "<<s2<<endl;
        for(int i=1;i<k;++i){
            if(s1.size()>=i&&s2.size()>=k-i){
                res=fun(s1,i)*fun(s2,k-i);
                //cout<<res<<endl;
                if(res>maxn)maxn=res;
            }
        }
    }
    return maxn;
}
int main(){
    string s;
    cin>>s;
    int k=s[s.size()-1]-'0';
    printf("%lld\n",fun(s,k));
}

H: Star X University

Title Description
The new campus of X-star university has finally been completed!
There are N teaching buildings and office buildings in the new campus. Now we need to connect these N buildings with optical fiber to ensure that there is a wired network communication link between any two buildings.
The linear distance between any two buildings is known in kilometers. In order to reduce the cost, the two buildings are required to be connected by linear optical fiber.
The unit cost C of optical fiber is known (unit: X-star coin / kilometer). How many X-star coins do you need at least to ensure that optical fibers are directly or indirectly connected between any two buildings?
Note: if building 1 is connected with building 2 and building 2 is connected with building 3, building 1 and building 3 are indirectly connected.
input
Single group input.
On the first line, enter two positive integers N and C, which respectively represent the number of buildings and the unit cost of optical fiber (unit: X star currency / km), N < = 100, C < = 100. The two are separated by English spaces.
Next, N*(N-1)/2 lines. Each line contains three positive integers. The first positive integer and the second positive integer represent the number of the building (from 1 to N). The smaller one is in the front, the larger one is in the back, and the third positive integer is the linear distance between the two buildings (unit: km).
output
How many X star coins does it take to output at least to ensure that any two buildings are directly or indirectly connected by optical fibers.
sample input
3 10
1 2 5
1 3 6
2 3 7
sample output
110

Analysis: the board problem of minimum spanning tree has been used just after review recently. I'm lucky

For the explanation of minimum spanning tree, you can see this article:
minimum spanning tree

The code is as follows:

#include<bits/stdc++.h>
using namespace std;
const int NUM=105;
int S[NUM];
struct Edge{int u,v,w;}edge[NUM*NUM];
bool cmp(Edge a,Edge b){
    return a.w<b.w;
}
int find(int u){
	return S[u]==u?u:find(S[u]);
}
int n,m;
int kruskal(){
    int ans=0;
    for(int i=1;i<=n;++i)S[i]=i;
    sort(edge+1,edge+m+1,cmp);
    for(int i=1;i<=m;++i){
        int b=find(edge[i].u);
        int c=find(edge[i].v);
        if(b==c)continue;
        S[c]=b;
        ans+=edge[i].w;
    }
    return ans;
}
int main(){
    int c;
    scanf("%d%d",&n,&c);
    m=n*(n-1)/2;
    for(int i=1;i<=m;++i)
        scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
    printf("%d\n",kruskal()*c);
}

summary
Search questions are still not done enough. It needs more practice to write code hesitantly. If I don't have luck next time, I'm afraid I won't. In addition to doing more search topics, you also need to solve the knapsack problem... Knock well..