(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）   T1 Contest 观察符合题目要求的队A、B在三场比赛中的先后顺序会出现怎么样的情况。 无非两种，A>B出现两场，A<B出现一场； A>B出现一场，A<B出现两场； 分别观察第一场比赛、第二场比赛； 第一场比赛、第三场比赛； 第二场比赛、第三场比赛； 这三组比赛中A和B的顺序，如果在某一场比赛中A>B且另一场比赛中A<B，答案加一； 这个可以用逆序对做。 最后发现无论是哪种情况，合法的方案都会被加两次； 所以最后答案除以2就可以了。   T2 River 这种题目的通解就是二分导数...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）   T1 队列Q 将操作离线倒序处理理，可以线性效率解决这个问题。看代码很快就能懂了，不再赘 述。 时间复杂度：O(N + Q)   T2 矩阵 ⾸先看一个问题：有一个长度为 N 的序列 A，对于每一个位置 i，计算以 i 位置为 结尾的最大⼦串和，且⼦串的左端点位置必须大于等于 Li 。数据保证 Li 是非递减 的。 设 Si 为 A 的前缀和，则以位置 i 为结尾的⼦串和为 Si − Sj ，在区间 [Li − 1, i] 内枚举位置 j 找到 Sj 的最小值就可以计算出以 i 为结尾的最⼤子串和。这个问题 利用单调队列...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）   T1 序列 考虑到类似于差分的思想。其实就是给出数字的取值，要这长度为n-1的序列所有数字的乘积是1。-2的个数必须是 偶数，0.5的个数和-2的个数相同，位置是任意的，于是可得答案为 时间复杂度O(n)。   T2 随机数 将随机数生成器运行x次产生奇数个1的概率记为f(x) 由独立性可知，f(a+b)=f(a)(1-f(b))+f(b)(1-f(a))=f(a)+f(b)-2f(a)f(b) 已知n的十进制表示，使用十进制下的快速幂可以计算f(n)。   T3 异或和 曼哈顿距离可以分解为X轴的距离和Y轴距离的和。分...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）   T1 走格子 模拟即可   T2 求值2 存在公式 C(2n, n)=ΣC(I,n)*C(I,n) (0<=i<=n) 预处理阶乘和逆元 即可O(n)出解   T3 简单环 状态压缩DP 考虑把环拆成一条路径 设f[s][i]表示当前路径中点的状态为ｓ，且当前路径的末尾为ｉ 为了使路径不重不漏 我们每次枚举一个编号最小的点ｖ作为起点 ｓ中的状态的其他点的编号必须比ｖ的编号大 时间复杂度O(n^2*2^n)   T4 01序列2 对于一个二进制串，考虑dp来记录有多少个子区间是3的倍数。 设f[i][j]表示当...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）   T1 取石子   考 虑 取 出 的 石 子 序 列 ， 序 列 长 度 为 a+b+c+d ， 属 于 第 1,2,3,4 堆 的 石 子 分 别 有 a,b,c,d 因 此 答 案 为 C(a+b+c+d,a)  C(b+c+d,b)  C(c+d,c)=(a+b+c+d)!/(a!b!c!d!)   T2 AB序列     显然这是个关于x的凹函数，最小值在-Ai,Bi,0组成的集合的中位数取到，如中位数有两个则最小值在两个中位数之间取到时间复杂度 （线性时间求中位 数）， 或者 （排序） 当然也可以用二分/三分等...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）   T1 最小化价格 首先，可以很明显的这道题可以贪心，对于每一个地点，尽量选择人数更多的小组。 先将地点按照容量从大到小排序，小组按照人数从大到小排序，对于每一个小组维护可选择地点。 每次小组选择价值最小的地点，可以证明这是最优解，且若无法解决则无解。 pq维护可选择的价值即可。   T2 车辆安排 这题看起来是一个分类讨论题，实际上标算也是用分类讨论写的，当然听说许多人露了细节，从5个人开始考虑，5个人就直接上车，4个人可以和1个人的搭配，2个人可以和三个1个人搭配。 想清楚这个就应该不会写错了。   T3 出队 经典约...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）   T1 直角三棱锥 签到题。思路有三种： • 打表，然后差分两次就发现，答案是 𝐾 三次方级别的多项式，插值或猜一猜 就出来了； •求几次和就出来了； •答案也可以视作是 𝑥 + 𝑦 + 𝑧 ≤ k, 𝑥 ≥ 0, 𝑦 ≥ 0, 𝑧 ≥ 0 整数解的个数，也即是 𝑥 + 𝑦 + 𝑧 + 𝑐 = k, 𝑐 ≥ 0 整数解的个数。   T2 前缀查询 在 Trie 上类似线段树一样地打标记，记录子节点需要变化多少声望值， 当前这个 节点作为名字属于多少人，作为名字声望值的和为多少，有多少人名字匹配前缀，...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）   T1 zzy的小号   这是一道简单组合题，代码长度极短，按照题意模拟即可，分四种情况 1、大小写的 o 和数字 0，当前位置的可能性种类 3 2、大小写的 l 和大小写的 i，当前位置的可能性种类 4 3、除 o 和 l 和 i 以外的字母，当前位置的可能性种类 2 4、除 0 外的数字，当前位置的可能种类为 1 考虑各个位置之间没有影响，那么答案即用乘法原理统计即可 时间复杂度 O(n)   T2 Jxc军训   这是一道用于混淆视听的水题，2000 的数据范围只是用于骗大家去想 dp（逃） 可以发现，云的位置实际没...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）    T1 银行存款 首先，假设存款的方案（a1 次一年期，a2 次两年期，a3 次三年期，a5 次五年期）已 知，那么其实存款的顺序是不影响答案的，答案为     再观察到 n 只有 20，所以我们只要枚举每种年限的存款存多少次就可以了。    T2 T95要减肥 ***肯定从快乐值高的开始吃，赛道肯定从痛苦值低的开始跑。 因为吃***得到的快乐值非负，所以有吃***的次数=跑步的次数。 那么我们只要枚举吃了几次***（即跑了几次步）就可以了。    T3 删除子串 f[i][j]表示前 i 个字符，变化了 j 次后保留的...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题） T1 白兔的分身术 显然取p=n,k=1最优    T2 白兔的式子 可以发现f[n][m]=a^{n-m}b^{m-1}C(n-1,m-1)。    T3 白兔的棋盘 状压DP，f[i][j][s]表示从（1,1）DP到了(i,j)，轮廓线上每个格子是否是空格的状态为s的方案数。放一个xy的矩形时直接转移到f[i][j+y]。    T4 白兔的字符串 枚举T的所有表示法存入哈希表 然后每个S直接查询 长度有10^6级别，所以哈希的姿势要足够优秀，必然很容易冲突 标算是ex_kmp。用R[i]表示S[i..len]和T的最...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）   T1 小H和迷宫 只要暴力枚举使用顺序即可，时空复杂度O(1)    T2 小H和密码 贪心确定每个密码盘选哪个字符是错误的，一个反例是： a# ba c# 这个密码盘能够表示出密码ac 考虑DP，设F[i][j]表示前i个密码盘，有j个选了某个小写字母的方案，则决策只有当前密码盘选择空字符或者小写字母两种，用桶记录每个位置有哪些可用字母，询问串过长直接输出NO，时间复杂度O(N^2Q)    T3 小H和游戏 考虑问题的简化版本，每次轰炸只会影响和轰炸点距离不超过1的城市 转化成有根树上的问题，用F[]记录每个点被轰炸...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可）   T1 找一找     统计一下1到1000000的数字分别有多少个。对于每个数字，看看原来的集合中有没有他的倍数，若有就更新答案。复杂度O(nlogn)。    T2 数一数     假如一个字符串的长度不是所有字符串中最短的，那么其答案一定为0，因为它在最短的字符串中没有出现过。找出任意一个长度最短的字符串，用kmp算法把它和每个串进行匹配，求出它在每个串中出现了多少次，乘起来就是答案。所有长度最短的字符串答案都相同，不需要重复匹配。       T3 列一列     选择一些素数，计算输入的数模这些素数的值，再一个一个计算斐...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）        T1 小Y和小B睡觉觉   模拟题，先把秒数 / 86400，再看看余数能不能凑够一天。     T2 LBJX的三角形    答案为a * b * c，因为满足条件的三角形一定是从红点、蓝点和绿点中分别取一个点。   T3 小C打比赛    令f[S][j]表示已经做的题的集合是S，一共用了j分钟的情况下，期望还能再做几道题。   枚举做哪道题以及做完的时间即可。   时间复杂度：O(2^n*n*m^2)    T4 Alice和Bob赌糖果    随机游走题http://www2.math.uu.se/~s...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）   T1 codeJan与***    可以根据 codeJan 的位置，将方格矩阵分成四个子矩阵分别考虑。对于每个子矩阵如果存在边长为 0的话，就不用考虑。如果存在边长小于 K 那一定不能完成任务，否则依次按照行列炸毁。因为要炸毁所有区域且允许重复炸一个区域，所以对于 a ∗  b 的子矩阵行上需要排炸弹，列上需要排炸弹。注意结果会爆 int。时间复杂度：O(1)  T2 codeJan与旅行     可以想象的是...