zcmimi's blog

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

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

点击跳转

题意

一棵以1为根的树,每个节点上都有1个字母,有m个询问。每次询问v对应的子树中,深度为h的这层节点的字母,能否打乱重排组成回文串。根的深度为1,每个点的深度为到根的距离。

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

点击跳转

f[i][j]表示状态为i,上一个吃的是第j道菜

f[i'][k]=\max(f[i'][k],f[i][j]+a[j]+d[j][k]) (d[j][k]表示连续吃j,k能额外获得多少满意度)

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

点击跳转

一开始看到题面是懵逼的

突然发现1 \le a \le 10

直接在每个重链顶端和节点上放个vector

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

点击跳转

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

点击跳转

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

点击跳转

静态链分治

记得开long\ long

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

点击跳转

E_xxn的期望时间

E_x = \sum_i E_i \times p_{xi}\prod_{j=1}^{i-1}(1-p_{xj})

我们可以用类似dij的思想来更新

每次取出E_x最小的x来更新

要注意我们现在求出来的还没算上1需要先停留在原地的概率,

除掉一个1-\prod p才是最终的期望

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

点击跳转

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

点击跳转

  1. 如果个数中没有奇数,那么答案就是所有数字的gcd,然后构造答案就是输出\frac {gcd}2个回文串

  2. 如果个数中只有一个奇数,那么答案也是所有数字的gcd,然后构造答案就是输出gcd个回文串,个数为奇数的颜色放在回文串的中间

  3. 如果个数中有两个或以上的奇数,那么答案就是0,因为两个奇数就已经构造不出有优美cut的环来了

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,直接用莫队统计就可以了

62/66
Search
search