2018年台州学院“云豆杯”第十一届大学生程序设计竞赛解题报告

2018年台州学院“云豆杯”第十一届大学生程序设计竞赛解题报告-by zhouzexi

A:学习使人进步

连续的11年有

 1893-1904年有4016天

 2001-2012年有4017天

 2000-2011年有4018天

B:学习之博弈

大于等于3的都是zzx win,没有平局

(注:此题有可能我题目的步数没有描述清楚,应该是zzx走[n*n/2]步后,即棋盘差不多下满为止)

C:学习之水题变形

先所有数对3取余判断,判断0的个数大于一半都是不可能的

然后讨论0的个数

0的个数为0时

先考虑竖的如果1的个数或者2的个数为奇数是必定存在1 2匹配,所以是不可以的

考虑横的如果1的个数加上2的个数乘以2能被6整除,则存在一行可以被3整除

0的个数为1时,这时候竖着的无论多出哪一个都可以和0匹配导致不能被3整除

因为存在0了,所以考虑当n等于1时,就是不可以的(下面一条包括了这一条,这行删去)

考虑横的如果1的个数加上2的个数乘以2能被3整除,则不存在行被3整除,所以是可以的

否则都是不可以

如果0的个数大于1

这时候竖着的无论多出哪一个都可以和0匹配导致不能被3整除。

这时候横着的无论多出哪一个都于有0的那一行上下对换导致不能被3整除。

(注1:2*n次足够把想要的数字放到自己想要的位置了)。

(注2:这题是去年南宁区域赛铜牌题,因我的过错导致题目看漏了一个词语而来,原题连接:J. Rearrangement,欢迎大家尝试)。

D:学习之MAP OR NOT MAP

模拟路径打印地图,然后bfs遍历输出最短路劲(毒瘤,虽然数据一部分是我弄的,逃)。

E:学习之数论

先进行因式分解,采取欧拉函数分解(注意:素数筛选),然后

方法一.二分枚举满足题目要求的数。

方法二.枚举素因子,寻找满足题目要求的数字。

方法三.贪心选取,由于阶乘是1乘到n,所以这个数大概率是最大素因子的倍数。

F:学习之取得小姐姐芳心

dp模板题,具体参考我们平台4702题解

G:学习之威尔伯特·麦基奇学习策略

根据题意模拟,比赛的时候图片有误,我们验题的时候没有注意,在此表示歉意。

(注:这题验题的时候数据水了,应该是可能存在相同的字符串需要去重的,后来BobHuang原来加上了这组数据,我还以为没有加。此句忽略)。

H:学习之我要直线

5个点以下特判所以情况(注:出题人BobHuang说只需要4个点就行,我一直没有想明白)

选取5个点,暴力枚举,一直找到3点共线为止,则这作为第一条直线

然后剩余的所有点,在判断是否在一条直线上,是否平行于第一条直线即可。

(注:此题为Codeforces Round #431 (Div. 2)B 改编 )

I:学习之二叉树

根据题解计算价值,暴力模拟肯定超时,找一下规律可发现,二叉树的价值即为该节点的键值乘以该节点的深度之和,采取深搜和广搜计算深度均可,然后重新创建的二叉树要价值最大,根据贪心思想即为最大的数字深度最大,所以sort一下键值计算即可。

J:学习之签到(2)

暴力模拟(祝贺大家入坑,今年模拟做的人好多,去年新生赛都没有人做)

K:学习之字母接龙

根据题意反向构图,然后

方法一、然后在以死循环串为起点进行广度优选遍历,找到最后遍历的字符串(相同深度主要字典序最小)输出即为最远的(感谢wangyifan的题解)

方法二、以每一个死循环串为起点为起点求单源最短路,找到最短路里最长的字符串输出

L:学习之city的帮助

暴力循环65536次,这题数据太少,不需要自己考虑其他东西

以下为数据不水需要考虑的

大于42的数只会有1个数满足即为0,所以只需要计算小于42的即可 5+9+9+9+9=41


感谢出题组:(zhouzexi,BobHuang,1629220022,wangyifan)感谢验题组;(wangyifan,zhouzexi,BobHuang,1629220022)以上排名依据贡献大小排名,感觉大家的支持,感谢这次比赛辛勤发气球的志愿者,感谢crq老师和王爱冬老师。


最后欢迎大家赛后AK。


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

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

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