数信学院第五届新生程序设计竞赛暨校ACM队员选拔赛解题报告

数信学院第五届新生程序设计竞赛--解题报告-by shfs

 题目很庞大,第一段可以得到的信息就是“3个人”。重点句:“现在的问题是已知有n个特工,密钥总量为k(编号为0到k-1),以及每个特工所带的m个密钥,求是否每3个特工的密钥都可以解密文件。”看到这句就知道要干什么了,(换句话说就是有n个人,每个人有m块橡皮,问你是否任意3个人就可以有k块不同的橡皮)。
处理方法,用3个for的嵌套,任选3个人,然后写一个判断这3个人是否有0到k-1的密钥(可以用数组标记解决),然后如果任意3个都可以,那么就输出YES,否则输出NO
 
题意很明显,就是找第K对孪生素数对。
有两种方法:
一.先用筛选法得到素数,然后就直接把1到10000对孪生素数对都求出来保存在数组里,然后对于每组输入直接输出(这个方法叫打表),这个方法显然不可能在6分钟内打出来,毕竟筛选法求素数不是那么熟,那么就有了方法2
二.直接从i=3开始找,判断i和i+2是否同时为素数(写一个判断素数的函数,最基础的那个就是判断到根号a),找到一个保存一个,直到满10000个,还是对于每组输入直接输出。
如果不打表,会超时,不管用什么方法,因为测试的输入数据可能有好多好多个10000或者9999这样的大数,打表是应对这种情况的最好方法

这道题目告诉我们,思维很重要,想通了就是a+b难度的题目

分析下5的时候的情况: 

5号鱼:因为没有比他大的鱼,所以他会选择吃掉4号鱼。

4号鱼:因为5号要吃他,所以根据规定,4号为了保命,不会去吃3号鱼。

3号鱼:因为4号不会吃他,所以选择吃掉2号鱼

2号鱼:3要吃他,为了不死,自然不吃1号鱼

结果1号鱼不会被吃掉。

题目的英语量吓到一片。
题目意思,把一段字符加密,让你输出密文
或者给你密文,让你输出原码
或者给你原码和密文,问你加密的n
加密的规则,其实很简单,看那张图就知道了,很多时候这样的图是很重要的,不然出题者也不会煞费苦心,弄这样一张图(目测是自己做的)。
图中n=3,分成了2组,假设原码是123456的话,那么经n=3处理的密文是142536,可以很清楚的发现,先从1开始放进新的数组,然后每次加n再放进去,然后从2开始,每次加n放进去,然后从3开始每次加n放进。这样就是一个二重循环
for(i=1;i<=n;i++)
for(j=i;j<=len;j+=n)//len 是长度
{直接放进去就好了,数组里面}
解密其实是一样的,也是2个for,赋值的次序换了下而已
 
然后就是给你原码和密文,求n的问题了,题目说了n是2到9,那么我们可以直接去试,把原码先按2去加密,看得到的密文和输入的密文是否相同,相同就跳出循环,不相同再试3直到9。一定要从2开始,因为题目说如果有多种情况就输出小的那一种。

 其实分析下题目可以知道,如果所有数的和是奇数,那么肯定是NO。

如果最大的数比其他所有的数的和大,就是max>sum-max,那么肯定也是NO。

减的想法是这样的,每次找到2个最大的数,都减去1,就是让所有的数尽量平均,然后就肯定能减到0

题目本身有个小漏洞,就是没有说有空格,导致用%s输入的同学,错了一遍,深表歉意。
非法内存访问的同学,可以看下在字符串里面已经空的时候在进行#操作,是否到了-1的下标

 题目加粗的部分,不知道大家有没有看,意思是区间可能重合。

所以自然就会想到大家应该都做过的   校门外的树 用数组模拟标记法可解

模拟题,左右转的问题
解决方法:定义一个 dir[4][2]={1,0, 0,1, 0,-1, 0,-1}
然后定义一个k标记方向,
开始的时候是0,左转就k++,加到4变成0.
右转k--,减到-1,变成3.
前进的时候直接
x+=dir[k][0];
y+=dir[k][1];
每次都判断下有没有出地图,出了直接结束,走完输出x,y 就可以了
 
 
卡诺图,据说不难,但是很烦,详询zhoukeke,我没写过
已经简化到最简了  
有以下情况
1个1 找到 就直接可以输出了
2个1 2个可能是左右相邻 或者上下相邻
4个1 正方形或者 一行
8个1 2行或者2列
16个1 直接就输出 1 
 
数据很弱,我那个过的代码,输入75,输出oh,no.,明显不应该是5么?
 
对于一行输入,求出长度,定义一个k=0,碰到加号+1,碰到减号-1,然后没行对x的处理是 x+=k/2
然后输出x即可
题目意思:有很多进程,他们分别有唤醒的时间,图中的数据,A 50ms  B 60ms C 65ms D65ms
那么就是50ms后唤醒A进程,然后过10ms后唤醒B进程,再过5ms唤醒C进程,再过0ms唤醒D进程(C进程先唤醒的原因是C的字典序比D小)
然后就很清楚了,定义一个结构体
struct Node
{
char name[10];//保存名字
int t;//保存需要唤醒的时间
int nt;//保存与前一个的时间差
}
先要分析个数有多少个,是n*x 也就是最多10000个,然后就对得到的结构体数组进行排序,排序后第一个默认就是第一个的t,然后第二个就是第二个的t减去第一个的t,保存到nt
接下来是输出的问题,题目描述中说没个名字,时间输出都要占5个字符位,并且左对齐
那么我们可以用printf("%-5s",s);和printf("%-5d",a);这样的语句输出,(直接把题目的样例输出复制来,你会发现末尾是没有空格的,这是题目的一个小问题吧)
然后就是换行的问题 我们可以这样处理,对于输入的T
while(T--)
{
其它输出
 
if(T!=0) printf("\n");
}
这样就可以比较好的处理空行问题了。
还有最后一个问题,那就是输入以后得到的进程数为0,
那么就在输入完成后,也就是排序前就直接
if(个数为零)
{
if(T!=0) printf("\n");
continue;
}
这样就不会有格式问题了。

最后希望比赛成绩好的不要骄傲,继续努力。

比赛成绩不佳的,也不要气馁,后面翻身的机会多得是呢。

看了留名,哈。

by shfs


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

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

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