JZYshuraK

分类

未归档(392)

/ 注册

全部文章（共392篇）

THUPC2017看题总结

THUPC2017 看题总结 #2402. 「THUPC 2017」天天爱射击 / Shooting 果题。求当前子弹能会使多少块木板损坏，发现因为木板会随着子弹数目的增加而更加容易损坏，故此询问具有单调性。而后又发现可以离线，考虑整体二分。每次用一个\(solve(x,y,l,r)...

2019-04-17

0 618

THUPC2018看题总结

THUPC2018看题总结 #6387. 「THUPC2018」绿绿与串串 / String 据说是签到题啊。首先根据题目的意思，我们发现如果能找到那个最后一次选择的对称轴岂不是美滋滋。自然地，我们先发掘发掘那个对称轴需要具备哪些性质。发现如果对原串做\(Manacher\)的话，对...

2019-04-15

0 513

[bzoj4199][Noi2015]品酒大会_后缀自动机_后缀树_树形dp

品酒大会 bzoj-4199 Noi-2015 题目大意：给定一个字符串，如果其两个子串的前$r$个字符相等，那么称这两个子串的开头两个位置$r$相似。如果两个位置勾兑在一起那么美味度为两个位置的乘积。注释：$1\le length \le 3\cdot 10^5$。想法：我们先建立后...

2019-03-15

0 614

[bzoj3998][TJOI2015]弦论_后缀自动机

弦论 bzoj-3998 TJOI-2015 题目大意：给定一个字符串，求其$k$小子串。注释：$1\le length \le 5\cdot 10^5$，$1\le k\le 10^9$。想法：后缀数组***题。初学后缀自动机我们尝试用后缀自动机解决。首先先建出$SAM$...

2019-03-15

0 388

[bzoj2780][Spoj8093]Sevenk Love Oimaster_广义后缀自动机

Sevenk Love Oimaster bzoj-2780 Spoj-8093 题目大意：给定$n$个大串和$m$次询问，每次给出一个字符串$s$询问在多少个大串中出现过。注释：$1\le n\le 10^4$，$1\le q\le 6\cdot 10^4$，$the\ total\ len...

2019-03-15

0 461

[bzoj2595][WC2008]游览计划/[bzoj5180][Baltic2016]Cities_斯坦纳树

游览计划 bzoj-2595 wc-2008 题目大意：题目链接、题目连接。注释：略。想法：裸题求斯坦纳树。斯坦纳树有两种转移方式，设$f[s][i]$表示联通状态为$s$，以$i$为根的最小代价。第一个转移就是$f[s][i]=f[t][i]+f[s-t][i]$。这个显然但...

2019-03-15

0 495

[bzoj4006][JLOI2015]管道连接_斯坦纳树_状压dp

管道连接 bzoj-4006 JLOI-2015 题目大意：给定一张$n$个节点$m$条边的带边权无向图。并且给定$p$个重要节点，每个重要节点都有一个颜色。求一个边权和最小的边集使得颜色相同的重要节点互相连通。注释：$1\le c_i \le p \le 10$，$1\le u_i,v_i,...

2019-03-15

0 590

OI模板のpoke流[大型考试复习必备/kl]

数论快速乘： ll qmul(ll x,ll y,ll mod) { ll ans=0; while(y) { if(y&1) (ans+=x)%=mod; y>>=1; (x+=x)%=mod; } return ans; } 快速幂：...

2019-02-15

0 526

[bzoj2453]维护队列_带修改莫队

维护队列 bzoj-2453 题目大意：给定一个n个数序列，支持查询区间数的种类数，单点修改。不强制在线。注释：$1\le n,m\le 10^5$。想法：带修改莫队裸题。如果没有修改操作的话，我们就正常按照莫队一样左右移动区间即可。有了修改操作的话，我们把块变成$n^{\...

2019-02-07

0 424

[bzoj4519][Cqoi2016]不同的最小割_网络流_最小割_最小割树

不同的最小割 bzoj-4519 Cqoi-2016 题目大意：题目链接。注释：略。想法：我们发现这和最小割那题比较像。我们依然通过那个题说的办法一样，构建最小割树即可。接下来就是随便怎么处理都行了。我们可以弄一个数组把枚举到的距离都记录下来即可。 Code： ...

2019-01-09

0 436