19-大数据一班-杨文冠

题解

学习(23) 未归档(1) 练习(1)

/ 注册

全部文章 / 题解（共137篇）

【模板】Link Cut Tree(动态树) 来自专栏

能够解决的问题:1.求LCA2.求最小生成树3.维护链上信息(最大最小，链上和等)4.维护联通性5.维护子树信息(需要配合树)6.优化单纯性算法，在的复杂度下求最大流（这两个是在它的论文最开头提到的，资料比较少）（以上现在只是听过）看别的大佬博客入门：【参考博客】链剖分一般分为三种：重链剖分，也就...

LCT

2020-12-02

4 685

牛客编程巅峰赛S2第5场 - 钻石&王者

怕npy的牛牛思路：以当前端点为右区间向，一个指针指向合法左端点最远的位置，维护最大的区间长度其实就是一个队列，因为要枚举左端点，所以左端点要入队同时要保证队列中所有的元素和发，如果同时出现了'n'、'p'、'y'，则不断出队直到区间合法，得到该左端点对应的最大合法区间 Code： #includ...

栈队列思维 DFS 图论基础

2020-12-02

3 617

BCD Code 来自专栏

题意：数字都要转为码，题目会给出个长度不超过的限制串，然后给出，求区间内有多少个数的码不包括限制串（）。有组数据。这题卡了我几天，我这是用自动机数位解的，这题对自动机数位的应用都不深，都是简单的应用，但自动机我之前没学明白（写了一些题还是没明白），花几天又学了一遍，对自动机的结构更清楚了，找出了紫...

AC自动机数位dp

2020-11-27

1 769

Balanced Numbers 来自专栏

思路：没特殊声明，在本题0算偶数，不要把前导零算进来了数位入门题，我又写了一堆，开始不知道算不算，就瞎写了一个，结果答案大了，如何算上又把前导零算上了，特判前导零但为了少写一个参数直接硬写，然后写错了。时因为是两遍，以为是一遍，然后出现了不能解释的结果。把每个数位是否出现状压到的二进制位里，一...

数位dp

2020-11-23

1 692

F(x) 来自专栏

思路：这个数位卡我时间又卡我空间，时间和空间限制都很小，时间就500ms。我想通过再开一个数组记录访问过的状态是否与本次输入有关，来避免每次都要初始化数组，同时又不用多开一维（会爆空间，），即便如此还是会超时，因为它有组数据，所以如果每次都重新算一遍的话，铁定超时，与是否初始化的时间开销无关。 ...

数位dp

2020-11-23

2 744

B-number 来自专栏

思路：简单的数位取2表示出现过13，取1表示当前位是1，否则取0 状态：，长度为，当前数值的值为，状态是，这个状态是能保证结果唯一的 Code： #include<iostream> #include<cstdio> #include<cstring> #incl...

数位dp

2020-11-22

1 604

Traveling by Stagecoach 来自专栏

题意：有一个旅行家计划乘马车旅行。他所在的国家共有m个城市，在城市之间有p条道路相连接。从某个城市沿着某条道路到相邻的城市需要乘坐马车。而乘坐马车需要使用车票，每用一张车票只可以通过一条道路。每张车票上都记有马的匹数，从一个城市移动到另一个城市的所需时间等于城市之间道路的长度除以马的数量的结果。这位...

状压dp

2020-11-22

1 711

Doing Homework 来自专栏

题意：一行给出科目名称，截止时间，需要的时间，超出截止时间多久就扣多少分，求一个做作业的顺序使扣的分最少，并按字典序打印顺序。科目的名称是按字典序给出的思路：状压入门二进制位表示一个数有没有被取指的是已做作业结合的上一个集合，指由上一个集合到集合做的是什么作业，表示到集合已经过了多久，就是做了集...

状压dp

2020-11-22

1 582

Travelling 来自专栏

题意：n 个城市已及 m 条路以及对应路费 c，要求遍历所有城市最少的路费，每个城市不能超过2次。思路：三进制位表示一个城市被走过的次数，三进制没有位运算，可以预处理三进制位每一位的权值以及每个十进制数的三进制表示。状态方程：表示访问中所有的点后最后到达城市（感觉紫书上对旅行商的解析不太好）转移...

TSP 旅行商问题

2020-11-22

1 476

Balanced Number 来自专栏

题意：定义一个数若以某个数字作为支点，左右力矩（到支点的距离乘数字大小）相等，则称这个数是平衡的。求区间中有多少个平衡数。比如，以第二位为支点，左边的力矩是，右边的力矩是思路：这道入门题是我大意了（锤子入门题，不能秒解的题还是入门题？）这道题求的答案时需记忆化搜索次，是的位数，表示当前是第位，...

数位dp

2020-11-20

1 598