2022年寒假训练赛第5场

A：三英战吕布

题目描述

程序员Kimi同学这几天在看《三国演义》。今天他看到了“三英战吕布”这一回。
话说在虎牢关前，张飞首先单独战吕布，几十个回合不分输赢；随后关羽提刀来帮助张飞，来回又是几十个回合，仍然没有将吕布打败；最后，刘备也催马前来，合杀吕布。终于，吕布渐渐打不过啦。
看着看着，Kimi突然想到这么一个问题：
假设刘备、关羽和张飞三个人组成一个正三角形，三个人的中心点是他们战斗力最大的地方。只有强大的吕布在中心点位置，三个人才可以联手打败吕布。
现在已知刘备、关羽、张飞和吕布四个人在某一时刻的坐标，请问此时如果三英要将吕布打败，距离吕布所在的位置还有多远？
【注：正三角形的中心点是指在正三角形中的一个内点，这个点到三角形三个顶点的距离均相同。】

输入

单组输入。
每组输入包含4行，每行包含两个非负数，分别表示刘备、关羽、张飞和吕布四个人在某一时刻的坐标值，X坐标值在前，Y坐标值在后，两者之间用英文空格隔开。
X<=1000，Y <=1000。
输入保证前三个点可以组成一个正三角形，X和Y均四舍五入保留两位小数。

输出

输出此刻三个人的中心点距离吕布所在位置的距离值，结果需四舍五入保留两位小数。

思维题求出点算距离就行

#include
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("%.2fn",sqrt((a[4]-x)*(a[4]-x)+(b[4]-y)*(b[4]-y)));
    return 0;
}

B: a碟求最大值

题目描述

有 n n n个数 a 1 a_{1} a1​ a 2 a_{2} a2​… a n a_{n} an​，和一个整数 k k k，求 i ∗ j − k ∗ ( a i ∣ a j ) i*j-k*(a_{i}|a_{j}) i∗j−k∗(ai​∣aj​)的最大值， 1 ≤ i < j ≤ n 1leq i

输入

第一行包含一个整数 T T T——测试用例的数量。然后是 T T T组测试用例。
每组测试用例的第一行包括两个正整数 n n n( 2 ≤ n ≤ 1 0 5 2leq nleq10^5 2≤n≤105)和 k k k( 1 ≤ k ≤ m i n ( n , 100 ) 1leq kleq min(n,100) 1≤k≤min(n,100))
第二行包括n个正整数 a 1 a_{1} a1​ a 2 a_{2} a2​… a n a_{n} an​（ 0 ≤ a i ≤ n 0leq a_{i}leq n 0≤ai​≤n）
保证所有测试用例中n的和不超过 3 ∗ 1 0 5 3*10^5 3∗105

输出

对于每组样例，输出一个整数— i ∗ j − k ∗ ( a i ∣ a j ) i*j-k*(a_{i}|a_{j}) i∗j−k∗(ai​∣aj​)的最大值

求最大值则 i * j 要尽可能大，可以从后往前枚举 i * j ，然后当枚举到 i * j 已经小于找到的最大值时，就可以跳出循环，节省时间注意一个细节，如果定义i 和 j 是int类型的话，i * j 要强制类型转换，不然会丢失精度

#include
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;//现在i*j已经小于找到的最大值，再往前枚举也只能比现在更小
            for(int j=n;j>i;--j){
                ll d=(ll)i*j-(ll)k*(a[i]|a[j]);//强转
                ans=max(ans,d);
            }
        }
        printf("%lldn",ans);
    }
    return 0;
}

C: 超级小分队

题目描述

X星司令部接到了一项紧急战斗任务，他们需要立即派遣一个“超级小分队”去执行这项重要的任务。
N个X星战士站成一排等候调遣，配合越默契的人在队伍中离得越近，且每一位战士都有一个战斗值。
为了组建一个密切团结且战斗力高的战斗队伍，现在需要挑选M个在队伍中连续站在一起的X星战士组成“超级小分队”，并且要求这M个X星战士的平均战斗值最大。
你能否编写一个程序，输出平均战斗值最大的连续M个X星战士的平均战斗值？

输入

单组输入。
第1行输入两个正整数N和M。其中N表示X星战士的总个数（N<=1000）；M表示挑选的X星战士的个数（1<=M<=N）。
第2行输入N个正整数，对应队伍中N个X星战士的战斗值。

输出

输出平均战斗值最大的连续M个X星战士的平均战斗值（结果四舍五入保留2位小数）。

数组b保存前n项和，枚举找出最大的m个数之和就行，比较水

#include
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("%.2fn",1.0*ans/m);
    return 0;
}

D: X星人的宝藏

题目描述

X星人发现了一个藏宝图，在藏宝图中标注了N个宝库的位置。这N个宝库连成了一条直线，每个宝库都有若干枚金币。
X星人决定乘坐热气球去收集金币，热气球每次最多只能飞行M千米，但是热气球在飞行过程中并不会发生故障。
此外，由于设计上的缺陷，热气球最多只能启动K次。
X星人带着热气球来到了第1个宝库（达到第1个宝库时热气球尚未启动），收集完第1个宝库的金币后将启动热气球前往下一个宝库。如果他决定收集某一个宝库的金币，必须停下热气球，收集完之后再重新启动热气球。当然，X星人每到一个宝库是一定会拿走这个宝库所有金币的。
已知每一个宝库距离第1个宝库的距离（单位：千米）和宝库的金币数量。
请问X星人最多可以收集到多少枚金币？

输入

单组输入。
第1行输入三个正整数N、M和K，分别表示宝库的数量、热气球每次最多能够飞行的距离（千米）和热气球最多可以启动的次数，三个正整数均不超过100，相邻两个正整数之间用空格隔开。
接下来N行每行包含两个整数，分别表示第1个宝库到某一个宝库的距离（千米）和这个宝库的金币枚数。（因为初始位置为第1个宝库，因此第1个宝库所对应行的第1个值为0。）
输入保证所有的宝库按照到第1个宝库的距离从近到远排列，初始位置为第1个宝库。

输出

输出一个正整数，表示最多可以收集的金币数。

动态规划dp[ i ][ j ]表示到第 i 个点时气球已经启动 j 次dp[ i ][ j ]该状态可由 i 之前的且距离小于等于m的某个位置 l 转移过来状态转移方程 dp[ i ][ j ]=max(dp[ i ][ j ],dp[ l ][ j-1 ]+b[ i ]);

#include 
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("%dn",ans);
    return 0;
}

E: 神奇的口袋

题目描述

有一个神奇的口袋，总的容积是40，用这个口袋可以变出一些物品，这些物品的总体积必须是40。John现在有n个想要得到的物品，每个物品的体积分别是a1，a2……an。John可以从这些物品中选择一些，如果选出的物体的总体积是40，那么利用这个神奇的口袋，John就可以得到这些物品。现在的问题是，John有多少种不同的选择物品的方式。

输入

输入的第一行是正整数n (1 <= n <= 20)，表示不同的物品的数目。接下来的n行，每行有一个1到40之间的正整数，分别给出a1，a2……an的值。

输出

输出不同的选择物品的方式的数目。

动态规划水题

#include
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("%dn",dp[40]);
    return 0;
}

F: 找出直系亲属

题目描述

如果A，B是C的父母亲，则A，B是C的parent，C是A，B的child，如果A，B是C的（外）祖父，祖母，则A，B是C的grandparent，C是A，B的grandchild，如果A，B是C的（外）曾祖父，曾祖母，则A，B是C的great-grandparent，C是A，B的great-grandchild，之后再多一辈，则在关系上加一个great-。

输入

输入包含多组测试用例,每组用例首先包含2个整数n（0 然后接下来是n行的形式如ABC的字符串，表示A的父母亲分别是B和C，
如果A的父母亲信息不全，则用-代替，例如A-C,再然后是m行形式如FA的字符串,表示询问F和A的关系。

输出

如果询问的2个人是直系亲属，请按题目描述输出2者的关系，如果没有直系关系，请输出-。
具体含义和输出格式参见样例.

方法1：直接模拟，map记录每一对父母关系，例如mp[a]=b 则a的儿子是b，然后对询问找出所有的可能模拟就行方法2：搜索，就不用找出所有可能，直接搜索，最终搜到了就是有关系，然后根据要求输出就行这题的字符不要单个字符单个字符输入，直接字符串输入一行会节省很多时间

#include
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
int n,m;
mapmp;
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]);//直接模拟
            int ans=dfs(s[1],s[0],0);//搜索
            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: 最小长方形

题目描述

给定一系列2维平面点的坐标(x, y)，其中x和y均为整数，要求用一个最小的长方形框将所有点框在内。长方形框的边分别平行于x和y坐标轴，点落在边上也算是被框在内。

输入

测试输入包含若干测试用例，每个测试用例由一系列坐标组成，每对坐标占一行，其中|x|和|y|小于 231；一对0 坐标标志着一个测试用例的结束。
注意(0, 0)不作为任何一个测试用例里面的点。一个没有点的测试用例标志着整个输入的结束。

输出

对每个测试用例，在1行内输出2对整数，其间用一个空格隔开。第1对整数是长方形框左下角的坐标，第2对整数是长方形框右上角的坐标。

水题左下角坐标（最小的x，最小的y），右上角坐标（最大的x，最大的y）

#include
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 %dn",a,b,c,d);
    }
    return 0;
}

H: 逆序五进制

题目描述

编写一个程序，首先将一个十进制正整数逆序【需要去掉前导0】，然后转换成五进制正整数，最后输出该五进制正整数。

输入

每组测试数据的输入占一行，输入一个十进制正整数n。 （n<=100000）

输出

每组测试数据的输出占一行，输出转换后所得的五进制正整数。

水题

#include
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<>n;
    while(n){
        m=m*10+n%10;
        n/=10;
    }
    turn();
    return 0;
}

I: XP的魔塔

题目描述

大部分同学都熟知魔塔这个游戏，当然，如果你不知道也没有关系，接下来会有简单的介绍：首先在魔塔中有一个魔王，魔王抓走了公主，于是勇士要去拯救她(狗血剧情忽略不计)，XP最近对魔塔非常感兴趣，这里的魔塔只考虑N*N的地图，在地图中’.'代表勇士可以通过的路径，'X’代表墙，勇士当然无法走到墙里去。勇士能走的方向只能是上下左右，并且他不能走出这个图。图中只有一个’S’代表勇士，并且只有一个’T’代表公主，当然还有’L’代表魔王的喽啰，勇士如果要走到喽啰的位置，他必须要杀死喽啰，当然他也要扣除相应的血量，如果血量小于等于0，那么勇士的拯救计划就失败了，XP想要找到一条合适的路径，能够救出公主，也就是说要找到一条S能够到T的路径，并且途中勇士不能死亡，现在XP想知道是否存在这样的一条路径。

输入

输入包含多组测试用例，第一行输入一个T表示测试数据组数，(1<=T<=10)。每组测试数据第一行包含一个N(2<=N<=100)，N表示地图大小，接下来N行每行包含N个字符Gij，保证只出现’S’，‘T’，‘L’，’.’，‘X’四种字符。保证输入一定存在一个’S’和一个’T’。接下来N行包含N个数字Aij(0<=Aij<=10)，其中S对应位置的数字代表勇士的血量，L对应位置的数字代表如果勇士要杀死喽啰所需要扣除的血量，其他字符对应的数字保证为0。

输出

如果存在这样一条拯救路径，请输出YES，如果不存在输出NO。

搜索就是普通的搜索，没什么难度…下面给出dfs和bfs两种方法

#include
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 ansq;
    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;
}