[原创]山东省第七届ACM大学生程序设计竞赛 训练总结 [8/12] 待补

Tabris

CSDN各OJ套题

发布于：2017年4月27日

次浏览

[原创]山东省第七届 ACM 大学生程序设计竞赛 训练总结 [8/12] 待补

2017-04-27 23:29:20 Tabris_ 阅读数：1131

博客爬取于 2020-06-14 22:40:50
以下为正文

版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/70880837

中期被学弟艹到爆啊。。。。

这套题目相对简单点 AC8 题（相对别的套题，对鄙队来说还是很难的。。还是这套题 有陈题，签到题偏多，面上还不错）

前期交 gcc CE2 发，不读题，直接写 wa 了一发。。。 还是我训练态度不认真，，，

模拟没时间出，难题没有时间开，出题速度慢，,,，菜的一逼，要加强

比赛策略来说，前期努力找水题，找一个 A 一个，中期思考，轮流上机，到此还不错，但是后期还是空机很长时间，1 是缺了一名模拟翻译字符串队友，2 是后期题没有开，模拟没人做，3 是 D 题卡了好久，最后十几分钟才 AC， 总体表现良好 待加强。

Problem A Julyed

————————————————————————————————————————————
没读题 队友 A 的 签到题 ，

Problem B Fibonacci

————————————————————————————————————————————
就是问你一个数能不能被一些 fibonacci 数的加和表示出 要求 fibo 数不能连续 能输出这个式子，不能输出-1

根据齐肯拉夫定理？ 好像叫这个名字，任何数都能被多个 fibonacci 数表示，所以那个-1 的输出是没有意义的，所以只要从大的数向下找就好了

至于有些人纠结如果其中有连续的怎么办，加入 结果中有 f(x)和 f(x+1)的话一定能被 f(x+2)代替。

Problem C Proxy

————————————————————————————————————————————
简单的最短路，反向建图，计算 n 到其他节点的最短路，然后枚举 0 能到达的点维护答案即可，

主体队友写的，我的贡献只有"然后枚举 0 能到达的点维护答案即可，"...

------------------------------------------------update------------------------------------------------------
自己实现了发虽然 1A，但是花了 40min，还看了 dij 的模板，，图论这一块好弱了。。。。

Problem D Swiss-system tournament

————————————————————————————————————————————
这题就是给你 n*2 个队伍，每个队伍有一个积分，还有一个能力值
现在来 n 轮比赛
每次比赛将当前积分第 1 大的和第 2 大的比，当前积分第 3 大的和第 4 大的比，当前积分第 5 大的和第 6 大的比，以此类推
能力值大的能比赢，且积分 +1,

问你最后能力值第 q 大的队伍是那支。

*积分一样按队伍编号小的来。

这题很简单了 模拟一下就是一个水题，写完交了一发 TLE.。。。卡了排序，
然后手写了归并排序，本机测试了极限数据结果时间和 sort 比就少了 1/7，，，

然后考虑这个比赛的过程
发现对于比赛顺序来说，
前面的大的一定比后面的大的大。小的同理，

那么我们维护两个序列，一个存每场比赛的大的，另一个存每场比赛的小的，
然后做一个归并的工程，就能在 O(n)的复杂度完成了。。

Problem E The Binding of Isaac

————————————————————————————————————————————
也是个水签到题，
就是给你一个 NM 的图
问你在(N+2)(M+2)的图上有几个位置四周只有一个'#'

(开始没仔细读题，以为只会出现在 N*M 这个范围的四周..

Problem F Feed the monkey

————————————————————————————————————————————
是个 dp 我不会 dp 队友出的

Problem G Triple Nim

————————————————————————————————————————————
Nim 游戏，Alice 先手，现在有 N 个石子，分成三堆，问让 Alice 数的分发有多少种，

*(a,b,c) <=>(a,c,b) and so on..

首先考虑最基本的博弈，就是(a^b^c)==0 的时候 Alice 才会输，

然后考虑怎么分？ 枚举复杂度是 O(n^2)的显然不可取，

就考虑先分成两堆，那么这两堆一定是一样的，
考虑二进制
那么一定是

这样的
这时候从中找几个 1 拿出来给第三堆就好了，,

然后枚举，dp，各种思路都试了，没有什么能做的...
但也发现了
1.n 为奇数的时候一定是 0,
2.结果的贡献只和二进制下 1 的个数有关，,,

那么答案就是 ans[1 的个数]...

然后有了 qls 的一个至理名言"遇事不决先打表"...

于是发现

有了表，看了一眼发现递推式，然后就 AC 了。。。

*注意： 要 long long int 3^x 会报

Problem H Memory Leak

————————————————————————————————————————————

Problem I Rock Paper Scissors

————————————————————————————————————————————

Problem J Execution of Paladin

————————————————————————————————————————————

Problem K Reversed Words

————————————————————————————————————————————
c 语言入门题 签到题

Problem L Password

————————————————————————————————————————————

本页文档最后更新于：2021年5月16日

CSDN

acm