第五届全国中医药院校大学生程序设计竞赛重现赛——题解

缺乏、安全感 2022-09-04 12:43 408阅读 0赞

### 目录 ###

*  A Jingwei Tian hai
 *  B Mona Lisa's smile
 *  C Morse Code
 *  D Peach Conference（线段树+区间增加+区间修改+长整型输入输出 待补）
 *  E Shennong tastes all kinds of herbs
 *  F 冰冻三尺
 *  G 车神羲和
 *  H 大秦宝藏（DFS+剪枝 待补）
 *  I 韩信点兵
 *  J 纪昌学射
 *  K 夸父逐日（BFS+图论+单源最短路径 待补）
 *  L 团结军团（后缀自动机SAM+动态规划 待补）

放个我们重现赛的链接：[HNUCM-OJ-第五届中医院校程序设计重现赛][HNUCM-OJ-]

# A Jingwei Tian hai #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70]  
样例输入 Copy

> 1 1  
> 0 0

样例输出 Copy

> 1

代码：

#include<bits/stdc++.h>
     
    using namespace std;
     
    int main(){ 
        int a,b,c;
        while(cin>>a>>b&&(a||b)){ 
     
            int num=a*b;
            printf("%d\n",num);
        }
     
     
        return 0;
    }

# B Mona Lisa’s smile #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 1]  
样例输入 Copy

> 4 1 1  
> 6 2 1  
> 0 0 0

样例输出 Copy

> 2.0  
> 3.0

代码：

#include<bits/stdc++.h>
     
    using namespace std;
     
    int main(){ 
        int a,b,c;
        while(cin>>a>>b>>c&&a){ 
     
            int mi=0x3f3f3f;
            if(b!=0){ 
               mi=min(mi,b);
            }
            if(b!=a) mi=min(a-b,mi);
            if(c!=0){ 
                mi=min(mi,c);
            }
            if(c!=a)    mi=min(mi,a-c);
     
            double num=mi*a/2.0;
            printf("%.1lf\n",num);
        }
     
     
        return 0;
    }

# C Morse Code #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 2]

> 样例输入 Copy  
> 2  
> 3  
> 0

> 样例输出 Copy  
> 3  
> 5

代码：

#include<bits/stdc++.h>
     
    using namespace std;
    long long a[1000010][2];
    int main(){ 
        int n,b,c;
     
        a[1][0]=1;
        a[1][1]=1;
        a[2][0]=2;
        a[2][1]=1;
        int k=3;
        while(cin>>n&&n){ 
     
            for(int i=k;i<=n;i++){ 
                a[i][0]=(a[i-1][0]+a[i-1][1])%2021;
                a[i][1]=a[i-1][0]%2021;
                k++;
            }
            printf("%d\n",(a[n][0]+a[n][1])%2021);
        }
     
     
        return 0;
    }

# D Peach Conference（线段树+区间增加+区间修改+长整型输入输出 待补） #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 3]

> 样例输入 Copy  
> 10 6  
> 1 1 10  
> 0 3 7  
> 2 1 10  
> 0 2 9  
> 1 7 8  
> 0 6 9

> 样例输出 Copy  
> 19  
> 12

# E Shennong tastes all kinds of herbs #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 4]

> 样例输入 Copy  
> 70 3  
> 71 100  
> 68 3  
> 1 2  
> 1 -2  
> 1 -3  
> 1 -4  
> 0 0

> 样例输出 Copy  
> 15

代码：

#include<bits/stdc++.h>
    
    using namespace std;
    int tt[110],vv[110];
    int dp[105][1010];
    int a[5][4];
    int T,M;
    int main(){ 
    
        while(cin>>T>>M&&(T||M)){ 
    
            for(int i=1;i<=M;i++){ 
                cin>>tt[i]>>vv[i];
    
            }
    
            for(int i=0;i<3;i++){ 
                cin>>a[i][0]>>a[i][1];
    
            }
    
            for(int i=0;i<=M;i++){ 
                for(int j=0;j<=T;j++) dp[i][j]=0;
            }
    
            for(int i=1;i<=M;i++){ 
                for(int j=1;j<=T;j++){ 
                    if(tt[i]<=j) dp[i][j]=max(dp[i-1][j],dp[i-1][j-tt[i]]+vv[i]);
                    else dp[i][j]=dp[i-1][j];
                }
            }
            int ma=dp[M][T];
            if((T-a[0][0]-a[1][0])>=0)
                ma=max(dp[M][T],(dp[M][T-a[0][0]-a[1][0]]+a[0][1]*a[1][1]));   //0 1
            if((T-a[0][0]-a[2][0])>=0)
                ma=max(ma,(dp[M][T-a[0][0]-a[2][0]]+a[0][1]*a[2][1]));   //0 2
            if((T-a[2][0]-a[1][0])>=0)
                ma=max(ma,(dp[M][T-a[1][0]-a[2][0]]+a[1][1]*a[2][1]));   //1 2
    
            cout<<ma<<endl;
        }
    
        return 0;
    }

# F 冰冻三尺 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 5]

> 样例输入 Copy  
> 1  
> 2  
> 3  
> 0

> 样例输出 Copy  
> 1  
> 2  
> 3

代码：

#include<bits/stdc++.h>
     
    using namespace std;
     
    int main(){ 
        int a,b,c;
        while(cin>>a&&a){ 
     
            int num=a;
            printf("%d\n",num);
        }
     
     
        return 0;
    }

# G 车神羲和 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 6]

> 样例输入 Copy  
> 120 90 30  
> 100 50 50  
> 0 0 0

> 样例输出 Copy  
> 120  
> 100

> 提示  
> 说明：测试实例保证输入数据合法，且输出数据一定为正整数。

代码：

#include<bits/stdc++.h>
     
    using namespace std;
     
    int main(){ 
        int a,b,c;
        while(cin>>a>>b>>c&&(a||b||c)){ 
     
            int num=(a*c)/(a-b);
            printf("%d\n",num);
        }
     
     
        return 0;
    }

# H 大秦宝藏（DFS+剪枝 待补） #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 7]

> 样例输入 Copy  
> 4 1  
> 1 1 1 2 8 8  
> 2 2 2 2 9 4  
> 1 2 8 3 1 7  
> 2 1 1 5 1 6  
> 6 4  
> 3 3 6 2 5 1  
> 5 5 1 8 2 9  
> 1 3 8 1 9 1  
> 3 1 4 5 9 4  
> 1 5 1 9 2 3  
> 5 1 3 2 6 2  
> 0 0

> 样例输出 Copy  
> Case 1: 16  
> Case 2: 45

# I 韩信点兵 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 8]

> 样例输入 Copy  
> 2  
> 160 1  
> 170 1  
> 4  
> 160 1  
> 165 1  
> 170 1  
> 180 2  
> 0

> 样例输出 Copy  
> Case 1: 10  
> Case 2: 35

代码：

#include<bits/stdc++.h>
     
    using namespace std;
     
    int main(){ 
        int n;
        int nu=0;
        while(cin>>n&&n){ 
                nu++;
            int a[100010]={ 0},k=0;
            int x;
            for(int i=0;i<n;i++){ 
                cin>>a[k++]>>x;
                for(int j=1;j<x;j++){ 
                    a[k]=a[k-1];
                    k++;
                }
            }
            sort(a,a+k);
            //cout<<"&"<<endl;
            int num=0;
            for(int i=0;i<k/2;i++){ 
                num+=a[k-i-1]-a[i];
            }
     
            cout<<"Case "<<nu<<": "<<num<<endl;
        }
     
     
    }

# J 纪昌学射 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 9]

> 样例输入 Copy  
> 2 2  
> 1 1 2 2  
> 0 0

> 样例输出 Copy  
> 1

代码：

#include<bits/stdc++.h>
     
    using namespace std;
     
    int main(){ 
        int a,b;
        while(cin>>a>>b&&(a||b)){ 
            int x,y;
            double r=b/2.0;
            int num=0;
            for(int i=0;i<a;i++){ 
                cin>>x>>y;
                if((x-r)*(x-r)+y*y==r*r) num++;
            }
     
            cout<<num<<endl;
        }
     
        return 0;
    }

# K 夸父逐日（BFS+图论+单源最短路径 待补） #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 10]  
样例输入 Copy  
4 7 3 2 2  
4 4  
1 4  
1 2 7  
1 3 8  
1 4 6  
2 4 1  
3 2 1  
3 4 3  
2 1 3  
4 7 3 2 2  
2 2  
1 4  
1 2 7  
1 3 8  
1 4 6  
2 4 1  
3 2 1  
3 4 3  
2 1 3  
0 0 0 0 0  
样例输出 Copy  
4  
2

# L 团结军团（后缀自动机SAM+动态规划 待补） #

[HNUCM-OJ-]: http://acm.hnucm.edu.cn/JudgeOnline/contest.php?cid=1196
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70]: /images/20220829/2dc7e3df54ea4074a4c770b100d0fe26.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 1]: /images/20220829/5b5dffd74b3548e589c63d86b5867eca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 2]: /images/20220829/c443bdee89fe45d6a520b3ada3c71a8e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 3]: /images/20220829/c4abdc3f0c3e46b2b78e013f26e5a93c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 4]: /images/20220829/cdca4ea46f2d4a30b8f91a85a68081a1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 5]: /images/20220829/7111544320da4d73b1425eac2d6e5ce0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 6]: /images/20220829/cc13e3613bb44ecd888470c1814f0100.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 7]: /images/20220829/a3f1759e28a649fdb26079944e0da726.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 8]: /images/20220829/e0ee6c160fb743cd9cd80f26acd13b59.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 9]: /images/20220829/31672bf50fc0424c8fa8a6fedb141610.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 10]: /images/20220829/1f9d971190ef41e9b396a3f0fbbd29f7.png