Dispwnl

Crazy Up

[HAOI2017]新型城市化

题目题解给定的是个二分图，发现题目就是给定一张图的反图，要求在反图中删掉哪条边能使原图最大团大小增加因为有定理$原图最大团=反图最大独立集=点数-最大匹配数$，所以现在要求的就是删掉哪条边能使最大匹配数减少，即此边是必选边首先这条边$(u,v)$的反边必须满流，而且在残量网络上$u$和$v$不在同一个强连通分量里我的理解是如果在同一个强连通分量里，说明可以不选这条边（即把...

Posted by Dispwnl on April 28, 2019

[HAOI2017]字符串

题目题解神仙题…… 题目中给的限制就是两个字符串$A,B$如果相等，那么$lcp(A,B)+lcs(A,B)+k\ge \vert A\vert$（$lcp$表示最长公共前缀，$lcs$表示最长公共后缀考虑建立$AC$自动机处理$lcp$和$lcs$（所以一上来就往$SAM,SA$上靠的就直接完蛋），$AC$自动机加入每个$p$和$p$的反串，然后把$s$和$s$的反串...

Posted by Dispwnl on April 28, 2019

[HAOI2017]供给侧改革

题目题解首先一个暴力做法就是把这题看成这题，然后暴力枚举就行了发现有个随机条件…… 你揣兜估计一下既然随机还只有$01$，$lcp$长度应该不大长，写个程序跑跑发现好像不大于$40$ 那么就用$Trie$来维护$lcp$，枚举每一位和往后的$40$位，在$Trie$加入这$40$个串，每个点位置维护这个子串出现的最右位置，然后维护当前点代表的后缀对于每个$lcp$能找到的最右...

Posted by Dispwnl on April 28, 2019

[JSOI2009]球队收益

题目题解先考虑假设球队$A$已经胜了$x$场，一共要打$y$场，则能产生的代价为$C_Ax^2+D_A(y-x)^2=(C_A+D_A)x^2+D_Ay^2-2D_Ax$ 计算多胜一场的代价为$((C_A+D_A)(x+1)^2+D_Ay^2-2D_A(x+1))-((C_A+D_A)x^2+D_Ay^2-2D_Ax)=(C_A+D_A)(1+2x)-2D_Ay$ 这样就可以先处...

Posted by Dispwnl on April 27, 2019

[六省联考2017]寿司餐厅

题目题解题目要求的就是$\sum d-(mx^2+cx)$的最大值看到这玩意我就想到了最大权闭合子图，直接建边$((i,i),T,a_i),(a_i,T,{a_i}^2)$，然后分值的正负每个区间连$S/T$，区间之间连一下$\inf$边即可代码 # include<iostream> # include<cstring> # include<...

Posted by Dispwnl on April 26, 2019

[ZJOI2005]沼泽鳄鱼

题目题解众所周知，因为鳄鱼名字里有鱼，食人鱼名字里有鱼，所以鳄鱼=食人鱼发现不能经过的点最多有$12$种情况，即$lcm(2,3,4)$ 所以把$12$种情况的矩阵都处理出来，然后$12$个时间一起处理，最后剩下的$k\%12$个时间暴力乘起来即可代码 # include<iostream> # include<cstring> # include...

Posted by Dispwnl on April 26, 2019

[SDOI2011]保密

题目题解感觉就是道多合一…… 先处理出来$n$到$1…n1$的最短距离，即求$\frac{\sum_{j\in path(n,i)}t_j}{\sum_{j\in path(n,i)}s_j}$最大，一脸分数规划的样子，设二分的答案为$T$，则有$\sum_{j\in path(n,i)}t_j -T\times \sum_{j\in path(n,i)}s_j\le 0$ 即$...

Posted by Dispwnl on April 26, 2019

[SCOI2003]字符串折叠

题目题解用$f_{i,j}$表示区间$[i,j]$压缩后的最小长度，直接暴力枚举是否可以压缩即可，子串是否相同用$Hash$判断即可复杂度跑不满的$O(n^4)$ 代码 # include<iostream> # include<cstring> # include<cstdio> # include<algorithm> us...

Posted by Dispwnl on April 26, 2019

[JLOI2016]字符串覆盖

题目题解对于求最大值的情况，如果确定子串出现顺序的话，贪心即可，即最优情况把当前串放在上一个串结尾后面第一个出现位置，否则放在上一个串结尾前面第一个出现位置对于求最小值的情况，设$f_{i,j}$表示转移到低$i$个字符子串出现状态为$j$（去重后）的最小值，设当前串为$S$，则有式子$f_{i,j}=\min(f_{a,j-S},f_{b,j-S}),i-len_S+1\le ...

Posted by Dispwnl on April 26, 2019

[TJOI2015]棋盘

题目题解所有东西都是从$0$开始的……$f_{i,j}$表示第$i$列状态为$j$的方案数，然后处理每种情况列列之间的关系，用矩阵快速幂优化即可代码 # include<iostream> # include<cstring> # include<cstdio> # include<algorithm> # define uint...

Posted by Dispwnl on April 25, 2019