• avatar jijidawang 2020-10-08 11:58:00

    清北学堂 2020 国庆J2考前综合强化 Day2

    目录 1. 题目 T1 一 题目描述 Sol T2 二 题目描述 Sol T3 三 题目描述 Sol T

    来自 jijidawang
    00
  • avatar jijidawang 2020-10-08 11:20:00

    清北学堂 2020 国庆J2考前综合强化 Day1

    目录 1. 题目 T1 一 题目描述 Sol T2 二 题目描述 Sol T3 三 题目描述 [前置] 向量点积 & 叉

    来自 jijidawang
    00
  • avatar jijidawang 2020-10-07 11:20:00

    题解 P1999【覆盖墙壁】

    数学题 令 \(A_n\) 为 \(2\times n\) 的墙壁放满块的方案数,考虑递推。 显然 \(A_0=1\),我们令对于 \(k<0\),\(A_k=0\) . 放直线型的块非常好递推: 此时答案即为 \(A_{n-1}+A_{n-2}\) . 接下来考虑放 L 型块的

    来自 jijidawang
    00
  • avatar jijidawang 2020-09-21 20:30:00

    最短路算法

    目录 1. 存图方法 1.1 邻接矩阵 1.2 vector 存图 1.3 邻接表存图 2. 单源最短路径 - dijkstra 2.1 算法描述 2.2 题目 2.2.1 Dijkstra 模板

    来自 jijidawang
    00
  • avatar jijidawang 2020-07-25 21:47:00

    数论

    咕咕咕

    来自 jijidawang
    00
  • avatar jijidawang 2020-07-05 00:02:00

    【P1809 过河问题】题解

    贪心,我们设时间序列为 \(\{a_i\}\),长度为 \(n\)(先排序 \(\{a_i\}\))。 分类讨论(其中的「\(1\)」「\(2\)」等均指「速度第 \(1\) 人」「速度第 \(2\) 人」): 如果 \(n=2\),那么答案显然是 \(a_2\)。 如果 \(n

    来自 jijidawang
    00
  • avatar jijidawang 2020-05-18 22:48:00

    题解 P4999 【烦人的数学作业】

    数位 dp。 设 \(dp_{q,i}\)(\(i\in\{0,1,2,3,4,5,6,7,8,9\}\))为 \(1\sim q\) 中 \(i\) 出现的次数,\(1\sim q\) 的数字和显然就是 \(dp_{q,0}\times 0+dp_{q,1}\times 1+\cdots+dp_

    来自 jijidawang
    00
  • avatar CHUAN_HA 2020-11-20 17:37:37

    Vuex

    1、Vuex的基本介绍 1.1Vuex是做什么的 官方解释:Vuex是一个专为Vue.js应用程序开发的状态管理模式。 它采用集中式存储管理应用的所有组件的状态,并以相应的规则保证状态以一种可预测的方式发生变化。 Vuex也集成到Vue的官方调试工具devtools extension,提供了诸如

    来自 CHUAN_HA
    00
  • avatar jijidawang 2020-05-18 22:45:00

    题解 P2657 【[SCOI2009] windy 数】

    数位 dp。 // 数位 dp 其实是爆搜加记忆化 #include<iostream> #include<cstring> #include<cmath> using namespace std; const int N=15; //数据范围是 10^n 就可

    来自 jijidawang
    00
  • avatar jijidawang 2020-05-13 19:14:00

    题解【洛谷 P1466 [USACO2.2]集合 Subset Sums】

    题目传送门 设 \(sum=1+2+3+4+\dots+n=\dfrac{n(n+1)}{2}\)。 如果 \(2\nmid sum\),则显然没有方案。 如果 \(2\mid sum\),则这两个集合的和必为 \(\dfrac{sum}{2}\)。 将 \(\dfrac{s

    来自 jijidawang
    00
  • avatar jijidawang 2020-05-09 00:12:00

    乘法逆元

    前置芝士: 同余 普通逆元 逆元是模意义下的除法。 就是求解同余方程 \(ax\equiv 1\pmod m\)。 用 exgcd 求解即可。 Code: #include<iostream> #include<cstdio> using namesp

    来自 jijidawang
    00
  • avatar jijidawang 2020-05-09 00:10:00

    浅谈二维前缀和

    首先要了解一个叫做前缀和的东西。 二维前缀和其实就是将普通前缀和加了一维。 也就是可以求一个矩阵内任意子矩阵元素和。 仿照一维前缀和,转移方程如下: \[sum_{i,j}=sum_{i-1,j}+sum_{i,j-1}-sum_{i-1,j-1}+a_{i,j} \] 这个转移方

    来自 jijidawang
    00
  • avatar jijidawang 2020-05-09 00:08:00

    浅谈位运算

    目录 位运算前言 位运算应用 1 快速幂 2 最大公约数 3 xor 一些应用 4 其他 位运算前言 程序中所有东西在计算机中都是以二进制储存的。 位运算可以直接操作这些二进制。 所以位运算相对于普通运算要快。 这些是所有位

    来自 jijidawang
    00
  • avatar jijidawang 2020-05-09 00:07:00

    浅谈 Lucas 定理

    Lucas 定理是用来求 \(C^n_m\mod p\) 的。 定理 \[C^n_m\equiv C^{n\bmod p}_{m\bmod p}\times C^{n/p}_{m/p}\pmod p \] 证明 由二项式定理得 \(C_a^b\) 为 \((1+x)^a\) 中 \(

    来自 jijidawang
    00
  • avatar jijidawang 2020-05-08 23:59:00

    浅谈 exgcd

    众所周知欧几里得算法是: \[\gcd(a,b)=\gcd(b,a\bmod \,b) \] 也叫辗转相除法。 拓展欧几里得算法(exgcd),可以用来找到形如 \(ax+by=\gcd(a,b)\) 的方程的一组特解。 由裴蜀定理知,原方程一定有解。 我们利用辗转相除法(普通欧几

    来自 jijidawang
    00
  • avatar jijidawang 2020-05-08 23:55:00

    【洛谷P1754 球迷购票问题】题解

    传送门 卡特兰数经典 \(\texttt{AB}\) 分拆问题。 分析: 题意相当于排列 \(n\) 个 \(\texttt A\) 和 \(n\) 个 \(\texttt B\),使得相邻 \(\texttt{AB}\)(有序!)消掉,然后左右元素并到一起再消,最后消完的序

    来自 jijidawang
    00
  • avatar jijidawang 2020-05-03 09:23:00

    浅谈前缀和

    引入 如果你想维护一个数据结构,有一个序列 \(a\),每次查询 \(l\sim r\) 区间和(求 \(\sum\limits_{i=l}^ra_i\)),只有查询,线段树&树状数组难免有些大材小用,但是维护它效率要高,甚至要达到 \(\mathcal{O}(1)\)。 这个东西该怎么

    来自 jijidawang
    00
  • avatar jijidawang 2020-05-03 09:21:00

    浅谈 LCA

    LCA(Least Common Ancestors),最近公共祖先,定义为两节点最近的公共祖先好像是废话 前置芝士: 图论 此文章中均设 \(\mathrm{fa}_i\) 为 \(i\) 的父亲,\(\mathrm{dep}_i\) 为 \(i\) 的深度。 暴力 显然我

    来自 jijidawang
    00
  • avatar jijidawang 2020-04-20 22:16:00

    浅谈Meet in the middle——MITM

    目测观看人数 \(0+0+0=0\) \(\mathrm{Meet\;in\;the\;middle}\)(简称 \(\rm MITM\)),顾名思义就是在中间相遇。 可以理解为就是起点跑搜索树基本一半的状态,终点也跑搜索树基本一半的状态,最后撞到中间,一种类似双向 DFS 的东西

    来自 jijidawang
    00
  • avatar jijidawang 2020-04-17 20:19:00

    拓扑排序

    介绍 拓扑排序,对于一个 DAG,每次去掉入度为 \(0\) 的边,最后将图去光,就是拓扑排序。 拓扑排序可以处理一些有序东西,比如在日常工作中,可能会将项目拆分成 \(A,B,C,D\) 四个子部分来完成,但 \(A\) 依赖于 \(B\) 和 \(D\),\(C\) 依赖于 \(D\)(有先

    来自 jijidawang
    00
  • avatar jijidawang 2020-03-12 16:17:00

    时间复杂度符号

    CSDN拓展 五种符号: \(Θ\),读音:\(theta\)、西塔;既是上界也是下界(\(tight\)),等于的意思。 \(O\),读音:\(big-oh\)、欧米可荣(大写);表示上界(\(tightness\;unknown\)),小于等于的意思。 \(ο\),读音:\(sm

    来自 jijidawang
    00
  • avatar jijidawang 2020-02-12 18:58:00

    浅谈排序算法[动图]

    目录 内部排序 1.内省式排序 2.冒泡排序 3.[冒泡排序优化]鸡尾酒排序 4.[冒泡排序优化]地精排序 5.[冒泡排序逆优化]臭皮匠排序 6.[冒泡排序优化]奇偶排序 7.选择排序 8.[选择排序优化]堆排序

    来自 jijidawang
    00
  • avatar jijidawang 2020-02-12 13:22:00

    浅谈悬线法

    待填坑

    来自 jijidawang
    00
  • avatar jijidawang 2020-02-07 22:06:00

    浅谈二分和二分答案

    一般来讲我们会在以下情况用到二分: 求单调函数的零点 求一堆东西的最小值最大是多少 很难直接算出答案,但是很好判定答案合不合法 如果想学就继续看吧! 二分查找 二分是一种可以再\(\mathcal{O}(\mathrm{ch}\log m)\)(\(m\)为数据规模,

    来自 jijidawang
    00
  • avatar jijidawang 2020-02-07 12:26:00

    OI常用模板

    1 long long qpow(long long a,long long b,int mod) 2 { 3 long long res=1; 4 while (b) 5 { 6 if (b&1) res=res*a%mod; 7

    来自 jijidawang
    00
  • avatar 阳莱 2020-11-20 18:18:09

    51 nod 1215 数组的宽度

    sb题,写线段树的时候懒得写query_min了直接cv的max然后cv错了,找了半天。就只需要找到每个区间最大的值相加减去每个区间最小的相加。然后每一个值他的贡献数是(mid-l+1)*(n-i+1).正解是单调栈(不会写,等会了在补。 #include<bits/stdc++.h>

    来自 阳莱
    00
  • avatar 努力学习的boy 2020-11-20 18:23:44

    数据类型 char

    public class DataTypeTest01{ pubilc static void main(String[ ] args){ //定义一个char类型的变量,起名c,同时赋值字符'a' char c = 'a'; System.

  • avatar 努力学习的boy 2020-11-20 18:26:01

    数据类型:转义字符

    关于java语言当中的char类型: 转义字符 \ 转义字符出现在特殊字符之前,会将特殊字符转换成普通字符 \n 换行符 \t 制表符 \' 普通的单引号 \\ 普通的反斜杠 \" 普通的双引号 public class DataTypeTest03{ pub

  • avatar 没得感情的程序员 2020-11-20 18:43:19

    Vue路由复用问题解决

    方法一:当一个页面跳转到相同页面时,就是页面的复用路由参数参数变化,但是页面没有刷新,这是Vue的组件复用的默认处理方式 不想复用的话,就在父组件的router-view上加个key <router-view :key="$route.fullPath"/>方法二:

  • avatar 没得感情的程序员 2020-11-20 18:44:13

    Vue中使用el-dialog集成echarts

    <el-dialog :title="diaTitle" :visible.sync="dialogVisible" @open="loadEcharts()" > &

  • avatar 老狗、 2020-11-20 19:16:03

    《金字塔原理》读书笔记之一

    之前都是手写笔记,现在就敲给自己看把,反正也当敲字速度的练习了 一、整本书提倡的几个观点 1.在写东西之前要先进行思考,不然你在看自己写的东西的时候是很难看出问题的 2.金字塔的基本结构: 结论在先,以上统下,归类分组,逻辑递进 3.金字塔观点先后顺序: 先重要后

    来自 老狗、
    00
  • avatar Max_n. 2020-11-20 19:21:28

    剑指offer - 复杂链表的复制(Java实现)

    题目链接:https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba?tpId=13&&tqId=11178&rp=1&ru=/ta/coding-interviews&qru=/ta/

    来自 Max_n.
    00
  • avatar Bernard5 2020-11-20 19:36:57

    JavaScript 杂项笔记

    npm换源加速 手动后缀 --registry=https://registry.npm.taobao.org -g 欢用cnpm npm install -g cnpm --registry=https://registry.npm.taobao.org

    来自 Bernard5
    10
  • avatar 小熠小熠很不容易 2020-11-20 19:40:11

    Tree with Small Distances

    思路 1.先对树从根结点进行一遍dfs求出每个点的深度 2.用大根堆把不满足要求的点存起来 3.按深度从大到小依次把该点的父亲结点与根结点相连 4.更新父亲结点和它的子节点的状态 代码 // Problem: Tree with Small Distances // Contest: NowCo

  • avatar 薄荷叶是不是长在树上 2020-11-20 20:00:40

    《MySQL技术内幕》读书笔记

    数据库(database):物理操作系统文件,或其他形式文件类型的集合 实例(instance) 数据库实例真正用于操作数据库文件 在mysql数据库中,实例与数据库通常一一对应(集群存在一个数据库被多个数据实例使用)**** Mysql数据库实例在系统上的表现是一个进程 观察进程情况: ps -e

  • avatar 派大sao 2020-11-20 20:06:57

    「金」点石成金

    金点石成金 题目分析: 会增加ai的财富,消耗bi的魔法 回复ci的魔法,但减少di的财富 从1到n进行深搜,枚举所有情况,然后到最后去最大值 代码如下: #include<bits/stdc++.h> using namespace std; #define mm(a,x)

    来自 派大sao
    20
  • avatar NightDW 2020-11-20 20:20:34

    Leetcode - 110. 平衡二叉树

    解题思路参考代码中的注释: /**  * Definition for a binary tree node.  * public class TreeNode {  

    来自 NightDW
    00
  • avatar 努力学习的boy 2020-11-20 20:31:33

    数据类型——整数型

    关于java语言当中的整数型 数据类型 占用空间大小 默认值 取值范围 byte 1 0 [-128~127] short

  • avatar 秃头小白 2020-11-20 20:35:27

    CodeForces - 998D Roman Digits

    题目链接 https://codeforces.com/problemset/problem/998/D 解题思路 哇,我还搞数学公式啥的,发现自己错误的证明出没有重复的了……打表找规律大佬思路: AC代码 #include<bits/stdc++.h> #define ll long

    来自 秃头小白
    10
  • avatar L-TOK 2020-11-20 20:43:34

    数据结构

    完全二叉树性质链接:https://www.nowcoder.com/questionTerminal/4342cbc1732644dc84938543392c1b34?orderByHotValue=1&page=1&onlyReference=false来源:牛客网n0是度为1的

    来自 L-TOK
    00
  • avatar 牛客703842422号 2020-11-20 20:46:46

    算法学习笔记

    Acwing 状态的划分 https://www.bilibili.com/video/av67759585/

  • avatar 牛客703842422号 2020-11-20 20:46:58

    Acwing学习笔记

    Acwing 状态的划分 https://www.bilibili.com/video/av67759585/ 矩阵路径问题 最低通行费问题 dp数组的长度 什么时候定义为len(n),什么时候定义为len(n)+1? 当dp[0]与迭代对象第0位元素的状态值的含义一致时,用len(n)来定义

  • avatar 拉布拉多丨晓 2020-11-20 20:55:54

    Java内存区域与内存溢出异常

    运行时数据区域 程序计数器 内存空间小,线程私有。字节码解释器的工作就是通过改变这个计数器的值来选取下一条需要执行指令的字节码指令,分支、循环、跳转、异常处理、线程恢复等基础功能都需要依赖计数器完成。 如果线程正在执行一个Java犯法,这个计数器记录的是正在执行的虚拟机字节码指令的地址;如果

  • avatar 神崎兰子 2020-11-20 20:59:56

    【题解】北京信息科技大学第十二届程序设计竞赛热身赛题解

    level 0 热身赛的签到题 基本上只要不看错题或者不马虎就不可能做错。 #include<bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; cout<<s

    来自 神崎兰子
    10
  • avatar Dear㉿You 2020-11-20 21:00:47

    牛客编程巅峰赛S2第2场 - 钻石&王者 A-牛牛切木棒

    A牛牛切木棒这格式真难调 分析 众所周知,假设 是三角形的三条边,那么一定满足任意两条边之和大于第三条边。假设我们把当前的长度为a的线段分成了p段,从小到大分别为 ,那么如果不能构成三角形,一定满足 ,因为要尽可能多的分段,那么就得尽可能的小。那就可以直接把b数组预处理出来,能分则分,同时记录一个

    来自 Dear㉿You
    133
  • avatar 林思艺 2020-11-20 21:03:43

    Network

    题意 一个无向图可以有重边,下面 个操作,每次在两个点间连接一条有向边,每次连接后整个无向图还剩下多少桥(注意是要考虑之前连了的边,每次回答是在上一次的基础之上) 分析 求出桥来之后缩点,缩点运用并查集实现,每一个点组用父亲节点代表。emm,好像就这样。 PS: 虽说楼上大佬说并查集实现更快,但我

    来自 林思艺
    50
  • avatar 牛客695804806号 2020-11-20 21:12:02

    最后有个空格没处理

    #include<iostream> #include<string> using namespace std; void output() { string str; char ch; cin >> str; scanf(&quo

  • avatar Bernard5 2020-11-20 21:12:37

    切木棒 斐波那契

    本题和https://ac.nowcoder.com/acm/contest/5758/F 一模一样。 显然是斐波那契。不能构成三角形的极限情况必然是。 class Solution { public: /** * * @param a long长整型 木棒的长度

    来自 Bernard5
    70
  • avatar WanRP 2020-04-30 17:41:00

    留言板

    坐标:HN - ZZ QQ:2167306203

    来自 WanRP
    00
  • avatar WanRP 2020-11-20 10:53:00

    李超线段树复习笔记

    复习笔记就离谱好吧 用途 大概是给你一个序列, 然后插入一条线段, 然后查询某一个位置上与所有线段交点的纵坐标的的最大值或者最小值。 然后就没了。 实现 定义一个区间的"优势线段"为在这个区间里面有超过一半的点在这个线段上取到最值。 考虑维护一个线

    来自 WanRP
    00
  • avatar WanRP 2020-11-20 10:52:00

    Luogu 3748 [六省联考2017]摧毁“树状图”

    题目大意: 求两条树上边不相交路径, 使得删掉这两条路径上的点以后剩下的连通块数量最多。 做法 两条路径在树上大概会长成两个倒着的‘V’字形, 考虑在某一个'V'的最上面那个点统计答案。 于是统计答案的时候我们发现有几种统计法: 父节点有一个'V', 子节点有一个'V‘。 父节点

    来自 WanRP
    00
  • avatar WanRP 2020-10-15 17:05:00

    [CQOI2017]老C的键盘

    发现题目给的很像一棵树。。。 就把这棵树建出来。 发现如果把大于小于号分别看成一条有向边, 发现这个题目就是求这个图有多少个拓扑序。对于每一个拓扑序, 直接$$12345$$这样标号就可以得到满足题目要求的序列。 考虑树\(dp\), 设\(f(i, j)\)为\(i\)这个点在这个子树所形成

    来自 WanRP
    00
  • avatar WanRP 2020-10-14 11:06:00

    题解 [AGC030F] Permutation and Minimum

    我们把位置在\((2i - 1, 2i)\)的两个点叫做一对点。 显然如果这对点两个都被限定了直接丢掉完事。 如果有一个没有被限定就先留下来。 注意到其他的形如\((-1, -1)\)的顺序是可以随便变化的, 所以先不考虑, 最后乘上一个阶乘就可以了。 考虑用\(f(i, j, k)\)表示

    来自 WanRP
    00
  • avatar WanRP 2020-10-14 10:41:00

    题解 AGC029E Pairing Points

    考虑\(1\)号点向外连出一条边之后, 整个圆被分成两个部分, 每个部分肯定是内部连边然后一个点连一条边出来跨越一号点连出的那一条线。考虑对这种形状的部分进行\(dp\)。 设\(f(i, j, k)\)表示\([i, j]\)这个区间内部匹配, \(k\)点向外连接的方案数, \(g(i,j,

    来自 WanRP
    00
  • avatar WanRP 2020-10-14 07:57:00

    题解 [AGC028D] Chords

    首先, 按照boshi巨佬的说法, 考虑每种联通块的出现次数。如果可以求出, 答案就是每种联通块的出现次数和。 再按照boshi巨佬的说法, 一种定义联通块长相的方法是用编号最小的点和编号最大的点表示。 于是设\(f[l][r]\)为\(l, r\)连通且外面的点不连接到里面的点, 里面的所有边

    来自 WanRP
    00
  • avatar WanRP 2020-08-18 20:58:00

    题解 luoguP5466 【[PKUSC2018]神仙的游戏】

    显然要是没有限制那就全都是\(1\)对吧, 所以考虑这些\(0, 1\)到底限制了啥。 首先看到\(border\), 容易想到当年写\(kmp\)求最短回文子串的那题。因为\(kmp\)的\(next\)数组实际上就是最长\(border\)。我们也在那题积累一个结论, 就是对于原来的串一个长

    来自 WanRP
    00
  • avatar WanRP 2020-08-14 22:44:00

    题解 P4233 【射命丸文的笔记】 && 考试T3

    考虑每一条哈密顿回路在所有竞赛图中的出现次数。 发现如果确定一个环, 其他的边乱选就可以保证出现哈密顿回路。所以对于一条哈密顿回路, 出现次数为\(2^{C_n^2-n}\), 减去的\(n\)为那\(n\)条边。哈密顿回路是\(1-n\)的一个排列首尾拼在一起, 共有\(n!/n\)种。于是总

    来自 WanRP
    00
  • avatar WanRP 2020-08-11 21:09:00

    图论学习(在更)

    note: 最小环 是枚举已有的最短路和k点连接的两条边, 保证三个点不重合。 for(R int k = 1; k <= n; k ++) { for(R int i = 1; i < k; i ++) for(R i

    来自 WanRP
    00
  • avatar WanRP 2020-07-28 17:20:00

    SP5971 【LCMSUM - LCM Sum】

    lei/ \[\sum^n_{i = 1} lcm(i,n)=\sum^{n}_{i=1}\frac{in}{gcd(i, n)}= \] \[\sum^{n}_{d|n}\sum^{n}_{i=1}\frac{in}{d}[gcd(i,n)==d]= \] \[n \t

    来自 WanRP
    00
  • avatar WanRP 2020-07-25 20:14:00

    数学小算法

    exgcd \[x = y \ \\ y = t - a /b \times y \] CRT \[ans = \sum_{i = 1}^n{b_i\times M_i\times inv(M_i,mod_i)} \] \[M_k=(\prod_{i=1}^n {} m

    来自 WanRP
    00
  • avatar WanRP 2020-07-23 16:09:00

    PAM

    struct PAM { int ch[N][26], fail[N], len[N]; int tot, las; PAM() { len[0] = 0; len[1] = -1; fail[0] = 1; tot = 1; las = 0; } inline int gtfail(

    来自 WanRP
    00
  • avatar WanRP 2020-07-22 09:00:00

    SAM模板

    #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define R register #define LL long long const int i

    来自 WanRP
    00
  • avatar WanRP 2020-06-17 18:00:00

    一个写得很shabi的differ

    #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <cstdlib> #include <string>

    来自 WanRP
    00
  • avatar WanRP 2020-06-16 10:16:00

    LCT板子

    #define ls(x) ch[x][0] #define rs(x) ch[x][1] int fa[N], ch[N][2], sum[N], val[N], rev[N]; inline void update(int x) { sum[x] = sum[ls(x)] ^ sum[rs(x)

    来自 WanRP
    00
  • avatar WanRP 2020-06-10 17:13:00

    [wqs二分模板] CF739E Gosha is hunting

    题目链接 首先一个很显然的想法就是直接\(DP\) 设\(f[i][j][k]\)表示抓前\(i\)个神奇宝贝用了\(j\)个宝贝球和\(k\)个超级球,有: \[f[i][j][k] = max (f[i - 1][j - 1][k] + p[i], f[i - 1][j][k - 1]

    来自 WanRP
    00
  • avatar WanRP 2020-06-09 18:18:00

    高精度板子

    //#include<bits/stdc++.h> #include<iostream> #include<iomanip> #include<cstring> #include<stack> #include<string>

    来自 WanRP
    00
  • avatar WanRP 2020-06-07 18:41:00

    斜率优化DP刷题单

    Luogu P3195 [HNOI2008]玩具装箱 Luogu P2900 [USACO08MAR]Land Acquisition G Luogu P5785 [SDOI2012]任务安排 Luogu P4360 [CEOI2004]锯木厂选址 Luogu P2120 [ZJOI2007]仓库建

    来自 WanRP
    00
  • avatar WanRP 2020-05-18 20:51:00

    「JOISC 2016 Day 3」回转寿司

    「JOISC 2016 Day 3」回转寿司 这题我无力吐槽了... 强烈谴责出题人用脚造数据 解法 其实这题主要还是部分分启发正解吧。看到有个\(s_i = 1, t_i= n\)的做法就是维护一个堆就可以了,所以扩展下就是分块,然后每个块维护一个堆。散块暴力,大块直接查。但是有个很坑爹的问题

    来自 WanRP
    00
  • avatar WanRP 2020-05-18 20:49:00

    「JOISC 2016 Day 2」三明治

    「JOISC 2016 Day 2」三明治 这题真正让我感受了记搜的强大。 我真的没想过搜索可以过\(400\)的啊喂 对,\(\text{NOI}\)还可以过\(1e5\)呢 解法 一个并不显然的\(n^4\)的做法是枚举每一个点,然后上下左右记忆化搜索。考试的时候觉得难打,但是看完别人的代码

    来自 WanRP
    00
  • avatar Bernard5 2020-11-20 21:16:37

    完全k叉树 模拟

    完全k叉树,每层节点数量是已知的,直接推过去模拟就可以了 class Solution { public: long long tree2(int k, vector<int>& a) { long long ans = 0; int

    来自 Bernard5
    60
  • avatar WanRP 2020-05-18 20:19:00

    JOISC 2016 Day3 电报

    JOISC 2016 Day3 电报 前置知识(伪) 基环树 基环外向树 基环内向树 此题就是一棵基环外向树。 其实这些都没什么用,跟这题没啥关系 思路 考试的时候不会做,考完才发现自己就差那么一点点... 首先考虑这样一张图: 我们的目的是让整个图成为一个环,但是这显

    来自 WanRP
    00
  • avatar WanRP 2020-05-16 17:20:00

    CF1093G Multidimensional Queries

    这题妙啊。 学会了一个新\(trick\)。 题解 \[|x_1 - x_2|+|y_1 - y_2| = \\ max (x_1-x_2+y_1-y_2,x_1-x_2-y_1+y_2,-x_1+x_2+y_1-y2,-x_1+x_2-y_1+y_2) = \\max((x_1+y_1)

    来自 WanRP
    00
  • avatar WanRP 2020-05-15 17:47:00

    CF1045G AI robots

    \(CDQ\)分治的妙题。 考虑按视野从大到小排序,那右边的可以看见左边的话左边一定看得见右边的,直接\(CDQ\)就行了。对于这种\([x-K,x+K]\)的区间维护可以在统计的时候差分也可以直接在更新的时候差分。本代码使用后者。 #include <cstdio> #include

    来自 WanRP
    00
  • avatar WanRP 2020-05-15 17:43:00

    CF149D Coloring Brackets

    DP神题。。。 设\(dp[i][j][0/1/2][0/1/2]\)表示\([i,j]\)这个区间内端点取不染色/染红色/染蓝色三个状态然后转移。一个新\(trick\)就是这里的转移只要考虑这个区间内的串是合法的就可以了 #include <cstdio> #include <

    来自 WanRP
    00
  • avatar WanRP 2020-05-15 17:39:00

    CF1175E Minimal Segment Cover

    一个很妙的操作,求出每个点通过一条边可以向右边覆盖的最远距离,然后倍增。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define R reg

    来自 WanRP
    00
  • avatar WanRP 2020-05-15 10:23:00

    UVA10328 Coin Toss

    考虑把答案拆成至多有\(n\)张朝上减去至少有\(k-1\)张朝上。 显然第一部分的答案就是\(2^n\),考虑\(DP\)第二部分。设\(dp[i][0/1]\)表示第\(i\)张是反面/正面的情况数。然后有: \[dp[i][0]=dp[i-1][0]+dp[i-1][1] \]

    来自 WanRP
    00
  • avatar WanRP 2020-05-14 17:43:00

    AT1983 [AGC001E] BBQ Hard

    前言 学到了一个\(trick\)。 对于一个组合数 \(C_{x+y}^x\)可以看成是从\((0,0)\)到\((x,y)\)的路径条数。 解法 对于这题而言,\(C_{a_i+b_i+a_j+b_j}^{a_i+a_j}\)就表示从点\((0,0)\)到点\((a_i+a_j,b_i+b

    来自 WanRP
    00
  • avatar WanRP 2020-05-13 17:29:00

    Luogu P3703 [SDOI2017]树点涂色

    Luogu P3703 [SDOI2017]树点涂色 用LCT中每一个Splay维护颜色相同的点集,则从一个点到根节点的轻边的条数就是这个点的到根的权值。至于路径查询的搞个差分就好,用树剖实现。 至于为什么可以直接这样查,是因为LCT里面涉及子树的权值变化只有access函数。在splay中的子树的

    来自 WanRP
    00
  • avatar WanRP 2020-05-11 12:03:00

    NTT板子

    #include <cstdio> #include <algorithm> using namespace std; #define R register #define LL long long const int inf=0x3f3f3f3f; const int

    来自 WanRP
    00
  • avatar R1ST 2020-11-20 21:17:24

    热心的牛牛

    题意:牛牛有k颗糖,要和n个朋友分享,且每个朋友得到的糖果要比牛牛多,求牛牛最多能得到几颗糖果。 我的想法:一共有n+1个人,将k颗糖平均分成n+1份;当k%(n+1)==n 时,将剩余的n颗糖,n个朋友每人再拿一颗,牛牛拿k/(n+1)颗(在平均的情况下,每个朋友都只比牛牛多一颗)。当k%(n+1

    来自 R1ST
    21
  • avatar WanRP 2020-05-11 11:33:00

    FFT板子

    #include <cmath> #include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; #def

    来自 WanRP
    00
  • avatar WanRP 2020-05-08 22:54:00

    BZOJ2568 比特集合

    题目链接 BZOJ2568 比特集合 思路 首先考虑不带区间加的情况,显然容易想到对每个数的每一个二进制位维护一个树状数组。设一个树状数组维护的是二进制的第\(k\)位,那就每次往里面存\(num\)的时候在这个树状数组的第\(num\ mod \ 2^k\)这个位置\(+1\),那么我们

    来自 WanRP
    00
  • avatar WanRP 2020-05-08 10:15:00

    ubuntu下c++ Gedit配置

    丢个配置。。  编译 #!/bin/sh fullname=$GEDIT_CURRENT_DOCUMENT_NAME name=`echo $fullname | cut -d. -f1` g++ -o $name $fullname -DIN 运行 #!/bin/sh fullnam

    来自 WanRP
    00
  • avatar WanRP 2020-05-06 19:11:00

    P6329 【模板】点分树 | 震波

    前言 由于这篇题解思路并没有什么区别,所以这篇题解的意义在于稍稍更细致地讲下思路和卡常方法。估计也只有我常数这么大了 思路 第一感 由于题目要查询到一个点距离为\(k\)以内的所有点的权值和,一个显然的想法就是对每个点开一个线段树维护权值和,下标维护距离,然后暴力查询。显然这是\(MLE+T

    来自 WanRP
    00
  • avatar WanRP 2020-05-06 13:33:00

    Luogu P3350 [ZJOI2016]旅行者

    这题正常的题面请看这里 由大佬之言可知,看见网格图想分治   所以这题考虑分治。   考虑把棋盘分成两半,那所有点就会有两种情况: 在完整的一半以内 跨越两半 考虑在我们分成两半的那条中线的所有点跑最短路来更新所有点的答案。然后对于跨越了两半的点就直接保存答案,在同一块的点就类似整

    来自 WanRP
    00
  • avatar WanRP 2020-05-05 21:25:00

    Luogu [ZJOI2015]幻想乡战略游戏

    显然,一棵树的带权重心最多只有两个,最少会有一个,而且在这两个点的答案一定相等。(都是带权重心当然相等)鉴于点分治的写法貌似并不太需要这样的分析,就不说了。我不会 首先建出一颗点分树,然后考虑在点分树上跳儿子来保证复杂度,于是我们就需要快速算出所有点到这个重心的带权距离和。由于这题是点分树,考虑在点

    来自 WanRP
    00
  • avatar WanRP 2020-05-05 16:12:00

    斐波那契数列简单性质

    计数性质 \(F_i=F_{i-1}+F_{i-2}\) \(\sum^{n}_{i=1}F_i=F_{n+2}-F_2\) 证明: 当\(n=1\)时,\(F_3-F_2=F_1\)显然成立。 当\(n=2\)时,\(F_4-F_2=F_3+F_2-

    来自 WanRP
    00
  • avatar WanRP 2020-05-04 23:04:00

    Luogu P2056 [ZJOI2007]捉迷藏

    动态点分治 先建出一颗点分树,然后维护。 对于每一个点维护两个堆,一个堆维护子树内所有点到分治父节点的距离最大值,一个堆维护一个点所有子树的第一个堆的最大值,再全局维护一个堆取所有分治重心的答案的最大值即可。 代码细节感人。。。 一个比较有用的trick就是用两个大根堆实现可删除的堆但是要开O2

    来自 WanRP
    00
  • avatar WanRP 2020-05-03 15:11:00

    Luogu P4127 [AHOI2009]同类分布

    数位DP 这题最妙的一点在于,由于我们无法存下原来的这个数,我们就考虑存取模之后的值,而这个模数就选择一个可能是最后的每一位数字的和的值。而这个总数只有\(9*18=162\)种,然后存下每一位的和以及从高位到低位的取模结果,数位DP即可。 #include <cstdio> #inc

    来自 WanRP
    00
  • avatar WanRP 2020-05-03 13:19:00

    二项式反演学习笔记

    前置知识 容斥原理 组合数 约定 \(A'_i\)表示集合\(A_i\)的补集。 反演形式 形式一 \[f(n)=\sum_{i=0}^{n}(-1)^iC^i_ng(i)\Leftrightarrow g(n)=\sum_{i=0}^{n}(-1)^iC^i_nf(

    来自 WanRP
    00
  • avatar WanRP 2020-05-03 09:23:00

    Luogu P3292 [SCOI2016]幸运数字

    看到异或最值,显然想到线性基。 用树上倍增的方法,维护当前点\(x\)到倍增父节点\(fa[x][i]\)这条路径上的线性基,在倍增的时候暴力合并即可。 注意这个线性基的倍增数组是没有包括最后一个点的信息的,需要特殊处理。然后就搞完了。 时间复杂度\(O(n*log_n*log_v+q*log_n*

    来自 WanRP
    00
  • avatar WanRP 2020-05-02 22:11:00

    Luogu CF555E 【Case of Computer Network】

    其实如果这是一颗树的话很好搞,把\(s\)到\(lca(s,t)\) 向上连,\(lca(s,t)\)到\(t\)向下连即可(然而事情并不是这样子的...)。 我们考虑什么样的情况是一定可行的呢?每两个点之间都有两条以上的路径,那就可以一边向前,一边向后,绝对可以。也就是求双联通分量以内是一定可以的

    来自 WanRP
    00
  • avatar WanRP 2020-05-02 17:11:00

    Luogu P4151 [WC2011]最大XOR和路径

    原题传送门 看见异或最值,估计线性基跑不了了。 考虑先随便提出一条从\(1\)到\(n\)的路径,这显然不一定是最优的,但是可以让它变强。比如可以让它中间插入一个环来让它变优。比如说有一条路径: \(1->A->B->C->N\) 可以补成: \(1->A->B-

    来自 WanRP
    00
  • avatar WanRP 2020-05-01 11:45:00

    线性基小结

    用处 没用我学这东西干嘛 快速查询一个数是否可以被一堆数异或出来 快速查询一堆数可以异或出来的最大/最小值 快速查询一堆数可以异或出来的第k大值 这么点? 还有点性质在下面 可能有点用 性质 原数列里的任何一个数都可以通过线性基里的数异或表示出来 线性基里任意一

    来自 WanRP
    00
  • avatar WanRP 2020-05-01 11:44:00

    HDU 3949 XOR

    线性基板子题,注意特判\(0\),开\(long~long\)就好。 #include <cstdio> #include <cstring> using namespace std; #define R register #define LL long long #def

    来自 WanRP
    00