zcmimi's blog
avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

同usaco工作调度

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

先预处理出以i结尾最长多少个连续

然后rmq预处理

查询的时候要先查以左端点开始最长多少,然后再求剩下的那段区间

注意多组数据

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

先用set预处理出离每个点最近的点和第二近的点

n~1 每次往set里插入{a[i],i} 然后把前驱后继找出来比较一下 具体看代码

(听说有排序后双向链表的神仙做法)

接着用倍增处理出开2^i循环次的数据

然后就直接暴力

具体看代码,码风有点新奇

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

直接树剖即可

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

解法1:

贪心

把深度大于2的都加到堆中

每次取出深度最大的点

从根结点往它父亲连边

然后把周围的节点标记为已经覆盖

解法2:

树形dp

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

记忆化搜索

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

我们定义第x个数中从右往左数第i位的贡献:有多少个在x之前的数j满足a_j \bigoplus a_{j+1} \bigoplus ... \bigoplus a_x的第i位是1.

f[x][i]表示第x个数第i位的贡献,a[x][i]表示第x个数第i位是多少。

a[x][i]=0,取j=x不会产生贡献。若j < x,aj \bigoplus a_{j+1} \bigoplus ... \bigoplus a_x=a_j \bigoplus a_{j+1} \bigoplus ... \bigoplus a_{x-1}。所以f[x][i]=f[x-1][i].

a[x][i]=1,取j=x产生1的贡献。若j小于x,aj \bigoplus a_{j+1} \bigoplus ... \bigoplus a_xa_j \bigoplus a_{j+1} \bigoplus ... \bigoplus a_{x-1}相反。所以f[x][i]=(x-1-f[x-1][i])(j小于x的贡献)+1(j=x的贡献)=x-f[x-1][i].

f[x]=f[x][0]×1+f[x][1]×2+f[x][2]×4+...+f[x][31]×2^{31}.

则答案就是f[1]+f[2]+...+f[n].

可以用滚动数组

54/73
Search
search