心得
赛中ac:5,目前ac:9,题目总数:13
中档可做题还是很多的,可惜遇到了难绷的queueforces,
最后15min才判出来,oi赛制5wa4遗憾离场,赛后把几个题都给调过了,写下题解
题目
J. Breakfast(签到)
签到,不过不是很懂python直接输出39.20为啥wa了
#include
#include
#include
#include
A. Paper Watering(枚举)
先特判1,
对于非1的情况,首先原数是可以一直平方不重的,
如果x开根号遇到了下取整,说明sqrt(x)*sqrt(x)也不会和x重,后续平方也都不会重
暴力模拟这个过程,直至出现1为止
#include
#include
#include
#include
#include
D. nIM gAME(博弈)
发现后手可以控制倒数第二张牌取什么,从而使先手必败
//#include
#include
#include
#include
#include
E. Checksum(枚举)
枚举最终的d有几个1,从而唯一确定后缀补的1的数量和位置,输出即可
//#include
#include
#include
#include
#include
L. Bracket Generation(计数)
一开始把第二个条件看错了,以为只有内层的选完了外层的才能选,没有这个限制之后就很好做
把左右括号相邻的()括号称为叶子节点(建括号树更直观),其他的称为非叶节点
非叶节点能选当且仅当其包含的最大叶子结点x及序列里位于x左侧的叶子结点都选完之后,才能选
将序列倒着考虑,就是非叶节点的一个插空问题
#include
#include
#include
#include
#include
F. Factor(数论)
先把p、k分别质因数分解,求出对应质因数和出现的幂次
对于p的质因子f,如果f也是k的质因子,显然出现多少次都无所谓,都能除尽,删掉这些f
对于p的独有质因子(也就是没有出现在k中的质因子)p1、p2、…,
记每个的最高幂次是k1、k2、…,将这些最高幂次乘起来得到y,
枚举y的因子z,也就是这些独有质因子出现了多少,
分母必须恰好能和z兑掉,且剩下的部分由k出现过的质因子构成,
在[1,x/z]内仅由k出现过的质因子构成的数,这个可以先预处理出所有,再二分
因为仅由质因子组成,所以数量没有太多
#include
#include
#include
#include
#include
I. Password(dp)
dp[i]表示[1,i]是合法答案的方案数
转移枚举最后一段的长度x,最后这一段和前面的x-k共同拼成了一个长度为k的排列
但是枚举长度为2的时候,会和长度为1的方案有重复,具体来说
不妨k=5,前5个肯定只能是一个排列,k!种方案,不妨是1 2 3 4 5,对于第6个往后,
对于x=1,1 2 3 4 5 [1],
x=2,1 2 3 4 5 [2 1]和 1 2 3 4 5 [1 2]中只能保留第一个,因为第二个和x=1重复了
x=3,同理,只能保留1 2 3 4 5 [3 1 2]、1 2 3 4 5 [3 2 1]和1 2 3 4 5 [2 3 1]
这个系数是需要递推减掉的,手玩发现:
记长度为x的系数是xs[x],对于长度x来说,若y<x,则需要在总数里减掉xs[y]*fac[x-y],
rep(i,1,k){
xs[i]=fac[i];
per(j,i-1,1){
xs[i]=(xs[i]+mod-1ll*xs[j]*fac[i-j]%mod)%mod;
}
//printf(“i:%d xs:%d
“,i,xs[i]);
}
O(k^2)预处理出系数之后,再O(nk)dp即可
#include
#include
#include
#include
#include
M. House(计算几何)
感觉计算几何的题平时不怎么写所以不太会写,
但实际上出题人应该平时也不怎么写,出的题还是挺基础的
先求出矩形,O(n^2logn)枚举点对,将点对放入(线段中点,线段长度)的map内,
矩形的对角线互相平分,所以共用中点且长度相等的两条对角线能构成一个矩形
两两枚举矩形,对于矩形四条边,任意两条邻边x、y检查一下,
统计房子在x外侧的第五个点的个数,这个需要叉积判断不在矩形内部
此时需要统计向量i->j左侧/右侧有多少点,O(n^3)预处理一下即可
#include
#include
#include
#include
#include
G. Diamond(分块)
想到分块之后就很好做了,虽然空间稍微用short卡了一下
先把n弥补成块的倍数,方便后面判断,后面的都用0补足即可,
对于第i个块,预处理出块内任意两种数(x,y)的逆序对个数,
计在这个块内x、y出现的第一个位置big[i][x][y]
所以,也需要记录每种数x在第i个块内出现的第一个位置pos[x][i]是多少,
这个位置可以对块长取模,就是一个最大为块长M(300多)的数,short足矣
然后就是在线查询,
对于长度不超过3*M的块,懒得分类讨论有一个块还是两个了,直接暴力,常数略大一点而已
超过3*M的,一定中间有完整块,然后最多两个半块,
对于每个完整块,先加上完整块的答案;对于半块,暴力统计答案
再从前往后、从后往前遍历块,分别统计块间能产生的答案,求和即可
#include
#include
#include
#include
#include