信息科学与工程学院第五届大学生程序设计竞赛——热身赛

A:X星人的地盘

题目描述

一天，X星人和Y星人在一张矩形地图上玩抢地盘的游戏。
X星人每抢到一块地，在地图对应的位置标记一个“X”；Y星人每抢到一块地，在地图对应的位置标记一个“Y”；如果某一块地无法确定其归属则标记一个“N”。
最终统计谁拥有的地盘最大，即统计“X”和“Y”的个数。如果“X”的个数多，则说明X星人的地盘更大，输出“X win”；反之，如果Y星人的地盘更大，则输出“Y win”；如果X星人和Y星人拥有的地盘一样大，则输出“The same”。

输入

单组输入。
第1行输入两个正整数m和n，表示地图矩阵的行和列。(m和n均不超过1000)
从第2行到第m+1行，输入一个由'X'、'Y'和'N'三种字符组成的矩阵，每行包含n个字符，一共m行。

输出

如果X星人拥有的地盘大，输出“X win”；如果Y星人拥有的地盘大，输出“Y win”；如果拥有的地盘一样大，输出“The same”。

样例输入 Copy

5 5
XXNYY
XYXYX
NNXXY
YYYYY
XXXXX

样例输出 Copy

X win

#include<iostream>
#include<algorithm>
#include<string>
char a[1005][1005];
using namespace std;
int main()
{
    int m,n;
    int s=0,sum=0;
    cin>>m>>n;
    for(int i=0;i<m;i++)
        cin>>a[i];
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(a[i][j]=='X')
                s++;
            if(a[i][j]=='Y')
                sum++;
        }
    }
    if(s>sum)
        cout<<"X win"<<endl;
    if(s<sum)
        cout<<"Y win"<<endl;
    if(s==sum)
        cout<<"The same"<<endl;
    return 0;
}

 B:X星人的统计

题目描述

一年一度的X星人口普查又开始了，其中有一项是统计各民族X星人的数量。X星人分属四个不同的民族，四个民族分别用A、B、C和D表示。
现在给出N个X星人的民族信息，请统计各民族X星人的总数。

输入

单组输入。
第1行输入统计的总人数N，N<=10^6。
第2行输入N个X星人的民族信息，四个民族分别用A、B、C和D表示，两两之间用英文空格隔开。

输出

请按照A、B、C、D的顺序分别输出每一个民族的总人数，两两之间用英文空格隔开。

样例输入 Copy

10
A C B D A C B D D A

样例输出 Copy

3 2 2 3

#include<iostream>
using namespace std;
int main()
{
    int n;
    int count[4] = { 0 };
    cin >> n;
    for (int i = 0; i < n; i++) 
    {
        char c;
        cin >> c;
        switch (c)
        {
        case'A':
            count[0]++;
            break;
        case 'B':
            count[1]++;
            break;
        case 'C':
            count[2]++;
            break;
        case 'D':
            count[3]++;
            break;
        default:
            break;
        }
    }
    cout << count[0] << " " << count[1] << " " << count[2] << " " << count[3] << endl;
    return 0;
}

 C:X星人的报数

题目描述

N个X星人站成一排，他们发明了一种奇怪的报数方式。
从第1个人开始报数，第1个人报数为1，第2个人报数为2，接下来奇数位置的人报数为前一个人报数加1，偶数位置的人报数为前一个人的两倍。
请问第N个人的报数是多少？

输入

输入一个正整数N(N<=40)。

输出

输出第N个人的报数。

样例输入 Copy

4

样例输出 Copy

6

#include<iostream>
using namespace std;
int a[64];
int main()
{
    int n;
    cin>>n;
    a[1]=1,a[2]=2;
    for(int i=3;i<=n;i++)
        if(i%2!=0)
            a[i]=a[i-1]+1;
        else
            a[i]=2*a[i-1];
    cout<<a[n]<<endl;
    return 0;
}

 D:X星人的变换

题目描述

X星人发明了一种简单的基于字符串变换的加密方法，具体规则如下：
(1) 将输入的明文字符串（明文中只包含小写字母和空格）以单词为单位进行逆序，即将明文中的第1个单词移到最后，第2个单词移到倒数第二，......，最后一个单词移到最前面。
(2) 再将每一个单词的第一个字母和它的最后一个字母进行调换。
(3) 输出变换之后的密文字符串。

输入

单组输入，每组输入一行字符串表示加密之前的明文，字符串中仅包含小写字母和空格，且长度不超过1000。

输出

输出变换之后的密文字符串。

样例输入 Copy

i love hnucm

样例输出 Copy

mnuch eovl i

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
    string a, b = "",c[1024];
    getline(cin, a);
    int t = 0;
    for (int i = 0; i < a.length(); i++)
        if (a[i] != ' ')
            b += a[i];
        else
        {
            c[t++] = b;
            b = "";
        }
    if (b != "")
        c[t++] = b;
    reverse(c, c + t);
    for (int i = 0; i < t; i++)
    {
        b = c[i];
        int n = b.size();
        swap(b[0], b[n - 1]);
        cout << b << " ";
    }
    cout << endl;
    return 0;
}

 E:X星人的高考

题目描述

一年一度的X星高考如期举行。今年X星新高考一卷的数学真的很难，据说把很多考生都考哭了。
今年数学考试的多选题仍然是4道题，每题5分，共20分。在每小题给出的4个选项中，有多项符合题目要求，全对得5分，选对但不全得2.5分，有选错的得0分。每道题均包含A、B、C和D四个选项。
现在给出某X星考生的多选题答案和正确答案，请编写一个程序计算该X星考生最终多选题的得分。

输入

单组输入。
每组输入两行，第1行包含该X星人四道多选题的答案，两两之间用空格隔开；第2行包含四道多选题的正确答案，两两之间用空格隔开（答案不一定按照字典序排列）。

输出

输出该X星考生最终多选题的得分(答案保留一位小数)。

样例输入 Copy

A BC AC ABC
AB BC AD AB

样例输出 Copy

7.5

#include<iostream>
#include<string>
using namespace std;
int main()
{
    string a[4],b[4];
 double s=0.0;
    for(int i=0;i<4;i++)
        cin>>a[i];
    for(int i=0;i<4;i++)
        cin>>b[i];
    for(int i=0;i<4;i++)
    {
        string x=a[i],y=b[i];
        int m=0,n=1;
                for(char c:x)
        {
            if(y.find(c)!=string::npos)
                m++;
            else
                n=0;
        }
        if(n)
        {
            if(m==y.size())
                s+=5;
            else
                s+=2.5;
        }
    }
    printf("%.1lf",s);
   return 0;
}

 F:X星人的纸牌

题目描述

X星人最近在玩一个纸牌游戏，该游戏的规则如下：
(1) 一共有N张纸牌，每张纸牌上都写有一个大于等于1且小于等于100的正整数，这N张纸牌从左往右一字排开。
(2) X星人先取出一张纸牌，然后在其右边再取出一张纸牌，不要求两张纸牌连续，但是下一张纸牌上的数字要小于上一张纸牌，依次取出若干张纸牌，即完成一轮操作。
(3) 对剩下的纸牌按照上述规则进行第二轮操作。
(4) 通过若干轮操作后所有的纸牌将全部取出。
现在需要你编写一个程序计算X星人最少需要进行多少轮操作可以将所有纸牌全部取出。

输入

单组输入。
第1行输入一个正整数N表示纸牌的数量，N<=1000。
第2行输入N个正整数，表示N张纸牌上对应的数字，两两之间用英文的空格隔开。

输出

输出将所有纸牌全部取出所需要的最少操作轮数。

样例输入 Copy

8
45 12 34 90 45 56 8 14

样例输出 Copy

4

#include <iostream>
using namespace std;
int a[1005];
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int s = 0;
    int sum=0;
    while (1)
    {
        int t = a[0];
        for (int i = 1; i < n; i++)
        {
            if (a[i] < t)
                t = a[i];
            else
            {
                a[s] = a[i];
                s++;
            }
        }
        sum++;
        if (s == 0)
            break;
        else
        {
            n = s;
            s = 0;
        }
    }
    cout<<sum<<endl;
    return 0;
}

 G:HNUCM的删数问题

题目描述

在HNUCM某学院的数学课堂上，老师提出了一个这样的问题：

• 有一个序列n个数，分别为1~n
• 其中某些数字需要将他们删除，每次删除可以选择一个K（1<=K<=n）,然后删除K的最小倍数，并且该次删除的代价为K（注意若K本身不需要被删除则不能选择K）
• 求删除所有需要删除的数的最小代价和（删除不同的数的代价可以相同，但需要分开计算）

现给定一个长度为N的01序列，若位置i为‘0’代表数字i（1<=i<=N）的数需要被删除，否则不需要删除，biscuit对这个问题很疑惑，你能写一个程序帮帮他计算最小代价和吗？
 

输入

多组输入。
第一行一个正整数T，代表T组测试用例（T<=10）
每组测试用例包含两行：
第一行一个正整数N（N<=50000），代表序列长度；
第二行一个长度为N的01序列，代表1~N个位置的数需不需要被删除，‘0’表示需要删除，‘1’表示不需要。

输出

删除所有需要删除数的最小代价和。

样例输入 Copy

6
6
111111
7
1101001
4
0000
4
0010
8
10010101
15
110011100101100

样例输出 Copy

0
11
4
3
17
42

提示

eg:
测试样例1：没有需要删除的数，代价和为0
测试样例2：需要删除的数有3、5、6，删除3和6的最小代价都是3，删除5的最小代价是5
测试样例3：1~4都需要删除，最小代价都是1

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =5e4 +5;
const int M =1e9 +7;
void solve(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        char c;
        cin>>c;
        a[i]=c-'0';
    } 
    vector<int> b(n+1);
    for(int i=n;i>=1;i--){
        if(a[i-1]==0){
            b[i]=i;
            for(int j=i*2;j<=n;j+=i){
                b[j]=min(b[j],b[i]);
            }
        }
    }
    int s=0;
    for(int i=1;i<=n;i++){
        if(a[i-1]==0){
            s+=b[i];
        }
    }
    cout<<s<<"\n";
}
int main() {
    cin.tie(0)->sync_with_stdio(false);
    int t;cin>>t;while(t--)
    solve();
    return 0;
}

 H:HNUCM的元素交换

题目描述

biscuit在HNUCM某学院的C语言程序设计课程中学习了数组的相关知识，在学习过程中他遇到了一个这样的问题：

• 给定一个含有N个元素的数组a，你可以进行如下操作至多K次（注意是至多，可能不操作或者少于K次操作）
  • 选择两个下标 i 和 j（1 <= i < j <= N）,并且 i MOD K == j MOD K（MOD代表取余）
  • 交换 a[i] 和 a[j] 元素的位置
• 在完成操作后，在数组a中选择连续的K个元素，它们的和作为你最终的分数，问最后能得到的最大分数是多少？

输入

多组输入。第一行一个正整数T表示T组测试样例（T<=100）
每组输入包含两行：
第一行两个正整数N(N <= 100)和K(K<=N)，分别代表数组长度和最多操作次数；
第二行N个正整数，代表数组a。(a[i] <= 1e9)

输出

每组输入，输出一个正整数代表能得到的最大分数。

样例输入 Copy

4
3 2
5 6 0
1 1
7
5 3
7 0 4 0 4
4 2
2 7 3 4

样例输出 Copy

11
7
15
10

提示

eg：
测试样例1和2，都不需要操作
测试样例3：交换a[1] 和 a[4] 之后选择a[3] a[4] a[5]三个元素可得到最大和

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =5e4 +5;
const int M =1e9 +7;
void solve(){
    int n,k;
    cin>>n>>k;
    vector<ll> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    } 
    vector<vector<ll>> b(k);
    for(int i=0;i<n;i++){
        b[i%k].push_back(a[i]);
    }
    for(int i=0;i<k;i++){
        sort(b[i].begin(),b[i].end(),greater<ll>());
    }
    vector<ll> c;
    for(int i=0;i<n;i++){
        c.push_back(b[i%k].back());
        b[i%k].pop_back();
    }
    ll s=0;
    for(int i=0;i<k;i++){
        s+=c[i];
    }
    ll m=s;
    for(int i=k;i<n;i++){
        s+=c[i]-c[i-k];
        m=max(m,s);
    }
    cout<<m<<"\n"; 
}
int main() {
    cin.tie(0)->sync_with_stdio(false);
    int t;cin>>t;while(t--)
    solve();
    return 0;
}