xjoi模拟赛44

t1:

观察到题目有性质,于是我们用方程的形式分别表示坐标为i,j的位置AB矩阵的表达式,并且对这个表达式解一个正整数解的方程即可

.

t2: 待更新

首先我们可以~~很简单~~的糊出一个60pts的暴力状态压缩,于是我们想如何优化它

状态压缩复杂度O(n^3*C)

我们可以发现,当已经达到和匹配串一样的时候,后面的操作都是多余的操作

我们发现多余的操作的运算仅仅与其中与原串转换的步数有关,于是我们可以维护一下这个步数

通过打表发现状态数差不多只有80种,于是我们用矩阵快速幂来维护

那么如何构造矩阵呢?

t3:

首先我们可以大力打一发表格,或者大力推一发结论

结论:f[n]=floor(n/2)+bitcount(n)是偶数||n%2==0

Proof:

我们设f[i]为小于等于N的数中有多少个数的二进制表示中有偶数个1
首先我们可以利用数位dp的思想,我们可以对于每一位分别的进行考虑
对于每一个这一位是1的位数,设该为是第t位,后面都有2^(t-1)次选择(因为最后一位不能选)并且我们的t不包括最后一位,最后一位在下面将考虑到,所以答案就是floor(i)在二进制下
但是我们忘记考虑了两种情况,一是原来的串本身就是满足条件的,二是对于最后一位如果是1的话,那么无论前面是多少都是满足的
但是这两种情况是冲突的,我们只需要吧这两种情况取or即可

于是我们就可以对数据结构来维护这个

我们可以做到 O(1) 询问O(logn)修改

Tips: 写区间取反可以先build一下线段树,到时候对于这一位的build的值取反就行了

.

今天 打了对拍所以好像有160

第三题数据好像出了一点小偏差,不过我本来就没有写对233

发表评论

电子邮件地址不会被公开。 必填项已用*标注