专栏首页Tanger的思源地ACM之7.21日作业题解

ACM之7.21日作业题解

1.A简单数学题

题目描述:

现在给你一个数n 判断 n的每一位数字是否都不相同

输入

一个数字n 1<n<1000000

输出

YES

1.A简单数学题

题目描述:

现在给你一个数n 判断 n的每一位数字是否都不相同

输入

一个数字n 1<n<1000000

输出

YES

要做的程序就是判断每位数字是否都不相等

参考程序

#include<stdio.h>
#include<stdbool.h>
int main()
{
char A[10];
bool result[300]; 
scanf("%s",A);
for(int i = 0; i < 200; i++)
{
    result[i] = false;
}
for(int i = 0; A[i] != 0; i++)
{
    if(result[A[i]] == true)
    {
        printf("NO");
        return 0;
    } 
    else
    {
        result[A[i]] = true;
    }
}
printf("YES");}

题解:这里的A是用来存放各位数的一个数组因为最多只有10个不同的数字所以A[10]恰好 够用,result[300]是用来打标记的,用过的数组就改false为ture,当然你也可以用一个 变量来统计数字出现的次数,出现2次就输出“NO”,然后return 0。

2.B二进制

题目描述:

如题 将数字转化为二进制

输入

一个数字n (1<n<10^5)

输出

输出数字n的二进制表示

参考程序

#include<stdio.h>
int main(){
int num[10001],i=0,n;
scanf("%d",&n);
while(n>0){
    num[i]=n%2;
    n=n/2;
    i++;
}
while(i--)
    printf("%d",num[i]);
    return 0;
}

题解:不详细介绍了

随便给一种快速求n进制的程序(来源杭电oj):

#include<stdio.h>
void fun(int n,int r){
if(n<r){
    if(n<10) printf("%d",n);
    if(n>=10) printf("%c",55+n);
} 
else{
    fun(n/r,r);

    if(n%r<10) printf("%d",n%r);
    if(n%r>=10) printf("%c",55+n%r);
}
}
int main(){
int n,r;
while(scanf("%d%d",&n,&r)!=EOF){
    if(n<0) printf("-"),n=-n;
    fun(n,r);
    printf("\n");
}
return 0; 
}

3.C经典字符串问题

题目描述:

现在给出一个字符串 如果这个字符串是左右对称的 (经过反转后,和原来的字符串相同) 那么称其为回文串 现在给出一个字符串 你要判断这个字符串是不是回文串

输入

第一行一个数字t 代表测试组数 0<t<100 以下每两行一个测试数据 第一行一个个数字n 代表字符串长度 (1<n<1000) 第二行 n个字母 ,代表这个字符串

输出

如果此字符串是回文串 输出YES 否则输出NO

参考程序

#include<stdio.h>
#include<string.h>
int main()
{
int n,i,t,abs=1;
char str[1001];
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
scanf("%s",&str);
abs=1;
for(i=0;i<n;i++){
    if(str[i]!=str[n-i-1])
    abs=0;
}
if(abs==1)
printf("YES\n");
else
printf("NO\n");
}
}

题解:判断回文的方法自然不用多说,那么如果不让你用数组而让你用整形,怎么办? 同样给程序:

#include<stdio.h>
void huiwen(int num){
 int x=0,s=0;
if(num==0||(num>0&&num<10)) return true;
if(num<0||num%10==0) return false;
while(num>x){
    x=x*10+num%10;
    num/=10;
    if(num>=x)
        s=num;
}
if(x==s)
    return true;
else 
    return false;}
int main(){
int num;
scanf("%d",&num);
huiwen(num);
return 0;}

4.D: 排序

题目描述:

给你一个长度为n的序列,要求从小到大排序后 输出这个序列 1<n<1000

输入

第一行为n 代表数列长度

第二行有n个数,表示数列中的每个数

输出

输出排序后的数列

样例输入

10

2 5 7 8 10 1 6 11 20 35

样例输出

1 2 5 6 7 8 10 11 20 35

参考程序

#include<stdio.h>
#include<bits/stdc++.h>
#include<string.h>
using namespace std;
int main(){
int n,a[1001],i;
scanf("%d",&n);
for(i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
for(i=0;i<n;i++)
printf("%d ",a[i]);
return 0;
}

题解: 用C++写很快也很方便,如果读者以后有打比赛的冲动,建议熟练掌握C++的函数 比如sort函数的使用:

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int a[]={45,12,34,77,90,11,2,4,5,55}; 
sort(a,a+10);//sort函数第三个参数采用默认从小到大
for(int i=0;i<10;i++)
cout<<a[i]<<" ";
}  
如果想从大到小怎么办?

#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int a,int b);
main(){
  //sort函数第三个参数自己定义,实现从大到小
  int a[]={45,12,34,77,90,11,2,4,5,55};
  sort(a,a+10,cmp);
  for(int i=0;i<10;i++)
    cout<<a[i]<<" ";
}
//自定义函数
bool cmp(int a,int b){
  return a>b;
}

5.E: 改作文

题目描述:

LZH是个超差劲的学生呢。 LLF每次批改他的英语作业都会很生气 LLF批改作文是这样计算得分的 : 文章里共有n 个字母,第 i(i<=n)个字母可能大写得一分(小写0分),也可能小写得一分(大写0分) 毕竟LLF是经常喜怒无常的呢,看心情给分。 同时lzh又是个unlucky boy 英语作文每次都必得零分(运气很差呢,每次都恰好得零分) 现在你掌握了时间回溯大法,可以穿越时空,回到过去,因为LZH跟你进行了PY交易,你要帮他在LLF批改作文时得满分,所以你要趁机修改他的作文 现在给出lzh的作文 要求帮他修改到满分

输入

第一行有一个数 n 代表文章长度 (1<n<1000) 第二行 有n个字母 代表LZH的作文

输出

输出此时可以让LLF给满分的作文

样例输入

 10
 adsadaAStY

样例输出

ADSADAasTy

参考程序

#include<stdio.h>
char str[1001];
int main(){
int n,i;
scanf("%d",&n);
scanf("%s",&str);
for(i=0;i<n;i++){
if(str[i]>='a'&&str[i]<='z')
str[i]=str[i]+'A'-'a';
else if(str[i]>='A'&&str[i]<='Z')
str[i]=str[i]+'a'-'A';}
puts(str);
return 0;
}

题解:一定要注意细节,这道题就这么多

6.F: 抽签game

题目描述:

由于LZH在国庆之前偷偷把作业给AK掉了,于是LLF提议玩一个小游戏,将写有数字的N个纸片放入盒子 LZH每次可以从盒子中抽取一个纸片,并将其放回盒子中,LZH一共可以抽取四次,LLF给出一个数字M,如果LZH四次抽到的数字之和等于M,那么LZH就会平安无事,否则LLF 会给他最喜爱的大嘴巴子。但是LZH玩了几次抽签游戏,每次都获得了他最喜爱的大嘴巴子,他怀疑LLF在搞他,于是他恼羞成怒,怒把盒子打开看看里面的到底能不能抽四次的数字之和等于M, 现在给你一个盒子 要求你帮LZH检查一下盒子里面的卡片是否真的可以满足上述条件

输入

第一行有一个数n 代表卡片数量    1<n<50
第二行有一个数M,M的意义如题      1<m<10000000
第三行有n个数,代表n张卡片上面所写的数值    1<每个数字<10000000

输出

如果抽四次可以满足上述条件 输出 YES
否则输出 NO

样例输入

5
10
1 2 3 4 5

样例输出

YES

参考程序

#include <stdio.h>
int main(){
    int str[50],i,j,k,l,n,m;
    scanf("%d",&n);
    scanf("%d",&m);
    for(i=0;i<n;i++)
    scanf("%d",&str[i]);
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            for(k=0;k<n;k++){
                for(l=0;l<n;l++){
                if(str[i]+str[j]+str[k]+str[l]==m){
                    printf("YES");
                    return 0;
                }
                }
            }
        }
    }
    printf("NO");
    return 0;
}

题解:就是穷举嘛,一个个试

7.G: help庞学姐

题目描述:

庞学姐和最帅的郑学长在玩密室逃脱,经历了千辛万苦,他们终于走到了最后一关, 最后一关是一个n*m的迷宫,里面有许多障碍物,这时上帝给了他们一张地图,上面给出了障碍物和终点分布,因为郑学长身手比较敏捷,所以可以无视障碍物,直接到达终点, 但是庞学姐只是一个肥宅,他无法穿越障碍物,只能一步一步走到终点 并且他只会往 上 下 左 右 四个方向走 “ * “代表此处可通 “ ? “代表此处为障碍物 现在给你迷宫的地图,请帮助庞学姐找到最短到终点的路。 起点坐标为(1,1) 终点坐标为(n,m)迷宫:

****?
*??*?
**?*?
??**?
*****

输入

第一行为两个数 n,m 意义如上 1<n,m<50 下面n行 每行有m个字符 “ * “代表此处可通 “ ? “代表此处为障碍物 题目保证 起点和终点为 “ * “

输出

输出使庞学姐走出迷宫的最少步数 题目保证有解

样例输入

5 5
****?
*??*?
**?*?
??**?
*****

样例输出

8

参考程序

#include<stdio.h>
int n,m;
char mp[51][51];
int vis[51][51];
int dx[]={-1,1,0,0},dy[]={0,0,1,-1};
int ans=0,step=0,min=999999;
void dfs(int x,int y,int step){
    if(x<0||x>=n||y<0||y>m) return ;
    if(x==n-1&&y==m-1){ans=1;
    if(step<min) min=step;
    return ;}
    for(int i=0;i<4;i++){
        int nowx=x+dx[i];
        int nowy=y+dy[i];
        if(mp[nowx][nowy]=='*'&&vis[nowx][nowy]==0){
            vis[nowx][nowy]=1;
            dfs(nowx,nowy,step+1);
            vis[nowx][nowy]=0;
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    scanf("%s",mp[i]);
    dfs(0,0,0);
    printf("%d",min);
    return 0;
}

题解:涉及搜索请移步搜索

8.H: 一根绳上的蚂蚁

题目描述:

n只蚂蚁以每秒1cm的速度在长为L cm的绳子上爬行,当蚂蚁爬到绳子端点时就会自动掉落,由于绳子太细,两只蚂蚁相遇时,他们不能交错通过,只能各自反向爬回去。 对于每只蚂蚁,我们知道它距离绳左端的距离Xi,和它当前的头朝向,请计算所有蚂蚁经过复杂的爬行后,全部落下绳子的时刻

输入

第一行为一个整数 L 代表绳子长度 (1<L<=10^6) 第二行一个整数 n 代表蚂蚁个数 (1<n<=10^6) 以下n行 每行有 Xi 和一个字母(R或L) Xi代表蚂蚁距离左端的距离 字母代表当前的方向 (R代表头朝右,L代表头朝左)

输出

输出所有蚂蚁都掉落时的时刻

样例输入

10
3
2 R
6 L
7 L

样例输出

8

参考程序

#include<stdio.h>
int main(){
    int t,l,y,max=0,sum;
    char x;
    scanf("%d",&l);
    scanf("%d",&t);
    while(t--){
        scanf("%d %c",&y,&x);
        if(x=='R')
        sum=l-y;
        else
        sum=y;
        if(sum>max)
        max=sum;
    }
    printf("%d",max);
    return 0;
}

题解:蚂蚁相撞从计算机的视角来看待这个问题就当成一个他们擦肩而过对最终的结果毫无影响,反正我们考虑的是最晚掉下去的蚂蚁而不在乎是那只蚂蚁 最后掉下去,所以很显然的,计算那只蚂蚁离两端最远就行了

9. I: 小学数学题

题目描述:

求这个数 答案可能很大 因此输出这个数对1e9+7取余; (10^9+7) 1<N<10^5

输入

第一行一个t 代表测试组数
下面t行  每行有一个数N 意义如题  

输出

输出有t行 
每行输出一个答案

样例输入

2
2
5

样例输出

11
120

提示

取余的加法运算律(a+b)%m=(a%m+b%m)%m
取余的乘法运算律 (a*b) % m = 【(a%m) * (b%m)】 % m                

计算机每秒进行10^7次运算
int 类型可以存的最大整数为2^32-1; 
long long 类型可以存的最大整数为 2^64 -1; 

参考程序

#include<cstdio>
using namespace std;
long long now,ans,p=1e9+7;
int t,n;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        ans=0;now=1;
        for(int i=0;i<=n;i++){
            ans+=now*(n+1-i)%p;
            ans%=p;
            now=(now*2)%p;
        }
        printf("%lld\n",ans);
    }
    return 0;
} 

题解:数学内容自己把握

10.J: 超简单的A+B

题目描述:

求两个不超过200位的非负整数的和。

输入

有两行,每行是一个不超过200位的非负整数,可能有多余的前导0。

输出

一行,即相加后的结果。结果里不能有多余的前导0,即如果结果是342,那么就不能输出为0342。

样例输入

22222222222222222222
33333333333333333333

样例输出

55555555555555555555

参考程序

#include<stdio.h>
#include<string.h>
char s[10100],ss[10100];
int a[10100],b[10100];
int len;

void jia()     //自定义函数"jia"(名字low了一点(好像不是一点,但容易理解不是吗)) 
{
    int l1 = strlen(s);     //"strlen"是一个计算字符串长度的函数 
    int l2 = strlen(ss);    //将输入的两个字符串的长度赋值给l1,l2
    if (l1 > l2) 
        len = l1;      //将len赋值为l1,l2中大的那个 
    else
        len = l2;
//      for (int i = 0 ; i <= len ; i++)  //清零(这里for循环和下面三句memset都为将字符串清零 ) 
//          a[i] = b[i] = c[i] = 0;
    memset(a,0,sizeof(a));    //清零too(只能清零,不能干别的) 
    memset(b,0,sizeof(b));    //这是清零函数(字符串) 
                                        //两个for循环是将输入的两个字符串倒过来
    for (int i = l1 - 1 ; i >= 0 ; i--)    //再将字符串里的字符转换为数字赋值给a,b整型数组 
        a[l1 - i - 1] = s[i] - '0';        //但为什么大数要用字符串存呢?
    for (int i = l2 - 1 ; i >= 0 ; i--)    //因为大数太大,用任何整型变量都存不下 
        b[l2 - i - 1] = ss[i] - '0';       //为什么要把字符串倒过来赋值呢? 
                                    //因为大数与大数是一位一位运算的,还要涉及进位等 
    for (int i = 0 ; i < len ; i++)
    {
        a[i] = a[i] + b[i];    //运算 
        a[i+1]+= a[i] / 10;    //如有进位,在后一位上加上 
        a[i] = a[i] % 10;      //原来那一位减掉进位了的 
    }
    if (a[len] != 0) len++;    //如果有进位就多显示一位(这句话很重要) 

    while (a[len - 1] == 0 && len>1) len--;      //我叫它while去零法
        
    for (int i = len - 1 ;i >= 0 ;i--)  //输出结果 
        printf("%d",a[i]);
}    

int main()
{
scanf("%s%s",s,ss);
jia();     
    return 0;
}

题解:高精度计算基本内容请掌握

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • ACM之7-25日作业题解

    一个如下的 6×6 的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。

    Tanger
  • ACM之7-23日作业题解

    给你一个数组a,注意下标从0开始 如果数组中的每个奇数下标为奇数且数组中的每个偶数的下标为偶数则叫好数组否则就是不好数组 比如...

    Tanger
  • ACM之7-22日作业题解

    一天,天上掉下来了一个可爱的小妹妹,小妹妹天天缠着你给她讲故事。并且让你在N天内给她讲K(K ≤ N)个不同小故事。你把你知道的所有K个故事从1到K进行编...

    Tanger
  • 腾讯犀牛鸟精英人才培养计划邀你与大师面对面

    ? 5月17日-19日,ACM中国图灵大会将在成都举行,多位图灵奖获得者、学界及工业界大咖将亲临现场分享他们对前沿技术研究及人工智能的未来发展趋势的思考。作为...

    鹅老师
  • OpenAI击败Dota 2世界冠军后记:如何训练你的AI

    本周末OpenAI Five与世界冠军Dota 2团队OG的总决赛中,它2比0大败对手。

    大数据文摘
  • 腾讯犀牛鸟精英人才培养计划邀你与大师面对面

    ? 5月17日-19日,ACM中国图灵大会将在成都举行,多位图灵奖获得者、学界及工业界大咖将亲临现场分享他们对前沿技术研究及人工智能的未来发展趋势的思考。作为...

    腾讯高校合作
  • 北大主场夺金ACM-ICPC全球总决赛,总教练罗国杰分享背后“秘笈”

    昨天(4月19日)下午,第42届ACM-ICPC国际大学生程序设计竞赛全球总决赛,在北京大学邱德拔体育馆举行,这也是2005年上海、2010年哈尔滨之后,中国第...

    量子位
  • 算法八股,简历项目,在校小白如何冲击大厂?快上车,我有!

    上海 985 计算机专业大三在读,有 acm 经验,无牌子,有一些算法竞赛和数模小奖,写在简历上的都是课程项目。

    ACM算法日常
  • 公司高层都在为CEO职位争得头破血流,而马斯克竟把职位改成...

    马斯克,很多人心中的偶像,随着比特币价格的一路高歌猛进,似乎马斯克的火箭事业又多了不少资金基础。

    程序猿DD
  • AI 人才遭疯抢,Google 为 22 岁印度毕业生开出 1000w+ 年薪

    他就是仅有 22 岁的 Aditya Paliwal。2013 年到 2018 年,Aditya Paliwal 参加了为期五年的计算机综合 M.Tech 双学...

    IT派
  • 学妹问,学网站开发还是打 ACM?

    大家好,我是鱼皮,前几天看到一位大一计科同学的问题:我想学做 Web 项目,又想学算法搞 ACM,如何取舍呢 ?

    程序员鱼皮
  • 动态 | 仅开放一天,已有 16 支队伍成功击败 OpenAI Five

    AI 科技评论按:虽然新版 OpenAI 连续两次击败 TI8 冠军 OG,但在今天 OpenAI 向公众开放仅一天后,便有 16 支队伍成功击败新版 Open...

    AI科技评论
  • 【回顾】飓风(SIGGRAPH ASIA 2014)来袭,登陆深圳!

      由国际计算机学会(ACM - Association for Computing Machinery)举办的SIGGRAPH是世界上影响最广、规模最大,同时...

    腾讯高校合作
  • 飓风(SIGGRAPH ASIA 2014)来袭,登陆深圳!

      由国际计算机学会(ACM - Association for Computing Machinery)举办的SIGGRAPH是世界上影响最广、规模最大,同时...

    腾讯高校合作
  • 第一个世界量子日,量子计算大牛Scott Aaronson获颁ACM计算奖

    刚刚,理论计算机科学家、UT Austin 教授、量子计算先驱 Scott Aaronson 因其「对量子计算的开创性贡献」被授予 2020 年度 ACM 计算...

    机器之心
  • 这位AI毕业生,Google得不到他,就拿百万抢他!

    他就是仅有 22 岁的 Aditya Paliwal。2013 年到 2018 年,Aditya Paliwal 参加了为期五年的计算机综合 M.Tech 双学...

    用户1737318
  • 90后清华女校友范楚楚获ACM 2020唯一博士论文奖!出任MIT助理教授后再摘桂冠

    近日,ACM公布了2020年博士论文奖,清华90后女学霸范楚楚凭借着题为「安全自主性的形式方法:数据驱动的验证、综合和应用」的论文荣获该奖。

    新智元
  • 2019年ACM Fellow出炉,陈熙霖、陶大程、周礼栋、谢源、李向阳等7位华人学者入选

    AI 科技评论消息,纽约时间12月11日,美国计算机学会(ACM)宣布了 2019 年新当选 ACM Fellow 名单,共有 58 位科学家当选,其中包括 7...

    AI科技评论
  • 2017 ACM Fellow名单出炉:杨强、马毅、芮勇等多位华人入选

    机器之心

扫码关注云+社区

领取腾讯云代金券