zcmimi's blog

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

avatar
zc
2020-01-19 11:09:00
查看原题

点击跳转

avatar
zc
2020-01-19 10:55:00
查看原题

点击跳转

f[sta]表示sta表示的所有颜色都排列到从1开始的相连的一段,最少要多少次

pre[i][j]表示所有颜色i前面总共有多少个颜色j,也就是说要将所有颜色i移动到颜色j左边要移动多少次

即:\sum[y<x,c[x]=i,c[y]=j]

sta[i]表示sta表示的第i种颜色的状态

f[sta]=\min{f[sta']+\sum_{sta[j]=1,sta[k]=0}pre[j][k]}

avatar
zc
2020-01-18 23:37:00
查看原题

点击跳转

看到边不能重复用,n\le 200,T\le 200就可以想到网络流

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

总和减去最小割即为答案

最小割删掉的边就是要减去的值,这样就可以最小化要减去的值,即答案最大化

那我们如何构造这张图呢?

  1. ST \xrightarrow{\text{选文科的值}} (i,j) \xrightarrow{\text{选理科的值}}ED

  2. ST \xrightarrow{\text{同时选文科的额外快乐}}new,new\rightarrow(i,j),new\rightarrow(i+1,j)(其他同理)

  3. (i,j)\rightarrow new,(i+1,j)\rightarrow new,new \xrightarrow{\text{同时选理科的额外快乐}}ED(其他同理)

每个点只能选择文科或理科,当某个点选择了文科,那么它向理科(ED)的边都应该要被断开。

它直接连向ED的边、它和别的点组合连向ED的边都要切断

这些边的权值就会从最终答案中减去

infinf同时选文科选理科选文科同时选理科infinf选理科选文科ST(i,j)ED(i+1,j)newnew'
avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

看到交换相邻字母,就想到逆序对

考虑一下,一定是将A的每个字母移动到离它最近的B中相同字母的位置

我们可以用讲位置存起来然后处理一下

之后数组变成了A中每个位置最后在B中的位置

这个数组中逆序对的数目就是答案

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

我们考虑两个断点(设为l,r)符合的条件:

每种颜色的珠子只能出现在其中一条链中

也就是若[l,r]中出现了某种颜色[l,r]也就包含了所有的这种颜色

我们可以记录颜色出现的前缀和

记录前i个位置每种颜色的出现次数,如果位置i是 颜色a[i]的最后一个位置, 就把颜色 a[i] 的结果清零。

这样若两个位置的前缀和相同,就是合法的

可以通过hash来判断,记录所有hash值,排序后统计

两个分割点 l,r 要尽可能满足 r−l 接近 \frac n2

可以用类似双指针的方式维护

这题卡hash,要双hash

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

x>y,看成x\rightarrow y的一条边

若最后的图出现环的话那就是不合法的

但是如果按照普通的建图方式的话每次要添加k(r-l-1-k)条边

我们可以线段树优化建图

因为k \le 3 \times 10^5

所以整个区间最多被划分成3\times 10^5

log n的复杂度是可以接受的

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

a是确定的,考虑b的情况:

  1. a的祖先

    可以作为b的点的数量是\min(d_x,k)(d_xx的深度),

    a的子树中除a外其他点都可以作为c

    总方案数为\min(d_x,k)\times(siz_x-1)

  2. a子树中

    对于每个b,可以作为c的点的数量为siz_b-1

    我们可以dfs序,记录当前区间中深度为d的数

    然后用主席树(可持久化权值线段树)维护

    这样就可以查询深度\in [d_a+1,d_a+k]的所有'点的子树大小-1'的和

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

这题考验的是仔细读题

可以发现修改带查询的只有1000个,这部分直接暴力求就可以了

区间加可以用差分来解决

剩下的部分:

可以预处理出[1,i]的答案ans_i

查询[l,r]的答案就是ans_r-ans_{l-1}

代码很短

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

f[i][j]表示前i个分j个邮局

f[i][j]=\min(f[x][j-1]+w[x+1][i])

满足决策单调性

27/66
Search
search