该文被密码保护
第一题：
博弈(tc srm 664a)
【问题描述】
𝐴𝑐𝑒𝑠𝑟𝑐的好朋友𝑔𝑖𝑠𝑝𝑧𝑗𝑧最近迷上了一个游戏！
作为𝑔𝑖𝑠𝑝𝑧𝑗𝑧的知心好友，𝐴𝑐𝑒𝑠𝑟𝑐决定和𝑔𝑖𝑠𝑝𝑧𝑗𝑧 打打游戏，沟通沟通感
情。
初始𝐴𝑐𝑒𝑠𝑟𝑐和𝑔𝑖𝑠𝑝𝑧𝑗𝑧各自有一个数a,b，这个游戏将进行k轮，每一轮游戏会有下面的事情发生：
假设a ≤ b，我们令b = b − a,a = a + a；
如果b < a，则a = a − b,b = b + b。
现在𝑔𝑖𝑠𝑝𝑧𝑗𝑧想知道，k轮游戏后，min(a,b)是多少。
【输入格式】
从文件game.in中读入数据。
第一行三个数，表示a,b,k。
【输出格式】
输出到文件game.out中。
一共一行，包含一个整数，表示答案。
【样例输入1】
2 3 5
【样例输出1】
1
【样例输入2】
955 812 828145516
【样例输出2】
167
【样例输入3】
955253431 806956091 857954
【样例输出3】
553642420
【数据规模】
对于20% 的数据，a,b ≤ 1000。
对于40% 的数据，a,b ≤ 106。
对于60% 的数据，a,b ≤ 108。
对于另20% 的数据，k ≤ 107。
对于100% 的数据，1 ≤ a,b,k ≤ 109。
显然a+b是定值，令n=a+b
若a<=b，a’=2a
若a>b，a’=a-b=2a-(a+b)=2a-n
所以就是在模n意义下乘2的k次方。
思维好题。
我发现了a+b是定值，然后开始考虑周期。。
所以说对称性很重要！！（还有单调性之类的。）
第二题：
(cf 446B)
给一个𝑁×𝑀的矩阵，共𝐾次操作，每次挑选一行或者一列，将其中的元素全都加到答案中，并且每个元素的值−𝑃。
问答案最大是多少。
显然行列独立（取多少行也不会影响该怎么取列）
预处理取k行的最大值，取k列的最大值
然后枚举行取多少，更新答案即可
O(klogn)
行列一起考虑随便反例
第三题：
给定𝑁个区间[𝑙𝑖, 𝑟𝑖]，你可以选出其中若干个区间，设为𝑡𝑜𝑡个；令𝑥为这𝑡𝑜𝑡个区
间的交。求min(𝑥, 𝑡𝑜𝑡)的最大值。
范围：𝑁 ≤ 300000，1 ≤ 𝑙𝑖 ≤ 𝑟𝑖 ≤ 𝑁。
显然区间的交是连续的
注意到区间越长，个数越少
想到二分区间长度
枚举左端点
每次均摊O(1)的插入区间（考试时来不及就写O(n)判。。）
或者枚举左端点，注意到随着右端点的右移，区间长度变大，个数变小。
那就二分呗，发现还要算覆盖它的区间个数
感觉还要一个log在线段树上求这个值
诶？线段树上求值，所以线段树二分
发现这题不管是按长度还是按位置都有单调性
说明这题的性质很强啊
发现two pointers也能做
所以说单调性很重要！！（还有对称性之类的。）