[原创]山东省第七届ACM大学生程序设计竞赛 训练总结 [8/12] 待补
[原创]山东省第七届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的一个至理名言"遇事不决先打表"…
于是发现
| 1的个数 | ans[1的个数] |
|---|---|
| 1 | 0 |
| 2 | 1 |
| 3 | 4 |
| 4 | 13 |
| 5 | 40 |
| 6 | 121 |
| … | … |
| n | ans[n-1]*3+1 |
有了表，看了一眼发现递推式，然后就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
————————————————————————————————————————————
wechat- alipay
