2022 winter vacation training game 5

A： Three British battles Lv Bu

Title Description

The programmer Kimi Students are watching these days 《 The romance of The Three Kingdoms 》. Today he saw “ Three British battles Lv Bu ” This time. .
Before the tiger prison , Zhang Fei first fought against Lv Bu alone , Dozens of rounds won or lost ; Then Guan Yu raised his knife to help Zhang Fei , There are dozens of rounds back and forth , Still did not defeat Lv Bu ; Last , Liu Bei also urged his horse to come , He Sha Lu Bu . finally , Lu Bu gradually failed .
We watch ,Kimi Suddenly came up with such a question ：
Suppose Liu Bei 、 Guan Yu and Zhang Fei form an equilateral triangle , The central point of the three men is their greatest combat effectiveness . Only the powerful Lv Bu is at the center , Three people can defeat Lv Bu together .
Now we know Liu Bei 、 Guan yu 、 The coordinates of Zhang Fei and Lv Bu at a certain moment , At this time, if San Ying wants to defeat Lv Bu , How far is it from Lu Bu's position ？
【 notes ： The center point of an equilateral triangle refers to an inner point in the equilateral triangle , The distance from this point to the three vertices of the triangle is the same .】

Input

A single set of inputs .
Each set of inputs contains 4 That's ok , Each line contains two non negative numbers , Respectively means Liu Bei 、 Guan yu 、 The coordinate value of Zhang Fei and Lv Bu at a certain time ,X The coordinates are at the top ,Y The coordinate value is after , The two are separated by English spaces .
X<=1000,Y <=1000.
Input to ensure that the first three points can form an equilateral triangle ,X and Y All rounded to two decimal places .

Output

Output the distance between the center point of the three people at the moment and the position of Lv Bu , The result should be rounded to two decimal places .

• Thinking questions
• Just find the point calculation distance

#include<bits/stdc++.h>
using namespace std;
#define ll long long
double a[5],b[5];
int main(){
    
    for(int i=1;i<=4;i++)
        scanf("%lf%lf",&a[i],&b[i]);
    double x=(a[1]+a[2]+a[3])/3.0;
    double y=(b[1]+b[2]+b[3])/3.0;
    printf("%.2f\n",sqrt((a[4]-x)*(a[4]-x)+(b[4]-y)*(b[4]-y)));
    return 0;
}

B: a Try to find the maximum

Title Description

Yes $n$ Number $a_1$$a_2$…$a_n$, And an integer $k$, seek $i\ast j-k\ast (a_i|a_j)$ The maximum of ,$1\le i<j\le n$,| Yes or operation

Input

The first line contains an integer $T$—— The number of test cases . And then there was $T$ Group test cases .
The first line of each set of test cases includes two positive integers $n$($2\le n\le 10^5$) and $k$($1\le k\le min(n,100)$)
The second line includes n A positive integer $a_1$$a_2$…$a_n$（$0\le a_i\le n$）
Ensure that all test cases n And not more than $3\ast 10^5$

Output

For each example , Output an integer —$i\ast j-k\ast (a_i|a_j)$ The maximum of

• Find the maximum, then i * j Try to be as big as possible , You can enumerate from back to front i * j , Then when enumerating to i * j When it is less than the maximum value found , You can jump out of the loop , Save time
• Pay attention to a detail , If you define i and j yes int Type words ,i * j To force a type conversion , Otherwise, the accuracy will be lost

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
int a[100005];
int n,k;
int main(){
    
    int t;
    scanf("%d",&t);
    while(t--){
    
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        ll ans=-INF;
        for(int i=n-1;i>=1;--i){
    
            if((ll)i*n<=ans)break;// Now? i*j Has been less than the maximum value found , Further enumeration can only be smaller than now 
            for(int j=n;j>i;--j){
    
                ll d=(ll)i*j-(ll)k*(a[i]|a[j]);// Strong go 
                ans=max(ans,d);
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

C: Super team

Title Description

X Star command received an urgent combat mission , They need to send one immediately “ Super team ” To perform this important task .
N individual X Star soldiers stand in a row waiting for dispatch , The more tacit the cooperation, the closer the people get to the team , And every soldier has a combat value .
In order to form a closely united and highly effective combat team , Now we need to choose M Standing together in a row X Star soldiers “ Super team ”, And ask this M individual X Star warriors have the highest average combat value .
Can you write a program , Output the continuous with the largest average combat value M individual X Average combat value of star warriors ？

Input

A single set of inputs .
The first 1 Enter two positive integers on the line N and M. among N Express X Total number of star warriors （N<=1000）;M Means selected X Number of star warriors （1<=M<=N）.
The first 2 Line input N A positive integer , In the corresponding team N individual X Battle value of Star Warrior .

Output

Output the continuous with the largest average combat value M individual X Average combat value of star warriors （ The results were rounded to keep 2 Decimal place ）.

• Array b Before saving n Xiang He , Enumerate to find the largest m The sum of the numbers is ok , Comparative water

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
int a[1005],b[1005];
int n,m;
int main(){
    
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
    
        scanf("%d",&a[i]);
        b[i]=b[i-1]+a[i];
    }
    int ans=0;
    for(int i=m;i<=n;i++){
    
        ans=max(ans,b[i]-b[i-m]);
    }
    printf("%.2f\n",1.0*ans/m);
    return 0;
}

D: X Star man's treasure

Title Description

X The star man found a treasure map , Marked in the treasure map N The location of the treasure house . this N The treasures are connected in a straight line , Each treasure house has several gold coins .
X The star man decided to take a hot-air balloon to collect gold coins , Hot air balloons can only fly at most M km , But the hot air balloon will not break down during flight .
Besides , Due to design defects , Hot air balloons can only be started at most K Time .
X The star man came to No. with a hot-air balloon 1 A treasure house （ Reach No 1 The hot air balloon has not yet started when the treasure house is opened ）, After collecting the 1 The gold coins in the treasure house will start the hot-air balloon to go to the next treasure house . If he decides to collect gold coins from a treasure house , Must stop the hot air balloon , Restart the hot air balloon after collection . Of course ,X Every time a star goes to a treasure house, he will take all the gold coins in the treasure house .
Every treasure house is known to be the first 1 The distance between two treasure houses （ Company ： km ） And the number of gold coins in the Treasury .
Excuse me, X How many gold coins can the star man collect at most ？

Input

A single set of inputs .
The first 1 Line enter three positive integers N、M and K, Each represents the number of treasure houses 、 The maximum distance a hot-air balloon can fly at a time （ km ） And the maximum number of times hot air balloons can be started , Three positive integers do not exceed 100, Two adjacent positive integers are separated by spaces .
Next N Each line contains two integers , Separate indication control 1 The distance from a treasure house to a treasure house （ km ） And the number of gold coins in this treasure house .（ Because the initial position is 1 A treasure house , So the first 1 The... Of the line corresponding to the treasure house 1 The values are 0.）
Input to ensure that all treasures are in accordance with to 1 The distance of the treasure houses is arranged from near to far , The initial position is 1 A treasure house .

Output

Output a positive integer , Indicates the maximum number of gold coins that can be collected .

• Dynamic programming
• dp[ i ][ j ] To i The balloon has started by the time of j Time
• dp[ i ][ j ] This status can be determined by i And the distance is less than or equal to m A location of l Turn around
• State transition equation dp[ i ][ j ]=max(dp[ i ][ j ],dp[ l ][ j-1 ]+b[ i ]);

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,m,k;
int ans;
int a[105],b[105];
int dp[105][105];
int main(){
    
 
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i],&b[i]);
    memset(dp,-0x3f,sizeof(dp));
    dp[1][0]=b[1];
    for(int i=2;i<=n;i++)
    for(int j=1;j<=k;j++){
    
        for(int l=i-1;l>=1;l--){
    
            if(m>=a[i]-a[l]){
    
                dp[i][j]=max(dp[i][j],dp[l][j-1]+b[i]);
            }
            else break;
        }
        ans=max(ans,dp[i][j]);
    }
    printf("%d\n",ans);
    return 0;
}

E: Magic pocket

Title Description

There's a magic pocket , The total volume is 40, You can make something out of this bag , The total volume of these items must be 40.John Now there is n I want to get something , The volume of each object is a1,a2……an.John You can choose from some of these items , If the total volume of the selected object is 40, So use this magic pocket ,John You can get these things . The problem now is ,John How many different ways to choose things .

Input

The first line of input is a positive integer n (1 <= n <= 20), Represents the number of different items . Next n That's ok , Each line has one 1 To 40 Positive integer between , Give respectively a1,a2……an Value .

Output

Output the number of different ways to select items .

• Dynamic planning water problem

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

F: Find immediate family members

Title Description

If A,B yes C My parents , be A,B yes C Of parent,C yes A,B Of child, If A,B yes C Of （ Outside ） grandfather , grandmother , be A,B yes C Of grandparent,C yes A,B Of grandchild, If A,B yes C Of （ Outside ） great-grandfather , great grandmother , be A,B yes C Of great-grandparent,C yes A,B Of great-grandchild, Then another generation , Then add a... To the relationship great-.

Input

The input contains multiple sets of test cases , Each set of use cases first contains 2 It's an integer n（0<n<=26） and m（0<m<50）, They are n A kinship and m A question ,
And then the next thing is n The form of the line is like ABC String , Express A My parents are B and C,
If A My parents' information is incomplete , Then use - Instead of , for example A-C, And then m Line form, such as FA String , Asking F and A The relationship between .

Output

If you ask 2 Individuals are immediate family members , Please output... According to the title description 2 The relationship between , If there is no direct relationship , Please export -.
See the example for the specific meaning and output format .

• Method 1： Direct simulation ,map Record every parent relationship , for example mp[a]=b be a My son is b, Then find out all possible simulations of the query
• Method 2： Search for , You don't have to find out all the possibilities , Search directly , Finally, it's related , Then output as required
• The character of this question should not be entered as a single character , Entering one line of string directly will save a lot of time

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
int n,m;
map<char,char>mp;
void ask(char a,char b){
    
    if(!mp[a]&&!mp[b]){
    
        puts("-");
    }
    else if(mp[a]==b){
    
        puts("parent");
    }
    else if(mp[b]==a){
    
        puts("child");
    }
    else if(mp[mp[a]]==b){
    
        puts("grandparent");
    }
    else if(mp[mp[b]]==a){
    
        puts("grandchild");
    }
    else {
    
        int ans=0;
        char c=a;
        while(mp[c]&&mp[c]!=b){
    
            c=mp[c];
            ans++;
        }
        if(mp[c]==b){
    
            while(ans>=2){
    
                ans--;
                printf("great-");
            }
            puts("grandparent");
            return ;
        }
 
        ans=0;
        c=b;
        while(mp[c]&&mp[c]!=a){
    
            c=mp[c];
            ans++;
        }
        if(mp[c]==a){
    
            while(ans>=2){
    
                ans--;
                printf("great-");
            }
            puts("grandchild");
            return ;
        }
 
        puts("-");
    }
}
int dfs(int be,int la,int ans){
    
    if(be==la)return ans;
    if(isalpha(mp[be])) return dfs(mp[be],la,ans+1);
    return -1;
}
int main(){
    
    char s[5];
    while(~scanf("%d%d",&n,&m)){
    
        mp.clear();
        while(n--){
    
            scanf("%s",s);
            if(s[1]!='-')mp[s[1]]=s[0];
            if(s[2]!='-')mp[s[2]]=s[0];
        }
        while(m--){
    
            scanf("%s",s);
            //ask(s[0],s[1]);// Direct simulation 
            int ans=dfs(s[1],s[0],0);// Search for 
            if(ans!=-1){
    
                for(int i=3;i<=ans;++i) printf("great-");
                if(ans>=2) printf("grand");
                puts("child");
                continue;
            }
            ans=dfs(s[0],s[1],0);
            if(ans!=-1){
    
                for(int i=3;i<=ans;++i) printf("great-");
                if(ans>=2) printf("grand");
                puts("parent");
                continue;
            }
            puts("-");
        }
    }
    return 0;
}

G: Minimum rectangle

Title Description

Given a series of 2 The coordinates of the points in the plane of dimension (x, y), among x and y All are integers , It is required to use the smallest rectangle to frame all the points . The edges of the rectangle are parallel to each other x and y Axis , If the dot falls on the edge, it is also included in the frame .

Input

The test input contains several test cases , Each test case consists of a series of coordinates , Each pair of coordinates occupies one line , among |x| and |y| Less than 231; a pair 0 The coordinates mark the end of a test case .
Be careful (0, 0) Not as a point in any test case . A test case without dots marks the end of the whole input .

Output

For each test case , stay 1 Inline output 2 Pair integer , Separated by a space . The first 1 For integers, it is the coordinate of the lower left corner of the rectangular box , The first 2 For integer, it is the coordinate of the upper right corner of the rectangular box .

• Water problem
• Bottom left coordinates （ The smallest x, The smallest y）, The top right coordinates （ maximal x, maximal y）

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
int a,b,c,d;
int x,y;
int main(){
    
 
    while(scanf("%d%d",&a,&b)&&(a+b)){
    
        c=a;
        d=b;
        while(scanf("%d%d",&x,&y)&&(x+y)){
    
            a=min(a,x);
            b=min(b,y);
            c=max(c,x);
            d=max(d,y);
        }
        printf("%d %d %d %d\n",a,b,c,d);
    }
    return 0;
}

H: Reverse pental

Title Description

Write a program , First, reverse a decimal positive integer 【 You need to remove the leading 0】, Then it is converted to a positive integer in quinary , Finally, output the quinary positive integer .

Input

The input of each group of test data occupies one line , Enter a positive decimal integer n. （n<=100000）

Output

The output of each group of test data occupies one line , Output the converted quinary positive integer .

• Water problem

#include<bits/stdc++.h>
using namespace std;
int n,m;
void turn(){
    
    string s="";
    while(m){
    
        s+=to_string(m%5);
        m/=5;
    }
    reverse(s.begin(),s.end());
    cout<<s<<endl;
}
int main(){
    
    cin>>n;
    while(n){
    
        m=m*10+n%10;
        n/=10;
    }
    turn();
    return 0;
}

I: XP Magic tower of

Title Description

Most students are familiar with the game magic tower , Of course , It doesn't matter if you don't know , Then there will be a brief introduction ： First of all, there is a demon king in the magic tower , The demon king took the princess , So the warrior is going to save her ( The dog blood plot is ignored ),XP Recently, I am very interested in magic tower , The magic tower here only considers N*N The map of , In the map ’.' Represents the path that warriors can pass ,'X’ Representative wall , Of course, warriors can't walk into the wall . Warriors can only go up, down, left and right , And he can't get out of this picture . There is only one ’S’ On behalf of warriors , And there is only one ’T’ On behalf of the princess , Of course, ’L’ Minions representing the demon king , If warriors want to go to the position of minions , He must kill his minions , Of course, he also has to deduct the corresponding amount of blood , If blood is less than or equal to 0, Then the warriors' rescue plan failed ,XP Want to find a suitable path , Can save the princess , That means finding one S Be able to T The path of , And warriors cannot die on the way , Now? XP Want to know if there is such a path .

Input

The input contains multiple sets of test cases , Enter one on the first line T Represents the number of test data sets ,(1<=T<=10). The first row of each set of test data contains a N(2<=N<=100),N Indicates the size of the map , Next N Each line contains N Characters Gij, Ensure that only ’S’,‘T’,‘L’,’.’,‘X’ Four types of characters . Ensure that the input must have a ’S’ And a ’T’. Next N Line inclusion N A digital Aij(0<=Aij<=10), among S The number in the corresponding position represents the blood volume of the warrior ,L The number in the corresponding position represents the amount of blood that the warrior needs to deduct if he wants to kill his minions , The number corresponding to other characters is guaranteed to be 0.

Output

If there is such a rescue path , Please export YES, If there is no output NO.

• Search for
• It's ordinary search , It's easy …
• Here's how dfs and bfs The two methods

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
int n;
bool flag;
int di[][2]={
    0,1,1,0,0,-1,-1,0};
int vis[105][105];
char a[105][105];
int b[105][105];
int dx,dy;
bool check(int x,int y){
    
    if(x>=1&&x<=n&&y>=1&&y<=n&&a[x][y]!='X')
        return 1;
    return 0;
}
void dfs(int x,int y,int ans){
    
    if(a[x][y]=='T'||flag){
    
        flag=1;
        return ;
    }
    for(int i=0;i<4;i++){
    
        int xx=x+di[i][0];
        int yy=y+di[i][1];
        if(check(xx,yy)&&!vis[xx][yy]&&ans>b[xx][yy]){
    
                vis[xx][yy]=1;
                dfs(xx,yy,ans-b[xx][yy]);
            }
        }
}
struct node{
    
    int x,y;
    int ans;
    bool operator<(const node &q)const{
    
        return ans<q.ans;
    }
};
void bfs(){
    
    priority_queue<node>q;
    q.push({
    dx,dy,b[dx][dy]});
    while(!q.empty()){
    
        node k=q.top();
        q.pop();
        if(a[k.x][k.y]=='T'){
    
            flag=1;
            return ;
        }
        vis[k.x][k.y]=1;
        for(int i=0;i<4;i++){
    
            int xx=k.x+di[i][0];
            int yy=k.y+di[i][1];
            if(check(xx,yy)&&k.ans>b[xx][yy]&&!vis[xx][yy]){
    
                q.push({
    xx,yy,k.ans-b[xx][yy]});
            }
        }
    }
}
int main(){
    

    int t;
    scanf("%d",&t);
    while(t--){
    
        memset(vis,0,sizeof(vis));
        flag=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
    
            scanf("%s",a[i]+1);
            for(int j=1;j<=n;j++)
                if(a[i][j]=='S'){
    
                dx=i;
                dy=j;
            }
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%d",&b[i][j]);
        dfs(dx,dy,b[dx][dy]);
        //bfs();
        if(flag)puts("YES");
        else puts("NO");
    }
    return 0;
}