- 博客(8)
- 收藏
- 关注
RSS订阅原创 Codeforces Round #686 (Div. 3) A-F题解
Codeforces Round #686 (Div. 3) A-F题解A. Special Permutation题意给定 nnn ,输出一个长度为 nnn 的全排列，每个位置 iii 上的数不等于 iii。思路1−n1-n1−n全排列循环右移一位。代码#include <bits/stdc++.h>using namespace std;const int M = 110;int dp[M];int main() { int T; cin >
2020-11-25 18:27:51
842
2
原创 Educational Codeforces Round 98 (Rated for Div. 2) A-E 题解
Educational Codeforces Round 98 (Rated for Div. 2) A-E 题解A. Robot Program题意给定 x,yx,yx,y ，一个机器人要从(0,0)(0,0)(0,0)点走到(x,y)(x,y)(x,y)点，每次操作能上下左右移动或者不动，且每次操作不能和上次操作相同，问最小操作次数。思路面 向 样 例 编 程其实就是每次向下或向右走，先交替，若到底还需要向右走，则一开始就向右走，之后每走一秒停一秒。反之亦然，不影响答案。答案为$ x +
2020-11-25 15:37:29
2119
4
原创 Codeforces Round #684 (Div. 2) A - C2 题解
Codeforces Round #684 (Div. 2) A - C2 题解A Buy the String题意给定一个长度为 nnn 的01串，你可以用 hhh 的代价把字符串中任意一个字符取反，最终你要把这个01串买下来，0的单价为c0c_0c0，1的单价为 c1c_1c1。现给你n,h,c0,c1n,h,c_0,c_1n,h,c0,c1以及一个01串，问你最少花多少可以买下这个串。输出最小总价。思路贪心，设c0<c1c_0 \lt c_1c0<c1，若c1−c0
2020-11-18 19:50:27
897
3
原创 Tarjan缩点算法 作用、原理、模板
Tarjan原理&模板来了来了，鸽了好久的图论基础。众所周知一个对于一个DAG我们可以做很多骚操作(比如拓扑，无需标记访问的DFS等)，那么一个图如果有环怎么办呢。Tarjan他来了（j不发音，所以中文应该是塔扬）。Tarjan算法作用：将一个有环图中的连通块缩成一个点(同一个连通块染上相同颜色)，使其变成一个DAG(有向无环图)后做各种操作。Tarjan算法原理其实还是DFS。需要一个dfn数组和一个low数组以及一个栈用于存放已遍历过但尚未染色的结点。dfn数组定义：dfn[u]
2020-07-07 14:10:22
781
原创 费马小定理 & Miller-Rabin素数测试
费马小定理 & Miller-Rabin素数测试1.简单介绍一下费马小定理若ppp为素数，aaa为正整数，且gcd(a,p)=1gcd(a,p)=1gcd(a,p)=1，则：ap−1≡1(mod p)a^{p-1}\equiv1(mod\ p)ap−1≡1(mod p)，证明如下：首先a,2a,3a,...(p−1)aa,2a,3a,...(p-1)aa,2a,3...
2020-02-07 00:56:52
384
3
原创 1.4 逆元
1.4 逆元定义，O(logn)O(logn)O(logn)求单个及线性求nnn个基本定义若a∗x≡1(mod b)a*x\equiv1(mod\ b)a∗x≡1(mod b)，则称xxx为aaa的逆元，记为a−1a^{-1}a−1。根据逆元的定义，可转化为a∗x+b∗y=1a*x+b*y=1a∗x+b∗y=1，用EXGCD算法求解逆元。代码如下：typedef lon...
2020-02-01 12:14:16
247
原创 1.3 GCD、EXGCD、线性同余方程
1.3 GCD、EXGCD、线性同余方程最大公约数（GCD）和最小公倍数（LCM）的基本概念也是小学知识。对于任意整数a,ba,ba,b，我们有一个很重要的公式，即a∗b=GCD(a,b)∗LCM(a,b)a*b = GCD(a,b)*LCM(a,b)a∗b=GCD(a,b)∗LCM(a,b)。首先我们会介绍几种基本的求GCD方式，虽然C++选手完全可以使用__gcd()函数去求，但自定义的求...
2020-01-27 20:34:36
1552
原创 【ACM入门】整除、同余的概念及快速幂
整除、同余的概念及快速幂整除、余数都是小学概念，但还是得学习一些细节。整除1、 a∣ba|ba∣b 代表b可以被a整除，b是a的倍数，a是b的约数。2、约定0可以被任何数整除。3、若存在整数 xxx ,yyy 使得a∗x+b∗y=1a*x+b*y = 1a∗x+b∗y=1，且a∣na|na∣n、b∣nb|nb∣n，那么(a∗b)∣n(a*b)|n(a∗b)∣n其他性质比较显然，就不作赘...
2020-01-27 15:30:56
3072
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人