作者: Zhang, Xuheng

86 篇文章

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
99%的人不知道的VMware的一个秘密(彩蛋)
这个彩蛋在12版本开始均有 1、按住Ctrl+Alt+Shift组合键不放,打开“文件菜单” 2、彩蛋会出现在菜单中,选择它即可 (新建····虚拟机) 3.此时会出现一个小游戏,规则很简单:用鼠标或者上下方向按键控制左侧横条,右侧横条由电脑自动操控,哪一方把小正方形反弹出界得一分
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 …
thumbnail
洛谷 8 月月赛 div1 & div2 赛后总结
先看结果。 Div1: 其实应该是388名,因为很多人都是1分。 Div2: Div2总结: T1 一开始用了ull直接算,结果20pts。感谢@23786提供的字符串思路。 然后就用了字符串做,92pts。 然后又加了一个特判,小的数直接算。AC。 大概卡了20min 考场代码: #include <bits/stdc++.h> using…
thumbnail
洛谷8月月赛官方题解
注意:题解是md格式。 # A. Number ## Subtask 1,3 对于Subtask 3,我们计算发现 $10^k+x\le 2\times10^{18}$,因此我们可以使用`long long`保存 $10^k$,直接计算结果。 如何计算 $10^k$ 呢?这里有三种写法: - 一个`for`循环将一个初始为 $1$ 的变量进行 $k…