2 康旭

学生身份

我要认证

暂无相关简介

等级
TA的排名 1w+

平衡树(splay)模板,包含常规6大操作以及区间翻转

P3391【模板】文艺平衡树P3369 【模板】普通平衡树已经测试过上述题目(而且性能较好),可放心食用~~#include <bits/stdc++.h>using namespace std;const int N = 100005;int n;struct Splay { int rt, tot, fa[N], ch[N][2], val[N], cnt[N], sz[N]; //sz[x]:x节点子树的大小;cnt[x]:与x节点权值相同的数的个数;v...

2020-08-03 23:10:21

P3391 【模板】文艺平衡树 区间翻转更新+查询操作 splay

这是线段树无法取代splay的地方。#include<bits/stdc++.h>using namespace std;const int N=101000;int ch[N][2];int size[N],rev[N],fa[N];//rev[x],x节点是否需要左右子树互换 int n,m,rt=0;int read(){ int x=0,f=1;char ch=getchar(); while (ch<'0' || ch>'9'){if (c

2020-08-03 22:51:11

2020牛客暑期多校训练营(第八场)GIK

G:#include <bits/stdc++.h>using namespace std;typedef long long ll;#define ls (o<<1)#define rs (o<<1|1)#define pb push_backconst double PI= acos(-1.0);const int M = 1e3+7; char s[M];struct node{ int a[5];}p[M];unordered

2020-08-03 21:55:54

P3369 【模板】普通平衡树 平衡树模板

过了一遍平衡树,把代码进行了标注,方便以后回顾。学平衡树主要为了处理区间翻转问题,和LCT(今天牛客多校考到了。。先回顾一下前置芝士)#include <bits/stdc++.h>const int N = 100005;struct Splay { int rt, tot, fa[N], ch[N][2], val[N], cnt[N], sz[N]; //sz[x]:x节点子树的大小;cnt[x]:与x节点权值相同的数的个数;val[x]:x节点的权值 inlin

2020-08-03 21:49:13

2020牛客暑期多校训练营(第七场) BDH

B:n*m个口罩分成最少的组使得可以这样分配:n个医院,每个医院m个口罩。m个医院,每个医院n个口罩。为了使得数量最少,每组的口罩尽可能要大。假设n<mn个医院,每个医院m个口罩,我们最多可以让 m/n*m组有n个口罩(当前最大值)。然后问题转化为了:n个医院每个医院需要m%n个口罩m%n个医院,每个医院需要n个口罩。变化为了子问题,dfs下去即可。#include <bits/stdc++.h>using namespace std;.

2020-08-02 21:39:57

牛客编程巅峰赛S1第8场 - 王者 ABC

A:枚举前两位,等差数列就确定了#include <bits/stdc++.h>using namespace std;typedef long long ll;#define ls (o<<1)#define rs (o<<1|1)#define pb push_backconst double PI= acos(-1.0);const int M = 1e5+7;/*int head[M],cnt=1;void init(){cnt=1,me

2020-08-01 22:48:03

2020牛客暑期多校训练营(第六场) Harmony Pairs 数位DP

经典数位DP,两个限制条件。AB同时跑。B由N限制,A由B限制。然后就变成经典数位DP的题目了。细节看代码。还有两个限制最好开到数组里,虽然浪费点空间,但能省好多时间,我就因为这里T了。。#include <bits/stdc++.h>using namespace std;typedef long long ll;#define ls (o<<1)#define rs (o<<1|1)#define pb push_backconst

2020-07-29 23:27:46

P4317 花神的数论题 数位DP经典题 两种处理方法

乍一看无法数位DP。但稍加思考发现:sum(i)的取值为1-50(二进制的位数)所以我们可以把问题转化为:1-N中:各个数位1的个数和为x的数的个数。这个问题很容进行数位DP,很经典的套路,具体见代码。这题想+敲就花了不到半小时,但调了好久,只是因为我把nm[i]给取模了mod。(我吐了。。。)显然次幂不能取模。。#include <bits/stdc++.h>using namespace std;typedef long long ll;#define ls (o

2020-07-29 22:02:39

P4127 [AHOI2009]同类分布 数位DP 经典题

这道数位DP对初学者来说还是很有难度的。//dp[i,j,k]处理到第i位,前面位数字和为j,前面数位组成的数模p等于k,且剩余数未确定的状态下:数模p==0的数的个数为什么要这么设状态呢?我们首先分析:要求某个数x,其数位和sm,求x%sm的数的个数。每个数的x与sm都不同,不方便记忆化。(之前做的数位dp都是只有x未知,不存在其他变量,只存在限制条件)观察易得:sm最大为9*18,完全可以通过枚举来确定sm,也就是固定一个变量,我们要求所有x%sm==0的数的个数。这样变量就只.

2020-07-29 20:31:48

P3413 SAC#1 - 萌数 数位DP 经典题

刚开始看到这题的时候完全没思路。于是去看题解,看到“ 正难则反 “四个字后,立刻关掉题解(整篇题解只看了这4个字),然后A了这道题。相信看到这里你也想试一下!下面说思路,正难则反,考虑1-n种不含回文子串的数。这是个经典问题了:任意连续三个数互不相同即可。证明:A:如果连续两个数相同,显然会出现长度为2的回文子串。B:如果一个数与另一个与他相距2的数相同,显然会出现长度为3的回文子串。显然任意偶回文子串都是由A拓展而来,任意奇回文子串都是由B拓展而来。只要保证不存在A..

2020-07-29 17:37:50

P2602 [ZJOI2010]数字计数 基础数位dp, 两种状态维护方法

1:dp[i][j]:处理到第i位,i位之前数码p已经出现了j次,这种情况下,数码p出现的次数。(包括所有数位)具体细节在代码注释里#include <bits/stdc++.h>using namespace std;typedef long long ll;#define ls (o<<1)#define rs (o<<1|1)#define pb push_backconst double PI= acos(-1.0);const int M

2020-07-29 13:32:44

P2657 [SCOI2009] windy 数 数位DP基础题

经典数位dp记录的状态:if0,上一位是否是前导0;limit,上一位是否达到上界;p,上一位的取值;按照题意把不符合条件的剔除+记忆化+处理好前导0即可。#include <bits/stdc++.h>using namespace std;typedef long long ll;#define ls (o<<1)#define rs (o<<1|1)#define pb push_backconst double PI= aco

2020-07-28 22:50:15

hdu 2089 不要62 数位DP入门题

重新学数位DP,这次准备学到进阶,至少可以做多校的数位DP的程度。数位dp跟普通dp一样。不过阶段变成了数位,状态变成了每一位的取值限制。用dfs递归+记忆化的方式完成状态转移。时间复杂度为:dp的数组大小*转移复杂度(一般为10)#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 1e5+7;ll di[60];ll dp[60][2];//d..

2020-07-28 22:25:49

2020 Multi-University Training Contest 3 1004,1005,1007,1009

168 team0691 北京林业大学 4 11:47:00 1004:如果是求和等于p,则直接用滑动窗口。而这里是取模,我们依然可以类比滑动窗口,用map进行快速维护。总体思想:贪心,前面能构造出尽量构造,给后面的数多一些选择空间#include <bits/stdc++.h>using namespace std;typedef long long ll;#define ls (o<<1)#define rs (o<&l

2020-07-28 19:15:13

2020牛客暑期多校训练营(第六场)BCEK

232 北林一队 北京林业大学 4 10:02:35 B:队友写的,等会再看看。#include<iostream>#include<cstring>#include<cstdio>using namespace std;#define mod 1000000007#define ll long long#define N 30000007int n,a[N],b[N],mul[N]; int Pow(int a,in.

2020-07-27 23:29:01

2020牛客暑期多校训练营(第六场) G:Grid Coloring 构造 (较简单的构造+证明)

题解的构造,比较麻烦。以下是更简单的构造:设a数组a[M][M];a[i*2-1][j],表示第i行(横线)第j个横着的线的颜色。a[i*2][j],表示第i行(竖线)第j个竖着的线的颜色。如代码中这样赋值,以下是样例涂色的图例。这样构造有个显然的好处:首先任意相邻两个横线(左右)的颜色一定不同,这样规则3就满足一半了。下面证明任意相邻两个竖线(上下)的颜色不同:这样规则3完全满足。且:任意相邻两个竖线(上下)的颜色不同不就说明:任意大小为4的环均不同颜色

2020-07-27 23:08:46

生成函数进阶(普通型生成函数)

https://www.cnblogs.com/RabbitHu/p/9178645.htmlhttps://zhuanlan.zhihu.com/p/52817010https://baike.baidu.com/item/%E7%94%9F%E6%88%90%E5%87%BD%E6%95%B0/1198009?fr=aladdin等下做几道题练练手https://www.luogu.com.cn/problem/P2000https://acm.taifua.com/bzoj

2020-07-26 18:23:32

HDU - 2110 生成函数基础题

最后一道水题了。顺便水水博客,香啊。#include<iostream>#include<cstring>#include<algorithm>#include<vector>using namespace std;typedef long long ll;#define ls (o<<1)#define rs (o<<1|1)#define pb push_backconst int M = 11000+7;

2020-07-26 15:29:56

Fruit HDU - 2152 生成函数基础题

还是水题。。这题每个种类数目起点不为0;#include<iostream>#include<cstring>#include<algorithm>#include<vector>using namespace std;typedef long long ll;#define ls (o<<1)#define rs (o<<1|1)#define pb push_backconst int M = 110+

2020-07-26 14:56:57

HDU - 2082 生成函数基础题

这些题都可以暴力直接做,但用于练习生成函数。(虽然并没有。。。马上做几道难题练练)#include<iostream>#include<cstring>#include<algorithm>#include<vector>using namespace std;typedef long long ll;#define ls (o<<1)#define rs (o<<1|1)#define pb push_back

2020-07-26 14:49:59

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。