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

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

目录

语法组

我要拿最多的Money(命题人:张毅)

平方矩阵I (命题人:朱奕锦)

Mocha数 (命题人:陈宇航)

格雷码 (命题人:魏佳琦)

啊哈哈 (命题人:邱键烁)

呆在寝室有糖吃(命题人:卫佳欣)

算法组

判断奇偶 

前缀和(模板) 

差分(模板) 

HF拿lys的辣条 

子矩阵的和 

这是什么招新 

来,骗 


语法组

我要拿最多的Money(命题人:张毅)

题目描述

某天,小朱同学在游戏里潜入了小张同学的家园,并无情掠夺了小张同学的金币,小张同学有个地图标记了自己所有箱子里的金币个数
可恶的小朱同学留下了一张纸条:我偷走了你最多金币的箱子,现在小张同学给了你他的地图和所有箱子里的金币个数,请你快速找出
小朱同学偷走的箱子的金币个数和坐标;

输入

第一行给出n,m代表箱子的行数和列数0<=n,m<=1000;
接下来n行,每行m个数,代表这个位置的金币个数;

输出

输出一行,表示被偷走的箱子的金币数量
第二行给出箱子位置(行小优先,行相同列小优先)

样例输入

2 2
4 5
3 3

样例输出

5
1 2

源代码 

简单的遍历二维整型数组,记录最大值,输出最大值和其第一次出现的位置即可 

#include <stdio.h>
int a[1010][1010];
int n,m;
int max(int x,int y)
{
    if(x > y)return x;
    else return y;
}
int main()
{
    scanf("%d%d",&n,&m);
    int ans = 0;
    for(int i = 1;i <= n;i ++ )
    {
        for(int j = 1;j <= m;j ++ )
        {
            scanf("%d",&a[i][j]);
            ans = max(ans,a[i][j]);
        }
    }
    for(int i = 1;i <= n;i ++ )
    {
        for(int j = 1;j <= m;j ++ )
        {
            if(a[i][j] == ans)
            {
                printf("%d\n%d %d",a[i][j],i,j);
                return 0;
            }
        }
    }
    return 0;
}

平方矩阵I (命题人:朱奕锦)

 题目描述

一个整数 N。

输入

对于输入整数 N,输出一个满足要求的 N 阶二维数组。
数组占 N 行,每行包含 N 个用空格隔开的整数。
数组输出完毕后,输出一个空行。

输出

0≤N≤100

样例输入

4

样例输出 

1 1 1 1
1 2 2 1
1 2 2 1
1 1 1 1

源代码 

简单的打印矩阵即可 

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1100;
int a[N][N];
int main()
{
    int n;
    cin >> n;
    for(int i = 1;i <= n;i ++ )
    {
        for(int j = 1;j <= n;j ++ )
        {
            a[i][j] = min(i,min(n - i + 1,min(j,n - j + 1)));
            cout << a[i][j] << ' ';
        }
        cout << endl;
    }
    return 0;
}

Mocha数 (命题人:陈宇航)

题目描述

旭丘幼儿园的小班开设了一门教授数论的课程。Mocha在研究数论的过程中,发现了一种奇妙的数 Mocha数。Mocha数是一个由几个互不相同的数字构成且不含前导零的正整数。

为了方便研究,Mocha想知道是否存在一个包含n个数位的 Mocha数,如果存在,其中最小的 Mocha数是多少。

输入

一个整数 n ( 1≤ n≤20 ), 代表询问的位数。 

输出

如果存在包含 n 个数位的 Mocha 数, 输出最小的 n 位 Mocha数,否则输出 -1 。  

样例输入

样例输出 

源代码

改编自2022河南省CCPC中的题目 

#include <stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
    if(n == 1)printf("1");
    else if(n >= 2)
    {
        int idx = 1;
        for(int i = 1;i <= n;i ++ )
        {
            if(i == 2)
            {
                printf("0");
                continue;
            }
            printf("%d",idx);
            idx ++ ;
        }
    }
    return 0;
} 

格雷码 (命题人:魏佳琦)

题目描述

小魏同学前些天“很开心”地学习了数电课中卡诺图中所用的循环码,即格雷码。这可给小魏同学恶心坏了,百思不得其解,写作业的时候抓破了头皮,连发际线都上升了,你能帮小魏同学写一写题吗?

典型的二进制格雷码(Binary Gray Code)简称格雷码,因1953年公开的弗兰克·格雷(Frank Gray,1887/09/13-1969/05/23)专利“Pulse Code Communication”而得名,当初是为了通信,现在则常用于模拟-数字转换和位置-数字转换中。

而在数字电路中,格雷码每次的变换只会有一个二进制位的跳变,极大地减少了亚稳态的产生,保证电路的稳定性,受到了广泛的应用。

这意味着任两个相邻数字的格雷码只会有一个位的值不同,且n位最大格雷码与最小格雷码之间也仅有一位不同,例如7位格雷码中,最大值应该是1000000, 最小值是0000000。
现在给出一个unsigned int型整数, 求其对应的格雷码。
 

输入

第一行一个整数T(1 <= T <= 10)

接下来T行每行有一个整数Ni(Ni是unsigned int类型)

输出

输出T行,每行只有一串32位的二进制格雷码,对应Ni的格雷码

样例输入

1
7

样例输出 

0000000000000100

源代码 

 在这里我选择先讲正整数n转换为二进制的形式,若是不满足十六位,则在其二进制前补前导零直至十六位,而后对于正整数n的二进制形式进行格雷码转换,提供二进制转换格雷码的思路:设二进制串为a,格雷码串为b,那么a[0] = b[0],b[i] = a[i] ^ a[i + 1],注意此处的a[i]、a[i + 1]为数字,也就是说我们要字符转换为数字进行二者的逻辑异或运算,而后再次转换为字符加回去

蓝色箭头表示直接相等,绿色箭头表示箭头起点的二者进行逻辑异或运算 

#include <iostream>
#include <algorithm>
using namespace std;
string tobin(int n)
{
    string ans;
    while(n > 0)
    {
        int num = n % 2;
        ans += (num + '0');
        n /= 2;
    }
    while(ans.size() != 16)ans += '0';
    reverse(ans.begin(),ans.end());
    return ans;
}
string toGra(string s)
{
    string ans;
    ans = ans + s[0];
    for(int i = 0;i < s.size() - 1;i ++ )
    {
        int j = i + 1;
        char c = char(((s[i] - '0') ^ (s[j] - '0')) + '0');
        ans += c;
    }
    return ans;
}
int main()
{
    int t;
    cin >> t;
    while(t -- )
    {
        int n;
        cin >> n;
        string t = tobin(n);
        string ans = toGra(t);
        cout << ans << endl;
    }
}

啊哈哈 (命题人:邱键烁)

题目描述

“233”有时会演变为2333或者更多3跟在后边表示自己笑得很猖狂~多个3还可表示笑声持久。
已知2可替换为啊,3可替换为哈。
既23333=啊哈哈哈哈。
现在请你输入长度为n(n>=3)的233,并输出对应长度的啊哈哈。

输入

一个正整数n

输出

转换后的形式

样例输入 

233

样例输出 

啊哈哈

源代码 

简单转换 

#include <stdio.h>
char a[1000];
int main()
{
    scanf("%s",a);
    for(int i = 0;a[i];i ++ )
    {
        if(a[i] == '2')printf("啊");
        else if(a[i] == '3')printf("哈"); 
    }
    return 0;
} 

呆在寝室有糖吃(命题人:卫佳欣)

题目描述

有一个神秘的寝室叫105寝室,这个寝室住着6个美女。这个寝室的寝室长很喜欢对其他5个室友进行投喂。一天,寝室长买了n(1<=n<=50)袋糖果(每个袋子上都有编号,编号为1~n),每个袋子中有m(1<=m<=1000)个糖,这个寝室的人每次拿出并吃掉1个糖。她们希望每个袋子被吃掉的糖数量一致,所以,她们从1号袋子吃到n号袋子,然后再从1号袋子吃到n号袋子,如此循环直到有袋子空了,(若这个袋子编号不是n)她们会继续吃直到其他袋子少的糖数与这个袋子一样。然后她们会把所有糖果还给寝室长,那么最后寝室长拿到的每个袋子中的糖分别有多少个。

输入

第一行输入n表示有n袋糖,1<=n<=50。之后一行输入n个数,分别为编号从1~n的袋子里的糖的数量

输出

输出一行,共n个数,表示最后剩余的每袋糖的数量

样例输入 

3
2 3 4

样例输出 

0 1 2

源代码 

找到最小值,数组中所有元素减去最小值输出即可 

#include <stdio.h>
int a[1010];
int min(int x,int y)
{
    if(x < y)return x;
    else return y;
}
int main()
{
    int n;
    scanf("%d",&n);
    int minnum = 666666;
    for(int i = 1;i <= n;i ++ )
    {
        scanf("%d",&a[i]);
        minnum = min(minnum,a[i]);
    }
    for(int i = 1;i <= n;i ++ )
    {
        a[i] = a[i] - minnum;
        printf("%d ",a[i]);
    }
    return 0;
} 

算法组

判断奇偶 

题目描述

给定一个 7 位十六进制数,该数的首位数字为字母 A,其它位数字均为 0∼9。

请你判断其末位数字能否被 2 整除。

输入

一个7位十六进制数

输出

如果末位数字能被2整除,输出YES,否则输出NO

样例输入 

A123456

样例输出 

YES

源代码 

简单的十六进制转化为十进制,而后对十进制数进行判断奇偶即可 

#include <iostream>
using namespace std;
int main()
{
    string s;
    cin >> s;
    int w = 1,ans = 0;
    for(int i = s.size() - 1;i >= 0;i -- )
    {
        ans = ans + (s[i] - '0') * w;
        w = w * 16;
    }
    if(ans & 1)cout << "NO" << endl;
    else cout << "YES" << endl;
    return 0;
}

前缀和(模板) 

题目描述

给定一个长度n的整数序列,然后进行m次询问,对于每次询问给定一个区间[l,r],请求出每次询问的区间中所有整数的和

输入

第一行两个正整数n,m
第二行n个整数
接下来的m行,每行两个数l,r表示询问的区间范围
1≤n≤3e5
1≤m≤1e5

输出

对于每次询问,输出区间和

样例输入 

6 3
1 2 3 4 5 6
1 1
1 5
2 6

样例输出 

1
15
20

源代码 

#include <iostream>
using namespace std;
const int N = 1000000 + 10;
int a[N],s[N];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++ )
    {
        scanf("%d",&a[i]);
        s[i] = s[i - 1] + a[i];
    }
    while(m -- )
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",s[r] - s[l - 1]);
    }
    return 0;
}

差分(模板) 

题目描述

给定一个长度为n的整数序列,对它进行m次操作,每次选择一个区间[l,r],将区间中的每一个数增加x,求经过m次操作之后的整数序列

输入

第一行两个正整数n,m
第二行n个整数
接下来的m行,每行三个整数l,r,x,如题所示
1≤n≤3e5
1≤m≤1e5
1≤x≤1e3

输出

一行n个整数

样例输入 

6 3
1 2 3 4 5 6
1 6 1
2 3 -1
3 3 6

样例输出 

2 2 9 5 6 7 

源代码 

#include <iostream>
using namespace std;
const int N = 1000000 + 10;
int a[N],b[N];
void insert(int l,int r,int c)
{
    b[l] += c;
    b[r + 1] -= c;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++ )
    {
        scanf("%d",&a[i]);
        insert(i,i,a[i]);
    }
    while(m -- )
    {
        int l,r,c;
        scanf("%d%d%d",&l,&r,&c);
        insert(l,r,c);
    }
    for(int i = 1;i <= n;i ++ )
    {
        b[i] += b[i - 1];
        printf("%d ",b[i]);
    }
    return 0;
}

HF拿lys的辣条 

题目描述

lys又在努力的学习中……
有一天lys在努力的学习当中,HF突然想吃辣条,便去找万能的lys大佬。lys大佬说:“我家后花园有一片地,可以长出非常有名的卫龙辣条。”我很是震惊,由于lys沉迷于学习,在拿辣条时给我规定了我只能拿指定区域的辣条。整片辣条地为长度为L、宽度为W的矩形,指定的长,宽为a,b。HF想知道自己最多能拿到多少辣条!!!
 

输入

第1行有2个整数,长度L和宽度W。

第2行至第L+1行,每行有W个整数,分别表示对应的单位面积上的辣条数量A(0≤A<10)。

第L+2行有2个整数,分别是指定的区域大小的长度a和宽度b。

1<=L,W,a,b<=2000

a<=L,b<=W
 

输出

输出一个整数,表示在lys指定大小的区域内,HF最多能拿到多少辣条。

样例输入 

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

样例输出 

38

源代码 

数据量过大,为了节省程序运算时间,仅仅开一个二维数组并对其进行自身前缀和运算,而后进行答案查找,否则时间超限

#include <iostream>
using namespace std;
const int N = 2000 + 10;
typedef long long ll;
ll s[N][N];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++ )
    {
        for(int j = 1;j <= m;j ++ )
        {
            scanf("%lld",&s[i][j]);
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + s[i][j];
        }
    }
    int a,b;
    scanf("%d%d",&a,&b);
    ll ans = 0;
    for(int x1 = 1;x1 <= n;x1 ++ )
    {
        for(int y1 = 1;y1 <= m;y1 ++ )
        {
            int x2 = x1 + a - 1;
            int y2 = y1 + b - 1;
            if(x2 <= n && y2 <= m)ans = max(ans,s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);
        }
    }
    printf("%lld\n",ans);
    return 0;
}

子矩阵的和 

题目描述

给定一个 n 行 m 列的二维数组 num,有 q 次询问,对于每次询问,给定两个坐标 P1(x1, y1),P2(x2, y2),求以 P1 为左上角,P2 为右下加的子矩阵的元素之和。

输入

第一行,三个整数 n,m,q

接下来 n 行 m 列,输入 num[i]

接下来 q 行,每行四个整数 x1, y1, x2, y2

输出

共 q 行,每行输出一个整数

样例输入 

3 3 2
1 2 3
1 2 3
1 2 3
1 1 2 2
2 2 3 3

样例输出 

6
10

源代码 

#include <iostream>
using namespace std;
const int N = 1100;
int a[N][N],s[N][N];
int main()
{
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i = 1;i <= n;i ++ )
    {
        for(int j = 1;j <= m;j ++ )
        {
            scanf("%d",&a[i][j]);
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }
    while(q -- )
    {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        printf("%d\n",s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
    }
    return 0;
}

这是什么招新 

题目描述

alexya是一位大一新生并且非常喜欢二次元,在学校的某一天晚自习上,他看到一群女装大佬走进了教室,这让他非常兴奋,但经过大佬们解释他才得知,原来是学校的ACM团队又双
叒来招新了,虽然初来乍到的alexya不知了解ACM是什么东西(他觉得可能是某种cosplay俱乐部),但是一位学长的cos深受alexya的喜爱,为了能再次见到这位学长,alexya决定加入ACM
团队,但是ACM招新有一个要求,就是会不定期的检查你在学校oj上前一周的做题情况,alexya非常不解为什么一个cosplay俱乐部会要求新生做编程,况且自己在这方面是蒟蒻一枚但
是为了学长,alexya决定从第二天开始拼命刷题,恰巧,因为ACM也是从招新的第二天开始记录,并且明确表示了会在一周后的某一天对前一周的做题情况进行统计,所以alexya想知道自己
从第x天开始计算前一周的刷题数量,你能帮助他吗?

输入

第一行两个整数,表示刷题天数n和询问次数t
第二行n个整数,第i个整数表示第i天的刷题数ai
第n+2~n+t+1行一个整数x,表示XX询问的第x天
7<n,t<=1e5
0<ai<100

输出

输出t行一个整数表示每次询问时前一周的刷题数量

样例输入 

10  2
1 2 3 4 5 6 7 8 9 10
8 
9

样例输出 

28
35

源代码 

#include <iostream>
using namespace std;
const int N = 1000000 + 10;
int a[N],s[N];
int main()
{
    int n,t;
    scanf("%d%d",&n,&t);
    for(int i = 1;i <= n;i ++ )
    {
        scanf("%d",&a[i]);
        s[i] = s[i - 1] + a[i];
    }
    while(t -- )
    {
        int num;
        scanf("%d",&num);
        printf("%d\n",s[num - 1] - s[num - 1 - 7]);
    }
    return 0;
}

来,骗 

题目描述

众所周知,狮均国内吼叫总值(Real GDS per lion)是衡量一个狮子国狮子健康程度的重要指标。
其计算方法为:选取若干个狮子,将每个狮子吼叫的次数相加即为总值。
叶子是狮子国健康委员会的会长,有人举报小林汇报的狮均国内吼叫总值的数据有误,所以他想请你帮忙计算。
具体来说,你会知道编号为 1 到 n 的 n 只狮子吼叫的次数 ai。
叶子会提出 q 个问题。对于每个问题他会给出 l 和 r。
他想知道编号在 l 和 r 之间的狮子的狮均国内吼叫总值。

输入

第一行一个整数 n,代表狮子的数量。
第二行 n 个整数 ai,代表编号为 i 的狮子的吼叫次数。
第三行一个整数 q,代表叶子的问题数。
第四到第 3+q 行,每行两个整数 l,r。
50% 的数据 q=1;
100% 的数据: 1≤n≤106,1≤ai≤103,1≤q≤105,1≤l≤r≤n。

输出

q 行整数,代表计算出来的狮均国内吼叫总值。

样例输入 

5
4 1 2 3 5
5
1 1
1 4
2 3
4 5
1 5

样例输出 

4
10
3
8
15

 源代码

#include <iostream>
using namespace std;
const int N = 1000000 + 10;
int a[N],s[N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++ )
    {
        scanf("%d",&a[i]);
        s[i] = s[i - 1] + a[i];
    }
    int q;
    scanf("%d",&q);
    while(q -- )
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",s[r] - s[l - 1]);
    }
    return 0;
}

相关文章:

  • SpringMVC之请求建立和响应流程
  • SpringBoot如何打包项目?
  • 方法的覆写【重写】
  • 九月的问题异常归纳(2022.9)
  • 这些环保相关的标准和规范自2022年10月起实施
  • 二叉排序树(BST)删除结点算法详解之C语言版
  • 永劫无间游戏玩法设计梳理
  • matlab遗传算法优化带电机分数阶四分之一车辆模型参数
  • 【GNN报告】GNN可解释性 基于几何与拓扑特性的图学习
  • 力扣记录:Hot100(9)——337-448
  • android studio 制作app欢迎界面-两种方法(功能)(备忘)
  • Portapack应用开发教程(十八)NavTex接收 B
  • 网课题库后台-公众号搜题查题
  • 第九天:RabbitMQ(安装)
  • 手机运行慢怎么办
  • 【Redis 源码学习笔记】Reactor模型 事件驱动框架
  • JS面向对象编程之类(1)
  • Kubernetes简介及基本组件
  • Spring(一)- 工厂基础
  • 公众号网课题库-题库接口平台