首页 > 其他分享 >10.7校赛初赛

10.7校赛初赛

时间:2022-10-22 12:12:56浏览次数:81  
标签:一堆 10.7 博弈论 初赛 校赛 SG

整体难度不大,但是因为前期冲的太猛了,15分钟做了3道题,后期跟风做题,看着别人都6题甚至AK了,就有点慌张,后期基本上没有深入思考,状态很浮躁,导致最终结果很差。因为后一个小时都靠直觉做题,有一些简单的问题反而没有思考,而且很容易被带偏方向。
博弈论SG函数不会做也是一个硬伤。

\(E\)
给一个二元序列\(<a_i,b_i>\)和\(n,tot\),求最大的\(k\)使得选出\(k\)个二元组满足\(k\times\sum b_j+\max a_j<= tot\),其中\(a_j\)和\(b_j\)是选出来的元素。

容易想到,对\(a\)排序后,枚举到当前的第\(i\)个元素则当作当前的最大的\(a_i\),然后看这个总和是否超限,如果超限,先除去最大的\(b_j\)(已经选过的那部分当中的最大的),以此类推。可以发现,这样的选法一定是最优的。用堆来维护选出来的\(b\)即可。然后每一步的\(k\)取一个最大值就是答案了。

\(F\)
博弈论,SG函数
n堆石子,可以把某一堆均分成2堆,也可以拿走一堆,或者拿走一堆中的一个,问谁赢?
写出SG函数推式子即可。因为注意到\(SG_{n/2}\ xor\ SG_{n/2}=0\)这个性质,是和\(SG_0=0\)是完全一致的,所以均分两堆石子这个操作是没有作用的,可以被其他操作等效掉,所以不考虑均分,然后就是简单的递推一下,发现奇数的SG是1,偶数的SG是2,然后异或起来即可。

标签:一堆,10.7,博弈论,初赛,校赛,SG
From: https://www.cnblogs.com/Ronald-MOK1426/p/16815776.html

相关文章

  • 西工大校赛2 weekly contest 10.16
    西工大校赛2weeklycontest10.16[Problems-Codeforces.pdf](assets/Problems-Codeforces-20221019121149-0g83yz5.pdf)校赛网址:https://codeforces.com/contestIn......
  • 用 Java?试试国产轻量的 Solon v1.10.7
    Java国产的轻量级应用开发框架。可用来快速开发Java应用项目。主框架仅0.1MB。Helloworld:@ControllerpublicclassApp{publicstaticvoidmain(String[]ar......
  • 2018农大校赛(dp大法)
    0&1DescriptionInput第一行是一个不超过100的整数t,代表了样例的组数接下来有多行,每行两个整数n和k,Output对于每组输入样例,先输出它的序号标识(‘CASE1:’,‘CASE2:’,......
  • 浙江工业大学校赛 画图游戏 BugZhu抽抽抽!!
    BugZhu抽抽抽!!TimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):695    AcceptedSubmission(s):253......
  • 动手动脑10.7号
     调用关系:如果一个类具有父类,在类加载的时候都是先加载父类的方法(相当于构造了一个父类对象)子类继承父类后,获取到父类的属性和方法,这些属性和方法在使用前必须先初......
  • 动手动脑10.7
    1.动手实验1:运行 TestInherits.java 示例,观察输出,注意总结父类与子类之间构造方法的调用关系修改Parent构造方法的代码,显式调用GrandParent的另一个构造函数,注意这句调用......
  • 10.7 上课问题的讨论与思考
    一、动手实验:继承条件下的构造方法调用继承的语法:class子类名extends父类名{......}  父类(parentclass)和超类(superclass)两者通常指直接上级基类(baseclass)......
  • 2022.10.7 Java第五次课总结
    继承java的继承与C++的继承的区分java中的继承是单项继承,区分与C++的多项继承,这种继承避免了C++继承中可能出现的冲突的问题,单项继承父类所有的属性,子类对于好的属性可以......
  • 2022.10.7第三次组会记录
    团队:集农广益小组地点:桃园食堂时间:晚上九点参与人:全体人员组会内容摘要:分析项目具体架构和功能,讨论数据流图的设计要求组会主要内容:1.分析讨论用户的具体功能:发帖、......
  • 2022.10.7
    ACM。结果不是很好。一开始的节奏是很好的,但从A题调不出来开始就乱了。每个人再自己的题上都有深入思考,但对别人的情况不了解,所以讨论的效率实际不高,而且很容易被套进死胡......