- 博客(191)
- 资源 (1)
- 收藏
- 关注
RSS订阅
原创 OI常见错误注意事项大汇总【不定期更新】
注意n,m的区别。long long数组1e7级别容易炸空间，注意数组的个数。多关键字排序时考虑清楚第二、第三关键字的顺序，它们往往更容易出错。三分时注意取等时的情况，最好特别考虑每次的边界。哈希最好使用双哈希或三哈希。图上遍历时不仅考虑点的遍历次数，还要考虑枚举边的复杂度。点分治要减去同一棵子树路径组合的答案。数论题与互质相关要特殊考虑1。看清模数是多少。需比较大小时不能取余。取余的同时要考虑到负数的情况。计数题乘上的数本身可能大于模数，本身需要先取余一次。DP记录状态判断当前状态
2020-12-04 20:32:32
347
原创 OI常见解题思路技巧大汇总【不定期更新】
典例JZOJ 6433. 【NOIP2019提高组正式赛day2】Emiya 家今天的饭&题解类型题中的限制条件为“若干种***中选取若干个， 保证每种不超过总数的一半”思路如果直接考虑递推转移，需要实时维护每种选择的个数，才能保证满足条件。但是可以想到，若有某种超过了一半，其它的则不可能超过一半，用总方案数减去不合法的，枚举哪一种超过了一半，需要记录当前选了多少个，以及不合法的这种选择了多少。典例JZOJ 6439. 【GDOI2020模拟01.17】小 ω 数排列&
2020-11-06 09:05:09
2076
5
原创 高考难度组合数学典型题选讲
前置知识从nnn个种选mmm个方案数=Cnm=C_n^m=Cnmnnn个与另nnn个任意配对方案数=n!=n!=n!基本原则熟悉基本模型，触类旁通理清逻辑，会分类讨论，不重不漏个人习惯整体列式组合算，部分可直接列举手算不使用排列数AAA，列式仅含组合数CCC和阶乘n!n!n!T1题目描述 在333双鞋中任取222只，恰好配对概率。法1 即总的符合条件情况除以总的可能情况。符合条件的有333种（三双鞋任意一双）情况，总的有C62=15C_6^2=15C62=15种，
2022-03-26 21:15:08
847
原创 JZOJ 7066. 【2021.4.24 NOI模拟】ehzeux与圆周（DP）
JZOJ 7066. 【2021.4.24 NOI模拟】ehzeux与圆周题目大意圆周上有2∗n2*n2∗n个点，两两相连构成nnn个点对，其中有mmm个点对已经连好，求所有方案下的连通块数量和。当两个点相连或所在线段相交则称之为属于同一个连通块。n,m≤300n,m\le300n,m≤300题解需要发现一个性质，把圆周展开成一条线段后和原来是一样的，并不会影响线段的连通。考虑把每种情况的连通块数量总和，转化为每个连通块出现的次数总和。设fi,jf_{i,j}fi,j为[i,j][i,
2021-04-28 22:05:30
289
原创 NOI2021 统一省选（A卷） Day2 T1 宝石（树上主席树+二分+倍增）
NOI2021 统一省选 Day2 T1 宝石题目大意大小为nnn的树上，每个点有一个权值wi≤[1,m]w_i\le[1,m]wi≤[1,m]，给出一个无重序列PPP，qqq组询问，每次求从xxx到yyy的最短路径的点权能从111开始对应序列PPP的多少位。n,q≤2∗105，m,∣P∣≤5∗104n,q\le2*10^5，m,|P|\le5*10^4n,q≤2∗105，m,∣P∣≤5∗104题解有一档m≤300m\le300m≤300的部分分，可以直接记录每个点向上权值为iii的点是哪
2021-04-20 21:55:34
516
原创 GDOI2021游记
Day -x众所周知，NOIP2020体验感不(jí)佳(chà)，区分度不大（但我还是被区分了）联赛省排208，校排45，赛季直接结束——感觉整个人从那时开始就对OI生涯的未来不报什么希望，一副颓废的样子Day -x广东省省选方式选择了A+B+C，也就是要记冬令营成绩，先送上2900元。WC分数也不是很高，水到了银牌，离前面的巨犇差的还远，加上联赛后省排87，校排29。Day -x省选竟然省二也可以报名了，不管怎么样还是去参加吧，也许这可能是我OI生涯最后一场比赛了。还记得我信
2021-04-09 09:43:15
1058
原创 JZOJ 7049. 2021.04.07【2021省赛模拟】生命游戏（拉格朗日插值+矩形面积并）
JZOJ 7049. 2021.04.07【2021省赛模拟】生命游戏题目大意二维平面网格中初始有nnn个点，每一时刻某一位置存在点当且仅当上一时刻相邻四格中存在点，QQQ次询问，求时刻000到时刻ttt平面上存在的点的总和。n≤100，Q≤106n\le100， Q\le10^6n≤100，Q≤106题解当只有一个点时，手玩一下可以发现，每一时刻ttt存在的点数为(t+1)2(t+1)^2(t+1)2。当有多个点时，坐标(xi+yi)(x_i+y_i)(xi+yi)奇偶性不同的点之
2021-04-08 14:59:07
211
1
原创 JZOJ 7047. 2021.04.07【2021省赛模拟】染色（计数+DP）
JZOJ 7047. 2021.04.07【2021省赛模拟】染色题目大意一个n∗mn*mn∗m的棋盘，一次染色可以把任何一行或任何一条左下-右上方向的对角线上所有格子都染黑，求各种染色方案可以得到的不同最终形态数。n,m≤500n,m\le500n,m≤500题解最终形态比较难统计，可以改为统计不同的染色方案。由于不同的染色方案可能会得到相同的最终形态，所以需要规定一些染色方案为“合法”的以保证不重复统计。可以让每种最终形态对应上唯一一种染色方案。具体的，使最终形态中有整行的必须由整行的
2021-04-07 20:49:15
184
原创 树链剖分之重链剖分 模板
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define N 100010#define ll long longint P;int a[N];int last[N], nxt[N * 2], to[N * 2], len = 0;int si[N], hv[N], fa[N], dp[N], dfn[N], tp[N];ll f[N * 4], bz
2021-04-06 15:52:47
98
原创 多项式求逆 模板
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define N 300000#define md 998244353#define ll long longll f[N], g[N], f0[N], g0[N];int rev[N];ll ksm(ll x, ll y) { if(!y) return 1; ll l = ksm(x, y / 2);
2021-04-06 11:39:27
125
原创 NTT快速数论变换 模板
#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;#define md 998244353#define N 4000010#define ll long longll a[N], b[N];int ns, p, rev[N];ll ksm(ll x, ll y) { if(!y) return 1; ll l =
2021-04-06 10:40:34
124
原创 拉格朗日插值 模板
#include<cstdio>#include<cstring>using namespace std;#define N 2010#define md 998244353#define ll long longstruct { ll x, y;}a[N];ll ksm(ll x, ll y) { if(!y) return 1; ll l = ksm(x, y / 2); if(y % 2) return l * l % md * x % md; ret
2021-04-06 09:55:20
109
原创 回文树 回文自动机 模板
#include<cstdio> #include<cstring>#include<algorithm>using namespace std;#define N 500010char st[N];struct { int len, fail, p[26], dp;}a[N];int tot = 1;int main() { int i, j; a[0].dp = a[1].dp = 0; a[0].len = 0, a[1].len = -
2021-04-06 09:52:58
140
原创 AC自动机 模板
#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;#define N 2000010#define M 3010queue<int> q;char st[N];struct { int p[26], s = 0, fail;}a[M * 10];int tot = 1;int main() { in
2021-04-06 09:51:31
104
原创 Treap 模板
#include<cstdio>#include<cstring>#include<cstdlib>#define N 100010using namespace std;int len=0,root=1;struct{ int v,s,l,r,si;}a[N];void update (int x){ a[x].si=a[a[x].l].si+a[a[x].r].si+1;}void split(int rt,int &x,int &
2021-04-06 09:49:55
83
原创 Splay（普通、区间翻转） 模板
Splay_普通#include<cstdio>#include<cstring>using namespace std;#define N 100010#define mn 1e+8struct{ int v[2]={0,0},s=0,x=mn,si,fa;}f[N];int len=1,root=1,n;void update(int x){ f[x].si=f[f[x].v[0]].si*(f[x].v[0]>0)+f[f[x].v[1]].si
2021-04-06 09:48:56
115
原创 JZOJ 7045. 2021.04.05【2021省赛模拟】数学考试（网络流）
JZOJ 7045. 2021.04.05【2021省赛模拟】数学考试题目大意给出nnn个三次函数，其中xix_ixi为第iii个函数的自变量，取值为[li,ri][l_i,r_i][li,ri]，另还需满足形如xa≤xb+dx_a\le x_b+dxa≤xb+d的mmm个限制，求∑fi(xi)\sum f_i(x_i)∑fi(xi)的最大值。n,∣li∣,∣ri∣≤100，m≤500n,|l_i|,|r_i|\le 100，m\le 500n,∣li∣,∣ri∣≤100，m≤50
2021-04-05 20:36:01
354
原创 UOJ Round #20 T1 A. 【UR #20】跳蚤电话（组合数+树形DP）
UOJ Round #20 T1 A. 【UR #20】跳蚤电话题目大意给出一棵树，求建出该树的不同操作方案数。建树方式如下：初始SSS集合只有111，操作111为取已连的边x,yx,yx,y和不在SSS的点zzz，删去边(x,y)(x,y)(x,y)，加入边(x,z),(y,z)(x,z),(y,z)(x,z),(y,z)，再把zzz放入SSS；操作222为取SSS内的点xxx和SSS外的点yyy，加入边(x,y)(x,y)(x,y)，再把yyy放入SSS。2≤n≤1052\le n \le 10
2021-04-05 19:59:50
277
原创 JZOJ 7039. 2021.04.01【2021省赛模拟】计数（推式子+DP）
JZOJ 7039. 2021.04.01【2021省赛模拟】计数题目大意给出n,m,xn,m,xn,m,x，定义一个序列的权值为min(l−x,0)min(l-x,0)min(l−x,0)，其中lll为最长连续段的长度。求所有长度为nnn且满足ai∈[1,m]a_i\in[1,m]ai∈[1,m]的正整数序列权值之和。x≤n≤106，k≤108x\le n\le10^6，k\le10^8x≤n≤106，k≤108题解首先很重要的一步是拆贡献，$min(l-x,0)=\sum_{i=x+1
2021-04-01 22:00:03
165
原创 JZOJ 7036. 2021.03.30【2021省赛模拟】凌乱平衡树（平衡树单旋+权值线段树）
JZOJ 7036. 2021.03.30【2021省赛模拟】凌乱平衡树题目大意给出两棵Treap，大小分别为n,mn,mn,m，每个点的priorityprioritypriority值为子树大小（因此满足大根堆性质），QQQ次修改（修改是永久的），每次单旋一个节点，求修改前和每次修改后后两树合并之后的所有节点深度之和。合并按照Treap的合并方式，左树根为xxx，右树根为yyy时，当sizex≥sizeysize_x\ge size_ysizex≥sizey时以xxx为根，否则反之。1≤n,
2021-03-31 16:51:02
171
原创 JZOJ 6085. 【GDOI2019模拟2019.3.26】要换换名字（二分+Trie+二分图匹配）
JZOJ 6085. 【GDOI2019模拟2019.3.26】要换换名字题目大意给出nnn个由小写字母组成的字符串，每个串用它的某个非空子序列替代它，求使得替代后所有串互不相同的最长串最小长度。若不存在则输出−1-1−1。1≤n,len≤3001\le n,len\le3001≤n,len≤300题解先二分答案，给每个串找出长度小于midmidmid的nnn个子序列，如果不足nnn个则找出所有子序列。任意找nnn个即可，因为只要有nnn个就能使得不出现重复。既然已经找出来了每个串替换为什
2021-03-31 16:06:03
181
原创 NOI Online 2021 #1 T3 岛屿探险（CDQ分治+Trie）
NOI Online 2021 #1 T3 岛屿探险题目大意nnn座岛屿编号为1−n1-n1−n，每个岛屿有两个值ai,bia_i,b_iai,bi。qqq次询问，给出l,r,c,dl,r,c,dl,r,c,d，求编号在[l,r][l,r][l,r]中的岛屿满足a⨁c≤min(b,d)a\bigoplus c\le \min(b,d)a⨁c≤min(b,d)的数量。n,q≤105，1≤a,b,c,d≤224−1n,q\le10^5，1\le a,b,c,d\le2^{24}-1n,q≤105，
2021-03-27 22:31:10
1250
4
原创 2018 ACM-ICPC World Finals Problem D. Gem Island（递推）
2018 ACM-ICPC World Finals Problem D. Gem Island题目大意有nnn个人，初始每个人手上有一颗宝石，每天等概率有一颗宝石变为两颗，求ddd天后宝石数最多的rrr个人的期望宝石总数。1≤n,d≤5001\le n,d\le5001≤n,d≤500，1≤r≤n1\le r\le n1≤r≤n题解首先通过手玩样例可以发现，最终的每种状态出现的次数都是相等的，均为d!d!d!次，不同的操作方案有n∗(n+1)∗...∗(n+d−1)n*(n+1)*...*
2021-03-18 19:56:03
350
原创 2016-2017 ACM-ICPC Northeastern European Regional Contest Problem C. Cactus Construction（仙人掌+构造）
2016-2017 ACM-ICPC Northeastern European Regional Contest Problem C. Cactus Construction题目大意初始有NNN个点互不联通，且颜色均为111，各自处于各自的只有一个点的集合中，给出三种操作方式：1、把集合xxx和集合yyy合并，但不连边；2、把xxx所在的集合中，所有颜色c1c1c1染成颜色c2c2c2；3、把xxx所在的集合中，任意一个颜色c1c1c1的点和任意一个颜色为c2c2c2的点之间连边，但不能连出重
2021-03-16 20:06:42
239
原创 JZOJ 6997. 2021.03.06【2021省赛模拟】排列（最小树形图）
JZOJ 6997. 2021.03.06【2021省赛模拟】排列题目大意ppp为一个111到nnn的排列，令F(p)=∑i=1nminj=1iapi⨁bpjF(p)=\sum_{i=1}^n \min_{j=1}^i a_{p_i}\bigoplus b_{p_j}F(p)=∑i=1nminj=1iapi⨁bpj，求使F(p)F(p)F(p)最小且字典序最小的ppp。n≤50n\le50n≤50题解若选择byb_yby和axa_xax构成一组贡献，则相当于从yyy往xxx
2021-03-10 21:38:06
216
原创 JZOJ 6653. 【2020.05.27省选模拟】树（权值线段树）
JZOJ 6653. 【2020.05.27省选模拟】树题目大意一棵以111为根大小为nnn的树，要求父亲编号小于儿子，2n−22n-22n−2个数，可任意分配使它们作为树的边权和每个点的父亲编号，求各种分配下111到nnn路径长度分别为[1,n)[1,n)[1,n)时路径的最大边权和。n≤105n\le10^5n≤105题解树的形态确定后，最大边权和自然为剩余未选的若干个数之和。统计每个数出现的个数cic_ici，求出前缀和，若存在sumi−1<i−1sum_{i-1}<i
2021-03-02 21:46:23
209
原创 JZOJ 6652. 【2020.05.27省选模拟】序列（贪心+序列翻转）
JZOJ 6652. 【2020.05.27省选模拟】序列题目大意问给出的NNN个MMM的排列，按从头到尾依次加到序列首或尾的规则，共同能得到的新排列的个数，并给出字典序最小的方案。询问有多组。T≤50，N,M≤1000，∑m≤5000T\le50，N,M\le1000，\sum m\le5000T≤50，N,M≤1000，∑m≤5000题解先加入队列的数位置不好确定，但最后加入的数一定只能再两端，不妨考虑从后往前推。这样一来每个时刻已经构成的排列是一段前缀和一段后缀，记录指针Li,Ri
2021-03-02 21:15:07
261
原创 JZOJ 6979. 【2021.02.03冬令营模拟】天各一方（DP）
JZOJ 6979. 【2021.02.03冬令营模拟】天各一方题目大意求nnn个点组成的所有不同连通图中，111到nnn的最短距离之和。n≤400n\le400n≤400题解很关键的一点是，因为是所有连边的方案，所以111到nnn和111到222、111到333……111到n−1n-1n−1本质上都是相同的，所以答案可以转化为111到剩下每个点的最短距离之和再除以n−1n-1n−1。试着把所有的点分层，距离即为它们层数的差值。初始时均在第000层，通过DP使除了111以外所有点下移
2021-02-04 09:27:40
207
1
原创 JZOJ 6974. 【2021.02.01冬令营模拟】联邦解体（拆绝对值+DP）
JZOJ 6974. 【2021.02.01冬令营模拟】联邦解体题目大意长为nnn的原序列中每个数有两个权值Ai,BiA_i,B_iAi,Bi，求保持相对顺序不变的前提下，把原序列分割为两个子序列后所有相邻两项的A,BA,BA,B权值之差的绝对值之和的最大值。n≤106n\le10^6n≤106题解既有绝对值，又要求最大值，考虑到若不取绝对值的话，一定不会比真实答案更优，所以可以去掉绝对值号，而只需保证相邻两项的AAA或BBB对答案的贡献符号相反，注意这里的贡献并不是每个数只贡献一次，而
2021-02-04 08:29:41
208
1
原创 GDKOI 2021 提高组 Day2 第三题 抄写（manachar+线段树维护DP）
GDKOI 2021 提高组 Day2 第三题 抄写题目大意要求按顺序写完一段小写字母组成的长为nnn的字符串，可以直接添加一个字符iii，代价为cic_ici，也可以用当前末尾的部分轴对称，代价为CCC，求最小代价。n≤106n\le10^6n≤106题解先考虑n2n^2n2的DP转移，fi=min(fi−1+ci,fj+C)f_i=min(f_{i-1}+c_i,f_j+C)fi=min(fi−1+ci,fj+C)，其中jjj是能作为对称轴的位置，可以用manachar预处理，
2021-02-01 22:04:24
172
原创 GDKOI 2021 提高组 Day2 第二题 群岛（线段树）
GDKOI 2021 提高组 Day2 第二题 群岛题目大意nnn个点，每个点iii只有连向i+1i+1i+1和aia_iai两条出边，mmm次操作，支持修改aia_iai，询问点xxx能到达的编号最小的点。n,m≤105n,m\le10^5n,m≤105题解显然ai≥ia_i\ge iai≥i是没有用的。考虑某个点xxx会以何种方式走向最优的点，不失一般性地，一定是先往右走若干格，再通过axa_xax走向较小的点，然后如此循环重复。这个过程中会使用多若干组(i,ai)(i,a_
2021-01-31 21:48:38
158
原创 GDKOI 2021 提高组 Day2 第一题 游戏（解方程）
GDKOI 2021 提高组 Day2 第一题 游戏题目大意从000颗星开始到nnn颗星结束，有iii颗星时，会有xix_ixi的概率升星，1−xi1-x_i1−xi概率降星，iii为000时则保持不变，求到达nnn颗星的期望步数。n≤106n\le10^6n≤106题解根据期望的线性性，可以分别求出每个从iii到i+1i+1i+1的期望步数，然后全部相加即为答案。当i=0i=0i=0时，可以列出方程：p0=x+(1−x)(1+p0)p_0=x+(1-x)(1+p_0)p0=x+(
2021-01-31 21:18:00
193
2
原创 GDKOI 2021 提高组 Day1 第三题 回文（manachar+ST表）
GDKOI 2021 提高组 Day1 第三题 回文题目大意给出长为nnn的串，和qqq组询问，每次询问区间中的最长回文串。n,q≤5∗105n,q\le5*10^5n,q≤5∗105题解可以先用manachar求出以每个位置为中心的回文串，询问时二分答案，然后在区间中判断是否存在长度为midmidmid的回文串，用ST表维护区间最值。注意二分判断时并非在整个区间[l,r][l,r][l,r]中找最大值，而需分别将左端点右移和右端点左移大约midmidmid（因奇偶而不同）的位置，以保证找
2021-01-31 20:54:19
178
原创 GDKOI 2021 提高组 Day1 第一题 割（贪心+二分图染色）
GDKOI 2021 提高组 Day1 第一题 割题目大意给出一种方案使nnn个点mmm条边分成两部分，两部分之间的边数≥m2\ge\frac{m}{2}≥2m。n≤105,m≤2∗105n\le10^5,m\le2*10^5n≤105,m≤2∗105题解没用的边删去后，剩下的部分是一张二分图，考虑贪心染色。DFS的过程中，每到一个未染色的点，统计与它相邻的点的颜色，将它自己染为较少的那种，令这些点有sss个，即边共sss条，这样可以保证连出的边≥s2\ge\frac{s}{2}≥2s
2021-01-31 20:39:11
161
原创 JZOJ 6958. 【2020.01.23冬令营模拟】国内战·剑鬼·魔法阵（环套树+结论）
JZOJ 6958. 【2020.01.23冬令营模拟】国内战·剑鬼·魔法阵题目大意nnn个点构成的若干棵环套树上，两人依次选边，要求不能与已选的构成环，两人分别尽可能最大化/最小化最终的边权和，直到两人都不能选为止，问此时选出的边权和。n≤105n\le10^5n≤105题解这是一道结论题，其实结论很好猜，但不好证。首先，不在环上的边是一定会被选上的，只用考虑环上的边。手玩一下奇环会发现，把边权排序后，两人为了对自己最有利总会对称地选，所以会剩下中间的边没选；而偶环类似地可以猜想，最
2021-01-31 20:20:57
217
2
原创 JZOJ 6957. 【2020.01.19冬令营模拟】板凳（前缀和+二分）
JZOJ 6957. 【2020.01.19冬令营模拟】板凳题目大意长为mmm的序列，初始有若nnn位置为111，其余为000，每次找到最长且靠左的一段全000序列，将该段中间位置修改为111，qqq次询问求第xxx次修改的位置。n,q≤105n,q\le10^5n,q≤105，m≤1014m\le10^{14}m≤1014题解首先要发现一个重要的性质，每个段中间位置修改后会被分成两段，尽管这两段长度可能相差111，但这两段再继续分割下去每一层的长度也只有两种可能的取值，也就是不同的段长最多
2021-01-28 21:50:56
98
原创 JZOJ 6944. 【2020.01.07冬令营模拟】球（数学计算）
JZOJ 6944. 【2020.01.07冬令营模拟】球题解发现数据很良心，区间坐标都是非负数，避免了更多的分类讨论。把区间拆开考虑， 发现在对角线y=xy=xy=x两侧都满足每行/列分别单调，如果在某一侧框出一个矩形，可以用等差数列求和直接解决。同时对角线上的可以用平方和计算，但对角边旁构不成矩形的部分如何解决？又发现可以把对角线所经过部分框出一个正方形，分层后每一层都可以用一个最高次为三次的多项式求和计算，直接用立方和公式和平方和公式，那么这样剩下的部分都分居对角线两侧，用上述的方法。至
2021-01-07 21:49:06
184
原创 JZOJ 6943. 【2020.01.05冬令营模拟】社会实践（线段树）
JZOJ 6943. 【2020.01.05冬令营模拟】社会实践题解题目的原型还是汉诺塔问题，操作规则和普通汉诺塔问题是一样的，先考虑对于某个单独询问如何计算最优答案。按普通汉诺塔，考虑还原的过程，发现根本不知道下一步该如何移动，无法解决，但如果从还原好的状态倒推，每一步移动都是自然的，初始所有圆盘都在最大圆盘应回到的柱子，然后从大到小，如果第iii个已复位则忽略， 否则将剩下i−1i-1i−1个移到第三根柱，再移动第iii个，步数为2i−12^{i-1}2i−1。这样移动可以保证时刻都是合法的。
2021-01-07 21:35:33
149
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人