Fyind's Blog

AtCoder Grand Contest 047 AtCoder Grand Contest 047 A. Integer Product 给定 \(n\) 个浮点数，计算有多少个 \((i, j)\) 使得 \(A_{i} \cdot A_{j}\) 是整数 \(2\leq N \leq 200 \ 000\) , $ 0 < A_{i} ^{4}$ , \(A_{i}\) 最多 \(9\) 为小数. 思路 通过题设条件缩小范围， 枚举 由于数据比较大，不能直接暴力做。判断是整数这个条件不太好集体维护。所以要找出题目中的特性，看看有没有机会让范围缩小。最好是可以 先考虑 \(A_{i} \cdot A_{j}\) 什么情况下是整数。发现，对于任意有限小数 \(x\), 可以在乘上 \(10^{n}\) 后肯定会变成整数。所以每个数必然是 \(k\cdot 2^{m}\cdot 5^{n}\) 的形式, 通过乘 \(10^{n}\) 把分母上的 \(2^{m}\cdot 5^{n}\) 约去. 而之前的 \(k\) 不影响答案。所以我们只要考虑 \(2^{m}\cd...

线段树 线段树是一种用来维护区间性质的数据结构，此篇不讲解基础，而是讲解在算法竞赛中的应用。读者需要至少会写线段树懒标记维护区间求和操作。 目前使用的模板 我的懒标记的定义是： 已经维护好了当前节点，但子节点还没维护好. 普通版本 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950const int maxn = 1e5 + 5;int n, m;typedef long long typec;#define lson (o<<1)#define rson (o<<1|1)#define mid ((l+r)>>1)#define len(x,y) ((y)-(x)+1)typec sumv[maxn*4], addv[maxn*4];typec A[maxn], qans, v;int ql, qr;void build(int o, int l, int r) { addv[o] = 0; ...

Educational Codeforces Round 92 (Rated for Div. 2) link A. LCM Problem 构造 给定区间 \([l,r]\) 求 \(2\) 个在里面的数，使得它们的最小公倍数也在区间内，否则输出-1 -1 . 可以知道 \(l, l*2\) 是2个最小的可能组合，只要判断 \(l*2 > r\) 即可. B. Array Walk 贪心 由于可以折返的步数比较少。我们可以枚举折返的步数。当折返的步数固定为 \(j\) 的时候。有2种情况， \(j\) 步都是折返后又回来。这种情况最远走到了 \([1,k-2j]\) \(j-1\) 步是折返后又回来，最后一步是折返后不回来。这种情况的区间是 \([1,k-2(j-1)-1]\) 可以证明：若折返，则必定是在当前区间的最大两个相邻元素间折返。 那么我们用前缀和的方式求出 \([1,i]\) 的和还有最大相邻元素的位置。那么分情况讨论这两种情况的最大值。最后取个更优的解即可 \(O(n)\) 123456789101112131415161718192021222...

Week1 : 树 概念 vollständige Baum 完全树(所有节点有相同孩子个数) -verzweigte Baum k叉树 数学归纳法 证明完全二叉树的深度为 Induktionsanfang: ==n = 1==: Laut induktiver Definition enthält jeder Unterbuam mindestens einen Knoten. n=1 bedeutet also, dass der Baum ein Blatt ist. Die Tiefe ist 1. Zu zeigen ist also: . Es gilt Induktionsvoraussetzung: ==Für alle gilt, dass== die Tiefe eines s vollständigen 2-verzweigten Baumes mit Knoten höchstens ist. Induktionsschritt: ==Betrachte Bäume mit Knoten.== Fallunterscheidung: ...

ArchLinux完整安装 首先贴几个有用的链接 https://www.viseator.com/2017/05/17/arch_install/ https://wiki.archlinux.org/ Vmware Workstation虚拟机安装 下载iso镜像 https://www.archlinux.org/download/ 这个链接里面找一个网站的版本下载，这里选择了163。然后下载里面的archlinux-日期-x86_64.iso 这个文件 image-20200602094003121 创建虚拟机 点击创建新的虚拟机 image-20200602094126559 然后选择镜像 image-20200602094239435 操作系统选择Linux 5.x 64位。VirtualBox可以直接Archlinux 64位 然后给虚拟机命名，然后选择cpu和内存大小。这个根据系统配置自行选择。我选择了2个2核处理器，4g内存。后面默认过去，到磁盘大小，我给了20g。然后后面的一直默认即可。 开启此虚拟机，进入安装界面 image-20200...

软件技术 编译环境设置 下载Maven 到这个链接 里下载maven的包 image-20200507114645077 然后解压到某个目录下， 配置环境变量 把maven目录下的bin目录添加到path里面 image-20200507114852666 然后可以用 mvn -v 检查配置情况 image-20200507115027756 Lecture 2 Software lifecycle 分析问题 要从问题中提取功能，然后记录在backlog上： 比如说： Bumpers is a game where cars drive on a game board and can crash each other. 
 In each collision, there is a winning car. 
 The car that wins all collisions is the winner of the game. 
 The player can start and stop the game. When the game is started,...

三行写完高斯消元，这就是Python!!! 洛谷评测链接 先给大家看一眼核心代码 核心代码 123for i in range(len(a)): row = [j for j in range(len(a)) if a[j][i] != 0 and sum(a[j][:i]) < 1e-8][0] a[:] = [r + a[row]*(-r[i]/a[row][i]) if j != row else r/a[row][i] for (j,r) in enumerate(a)] 没错，就只有三行，完成了高斯消元最核心的操作，把矩阵消元成主对角线为1，其余除了常数项全是0的形式。我只用了Python中的切片操作，列表解析式，还有numpy中array的性质。 为了方便大家理解，我先来介绍一些这些python中的语法 python语法介绍 切片 语法格式是 [开始:结束] 可以取出列表中的一段区间,如果不填写就是默认开始位置是0，结束位置是列表最后一个元素位置。注意这里的区间是左闭右开区间。并且支持倒着数，也就是使用负号 比如： 12345l = [0,2,3,4...

Formale Sprachen 语言问题(Wortproblem)：给定一个字符串，这个字符串是由某个语法生成的吗？也就是它是否符合某个语法规则。 识别器(Recognizer): 一个能解决对应语法的语言问题的抽象 基本概念 定义2.1 一个字母表(Alphabet) 是一个有限集合。比如 ASCII, Unicode 一个语句(Wort/String) 是从字母表中组合出的有限字母序列，比如 010 指代语句的长度 空字符串是 $$ 若 是语句，那么 是它们的组合(Konkatenation) 若 是一个语句，那么 是如下定义的： 是字符集 的所有语句 子集 是一个语言(formale Sprache) 定义2.3 语言的操作 连接: 计算规则 定义 2.7 语法 一个语法(Grammatik)是4元组 是变量符号集合(Menge von Nichtterminalzeichen), 它是组织语言的字符。 是字符集(Menge von Terminalzeichen) 是Produktionen的有限集合 是...

语义分析 大观念是输入一个程序文本，我们把它分解为一个个小的词组(Token) image-20200430170243609 Token 名字 , 常数 , 操作符 保留字 Siever 在做分析之前，我们要进行预处理(pre-processing): 扔掉多余的： 空格，注释 收集Pragmas, 用它们更具体的含义代替 Token，比如constants,names 正则表达式 时程序编写的有限字符集 定义：正则表达式的集合 时最小的集合 ，满足： ($$ 不是 中的新符号) 对于所有 , 若 练习 1.1 根据要求写出正则表达式 我们定义了一个语法： 对于 ,我们递归地定义一个语言 如下： > 练习1.2 写出正则表达式的语言 对于一个正则表达式，我们也有一棵树与之对应： image-20200430171931128 有穷自动机 一个不确定的有穷自动机( nicht-deterministischer endlicher Automat (NFA) ) 是一个元组 . 是事件的有限集 是有限的字符集...

信号与系统 信号系统概念 信号的分类 确定信号：可以用函数描述的 连续信号：在 时间内有定义 离散信号 可以写成 随机信号：不能用函数描述的，只能知道概率 周期信号和非周期信号 连续信号的周期 连续周期信号 ，周期是，满足： 比如余弦信号 ，周期是 若两个周期信号相加，判断 是有理数。如果是那就是。 离散信号周期 周期是 : 能量与功率信号 能量等于损失功率的积分，可以想象成是一个1欧姆的电阻的电功率 将信号 施加于 的电阻上，它所消耗的瞬时功率为 ,于是能量定义为： 平均功率： 能量有限信号： ，此时 功率有限信号： ，此时 对于离散信号也有能量信号和功率信号： 因果和反因果信号 因果信号： 的信号 ,也就是时接入的信号 反因果信号： (除0信号外) 基本信号 阶跃函数 选的一个函数序列 ,求极限 它可以用来叠加表示其他信号，比如 image-20200423114537474 可以表示信号作用的区间 image-20200423114640594 积分 冲激函数 单位冲激函数：是奇异函数，它是对强度极大，作用时间 极短的...