wyxdrqc

未归档

题解(3)

/ 注册

全部文章 / 未归档（共64篇）

CDQ分治小结

CDQ分治小结 P3810三维偏序（陌上花开) 一道CDQ分治的比较模板又不是模板的问题. 设\(f_i\)表示\(a_j<=a_i\)且\(b_j<=b_i\)且\(c_j<=c_i\)的\(j\)的数量对于\(d\in[0,n)\)让你求\(f(i) == d\)的数...

2019-05-12

0 507

SDOI2019热闹又尴尬的聚会

P5361 [SDOI2019]热闹又尴尬的聚会出题人用脚造数据系列只要将\(p\)最大的只求出来,\(q\)直接随便rand就能过真的是我们说说怎么求最大的\(p\)，这个玩意具有很明显的单调性的吧直接二分一下\(p\)的值,然后将其和他所以相连的所有度数\(>=p\)加...

2019-05-11

0 494

P5358 [SDOI2019]快速查询

P5358[SDOI2019]快速查询和当初对一轮D2T2有着同样的感觉吧,省选上最应该做出来的一道题(菜永远是原罪) 首先对于\(50\%\)的数据,我们可以直接线段树过去但是,我们发现除了单点赋值和查询以外,其他的操作都是对全局进行的操作虽然元素有\(10^9\)个,但是,操作也最多只有...

2019-05-08

0 341

luoguP2679 子串

luoguP2679 子串个人感觉\(noip\)系列中挺好的一道DP题目. 题面有点难理解. 我们设\(f_{i,j,k,0/1}\)表示\(A\)串前\(i\)个字符,匹配\(B\)串前\(j\)个字符,正在用第\(k\)的子串,且第\(i\)个字符选或者不选的方案数则有\(f_{i...

2019-05-03

0 464

Educational Codeforces Round 63部分题解

Educational Codeforces Round 63 A 题目大意就不写了. 挺简单的,若果字符本来就单调不降,那么就不需要修改否则找到第一次下降的位置和前面的换就好了. #include<iostream> #include<cstdio> #incl...

2019-05-03

0 450

Educational Codeforces Round 64部分题解

Educational Codeforces Round 64部分题解 A 题目大意:给定三角形(高等于低的等腰),正方形,圆,在满足其高,边长,半径最大(保证在上一个图形的内部)的前提下. 判断交点个数是否有限,如果有限,输出. 很明显当正方形套三角形或者三角形套正方形是交点个数是无限的(...

2019-05-02

0 442

[十二省联考2019]春节十二响

[十二省联考2019]春节十二响考场上最简单的一道题,可惜我没有想到合并(明明链都打出来了) 直接维护堆的启发式合并就好了 #include<cstdio> #include<cstring> #include<iostream> #include<...

2019-04-28

0 510

[十二省联考2019]异或粽子

[十二省联考2019]异或粽子先吐槽一下,在考场上完全没有将这道题和超级钢琴联系起来,然后\(GG\),喜提\(60\)走人赛后听说直接上可持久化\(Trie\)用堆维护就好了然后自己回来又打开了超级钢琴. 这道题就有思路了很明显,这道题我们可以利用前缀和优化到最大的\(k\)...

2019-04-28

0 416

二维数点问题

二维数点问题二维数点在OI中有着广泛的应用,很多题目正解或其部分分都可以转化为二维数点的模型. 一般性的静态二维数点问题: 给出平面上的\(n\)个点的坐标\(P_i(x_i,y_i)\),\(Q\)次查询,每次查询\((a,b,c,d)\),表示,求在矩形\((a,b),(c,d)\)中的...

2019-04-04

1 1658

后缀数组复习笔记

[后缀数组复习笔记] 首先推荐一篇写的非常好的Blog,本文中部分内容也会选自该博客。个人认为后缀数组的核心内容其实就是对\(2^x\)的字符串按照\(2^{x - 1}\)求出的第一第二关键字进行排序.然后进而一步一步对数组进行排序. 所以要用到基数排序：基数排序在后缀数组中可以在\(...

2019-04-03

0 526