第二届全国中医药院校大学生程序设计竞赛

朱雀 2022-08-31 12:28 258阅读 0赞

### 目录 ###

*  A 篮球队选拔
 *  B 黑暗意志
 *  C 调酒壶里的酸奶
 *  D 过分的谜题
 *  E 不存在的泳池
 *  F fps游戏
 *  G 流连人间的苏苏
 *  H 路哥从不低头 (还没有写)
 *  I 闪闪发光
 *  J 小C的数学问题
 *  K 周期串plus
 *  L TCMPC进阶之路

--------------------

# A 篮球队选拔 #

云南中医学院坐落于风景秀丽、四季如春的——昆明，…

一次训练时候，a老师给出了一个新的组队方案：将所有同学分成两队，一队由他带领，一队由另外一位体育老师b老师带领。  
组队的时候，a老师因为是发起者，所以他可以选择自己队的成员，也就是他选择一半的同学进入自己的队，剩下一半同学归b老师队。  
然后a老师每次派出己方一人进行单挑赛，由b老师从自己队伍中选择与之比赛的队员，进球数量多的一方获胜，败者出局。当然为了防止同学过度训练，每位同学只能进行一场单挑赛。每场比赛持续五分钟，若结束时双方都未进球，则两人同时出局。  
现在a老师希望自己的队伍没有人出局，请问a老师能否得到一个选人方案？

**输入**

> 第一行包含一个正整数T(1≤T≤10)表示多组输入数据，  
> 每组数据第一行包含一个正整数n(1≤n≤100000)表示有2n位同学参与训练  
> 第二行包含2n个正整数表示每位同学的技术值ai(0<=ai<=2000)  
> 第三行包含2n个正整数表示每位同学的发挥水平bi(-1000<=bi<=1000)

**输出**

> 每组数据包含一行，若能得到a老师想要的方案，则输出"Cheat",若不能得到，则输出"Fail"。

**样例输入 Copy**

> 2  
> 2  
> 1 3 2 4  
> 1 1 1 1  
> 1  
> 1 2  
> 2 1

**样例输出 Copy**

> Cheat  
> Fail

代码：

#include<bits/stdc++.h>
     
    using namespace std;
    const int N=200010;
     
    int n;
    struct ll{ 
        int a,b,nu;
        bool operator < (const ll &w) const{ 
            return nu>w.nu;
        }
    }l[N];
     
    int main(){ 
        int t;
        cin>>t;
     
        while(t--){ 
            scanf("%d",&n);
     
            for(int i=0;i<n*2;i++){ 
                scanf("%d",&l[i].a);        }
            for(int i=0;i<n*2;i++){ 
                scanf("%d",&l[i].b);
                l[i].nu=l[i].b+l[i].a;
            }
     
            int nn=n*2;
            sort(l,l+nn);
     
            if(l[n-1].nu>l[n].nu) printf("Cheat\n");
            else printf("Fail\n");
        }
        return 0;
    }

--------------------

# B 黑暗意志 #

在数千年前潘达利亚从卡利姆多分离之时，迷雾笼罩着这块新形成的大陆，…

但是团长需要知道，他们两个的小魔像血量是多少，才可以去攻击那个血量较多的小魔像，来保证这两个小魔像血量相同，从而击杀BOSS。  
所以现在告诉你所有小魔像的血量，你能告诉团长，那两个玩家所对应的小魔像血量是多少吗？

**输入**

> 第一行一个整数T，代表数据的组数（1<=T<=10）,接下来T组数据，每组数据的第一行是一个整数n（2<=n<=1000000,保证n是偶数），第二行是n个整数ai（0 <= ai <= 1000000000）代表血量，每两个整数之间有一个空格，（输入保证有且只有两个小魔像无法连线）

**输出**

> 对于每组数据，输出两个整数，分别代表两个小魔像的血量，中间有一个空格，并且血量较大的先输出。

**样例输入 Copy**

> 2  
> 6  
> 2 2 1 1 3 4  
> 4  
> 1 1 3 4

**样例输出 Copy**

> 4 3  
> 4 3

#include<bits/stdc++.h> //B
     
    using namespace std;
    typedef long long ll;
    const int N=1000010;
    ll a[N];
    int n,ma;
     
     
    int main(){ 
        int t;
        scanf("%d",&t);
        while(t--){ 
     
            scanf("%d",&n);
            ma=0;
            for(int i=0;i<n;i++){ 
                scanf("%lld",&a[i]);
            }
            int fl=0;
            a[n]=0;
            sort(a,a+n);
            reverse(a,a+n);
     
            for(int i=0;i<n;i++){ 
                if(a[i]!=a[i+1]){ 
                    if(fl==1) cout<<" ";
                    cout<<a[i];
                    fl++;
                }
                else i++;
                if(fl==2) break;
            }
     
                printf("\n");
        }
        return 0;
    }

--------------------

# C 调酒壶里的酸奶 #

最近小w学了一手调酒的技巧，这么帅的操作，说不定能靠这个俘获女神的芳心…

满心失望的小w想找一朵花，一瓣一瓣的撕下来，问问花朵女神到底喜不喜欢他…虽然这个答案是显而易见的，但是他还是想找一朵花…然而找花未果，反正花瓣不是偶数就是奇数，那他索性就用自己的操作次数作为花瓣个数吧！（找不到花我还不能脑补一朵吗…）  
但是小w已经没有心情去想答案了…那么你能告诉他，需要多少步操作才能倒出女神想要的酸奶吗？

**输入**

> 输入包含多组数据，每行三个正整数a,b,c分别表示两个调酒壶的容量以及女神想要的酸奶体积,a,b的范围都在\[0,100\]，c<=max(a,b)

**输出**

> 一行包含一个整数表示完成要求的最少操作次数，若达不到则输出"impossible"（没有双引号）

**样例输入 Copy**

> 10 15 11  
> 6 5 4

**样例输出 Copy**

> impossible  
> 4

代码：( dp )

#include<bits/stdc++.h>
    #define mem(a,b) memset(a,b,sizeof a);
    
    using namespace std;
    const int N=1e2+5;
    int a,b,c;
    int num;
    int dp[N][N],vis[N][N];
    
    void init(){ 
        mem(vis,0);
        mem(dp,0);
    }
    
    int bfs(){ 
        int A,B;
        dp[0][0]=0;
        vis[0][0]=1;
        queue<pair<int,int> > q;
    
        q.push({ 0,0});
        while(!q.empty()){ 
            int x=q.front().first,y=q.front().second;
            q.pop();
            for(int i=0;i<6;i++){ 
                if(i==0) A=a,B=y;
                if(i==1) A=x,B=b;
                if(i==2) A=0,B=y;
                if(i==3) A=x,B=0;
                if(i==4){ 
                    A=x-b+y>=0?x-b+y:0,B=x-b+y>=0?b:x+y;
                }
                if(i==5){ 
                    B=x-a+y>=0?x-a+y:0,A=x-a+y>=0?a:x+y;
                }
    
                if(!vis[A][B]){ 
                    vis[A][B]=1;
                    dp[A][B]=dp[x][y]+1;
                    if(A==c||B==c) return dp[A][B];
    
                    q.push({ A,B});
                }
            }
    
        }
    
        return 0;
    }
    
    
    int main(){ 
        while(cin>>a>>b>>c){ 
            init();
    
            num=bfs();
            if(num==0) cout<<"impossible"<<endl;
            else
            cout<<num<<endl;
        }
    
        return 0;
    }

--------------------

# D 过分的谜题 #

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

> 多组测试数据.每组数据的第一行包含一个正整数n(1<= n<=10000).

**输出**

> 每组数据输出一行整数表示最少需要经过几次移动能变回原序列，若不能，则输出"-1"

**样例输入 Copy**

> 3  
> 16

**样例输出 Copy**

> 3  
> 10

#include<bits/stdc++.h>
     
    using namespace std;
    typedef long long ll;
    const int N=100010;
     
    int n,t;
    int main(){ 
        int a[10010]={ 0};
     
        while(~scanf("%d",&n)){ 
     
            if(a[n]!=0){ 
                printf("%d\n",a[n]);
                continue;
            }
            if(n==1) printf("0\n");
     
            int m=n*2;
            int num=0;
            m=2*(m-n)-1;
            num=1;
            while(m!=n*2){ 
                if(m>n) m=2*(m-n)-1;
                else m=m*2;
                num++;
                //cout<<n<<"& "<<m<<endl;
                if(num>=1e5){ 
                    num=-1;
                    break;
                }
                if(m==1){ 
                    num*=2;
                    break;
                }
                if(m>=2*n) break;
            }
            a[n]=num;
            //cout<<num<<endl;
            printf("%d\n",num);
        }
     
        return 0;
    }

--------------------

# E 不存在的泳池 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 1]  
**输入**

> 多组测试数据，给出A,B表示两个泳池当前的水量(立方米)  
> （1<=A,B<=10^9）

**输出**

> 每组测试数据输出一个整数表示至少需要买多少个一次性抽水机，若买多少个都不能让泳池的水相等，则输出"-1"

**样例输入 Copy**

> 5 20  
> 14 8  
> 6 6

**样例输出 Copy**

> 2  
> \-1  
> 0

#include<bits/stdc++.h> //E
     
    using namespace std;
    const int N=200010;
     
    struct ll{ 
        int a,b,nu;
        bool operator < (const ll &w) const{ 
            return nu>w.nu;
        }
    }l[N];
     
    int gcd(int a,int b){ 
        return b?gcd(b,a%b):a;
    }
     
    int main(){ 
        int n,m;
        while(cin>>n>>m){ 
            if(n==m){ 
                cout<<"0"<<endl;
                continue;
            }
            int nu=gcd(n,m);
            int num=0;
            n=n/nu;
            m=m/nu;
            //cout<<n<<" "<<m<<endl;
            while(n%2==0||n%3==0||m%2==0||m%3==0){ 
                    if(n%2==0){ 
                        n=n/2;
                        num++;
                    }
                if(n%3==0){ 
                        n=n/3;
                        num++;
                    }
                if(m%2==0){ 
                        m=m/2;
                        num++;
                    }
                if(m%3==0){ 
                        m=m/3;
                        num++;
                    }
     
            }
            if(n==m) cout<<num<<endl;
            else cout<<-1<<endl;
     
        }
        return 0;
    }

--------------------

# F fps游戏 #

**题目描述**

> fps游戏是第一人称射击游戏。这类游戏有一个很重要的技巧也是基本功之一的，是压枪。  
> 为了模拟真实环境，在游戏里你每开一枪，枪口都会往上和左右浮动。  
> 如果你想使枪口在某个范围内，为了提高精准度，你就必须压枪。  
> 而且每把枪的后坐力不同和有效打击距离不同，就需要对每把枪都很熟悉，能很快的计算出在多远距离外开枪枪口会往上和左右浮动多少。  
> 现在只考虑枪的垂直浮动。  
> 假设在d米外有一个靶子，初始枪口正对靶心的圆心，靶心是个半径为r米的圆,现在你要射击c次。(你可以把枪看成一个点)。  
> 为了省力，要使压枪次数最少。  
> 只有当在靶上的射击位置在靶心之外时才需要压枪。  
> 每次压枪，枪口都会回到上次的射击位置。  
> 每次开枪最多只能压一次枪，不能连续压枪。

**输入**

> 每个输入文件只包含一组数据。  
> 包含3个正整数d,r，c和1个实数a(d,r,c意义如上文所述，a是每次开枪，枪口向上浮动的角度)。  
> (1 <= d,r <= 100,0 <= c <= 1000000,0 <= a < 90)

**输出**

> 一个整数，表示压枪的最少次数。

**样例输入 Copy**

> 10 1 10 3

**样例输出 Copy**

> 8

#include<bits/stdc++.h>
      
    using namespace std;
      
    int main(){ 
        double d,r,a;
        int c;
        cin>>d>>r>>c>>a;
        double mm=atan2(r,d)*180/3.1415926535;
      
      
        int num=mm/a+1;;
        //cout<<num<<endl;
        cout<<max(c-num,0)<<endl;
        return 0;
    }

--------------------

# G 流连人间的苏苏 #

**题目描述**

> 苏苏在做红尘仙的任务时，发现坐落于风景秀丽、四季如春的昆明市的云南中医学院。  
> 没过多久，苏苏就喜欢上了这个学校。以致于苏苏忘了回涂山的时间，现在她只剩下d天的时间待在云南中医学院。由于时间紧迫，苏苏想方设法为建设更好的云南中医学院。  
> 假设学校里某条街道有n个房子。  
> 每天选择两个门牌号l、r,给这两个门牌号之间的所有房子的门前都栽一棵树，已经有树的不需要再种。  
> 苏苏想知道在某天，有哪些房子前有树。

**输入**

> 每个输入文件只有一组数据  
> 第一行包含n,d。(1 <= n,d <= 1000)  
> 接下来d行，每行包含两个整数l,r(1 <= l <= r <= n)

**输出**

> 输出d行。  
> 每行输出门牌号的区间。每个区间以逗号分隔。  
> 具体看样例。

**样例输入 Copy**

> 10 4  
> 1 3  
> 2 4  
> 5 6  
> 8 10

**样例输出 Copy**

> \[1,3\]  
> \[1,4\]  
> \[1,6\]  
> \[1,6\],\[8,10\]

#include<bits/stdc++.h>
     
    using namespace std;
    typedef long long ll;
    const int N=100010;
     
    int n,t;
    int main(){ 
        cin>>n>>t;
        int l,r;
        int v[n+10]={ 0};
        while(t--){ 
     
            cin>>l>>r;
            for(int i=l;i<=r;i++) v[i]=1;
     
            int fl=0,num=0,f=0;
            for(int i=1;i<=n;i++){ 
                if(fl==0&&v[i]==1){ 
                    if(f==1) printf(",");
                    printf("[%d",i);
                    num=i;
                    fl=1;
                    f=1;
                }
     
                else if(v[i]==1) num++;
                else if(fl==1&&v[i]==0){ 
                    printf(",%d]",i-1);
                    fl=0;
                }
     
            }
            if(fl==1)   printf(",%d]",n);
            printf("\n");
        }
     
     
     
        return 0;
    }

--------------------

# H 路哥从不低头 (还没有写) #

**题目描述**

> 路哥是云南中医学院大一新生，对路哥来说任何人任何物都只是他的道具而已。  
> 过程不重要，只要最后胜利是属于路哥的。  
> 路哥每次出完手就把这锅扔给别人。  
> 而他自己，深藏功与名，事了拂衣去。  
> 毕竟，深藏不露是一种卓越的才能。  
> 某天，路哥被班主任叫去清理海报。  
> 这里有一块宽为W，高为H的海报栏。以左下角为原点建立直角坐标系。  
> 第i张贴上去的海报左下角为(x1\_i,y1\_i),右上角为(x2\_i,y2\_i)。  
> 撕去一张海报会导致所有覆盖在其上的海报被同时撕掉(这个过程具有传递性，即如果A覆盖B，B覆盖C，那么撕掉C会导致A和B均被撕掉)  
> 一张海报如果可以被撕掉需要至少存在一个角没有被其他海报覆盖。  
> 海报A被海报B覆盖当且仅当存在A和B的交面积大于0，并且A在B之前贴出。  
> 由于路哥嫌麻烦，为了提高效率，路哥会一次性的撕掉尽可能多的海报。  
> 现在请你帮路哥计算路哥一次最多可以撕掉多少张海报。  
> 在张数相同的情况下，路哥会选择更早贴出的海报。

**输入**

> 多组数据。  
> 第一行三个整数W,H,N,分别为海报栏的宽和高，贴出的海报数量。  
> 接下来N行，每行四个整数x1\_i,y1\_i,x2\_i,y2\_i。  
> (1 <= W,H <= 10000000, 1 <= N <= 1000, 0 <= x1\_i,x2\_i <= W, 0 <= y1\_i,y2\_i <= H)

**输出**

> 输出两个整数，分别是海报数量和撕去的是第几张。

**样例输入 Copy**

> 6 7 4  
> 0 0 4 4  
> 1 0 3 4  
> 1 4 4 6  
> 0 0 3 5

**样例输出 Copy**

> 3 1

在这里插入代码片

--------------------

# I 闪闪发光 #

**题目描述**

> 一所位于云南昆明的中医药本科院校–云南中医学院。  
> 因为报考某专业的人数骤减，正面临着停招的危机。  
> 其中有九名少女想到一条妙计——成为偶像，  
> 只要她们成为偶像，学校的名气便会增加，而报考的人数亦会上升。  
> 就这样，九位个性鲜明的少女决定一起努力成为偶像。  
> 希望可以凭借偶像的名气增加生源来挽救自己所喜爱的专业，让自己的学校闪闪发光。  
> 她们为了成为偶像，第一步对于她们来说是减肥！  
> 这里有n个重物，第i个重物的重量是2^\{w\_i\}。她们每天任务要完成的重量是n个重物的重量和。  
> 每次举重的重量和必须是2的幂，重物数量不要求。  
> 但是为了方便，要使举重的次数最少。

**输入**

> 多组数据。  
> 每组数据第一行一个整数n。(1 <= n <= 10^6)  
> 第二行有n个整数w\_1,w\_2,…,w\_n。(0 <= w\_i <= 1000000)

**输出**

> 输出最少的举重次数。

**样例输入 Copy**

> 5  
> 1 1 2 3 3

**样例输出 Copy**

> 2

**提示**

> 1,1,2一组;  
> 3,3一组。

#include<bits/stdc++.h>
    
    using namespace std;
    const int N=2e6+5;
    int a[N];
    
    int main(){ 
        int n;
        while(~scanf("%d",&n)){ 
            memset(a,0,sizeof a);
    
            for(int i=0;i<n;i++){ 
                int x;
                scanf("%d",&x);
                a[x]++;
            }
            long long num=0;
    
            for(int i=0;i<=N;i++){ 
                if(a[i]>0){ 
                    a[i+1]+=a[i]/2;
                    if(a[i]%2==1) num++;
                }
    
            }
    
            printf("%d\n",num);
    
        }
    
        return 0;
    }

--------------------

# J 小C的数学问题 #

**题目描述**

> 小C是个云南中医学院的大一新生，在某个星期二，他的高数老师扔给了他一个问题。  
> 让他在1天的时间内给出答案。  
> 但是小C不会这问题，现在他来请教你。  
> 请你帮他解决这个问题。  
> 有n个数，每个数有权值。  
> 数学老师定义了区间价值为区间和乘上区间内的最小值。  
> 现在要你找出有最大区间价值的区间是什么，并输出区间价值。

**输入**

> 每个输入文件只包含单组数据。  
> 第一行一个整数n。(1 <= n <= 100000)  
> 第二行n个整数a\_1,a\_2,…,a\_n。(0 <= a\_i <= 1000000)

**输出**

> 第一行输出一个整数，表示最大的区间价值。  
> 第二行输出两个整数，表示区间的起点和终点。  
> 保证答案唯一。

**样例输入 Copy**

> 6  
> 10 1 9 4 5 9

**样例输出 Copy**

> 108  
> 3 6

#include<bits/stdc++.h>
    
    using namespace std;
    const int N=1e5+5;
    int n;
    long long a[N],q[N];
    int l[N],r[N];    //第i个元素对应的最左和最右位置。
    
    int main(){ 
        scanf("%d",&n);
        long long ma=-1;
        int x=0,y=0;
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    
        for(int i=1;i<=n;i++) q[i]=q[i-1]+a[i];
    
        for(int i=1;i<=n;i++){ 
            int k=i;
            while(k>1 && a[k-1]>=a[i]){ 
                k=l[k-1];
            }
            l[i]=k;
            //printf("%d\n",k);
        }
        for(int i=n;i>=1;i--){ 
            int j=i;
            while(j<n && a[j+1]>=a[i]){ 
                j=r[j+1];
            }
            r[i]=j;
            //printf("&%d\n",j);
        }
        for(int i=1;i<=n;i++){ 
            if(a[i]*(q[r[i]]-q[l[i]-1]) > ma){ 
                ma=a[i]*(q[r[i]]-q[l[i]-1]);
                x=l[i];
                y=r[i];
            }
        }
    
    
        printf("%lld\n",ma);
        printf("%d %d\n",x,y);
    
    
        return 0;
    }

--------------------

# K 周期串plus #

**题目描述**

> 如果一个字符串可以由某个长度为k的字符串重复多次得到，我们说该串以k为周期。例如abcabcabcabc以3为周期（当然他也以6，12为周期）。输入一个长度不超过100000的串，输出他的最小周期。

**输入**

> 多组测试数据,每组仅一行为一个仅有大写字母组成的字符串。

**输出**

> 对于每组数据输出该字符串的最小周期。

**样例输入 Copy**

> HOHO

**样例输出 Copy**

> 2

#include<bits/stdc++.h>
     
    using namespace std;
    typedef long long ll;
    const int N=100010;
     
    int n,t;
    string a;
     
    int main(){ 
        while(cin>>a){ 
            string s="";
            int m=0;
            s+=a[0];
            m=1;
            int len=a.size();
            for(int i=0;i<a.size();i++){ 
                if(a[i]==s[0]){ 
                    int j=1;
                    //while(j<m && i+j<len && a[i+j]==s[j]) j++;
                    if(a.find(s,i)==i){ 
                        //cout<<"a.find(s,i)"<<a.find(s,i)<<endl;
                        i=i+m-1;
                    }
                    else{ 
     
                        for(;m<=i;m++) s+=a[m];
     
     
                    }
     
                    //cout<<"j="<<j<<endl;
                    //cout<<"a["<<i<<"]="<<a[i]<<endl;
     
     
                }
                else{ 
     
                    for(;m<=i;m++) s+=a[m];
     
                }
                //cout<<"&s="<<s<<endl;
                //cout<<"&i="<<i<<endl;
                //cout<<"&m="<<m<<endl;
            }
     
            cout<<m<<endl;
     
        }
     
     
     
        return 0;
    }

--------------------

# L TCMPC进阶之路 #

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

> 多组数据，第一行输入一个整数T（1≤T≤10000）表示数据组数  
> 以下T行，每行输入一个正整数n(1≤n≤10000）表示小w当前做到第n题(第n题也已AC)，且题目编号是有序的。

**输出**

> 每行输出一个整数表示小w当前的积分

**样例输入 Copy**

> 2  
> 5  
> 10

**样例输出 Copy**

> 15  
> 55

#include<bits/stdc++.h>
     
    using namespace std;
    int n;
     
    int main(){ 
        int t;
        cin>>t;
     
        while(t--){ 
            cin>>n;
     
            long long num=(1+n)*n/2;
            cout<<num<<endl;
        }
        return 0;
    }

今天重现赛好多题都没写出来，心态炸裂。。。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70]: /images/20220829/c0575fa6d84e4bba94bc0bbcca566cd4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 1]: /images/20220829/9211bcca5c3f49a3af6db96fdb45f639.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 2]: /images/20220829/7d2405846d644db69ef542208d9ff649.png