PhantomSamurai
PhantomSamurai
全部文章
分类
图论(1)
基础算法 二分 双指针等(4)
数据结构(3)
数论 数学(5)
比赛(1)
题解(53)
归档
标签
去牛客网
登录
/
注册
Blog
TA的专栏
29篇文章
0人订阅
每日一题
29篇文章
725人学习
全部文章
(共68篇)
约数 数学
description: 输入一个数a和b 求他们所有的公约数 a,b范围为1e13 solution: 数据范围大 直接暴力肯定是不行的 先gcd求他们的最大公约数x 那么有 a%x = 0 , b % x = 0 题目要求所有约数 设x的任意因子为i 那么有x%i = 0 , 所以有 a % i...
2020-07-25
0
481
Rinne Loves Xor 位运算
description: 给出数组A和B 求 solution: 首先我们根据乘法原理 可以把式子转变成 可以模拟一下题目的公式发现展开来这两的展开项是一样的,我们知道异或只有对应的位不同才对答案有贡献,所以我们将每个数拆分成每一位,按照位来处理结果分别是Ai的0位 * Bi的1位 + Ai的1...
2020-07-24
0
391
数列操作 STL vector
description: 设计一种数据结构 实现以下操作: 1.插入一个数x(insert)2.删除一个数x(delete)(如果有多个相同的数,则只删除一个)3.查询一个数x的排名(若有多个相同的数,就输出最小的排名)4.查询排名为x的数5.求一个数x的前驱6.求一个数x的后继 solution:...
2020-07-18
0
489
CSL分苹果 背包
description: 有n个苹果 分给两个人 要求两个人所得苹果质量之间差距最小 苹果不能被拆分 solution: 最理想的状态是两边均分 根据其没办法拆分的特性 把均分的质量作为背包的容量 这样问题就转换成背包最大容量是多少了跑一遍背包即可 code: #include <bits/s...
2020-07-18
0
638
新建 Microsoft Office Word 文档 STL
description: 对于文档有两个操作1.新建 编号取当前最小的没有用过的值 从1开始计算2.删除 删除对应编号询问每次新建的编号 solution: 容易想到先用bool来表示当前编号是否使用 但是正向维护当前已经使用的编号查询最小未使用的编号有些困难用一个优先队列或者set来维护被删除过的...
2020-07-18
0
585
指纹锁 STL
description: 把指纹当做一个小于1e7的数字 当数字差距<=k的时候认为是同一个人 对指纹系统有三种操作:1.添加 若有差距<=k的忽略此操作2.删除 删除所有差距<=k的数3.查询 solution: 用一个set来维护数据1.add 二分找大于等于该数的 判断差距是...
2020-07-14
2
568
发电 树状数组 逆元
description: 有n个发电机 开始效率均为1 对应有三种操作 1.给效率翻i倍 2.给效率翻1/i倍 3.查询区间内效率乘积 solution: n为1e6 看到求区间操作容易想到用树状数组或者线段树维护区间乘积 存在1/i倍的情况用逆元处理 模数是质数采用快速幂求逆元即可 code: #...
2020-07-14
1
499
字符串丝带 基础
description: 长度为n的字符串 m次询问 第i个位置上的字符在i之前出现几次 solution: 题意有点绕 只要用一个数组f[i] 来代表字符i在i之前出现多少次 数组标记字符出现多少次即可也可以考虑离线操作 code: #include <bits/stdc++.h> ...
2020-07-14
0
536
桃花 dfs 求最长链
description: 给出n个点的一颗树 求最长的一条链 solution: dfs两次 第一个次找到一条直径的另一端 第二次从该点开始跑 找到最远距离即可 code: #include <bits/stdc++.h> using namespace std; #define L...
2020-07-14
0
572
无关(relationship) 容斥原理
description: 给出一个包含k个全素数序列A 对于一个数x A中没有x的因子 则称x与A无关 问区间L,R中包括多少个与A无关的数 solution: L,R的范围很大 1e18 暴力肯定不可取 观察到k的范围很小 从k入手 考虑生成1~k的全排列 复杂度爆炸考虑容斥原理 由于每个Ai...
2020-07-12
0
497
首页
上一页
1
2
3
4
5
6
7
下一页
末页