ACM集训队周末训练20191013解题报告

只给出八道简单题的题解-by wff325000

A:C语言实验题――约瑟夫问题

题意:众人围成圈,从第一个开始每数m个活人,将他杀掉,问最后活下来的人的编号


众人排成圈,最后一个人后接第一个人。

数组surv[i]=0表示第i个人活着

只有surv[]=0才进行计数

第m个活着的人surv[]=1表示死亡

直到存活的人数为1

while(如果存活数大于1)

{

        if(如果编号i的人活着)

        {

            计数+1;

            如果为第m个人,将他杀死,surv[]=1;

            存活人数--;

        }

        下一个人;

        如果下一个人超过上限,回到第一个人;

 }


B:超缘分ACM队伍

题意:将生日两两比较,相同生日个数为3个答案+1

注意:输入除生日的月日之外所有信息无用,所以要知道怎么在输入的时候只保存我们需要的部分

提示:%d只读连续的数字,%s只读连续的字符串,%c读取一个字符


将生日储存在数组中(二位数组

用num[i]储存第i个生日的个数

将str[i][]与str[j][]进行比较,i<j

如果相同num[i]++,str[j]删除

最后遍历num,数值为2的话答案++

C++用map超级方便


C:统计最长单词

题意:取每一行包含'a'字符的最长单词

注意:单词之间可能有多个空格

难点:在于如何分割单词


除了一个个剥离字符构成单词之外

可以利用scanf中%s的特性,只截取连续的字符串

循环读入需要用到一点小技巧

可以用一个while同时进行每个单词的读入以及对EOF的判断,直到遇到单词结尾包含'.'的时候输出答案


J:A除以B

题意:大数A除整数B


用字符串读入A

1.从左至右将每个A中的字符取出转换成数字,与步骤2的结果相加

2.将步骤1得到的数据整除B的结果保留,余数乘10参与步骤1的运算

简而言之,模拟我们笔算除法的过程


K:区间和

对不起朝纲了这道题按理来说没办法做!!!

但是,这道题的数据很弱,会前缀和就可以暴力过(嘿嘿

所以这道题要求会“前缀和”,听起来很厉害但是很容易想到

题意:单点修改加区间查询


前缀和(区间查询):

用Sum[i]表示第1个数到第i个数的累加

那么查询区间[x,y]的和,我们就可以O(1)复杂度得出,Sum[y] - Sum[x-1]


那么这道题AC方法(仅限这道题

单点修改:

将修改的位置和值记录下来

通过前缀和求出区间和

然后遍历一遍储存下来的所有单点修改数据

如果修改的点在区间内,那么区间和+上修改数据



L:人见人爱A^B

题意:计算A^B的后三位


没啥好说的,循环B遍

每次循环ans = ans * A % 1000;


M:组合数

题意:计算C(n,m),谢谢某热情观众的提示这道题用到了高中二年级的排列组合知识


一般来说,组合数的求解需要用到特别的办法,因为数据庞大

但是这道题的数据很弱,只需要知道组合数怎么解的,暴力就行

不知道组合数怎么算的,百度吧!


for(int i = 0; i < n; i++)

      s=s*(m-i)/(i+1);

简单吧


N:数字回文

题意:判断给出的5位数是否为回文数


回文数:从左读或者从右读都是一样的数


作为字符串读入,将字符串逆置

判断与原串是否相等



为解题报告打分
暂时不评分

★★
★★★
★★★★
★★★★★
发表您的评论(若贴AC代码或发表禁止言论等违禁行为将被删除并扣除积分)

|返回 |   | 转到页头|
Copyright @ 2008-2024(浙ICP备2022001332号), TZOJ. All Rights Reserved.