分类: C++学习笔记

70 篇文章

thumbnail
算法讲解之贪心算法(转)
贪心算法 本站OJ已搭建完成。本文题目提交地址: https://hywiki.xyz/contest/1 思路 若在求解一个问题时,能根据每次所得到的局部最优解,推导出全局最优或最优目标。 那么,我们可以根据这个策略,每次得到局部最优解答,逐步而推导出问题,这种策略称为贪心法 【例1】 在N行M列的正整数矩阵中,要求从每行中选出1个数,使得选出的…
thumbnail
算法讲解之回溯法(转)
网上偶然看到这篇文章,发现跟许老师的ppt内容一模一样,故在此分享。 回溯算法 搜索与回溯是计算机解题中常用的算法,很多问题无法根据某种确定的计算法则来求解,可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是:为了求得问题的解,先选择某一种可能情况向前探索,在探索过程中,一旦发现原来的选择是错误的,就退回一步重新选择,继续…
thumbnail
C/C++ IDE推荐
23786 NSObject: (1)搞OI Mac:Xcode,C+++(未开发完) Windows:Dev-C++,Code::Blocks(不是特别推荐) 跨平台(含Linux):Visual Studio Code / Sublime Text 加装插件 Mac / Linux:Vim + g++ + 插件(全部在终端完成) (2)大项目 …
thumbnail
树状数组学习笔记
Part 1 基础 树状数组可以解决大部分基于区间上的更新以及求和问题。 树状数组修改和查询的复杂度都是 $O(logn)$,而且相比线段树系数要少很多,比传统数组要快,而且容易写。 缺点是遇到复杂的区间问题还是不能解决,功能还是有限。 单点更新、区间查询 核心: int a[500005],c[500005]; int lowbit(int x)…
thumbnail
位运算学习笔记
为了初赛写的。。 与、或、异或、非 非 $¬$ 取反。 与 $∧$ 只有两个对应位都为 $1$ 时才为 $1$。 或 $∨$ 只要两个对应位中有一个 $1$ 时就为 $1$。 异或 ^ 只有两个对应位不同时才为 $1$。 $a$ ^ $b$ ^ $b=a$ 补码:在二进制表示下,正数和 $0$ 的补码为其本身,负数的补码是将其对应正数按位取反后加一…
thumbnail
前缀和与差分学习笔记
其实是复习笔记。 前缀和 一般用来求区间和。 一维 现在给出一个数列 $a$,要求回答 $m$ 次询问,每次询问下标 $l$ 到 $r$ 的和。 算好前缀和, ```s[r]−s[l−1]``` 就是答案。 #include <bits/stdc++.h> using namespace std; int n; int a[1005],…
thumbnail
简单数论学习笔记
注意标题:简单。 素数 素性测试 Fermat 小定理乱搞 bool millerRabin(int n) { if (n < 3) return n == 2; // test_time 为测试次数,建议设为不小于 8 // 的整数以保证正确率,但也不宜过大,否则会影响效率 for (int i = 1; i <= test_time…
thumbnail
图论基础学习笔记
文章中包含的模板都集中在这里 目录 画图工具 第一部分 图的遍历 $1.$ 什么是图 由一些顶点和边组成的图形即为图。 上图中,边有 $1-2,2-5,2-3$ 等。 $2.$ 有向图和无向图 简单来说,如果有两个顶点 $a,b$。 那么无向图有 $a-b,b-a$ 两条。 而有向图只有 $a-b$ 或 $b-a$ 一条。 $3.$ 深度优先搜索遍…
thumbnail
洛谷 10 月月赛 II 赛后总结
本文同见于,作者都是我。 结果:150pts rk 286。 100+30+20+0=150 T1: 找规律题。 T2: 做了 m=0 的部分分。 $T3$ 前缀和 + 暴力 = AC Subtask 1。 #include <bits/stdc++.h> using namespace std; typedef long long l…
thumbnail
洛谷10月月赛 I 赛后总结
本文同见于:Link 作者都是本人。 结果: div1 rk190 10+0+0+5=15pts div2 rk324 100+40+10+0=150pts div2: T1: 太水的一道题,直接加加加就好了。 本来 5 分钟就能 AC 的,但因为讨厌的测评机坏了,测了 30min 才 AC (本来还有机会一血的) T2: 想打全部分的,但 WA …
thumbnail
C++ gcd 函数的写法
C++写gcd函数有几种写法,下面介绍几种。 1.while循环(常速) 此段代码a、b可以为0 inline int gcd(int a,int b) { int r; while(b>0) { r=a%b; a=b; b=r; } return a; } 2.三目运算符(较快) 此段代码a、b可以为0 int gcd(int a,int …