Master.Yi-CSDN博客

原创满脸心酸泪的改错本

本人（蒟蒻）几经风(WA) 风(dao) 雨(zi) 雨(bi)，列出如下巨坑： 1.循环顺序出错（区间DP）。 2.数组定义小了，题目（迷宫，线段树，链接字符串，数组两边循环，主席树）给的n,m并不是实际真正储存的大小。计算的时候一定小心，并且做完要检查。 3.设边界的时候一定要注意，画个草图出个简单数据模拟一下，少一多一都是无尽的懊悔。 4.<还...

2016-11-23 13:41:40 1378

原创 C++ 五子棋面向对象实现

C++写五子棋对弈程序，面向对象实现。

2022-02-28 19:43:40 1026 1

大一了…又开始学程设基础（梦回初一）发现打了几年的题基本没怎么用过指针，就来写写指针版的链表…结果被恶心坏了开始写的时候没在首尾插入一个极小极大值，然后插入删除的时候就要特判好多开头结尾的空指针…后来突然想到以前做Splay的时候的方法…插个极小极大值…瞬间和谐了100倍。。#include<cstdio>struct link{ int id,val; link *pre,*nxt; link(int id=0,int val=0,link *pre=0,l

2021-12-23 00:28:24 345 1

原创 Vscode的简单配置

先到官网https://code.visualstudio.com/下个Vscode然后找个地方https://www.jianshu.com/p/ee1ccb0a3062下一个Mingw（如果有其他IDE的话就不用了）下了Mingw之后把bin添加到环境变量Path里面。（此电脑 -> (右键)属性 -> 高级系统设置 -> 环境变量 -> Path -> 添加路径）然后需要一些插件：Chinese(simplified)转成中文C/C++Code Runner

2021-11-07 18:10:54 1519

原创 UOJ#554【UNR #4】挑战哈密顿【找哈密顿路径（调整法）】

题目描述Link提交答案题给一个有向图，求最长的不经过重复点和边的路径，保证无重边自环。题目分析直接看官方题解咯在做了点三染色使得没有同色边的问题后，我们学到了提交答案题的姿势：调整法，找一个不会使答案变劣，并且可以一直进行下去的调整方法。（如果进入死胡同就重来）在这道题上，就是按随机顺序考虑加边，然后维护一个链的集合，每次考虑合并两条链，或者替换一条边。写的过程中遇到一些问题：暴力判断是否会成环的版本：跑得很慢，基本卡卡地才跑完一次检验。发现是在走路径之前没有判断是否两个点都有入

2020-08-14 20:23:57 512

原创 UOJ#553【UNR #4】己酸集合【计算几何(圆内数点→半平面数点)】

题目描述Link二维平面 nnn 个点 (xi,yi)(x_i,y_i)(xi,yi)，QQQ 次询问距离 (0,z)(0,z)(0,z) 小于等于 RRR 的点的数量。n≤12000,Q≤106,∣xi∣,∣yi∣,∣zi∣,R≤109n\le12000,Q\le10^6,|x_i|,|y_i|,|z_i|,R\le10^9n≤12000,Q≤106,∣xi∣,∣yi∣,∣zi∣,R≤109题目分析x2+(y−z)2≤R2x^2+(y-z)^2\le R^2x2+(y−z)2≤R2x

2020-08-13 20:03:52 475

原创 UOJ#551【UNR #4】校园闲逛【多项式好题（雾）】

题目描述Linknnn 个点 mmm 条边的无向带权图，1≤1\le1≤ 边权 ≤V\le V≤V，QQQ 次询问，从 xxx 到 yyy 有多少条权值和为 www 的路径，路径可以经过重复边和重复点。1≤n≤8,0≤m≤3∗105,1≤V≤65000,0≤Q≤100001\le n\le 8, 0\le m\le 3*10^5,1\le V\le65000,0\le Q\le 100001≤n≤8,0≤m≤3∗105,1≤V≤65000,0≤Q≤10000题目分析暴力 DP：dp[i][j][v

2020-08-13 08:01:42 350

原创 20200810 T2 Dispatch Money【区间逆序对，分治套分治解决决策单调性】

题目描述给一个长度为 nnn 的排列 aia_iai，把它划分为若干段，每划分一段有 XXX 的代价，划分完后段内需要排序，代价为区间逆序对个数。求最小总代价。n≤300000,1≤X≤109n\le 300000,1\le X\le 10^9n≤300000,1≤X≤109时限 5s.题目分析暴力 O(n2)O(n^2)O(n2) DP：fi=fj+inversion_pair(j+1,i)f_i=f_j+inversion\_pair(j+1,i)fi=fj+inversion_pair

2020-08-10 19:12:28 380

原创 20200802 T3 我永远喜欢【生成函数容斥，拉格朗日反演】

题目描述有 nnn 种颜色的石子，每种 cic_ici 个，记一个石子序列首尾相接后极长连续段的长度为 lil_ili，求所有石子序列的 1∏li!\frac 1{\prod l_i!}∏li!1 的和。n≤105,∑ci≤2∗105n\le10^5,\sum c_i\le2*10^5n≤105,∑ci≤2∗105题目分析先考虑去掉首尾相接的情况怎么做。因为限制了极长，容易想到把每种颜色分成几段，然后合并，但是不好保证相同颜色不被并在一起。先不谈容斥做法，题解给出了一种用生成函数解决的

2020-08-09 20:49:41 285

原创 WC2020 选课

题目描述LOJ3331题目分析把有限制的分类的和没有限制的分类分开考虑。令 X=T−∑siX=T-\sum s_iX=T−∑si没有限制的分类，求出 f[i][j],j∈[si,si+X+2]f[i][j],j\in[s_i,s_i+X+2]f[i][j],j∈[si,si+X+2]，表示第 iii 中分类获得至少 jjj 学分需要的最少脑力值，大于 si+X+2s_i+X+2si+X+2 的部分是没有用的，因为必然可以少学一门课程使答案更优。然后把它们合并，求出 f′[j],j∈[s′

2020-08-09 19:21:43 367

原创 2020080模拟赛【横纵坐标互不影响，仙人掌最小割，组合意义翻译式子】

T1 这把我们就遇到了高手了题目描述X∗YX*YX∗Y 的环形网格（左边和右边连通，上边和下边连通）。给出 nnn 个矩形的左下和右上点对，每个矩形可以选择四种方式之一摆放：求 nnn 个矩形能同时覆盖的最大面积。样例：题目分析乍一看非常不可做。仔细思考/打完暴力感觉这个矩形的形式非常的美妙。恰好是4种方式，横纵坐标各2种。这启示我们可以把横纵坐标分开看，然后把两个的最优答案乘起来。然后问题就变成了一维的，每个矩形变成一条线段，把数轴划分成很多段。那么每段有一个状态，对应每个矩

2020-08-09 17:31:29 284

原创 WC2020 猜数游戏

题目描述LOJ3330题目分析若存在 kkk 使得 ak≡b(modp)a^k\equiv b\pmod pak≡b(modp)，则 aaa 向 bbb 连一条边。那么一个点在一个集合里面要被选的条件就是集合中不存在另一个点能够到达它（把环缩成点，每个环要被选的方案数是 2环大小−12^{环大小}-12环大小−1），那么所有方案选择的点数之和就是 ∑某个环2n−(可到达这个环的点数)∗(2环大小−1)\sum_{某个环} 2^{n-(可到达这个环的点数)}*(2^{环大小}-1)∑某个环2n−(可

2020-08-08 20:40:39 224

原创二次剩余学习笔记

水平时间有限，只考虑 ppp 为奇质数的情况。x2≡n(modp)x^2\equiv n\pmod px2≡n(modp)浅谈二次剩余链接里的证明讲得很好。判定 n∈[1,p−1]n\in[1,p-1]n∈[1,p−1] 是否是二次剩余的方法：如果不存在 x2≡n(modp)x^2\equiv n\pmod px2≡n(modp)，则 np−12≡−1n^{\frac {p-1}2}\equiv -1n2p−1≡−1；如果存在，则 np−12≡(n)p−1≡1n^{\frac {p-1}2}\eq

2020-08-05 18:19:42 206

原创 20200803 T3 我的朋友们【分治NTT优化递推】

题意描述Lynn 要买新发卡，拉上了君儿和薇帮她参考。可供选择的发卡总共有 nnn 个。Lynn 会问很多次君儿某个发卡是否适合 Lynn。由于君儿沉迷于她的数竞习题，所以某一次 Lynn 问她第 iii 个发卡是否适合 Lynn 的时候，她有 1−pi(0<pi<1)1-p_i(0<p_i<1)1−pi(0<pi<1) 的概率会告诉 Lynn “这个发卡很适合你”，有 pip_ipi 的概率告诉 Lynn “这个发卡一点也不适合你”。因为君儿太沉迷了，所以两

2020-08-03 23:01:31 397

原创矩阵树定理

求生成树边权之积的和普通：度数矩阵 - 邻接矩阵树形图：内向树（指向根，根出度为0）：出度矩阵 - 邻接矩阵外向树（根往外，根入度为0）：入度矩阵 - 邻接矩阵

2020-08-02 15:17:06 188

原创 NOI linux如何在Gedit里快速编译运行

如何在 Gedit 里快速编译运行首先勾选首选项中的外部工具：添加之后取名，设置快捷键。然后在旁边的框里面输入 Shell 指令。Code：（Complie and Run）#!/bin/shfullname=$GEDIT_CURRENT_DOCUMENT_NAME//获取文件全名 1.cppdir=$GEDIT_CURRENT_DOCUMENT_DIR//获取目录名name=`echo $fullname | cut -d. -f1`//获取文件名 1，注意这些赋值操作等号前面不

2020-08-01 12:03:38 905

原创 Djikstra解决带负权最短路

这篇blog讲得超好每个点设个势函数 hih_ihi，并令新图的边权 wi,j′=wi,j+hi−hjw'_{i,j}=w_{i,j}+h_i-h_jwi,j′=wi,j+hi−hj，要求 wi,j′≥0w'_{i,j}\ge 0wi,j′≥0原图 1→n1\to n1→n 的最短路等于新图 1→n1\to n1→n 的最短路减去 h1−hnh_1-h_nh1−hn如何维护 hih_ihi：对 hih_ihi 的要求是对于任意有流量的边 (i,j)(i,j)(i,j)，hi+wi

2020-07-31 22:38:02 162

原创 20200730 T3 小B的农场【最大周长空矩形 (单调栈+线段树)】 && 「ROI 2017 Day 2」学习轨迹

小B的农场题目描述n≤3∗105n\le3*10^5n≤3∗105题目分析n2log⁡nn^2\log nn2logn 的做法是枚举左边界，右边界从大到小枚举，维护中点 yyy 轴相邻两点差的最大值，删掉一个点时加入它上下相邻两点的差，双向链表实现。nlog⁡nn\log nnlogn 做法：因为是整点，答案至少为 2∗(max⁡(W,H)+1)2*(\max(W,H)+1)2∗(max(W,H)+1)，所以答案矩形一定经过 x=W2x=\frac W2x=2W 或 y=H2y=\frac

2020-07-30 16:10:20 456

原创 20200727 T2 小w玩游戏【生成函数(二项式反演技巧)】

题目描述题目分析设有 iii 行选了奇数次的方案数为 fif_ifi，jjj 列选了奇数次的方案数为 gjg_jgjAns=∑im+jn−2ij≤kfi∗gjAns=\sum_{im+jn-2ij\le k} f_i*g_jAns=∑im+jn−2ij≤kfi∗gjfi=q![xq](ex−e−x2)i(ex+e−x2)n−i(ni)f_i=q![x^q](\frac {e^x-e^{-x}}2)^i(\frac {e^x+e^{-x}}2)^{n-i}\binom nifi=q!

2020-07-29 21:01:32 291

原创 Nim积

下面几张图是引入，截自2009年论文《从“k倍动态减法游戏”出发探究一类组合游戏问题》翻转四个格子。设 SG(x,y)=x⊗ySG(x,y)=x\otimes ySG(x,y)=x⊗yx⊗y=mex{(a⊗y)⊕(x⊗b)⊕(a⊗b) ∣ 0≤a<x,0≤b<y}x\otimes y=mex\{(a\otimes y)\oplus(x\otimes b)\oplus(a\otimes b)~|~0\le a<x,0\le b<y\}x⊗y=mex{(a

2020-07-29 20:38:55 329

原创 20200726 T3 树高【ETT(dfs序splay)维护同色边连通块】

题目描述n,m≤105n,m\le10^5n,m≤105，点的颜色范围为 [1,30][1,30][1,30]题目分析LCT可以维护黑白两色，黑点向父亲连边，实际连通块去掉根。但是整个连通块同时变色就不好整了。用ETT（就是dfs序splay）维护边连通块，这样改变颜色的时候只会改变这条边与上下的连通性。初始时看做同一种颜色，按dfs序建树，splay点标对应原树点标。一个边连通块为一棵以dfs序为关键字的 splay。上图中同一种颜色的箭头指向的节点在同一棵 splay 中。（link

2020-07-28 09:54:07 286

原创 20200727 T3 小w维护序列【平衡树预留插入位置+三维数点】

题目描述题目分析先考虑没有插入删除的情况。区间不同的数有个常见的 trick 是把它表示为二维的点 (prei,i)(pre_i,i)(prei,i)，区间查询就变成数第一维在 [0,l−1][0,l-1][0,l−1]，第二维在 [l,r][l,r][l,r] 的点。修改就是去掉原来的点，加入新的点，可以用 map 套 set 维护。（离散化好麻烦，复杂度也没区别）询问一也可以通过简单的处理把不同点之间的贡献分离开：那么这就是一个三维数点问题，cdq分治即可。（学到一个树状数组套树状数组

2020-07-27 21:26:54 221

原创 20200726 T1 钩子【概率DP】

题目描述n≤1000n\le 1000n≤1000题目分析假设前面的人已经选好了，把序列分成了 MMM 段。记每段中点到两边的距离为 ddd，把 ddd 最大的 mmm 段提出来。不难发现，如果这 mmm 段的 d>1d>1d>1，那么剩下的 mmm 个人一定会选在这 mmm 段的中点。（d=1d=1d=1 的情况就是每个人落在每个位置的概率都相等，特判）。把这 mmm 个人一起处理。如果某一段的长度为奇数，那么只能选在中点；如果某一段的长度为偶数，那么有两个点可以选。如果

2020-07-26 17:21:56 144

原创 20200725 T3 sort【区间异或，区间排序，平衡树 + trie】

题目描述长度为 nnn 的序列，0≤ai<2320\le a_i<2^{32}0≤ai<232要求支持区间与，区间或，区间异或，区间排序。输出最终的 aaa 序列。n,m≤105n,m\le10^5n,m≤105题目分析ai<16a_i<16ai<16 的时候可以线段树维护每种数的个数，排序的时候提取每种数然后区间赋值。看似是 log3log^3log3 实际上却跑得很快，（可能有些数没有；赋值时的pushup可以小常数memset）正解：平衡树维护

2020-07-26 16:40:20 469 1

原创 20200723 T3 图【平面图环内点数】(CF223E Planar Graph)

题目描述给一张连通平面图，每次询问给出一个环（由给出的点组成），问环内的点数n≤105,m≤3∗105,∑circle≤3∗105n\le10^5,m\le3*10^5,\sum circle\le3*10^5n≤105,m≤3∗105,∑circle≤3∗105题目分析写完代码受到精神污染的我直接截Freopen的图进入环的点 = 父边连到环上的在环外的点的子树大小出环的点个数 = 父边在环外的环上的点的子树大小当前后两条边的极角区间跨越Pi时，用全集减去补集会好算很多。写完之后看Sh

2020-07-23 19:41:51 385

原创 20200723 T1 数【推式子】

题目描述对 m∈[0,n]m\in[0,n]m∈[0,n] 求 ∑i=0nai∑j=0n(−1)j(mj)(n−mi−j)\sum_{i=0}^na_i\sum_{j=0}^n(-1)^j\binom mj\binom {n-m}{i-j}i=0∑naij=0∑n(−1)j(jm)(i−jn−m)题目分析mmm 个里面选 jjj 个，每选一个有 −1-1−1 的系数，(1−x)=2−(1+x)(1-x)=2-(1+x)(1−x)=2−(1+x)：∑i=0nai[xi](1−x)m(1+x)

2020-07-23 16:10:43 165

原创 CF1019E Raining season【半平面交转凸包，边分治】

题目描述一棵树，nnn 个点，每条边有权值 (ai,bi)(a_i,b_i)(ai,bi) ，表示在 ttt 时刻这条边的值为 ait+bia_it+b_iait+bi问对于 t∈[0,m−1]t\in[0,m-1]t∈[0,m−1]，树的直径长度。n≤105,m≤106n\le10^5,m\le10^6n≤105,m≤106题目分析与最长路径有关，考虑点分治。每个子树内的一条到点分中心的路径求和表示为一条射线 At+BAt+BAt+B。子树内的所有路径要求一个下凸形式的半平面交，但是

2020-07-22 21:36:30 168

原创 20200722 T3 积木【可重集排列转组合数路径方案DP】

题目描述1e8+71e8+71e8+7，两堆，不是两堆以及之间的和。n≤200000,ai,bi,ci≤150n\le200000,a_i,b_i,c_i\le 150n≤200000,ai,bi,ci≤150题目分析可重集排列，表示为(ai+aj+bi+bj+ci+cjai+aj,bi+bj,ci+cj)=(ai+aj+bi+bj+ci+cjai+aj+bi+bj)∗(ai+aj+bi+bjai+aj)\binom {a_i+a_j+b_i+b_j+c_i+c_j}{a_i+a_j,b

2020-07-22 18:55:09 189

原创 20200722 T2 ACT4！无限回转！【辛普森积分】

题目描述nnn 个点的凸多边形，逆时针方向给出，在内部随机一个起点，随机一个方向，一直往这个方向走直到碰到某一条边。求每条边被碰到的概率。n≤1500,∣xi∣,∣yi∣≤104n\le 1500,|x_i|,|y_i|\le 10^4n≤1500,∣xi∣,∣yi∣≤104题目分析对于第 iii 条边，求它被碰到的概率。随机过程有两个，一个是坐标，一个是角度，考虑积分，最后除以 (面积∗2π*2\pi∗2π)直接按坐标积分 dx,dydx,dydx,dy，用 atanatanatan 求角

2020-07-22 18:50:25 211

原创 20200713 T1 集合划分(JOISCD1T1)【多项式优化DP】

题目描述长度为 2n2n2n 的 {Ai},{Bi}\{A_i\},\{B_i\}{Ai},{Bi} 序列，现在要选出一个新序列 {Ci}\{C_i\}{Ci}，其中 Ci=AiC_i=A_iCi=Ai 或 Ci=BiC_i=B_iCi=Bi要求 Ci≤Ci+1C_i\le C_{i+1}Ci≤Ci+1，且选择的 AAA 的个数恰为 nnn 个，问方案数，方案不同当且仅当某个位置的选择不同。n≤5∗104,mod 998244353n\le 5*10^4,\mod 99824435

2020-07-22 16:40:37 250

原创 20200721 T1 s1mple【容斥，划分】

题目描述n≤17,q≤105n\le17,q\le10^5n≤17,q≤105题目分析先不考虑0的限制，相当于强制一些链连通，其它任意，这样很多排列状态就变成了本质相同的划分方案。Code：#include<bits/stdc++.h>#define maxn 17#define LL long longusing namespace std;int n,N,Q,lg[1<<maxn],bit[1<<maxn];LL f[1<<max

2020-07-21 20:10:20 197

原创 20200721 T3 s3mple【DP，点值优化卷积】

题目描述n≤200,x≤109n\le200,x\le 10^9n≤200,x≤109题目分析容易想到枚举最大值的位置，然后递归两边，于是有这样的DP：上面式子里面有个地方要改成 f(n−1−i,m−min(i,n−1−i)−1−j)f(n-1-i,m-min(i,n-1-i)-1-j)f(n−1−i,m−min(i,n−1−i)−1−j)可以DP求出区间长度为 nnn 的 xxx 的最大值：mx[n]=min(n+12,n+1−n+12)mx[n]=min(\frac {n+1}2,n+1

2020-07-21 20:05:23 237

原创 20200721 T2 s2mple【后缀自动机妙用】

题目描述n,Q≤4∗105n,Q\le4*10^5n,Q≤4∗105题目分析建 SSS 的 SAM。记询问串为 TTT。要数 SSS 中本质不同的串中 TTT 的出现次数之和相当于给 TTT 后面接上一个串 RRR，前面接上一个串 LLL，LTRLTRLTR 出现在 SSS 中，求 L,RL,RL,R 的对数。假设已经确定了 TR=pTR=pTR=p，考虑怎么数 LLL：以 ppp 为后缀的串，就是在 ppp 对应 fail 树上节点 qqq 子树中的串，加上 qqq 剩下长度对应的串。可以表

2020-07-21 15:50:04 314

原创 CF1375H Set Merging

这篇题解写的真是太好辣！虽然实际上是我自己脑补的看题解之前先看清楚题意。。原序列是个排列，不是有序的，要把 [l,r][l,r][l,r] 位置的集合合并出来，合并要保证值域有序。对值域分块，然后将每一块中位置在 [l,r][l,r][l,r] 的段提取出来，依次合并。这一步合并次数是 nqB\frac {nq}BBnq 的。然后考虑怎么把值域块内的每个位置连续段合并出来，因为位置连续段的值域并不一定连续，再次对值域分治，先合并出值域在 [L,M],[M+1,R][L,M],[M+1,R][L,M

2020-07-20 17:38:54 173

空空如也

空空如也