当前位置：首页 > news >正文

计算机学院第三周语法组及算法组作业

news 来源：原创 2024/5/18 19:13:22

语法组

Ayo唱歌阿伟死

旋转字符串

朱奕锦的字符串匹配

核酸检测小能手

字符统计

收帐

算法组

年月日问题

蒙德佳酿节

K-优字符串

最长连续休息时间

品种临近

懒惰的公牛

语法组

Ayo唱歌阿伟死

题目描述

阿伟非常喜欢一个叫做Ayo的歌手，每次看到Ayo发新歌就会马上在评论区发Ayosings aws（Ayo唱歌阿伟死），阿伟把这句话当作自己的电脑锁屏密码，并且收藏了一份Ayo无损音乐.zip，阿伟决定对这份压缩包进行加密，他将电脑锁屏密码所有字母转换成Ascii码值，相加起来得到一串数字作为密码。现在你知道了阿伟密码的由来，请先输入Ayosingsaws解锁电脑，然后算出密码，获得珍贵的Ayo无损音乐吧

输入

一行，一个字符串

输出

输出一个整数，为字符串每个字符ASCII码值之和

样例输入

Ayosingsaws

样例输出

源代码

#include <iostream>
using namespace std;
int main()
{
    string s;
    cin >> s;
    int ans = 0;
    for(int i = 0;i < s.size();i ++ )
    {
        ans += int(s[i]);
    }
    cout << ans;
    return 0;
}

旋转字符串

题目描述

输入两个字符串, s 和 goal。如果在若干次旋转操作之后，s 能变成 goal ，那么输出 true ，否则输出false。s 的旋转操作就是将 s 最左边的字符移动到最右边。例如, 若 s = 'abcde'，在旋转一次之后结果就是'bcdea' 。

输入

共两行，分别为字符串s和字符串goal。输入的两个字符串s和goal由小写英文字母组成，且两个字符串的长度length满足：1<=length<=100。

输出

共一行，为"true"或者"false"

样例输入

abcde
cdeab

样例输出

true

源代码

#include <iostream>
using namespace std;
int main()
{
    string str;
    cin >> str;
    int flag = 0;
    string s;
    cin >> s;
    s = s + s;
    for(int i = 0;i < s.size();i ++ )
    {
        if(s[i] == str[0])
        {
            int j = i + 1,k = 1;
            while(s[j] == str[k])
            {
                j ++ ;
                k ++ ;
            }
            if(k == str.size())
            {
                flag = 1;
                break;
            }
        }
    }
    if(flag == 0)printf("false\n");
    else if(flag == 1)printf("true\n");
    return 0;
}

朱奕锦的字符串匹配

题目描述

朱奕锦学长有n个字符串，张毅学长也给了你一个字符串，你需要判断朱奕锦学长的哪些字符串
里含有张毅学长的给你的字符串，如果存在输出Yes，否则输出N0末尾换行；
字符串长度不大于100

输入

第一行一个整数n
第二行是张毅学长给你的字符串
接下来n行，每行一个字符串，是朱奕锦学长给你的字符串

输出

yes或no

样例输入

1
dfg
asdfghjkl

样例输出

yes

源代码

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    string a;
    cin >> a;
    while(n -- )
    {
        string b;
        cin >> b;
        int flag = 0;
        for(int i = 0;i < b.size();i ++ )
        {
            if(b[i] == a[0])
            {
                int j = i + 1;
                int k = 1;
                while(b[j] == a[k])
                {
                    j ++ ;
                    k ++ ;
                }
                if(k == a.size())
                {
                    flag = 1;
                    break;
                }
            }
        }
        if(flag == 0)printf("no\n");
        else printf("yes\n");
    } 
    return 0;
}

核酸检测小能手

题目描述

假使你在提瓦特大陆工作，为一名核酸检测人员，由于提瓦特大陆的蒙德缺少核酸检测人员(芭芭拉只会扯着嗓子嗷嗷)，现给你一批核酸检测后的试管，已知每个试管之中有着n个咽拭子，现要求你检测试管中有多少核酸阳性结果，若是咽拭子的编码之中含有新冠编码则确诊为阳性，已知咽拭子序列的头尾可以相接构成一个环

输入

输出

n次的检测结果(每次结果换行表示)

样例输入

3
as
asdlkbasd
sadca
fdjvdnd

样例输出

阳性
阳性
阴性

源代码

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    string str;
    cin >> str;
    while(n -- )
    {
        int flag = 0;
        string s;
        cin >> s;
        s = s + s;
        for(int i = 0;i < s.size();i ++ )
        {
            if(s[i] == str[0])
            {
                int j = i + 1,k = 1;
                while(s[j] == str[k])
                {
                    j ++ ;
                    k ++ ;
                }
                if(k == str.size())
                {
                    flag = 1;
                    break;
                }
            }
        }
        if(flag == 0)printf("阴性\n");
        else if(flag == 1)printf("阳性\n");
    }
    return 0;
}

字符统计

题目描述

给定一个不包含空白符的非空字符串，请你统计字符串中各个字符出现的个数，非字母或数字字符定义为其他字符

输入

一行，包含一个字符串
字符串长度不超过200

输出

按照ASSCII顺序从小到大输出，出现的字符的个数，其他字符输出others

样例输入

123456ahjsidjoOJN**--

样例输出

1 1
2 1
3 1
4 1
5 1
6 1
J 1
N 1
O 1
a 1
d 1
h 1
i 1
j 2
o 1
s 1
others 4

源代码

#include <iostream>
using namespace std;
int a[10000] = {0};
int main()
{
    int others = 0;
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    for(int i = 0;i < s.size();i ++ )
    {
        int idx = s[i] - '0';
        if((s[i] >= '0' && s[i] <= '9')||(s[i] >= 'a' && s[i] <= 'z')||(s[i] >= 'A' && s[i] <= 'Z'))a[idx] ++ ;
        else others ++ ;
    }
    for(int i = 0;i <= 200;i ++ )
    {
        if(a[i] != 0)
        {
            char c = i + '0';
            cout << c << ' ' << a[i] << endl;
        }
    }
    if(others != 0)cout << "others" << ' ' << others;
    return 0;
}

收帐

题目描述

小V同学趁着暑假在楼下的便利店里面兼职做售货员，平时干的活也就是收收帐，因为平时大家都是用VX或者ZFB付款，所以小V同学只需要扫别人的收款码就行了。

但是今天小V同学头疼了，因为他没想到现在居然有人用现金支付，由于小V同学数学不好，而收款机给出的应收款是数字表示的，小V同学想知道这个数字怎么读，即翻译成汉语拼音。

例如应收款是2305，则需要翻译为”liangqiansanbailingwu“。

现在客人用现金支付，而小V同学如果不能收款的话就要丢掉工作了！你能帮帮他吗？

注意：翻译规则如下，如果是整百上千，例如5200,520,读作wuqianerbai，wubaiershi，中间位数连续为0则读ling，例如2305,2035，5002读作erqiansanbailingwu，erqianlingsanshiwu，wuqianlinger。

输入

第一行一个整数t表示样例数（0 <= t <= 1e3）

接下来t行每行一个整数Ti表示应收款（1 <= Ti <=5e4）

输出

输出t行字符串，表示对应应收款的汉语拼音。

样例输入

2
600
325

样例输出

liubai
sanbaiershiwu

源代码

#include <iostream>
using namespace std;
typedef long long ll;
string w[5] = {"", "shi", "bai", "qian", "wan"};
string num[10] = {"ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu"}; 
int main()
{
    int t;
    string s;
    cin>>t;
    while(t--)
    {
        cin >> s;
        int len = s.size();
        int b = 0;
        for(int i = len - 1; i >= 0; i--)
        {
            if(s[i] == '0') b++, len--;
            else break;
        }
        bool flag = false;
        for(int i = 0; i < len; i++)
        {
            if(s[i] == '0') flag = true;
            else
            {
                if(flag) cout<<num[0];
                cout<<num[s[i] - '0']<<w[len - i - 1 + b];
                flag = false;
            }
        }
        cout<<endl;
    } 
    return 0;
}

算法组

年月日问题

题目描述

给定起始日期和终止日期，请求出有多少个日期所形成的八位字符串是回文串
例如2022年10月1日转换成字符串就是20221001

输入

输入包含两行
第一行包含三个正整数，起始日期的年、月、日
第二行包含三个正整数，终止日期的年、月、日
保证日期是合法的，并且终止日期一定在起始日期后面

输出

输出一个正整数，表示起始日期到终止日期一共有多少个满足要求的日期

样例输入

2000 1 1
2022 10 10

样例输出

源代码

#include <iostream>
#include <algorithm>
using namespace std;
int a[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int b[13] = {0,31,29,31,30,31,30,31,31,30,31,30,31};
bool judge(int x)
{
    if((x % 4 == 0 && x % 100 != 0) || (x % 400 == 0))return true;
    else return false;
}
int main()
{
    int nums = 0;
    int sy,sm,sd;
    scanf("%d%d%d",&sy,&sm,&sd);
    int ey,em,ed;
    scanf("%d%d%d",&ey,&em,&ed);
    for(int i = sy;i <= ey;i ++ )
    {
        string s = to_string(i);
        reverse(s.begin(),s.end());
        int d = (s[2] - '0') * 10 + (s[3] - '0');
        int m = (s[0] - '0') * 10 + (s[1] - '0');
        if(i == sy)
        {
            if(d + m * 30 < sd + sm * 30)continue;
        }
        if(i == ey)
        {
            if(d + m * 30 > ed + em * 30)continue;
        }
        if(m >= 1 && m <= 12)
        {
            if(judge(i))
            {
                if(d >= 1 && d <= b[m])nums ++ ;
            }
            else
            {
                if(d >= 1 && d <= a[m])nums ++ ;
            }
        }
    }
    cout << nums << endl;
    return 0;
}

蒙德佳酿节

题目描述

我们把这些东西封进桶，

等啊，等啊，等着风起涌。

把佳酿的瓶口先蜡上，

南风和煦，北风猛。

佳酿味道像什么？

蒙德的名字，自由的梦。

究竟是什么发酵成佳酿？

探索的勇气，慈爱的温柔。

守护的执着一如初，

伴着千风起祝颂，

酸汁变甜，糙桶润透，

等啊，等啊，等着风起涌。

酒桶里面放了啥？

小麦的金黄，潜荟葱茏。

佳酿出桶，飘来了什么？

风铃的声音，万古的长空。

我们伴着这些美酒唱起歌，

等啊，等啊，等着风起咏。

千风带走了什么下酒？

琴弦上的故事，今夜的美梦。

蒙德佳酿节到了，风神大人是出了名的“酒鬼”，但喝酒又很挑剔，他只喜欢喝相似度接近的酒，酒的相似度接近定义为任意两杯酒的质量相差不超过k（可以等于k）。现在桌子上有n杯酒，请帮忙算出风神大人最多能够喝到多少杯酒。

输入

第一行两个正整数n,k
第二行n个正整数，a[i]表示每一杯酒的质量
1≤n≤1e6
0≤k≤1e3
1≤a[i]≤1e3

输出

输出风神大人最多能够喝多少杯酒

样例输入

5 100
109 137 267 76 392

样例输出

源代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000000 + 10;
int a[N];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    int ans = 0;
    for(int i = 1;i <= n;i ++ )scanf("%d",&a[i]);
    sort(a + 1,a + 1 + n);
    for(int i = 1,j = 1;i <= n;i ++ )
    {
        while(a[i] - a[j] > k)j ++ ;
        ans = max(ans,i - j + 1);
    }
    printf("%d",ans);
    return 0;
}

K-优字符串

题目描述

Charles 将一个字符串的优良分数定义为，在 1≤i≤N/2 的范围内，满足 Si≠SN−i+1 的 i 的数量（索引从 1 开始）。

例如，字符串 CABABC 的优良分数为 2，因为 S2≠S5 并且 S3≠S4。

Charles 给了 Ada 一个长度为 N 的由大写字母构成的字符串 S，并让她将其转换为一个优良分数为 K 的字符串。

每次操作，Ada 都可以将字符串中的任意一个字符转换为任意一个大写字母。

请你帮助 Ada 确定，将给定字符串 S 转换为优良分数为 K 的字符串，所需要的最少操作次数。

输入

第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含两个整数 N 和 K。

第二行包含一个长度为 N 的由大写字母构成的字符串 S。

输出

第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含两个整数 N 和 K。

第二行包含一个长度为 N 的由大写字母构成的字符串 S。

样例输入

2
5 1
ABCAA
4 2
ABAA

样例输出

Case #1: 0
Case #2: 1

源代码

#include <iostream>
using namespace std;
int main()
{
    int t;
    cin >> t;
    for(int T = 1;T <= t;T ++ )
    {
        int lenth,k;
        cin >> lenth >> k;
        string s;
        cin >> s;
        s = ' ' + s;
        int ans,num = 0;
        for(int i = 1;i <= lenth / 2;i ++ )
        {
            if(s[i] != s[lenth - i + 1])num ++ ;
        }
        ans = abs(k - num);
        printf("Case #%d: %d\n",T,ans);
    }
    return 0;
}

最长连续休息时间

题目描述

一天可以被分为 n 个时段。

一个工人的每日工作安排可以用一个长度为 n 的 01 序列 a1,a2,…,an 来表示。

ai 为 0 表示第 i 个时间段是工作时间，ai 为 1 表示第 i 个时间段是休息时间。

工人日复一日的严格按照这个工作安排来进行工作和休息。

请问，工人的最长连续休息时间有多长（单位：时段）？

注意，连续休息时间可能跨天。

保证工人至少在一个时间段处于工作状态。

输入

第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

输出

每组数据输出一行结果，表示最长连续休息时间。

样例输入

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

样例输出

源代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 400010;
int a[N];
int main()
{
    int t;
    scanf("%d",&t);
    while(t -- )
    {
        memset(a,0,sizeof(a));
        int n;
        scanf("%d",&n);
        for(int i = 1;i <= n;i ++ )
        {
            scanf("%d",&a[i]);
            a[i + n] = a[i];
        }
        int res = 0,num = 0;
        for(int i = 1;i <= 2 * n;i ++ )
        {
            if(a[i] == 1)num ++ ;
            else num = 0;
            res = max(res,num);
        }
        printf("%d\n",res);
    }
    return 0;
}

品种临近

题目描述

农夫约翰的 N 头奶牛排成一排，每头奶牛都用其品种 ID 进行描述。

如果两头相同品种的牛靠得太近，它们就会吵架。

具体的说，如果同一品种的两头奶牛在队列中的位置相差不超过 K，我们就称这是一对拥挤的牛。

请计算品种 ID 最大的拥挤奶牛对的品种 ID。

输入

第一行包含两个整数 N 和 K。
接下来 N 行，每行包含一个整数表示队列中一头奶牛的品种 ID。
1≤N≤50000,
1≤K<N,
品种 ID 范围 [0,1e6]。

输出

输出品种 ID 最大的拥挤奶牛对的品种 ID。
如果不存在拥挤奶牛对，则输出 −1。

样例输入

样例输出

提示

样例解释：
一对品种 ID 为 3 的奶牛以及一对品种 ID 为 4 的奶牛属于拥挤奶牛对。
所以，最大拥挤奶牛对的品种 ID 为 4。

源代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
vector<PII> A;
vector<int> ans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin >> n >> k;
    for(int i = 1;i <= n;i ++ )
    {
        int num;
        cin >> num;
        A.push_back({num,i});
    }
    sort(A.begin(),A.end());
    for(int i = 0;i < A.size();i ++ )
    {
        if(A[i].first == A[i + 1].first && i + 1 < A.size() && A[i + 1].second - A[i].second <= k)ans.push_back(A[i].first);
    }
    if(ans.size() == 0)cout << "-1";
    else cout << ans[ans.size() - 1];
    return 0;
}

懒惰的公牛

题目描述

这是一个炎热的夏日。

懒洋洋的奶牛贝茜想将自己放置在田野中的某个位置，以便可以在短距离内尽可能多地吃到美味的草。

贝茜所在的田野中共有 N 片草地，我们可以将田野视作一个一维数轴。

第 i 片草地中包含 gi 单位的青草，位置坐标为 xi。

不同草地的位置不同。

贝茜想选取田野中的某个点作为她的初始位置（可能是某片草地所在的点）。

只有一片草地与她的初始位置的距离不超过 K 时，贝茜才能吃到那片草地上的草。

如果贝茜选择最佳初始位置，请确定她可以吃到的青草最大数量。

输入

第一行包含两个整数 N 和 K。
接下来 N 行，每行描述一片草地，包含两个整数 gi 和 xi。
1≤N≤1e5
1≤gi≤10000
0≤xi≤1e6
1≤K≤2e6

输出

输出如果贝茜选择最佳初始位置，则她可以吃到的青草最大数量。

样例输入

样例输出

提示

样例解释
最佳初始位置选择为 x=4，可以吃到 x=1,x=2,x=7 处的青草。

源代码

#include <iostream>
using namespace std;
const int N = 1000000 + 10;
int a[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int L = 1,R = -1;
    int n,k;
    cin >> n >> k;
    while(n -- )
    {
        int grass,idx;
        cin >> grass >> idx;
        a[idx + 1] += grass;
        R = max(R,idx + 1);
    }
    for(int i = L;i <= R;i ++ )a[i] += a[i - 1];
    int ans = -1;
    for(int i = L;i <= R;i ++ )
    {
        int r = min(i + k,R);
        int l = max(i - k,1);
        ans = max(ans,a[r] - a[l - 1]);
    }
    cout << ans << endl;
    return 0;
}