998244353

分类

Atcoder(3) C/C++(21) Codeforces(6) study(2) 动态规划(2) 图论(1) 基础知识(30) 字符串(2) 思维(15) 技巧(1) 搜索(1) 搜索基础(1) 数论(5) 未归档(14) 简单题解(1) 线段树(8) 贪心(1) 题解(34)

/ 注册

全部文章（共148篇）

Codeforces Round #595 (Div. 3) B. Books Exchange

赛时不停的找环以及用并查集把自己卡sb了。赛后一发入魂。题意：给一个序列，问你从某个位置开始传书后，要传几次才能回到自己手上 q次询问，总共有n(n <= 2e5)个序列题解：模拟下样例会发现是个环，所以从某个位置开始传导后，它所到达的所有位置，从这所有位置开始后，再回...

2020-05-08

0 627

Codeforces Round #595 (Div. 3) C. Good Numbers

数学太差自闭了。题意：给一个数n，问你大于等于n的数中，可以拆分成3的幂之和的最小的数，其中每个幂最多出现一次题解：先将n分解成三进制，然后观察，当某位出现2的时候，我们需要从大于这位的幂开始寻找一位出现0次的幂，将其改成1，同时将小于这个幂出现次数被改成1的幂的出现次数全部改成0 ...

2020-05-08

0 593

最短哈密顿路径（位运算+dp）

原题链接：https://www.acwing.com/problem/content/description/93/ 题意：求从点0到点n-1的最短哈密顿路径，即0~n-1这n个点每个点必须且只能经过一次。起点为0，终点为n-1，问你最短路径长度题解：设f[i][j]表示从...

2020-05-08

0 559

Codeforces Round #598 (Div. 3) C.Platforms Jumping

题意：一个长为n的河，中间有m个木台，每个木台长为ci，你想从河的左岸跳到右岸，每次你可以往前跳的范围为[x + 1, x + d]，你可以移动木台使得可以跳跃，但是木台之间的相对顺序不得改变。现在问你是否可以跳到右岸？如果不可以输出NO，如果可以输出YES以及河的每个单元所对应的木台序号，...

2020-05-08

0 558

归并排序

归并排序，简而言之就是将两个内部顺序已经确定的集合进行合并，使得合并后的集合仍然有序那么对于一个无序集合，就需将其递归到最底层从底开始回归上一层，这样不停地将每个集合内部归并而有序。那么对于一个集合的逆序对该如何求呢？比如集合{5,4,3,2,1}逆序对为4+3+2+1 = 10 ...

2020-05-08

0 470

字符串哈希

字符串哈希就是将一个字符串映射成一个P进制的数，然后用前缀记录下来，当你查询某个字符串的哈希值时，只要用前缀相减就可以了。通常P取131或者13331来尽可能减少冲突，同时用unsigned long long值过大自动溢出避免手动取模 eg：s[] = "ABACBDAB"，...

2020-05-08

0 579

Codeforces Round #597 (Div. 2) A

题意: 给你两个数a和b(1 <= a, b <= 1e4)，i-a>=0 且i-a为白，则i为白，i-b>=0且i-b为白，则i为白，否则为黑。其中初始化0为白。问你是否有无穷个黑。题解：对这个问题，我们只需要简化：如果并没有无限个黑，必然是存在某...

2020-05-08

0 610

Codeforces Round #589 (Div. 2) D. Complete Tripartite （三分图）

题意： n点m边无向图，无自环，无重边给定的图可以断开连接下面我们有一个定义：让v1和v2为两个不连通的顶点非空子集函数f(v1, v2)为真当且仅当下面所有情况否满足： 1. 顶点集v1中的两点无边连接 2.顶点集v2中的两点无边连接 3.对任意在v1中的点和v2中的点，两点间有一条边 ...

2020-05-08

0 490

最长上升子序列

一、O(n^2)暴力，对于第i个元素，找到前i-1个元素中小于第i个元素的当前最长上升子序列。二、O(nlogn)二分，维护一个递增序列，对于第i个元素，如果其大于这个递增序列的最大值，将其加入序列末尾否则用第i个元素置换掉递增序列中最小的大于第i个元素的元素最长上升子序列的输出：...

2020-05-08

0 633

求组合数

1. 范围较小. 求，共n组询问。 1 ≤ n ≤ 10000, 1 ≤ b ≤ a ≤ 2000 暴力使用杨辉三角即可。f[i][j] = f[i - 1][j - 1] + f[i - 1][j] 2. 仍求第一问的值，但是1 ≤ b ≤ a ≤ ，预处理出的逆元和阶乘展开即可。 ...

2020-05-08

0 408