zcmimi's blog

categories/刷题记录/共653篇文章

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

点击跳转

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

点击跳转

f_{i,j} =f_{i,k}+1(|a_i-a_k| = |a_k-a_j|)

先对a排序,然后dp,双指针,记得数组开成short

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

点击跳转

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

点击跳转

找度最大的点

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

点击跳转

维护两个单调递减栈,当i加进栈,位置x的数弹出的时候,在另一个栈中找到和这个数一样大的数,计算贡献(x-靠右左端点)\times (i-x)

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

点击跳转

S_i表示[1,i]的异或和,区间[l,r]的异或和就是S_r \bigoplus S_{l-1}

那么题目可以转化为[l-1,r]中有多少对S_i \bigoplus S_j = k,直接用莫队统计就可以了

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

点击跳转

我们设f[i][k][j]表示第i列状态为j,联通块个数为k的方案数

我们可以列出个种状态的转移

00 | 00 | 10 | 10
00 | 10 | 00 | 10

00 | 00 | 10 | 10
01 | 11 | 01 | 11

01 | 01 | 11 | 11
00 | 10 | 00 | 10

01 | 01 | 11 | 11
01 | 11 | 01 | 11

增加的联通块数(设这个矩阵为g):

0 0 0 1
1 0 2 1
1 2 0 1
1 0 0 0

那么f[i][k][j] = \sum f[i-1][k-g[j][t]][t]

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

点击跳转

集合hash

  1. 两个点不认识

    两个点是相似关系说明他们的所有朋友都相同,可以把一个点的朋友当成集合hash一下,然后就可以统计了

  2. 两个点认识

    两个点是相似关系说明他们的所有朋友加上对方都相同,可以把一个点的朋友加上它自己当成集合hash一下,然后就可以统计了

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

点击跳转

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

点击跳转

静态链分治 参见模板

51/66
Search
search