JZYshuraK

分类

未归档(392)

/ 注册

全部文章（共392篇）

[bzoj1692][Usaco2007 Dec]队列变换_后缀数组_贪心

队列变换 bzoj-1692 Usaco-2007 Dec 题目大意：给定一个长度为$n$的字符串。每次从头或尾取出一个字符加到另一个字符串里。要求变换后生成的字符串字典序最小，求字典序最小的字符串。注释：$1\le n\le 3\cdot 10^4$。想法：考虑暴力怎么做：每...

2018-12-12

0 428

[bzoj2882]工艺_后缀数组

工艺 bzoj-2882 题目大意：题目链接。注释：略。想法：跟bzoj1031差不多啊。把串倍长后扫$sa$数组。最后再统计答案即可。 Code： #include <iostream> #include <cstdio> #includ...

2018-12-12

0 344

[bzoj1031][JSOI2007]字符加密Cipher_后缀数组

字符加密Cipher bzoj-1031 JSOI-2007 题目大意：题目链接。注释：略。想法：后缀数组裸题啊。后缀数组其实背下来板子之后有几个数组记住就可以了。 $sa_i$表示排名为$i$的后缀所对应的下标。 $rk_i$表示下标为$i$的后缀的排名。 $ht_i$...

2018-12-12

0 369

[bzoj5343][Ctsc2018]混合果汁_二分答案_主席树

混合果汁 bzoj-5343 Ctsc-2018 题目大意：给定$n$中果汁，第$i$种果汁的美味度为$d_i$，每升价格为$p_i$，每次最多添加$l_i$升。现在要求用这$n$中果汁调配出$m$杯混合果汁。第$j$杯混合果汁的要求是总价格不多余$g_j$，总体积不小于$L_j$且美味度最大。一...

2018-12-12

0 386

[bzoj2527][Poi2011]Meteors_整体二分_树状数组

Meteors bzoj-2527 Poi-2011 题目大意：题目链接。注释：略。想法：首先答案可以离线，且具有单调性。这里的单调性就是随着时间的推移，每个国家收集的陨石数增加。不难想到整体二分，对时间进行二分。但是有一个问题，就是一个国家出现了多次，这样的话我们用链...

2018-12-12

0 386

[bzoj2738]矩阵乘法_整体二分_树状数组

矩阵乘法 bzoj-2738 题目大意：给定一个$n*n$的矩阵。每次给定一个矩阵求矩阵$k$小值。注释：$1\le n\le 500$，$1\le q\le 6\cdot 10^4$。想法：新操作整体二分。整体二分是一个必须离线的算法而且所求的答案必须满足单调性。所谓单调...

2018-12-12

0 485

[bzoj3513][MUTC2013]idiots_FFT

idiots bzoj-3513 MUTC-2013 题目大意：给定$n$根木棍，问随机选择三根能构成三角形的概率。注释：$1\le n\le 3\cdot 10^5$，$1\le a_i\le 10^5$。想法：考虑暴力：枚举三条边。复杂度$O(n^3)$。优化一下发现第三条...

2018-12-12

0 342

[bzoj3160]万径人踪灭_FFT_Manacher

万径人踪灭 bzoj-3160 题目大意：给定一个ab串。求所有的子序列满足：位置和字符都关于某条对称轴对称而且不连续。注释：$1\le n\le 10^5$。想法：看了大爷的题解，OrzOrz。因为对称轴可以是两个字符中间的位置，所以我们把字符串按照$Manacher$的形式...

2018-12-12

0 340

[bzoj1188][HNOI2007]分裂游戏_博弈论

分裂游戏 bzoj-1188 HNOI-2007 题目大意：题目链接。注释：略。想法：我们发现如果一个瓶子内的小球个数是奇数才是有效的。所以我们就可以将问题变成了一个瓶子里最多只有一个球球。设$sg(x)$表示位置为$x$的小球的$sg$值。显然通过$n^2$暴力转移即...

2018-12-12

0 333

[bzoj4131]并行博弈_博弈论

并行博弈 bzoj-4131 题目大意：题目链接。注释：略。想法：我们发现无论如何操作都会使得$(1,1)$发生改变。所以单个$ACG$的胜利条件就是$(1,1)$是否为黑色。如果为黑色那么可以让它变成白的。接下来无论对手如何操作都可以通过翻转$(1,1)$使得进入对手回合。 ...

2018-12-12

0 419