生之、如舟

分类

动态规划(8) 博弈论(1) 图论(7) 基本算法(29) 并查集(17) 思维(3) 数学(14) 数据结构(5) 数论(18) 最短路(4) 枚举(1) 树状数组(13) 树论(4) 模板(7) 比赛(15) 算法总结(3) 线段树(11) 蓝桥杯(1) 贪心(1)

/ 注册

TA的专栏 67篇文章 1人订阅

Ryuichi的算法分享

67篇文章 1416人学习

全部文章（共166篇）

Acwing217. 绿豆蛙的归宿【DAG+数学期望】来自专栏

需要使用记忆话，一个点的期望只去计算一次。 #include <stdio.h> #include <cstring> #include <algorithm> #include <vector> #include <stack> #inc...

数学期望

2021-01-11

0 671

Acwing216. Rainbow的信号【期望+位运算】来自专栏

网上好多异或都用的奇期间，偶区间来处理的。我是用的计数异或前缀和为0和为1的个数来处理的，比较好理解。但是要注意到前缀可以为空，多一个什么也不选，异或为0的前缀 #include <stdio.h> #include <cstring> #include <algori...

数学期望

2021-01-11

0 637

A. Division 【数学】1500 来自专栏

A. Division 题意给定p和q，找一个最大的x，x能整除p，但是q不能整除x 分析 x肯定是p的唯一分解定理的一部分，所以可以考虑从x中删除一下，使得q整除x。由于p太大，分解它肯定会超时，所以可以分解q，然后看q的每一个质因数的次方，p的这个质因数次方是否都小于它。如果都小于它，那么...

数学2000以下

2020-11-30

0 776

Matrix POJ - 2155 【二维树状数组】【模板题】来自专栏

Matrix POJ - 2155 解法二维树状数组直接写即可，变反写成+1，最后查询的时候%2就行代码 #include <iostream> #include <stdio.h> #include <cstring> #include <str...

树状数组

2020-11-20

0 695

Different GCD Subarray Query HDU - 5869 【离线处理】【gcd】【树状数组】来自专栏

Different GCD Subarray Query HDU - 5869 解法以一个数字结尾的所有连续段gcd，不会超过log个，想象一下一个gcd的唯一分解，每次要产生新的gcd，肯定是从老的gcd去掉一些质因子，也就是说至少会去掉>=2的数，gcd至少变成1/2，是呈指数型减少...

树状数组

2020-11-20

0 724

B. Neko Performs Cat Furrier Transform 【位运算】1300

B. Neko Performs Cat Furrier Transform 解法目的就是为了让二进制全变成1，那么直接从最高位的0开始，假如最高位的0位置是h，那么就异或(1<<(h+1))-1,当然如果是偶数次操作，就+1这样能够保证2次操作最少可以消除一个0，1e6不到20位...

位运算

2020-11-19

0 641

A. You Are Given Two Binary Strings... 【位运算】1100

A. You Are Given Two Binary Strings... 题解考虑y的最后一个1的位置，需要刚好把它左移到跟x的一个1匹配，如果左移多了，字典序就增加了1，左移少了，就浪费了一些位置可以是0和0匹配从而使得字典序更小代码 #include <bits/stdc++....

位运算

2020-11-19

0 527

C. Make Good 【位运算】1400 来自专栏

C. Make Good 解法遍历a数组，把和跟异或值都算出来，我们最终要做到的目的是，sum和的二进制是异或值yi左移1位得来的。 step1 ：添加yi，这样和就变成了sum+yi，yi就变成了0step2 ：添加sum+yi，这样和就变成了2*（sum+yi），yi就变成了s...

位运算

2020-11-19

0 644

C. Adding Powers 【位运算】1400 来自专栏

C. Adding Powers 解法因为选择是可以任意位置的，所以相当于数组是无序的。然后k的每次方要么不用，要么用一次。所以将数组里面的每个数转换成k进制，然后用一个cnt[]数组来计算，计算k的每次方出现了多少次。只有所以cnt[i] >= 0 才是yes 代码 #include ...

位运算

2020-11-19

0 692

C. Johnny and Another Rating Drop 【位运算】1400 来自专栏

C. Johnny and Another Rating Drop 解法这种题，可以先打表找找规律。然后观察发现，每一个数相对于前一个数，都是由其进位得来的，想想一下一个数进位之后就只会把进位位由0变1，右边的1变成0，也就是之后涉及进位的部分发生了反转。就类似于反码+1变补码。现在就能知道任...

位运算

2020-11-19

0 708