本文主要是介绍codeforces做题 记录,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1033 G 题意是 给 n堆 石子 Alice 和 Bob 游戏 Alice 每次可以在一堆中取出a枚石子,Bob可以在一堆中取出b枚石子,求对于a 属于 [1,m] b 属于[1,m] 有多少对 <a,b> 满足 1)Alice必胜 2)Bob必胜
3)先手必胜 4) 后手必胜
这一类 博弈题 考虑 每堆对于 (a+b)的余数即可, 像这种 双方在对手操作后总可以再进行一步操作达到某个特定效果的题,这么考虑。
然后细节方面比较繁琐,一开始我写了一个 set 的模型, 常数非常大,设关键点比较复杂。 后来 看了一下VooV的 考场代码。
他维护了3) 和 4) 这样只需要考虑 a和 b 在同一区间的情况。 对于这种情况只需要考虑 2*a 的 限制就可以,细节比较少,写也很方便。 这种 维护的题目可能维护一些特定的东西 能够有一些优美的性质来优化写法。
1033 F 题意 n个w位的模板串 m次询问,每次给出一个长度为w的逻辑运算符串,让你求多少对数 按位做串上的操作能够得到 0.
复杂度 m*(2^w)想到复杂度 标算是 总共三种情况,直接利用和的方式表示。 比如说 一个0 一个 1 和1为1 ,这样一个为0 至多表示为2种不同的和。这样就可以做了。下次这种题 要敢于些这种复杂度。
还有一种留空白的方法其实也是差不多的,就是优化状态。
1033 E 题意 每次可询问一个点集内的边数,让你用 O(n log n) 次询问判断出这个图是否是一个二分图。 n 500 无重边 无自环。
考虑构造二分图的几个方法, 直接搜点集不靠谱,这里只能先构造一个生成树。 我们对这个图 进行dfs,我们可以O(log n)次询问 问出一条边,然后继续搜索。 这样子 共用了 O(n log n) 剩下的 随便做。<
这篇关于codeforces做题 记录的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!