PhantomSamurai

分类

图论(1) 基础算法二分双指针等(4) 数据结构(3) 数论数学(5) 比赛(1) 题解(53)

/ 注册

TA的专栏 29篇文章 0人订阅

29篇文章 711人学习

全部文章（共68篇）

区间异或打表+二分

description：一个长为n的序列查询m次每次输出最短区间长度使得区间内异或和大等于x solution：区间长度只有3000，没有更新操作，支持离线。先前缀异或和，而后先n*n 打表构造区间长度和获取区间值，区间值肯定取尽量大。对数组求max操作后，明显具有单调性，二分答案即可打...

2020-12-09

0 450

最好的宝石线段树

description： n个数有两种操作 1. 将a[x]的值改成y 2.查询区间l,r中的最大值以及最大值出现的次数 solution：线段树维护最大值的同时，再维护一个出现次数。对于出现次数的修改需要注意：1.初始值为1 2.更新操作时当结点值改变出现次数变成 -> 只有当父...

2020-12-09

0 389

Jokewithpermutation dfs

Jokewithpermutation description 给定一个不含空格的字符串问字符串能否构成一个1~n全排列 solution： n只有50 说明只有1位数或者两位数如果字符串长度小于9 说明只有一位数输出全部就好算是一个剪枝其次可以根据字符串长度计算出全排列最大的数是多少 ...

2020-10-05

0 579

装货物 dfs

装货物 description： n个物品 x个可容纳体积为w的箱子问n个物品是否能全部装进箱子内物品不可拆分 solution： n只有21 可以状压dp或者dfs 这里直接采用dfs 先预处理x个箱子的体积为w 然后从第一个物品开始搜加上一些剪枝从大的开始放你大的肯定没有小的更加灵活所...

2020-08-31

0 429

打boss 数学回合制游戏

打Boss description：题目说的很明显了 solution：对于这种回合制问题一般都采用让最后一回合来计算。首先特判一些特殊情况：1.玩家一下就可把Boss打死输出Yes2.Boss一下就可把玩家打死输出No3.玩家的攻击力还没回血高输出No 然后我们计算一下玩家能挺过多...

2020-08-31

0 440

多重序列快速幂数学

link: https://ac.nowcoder.com/acm/contest/5961/B description: n个序列每个序列有m个数他们都是k的整数次幂 n个序列中所有数相乘乘积最大的值是多少取模后输出 solution: n和m范围不大可以接受n * m 如果暴力计算的话 ...

2020-08-14

0 511

公因子数论

link https://ac.nowcoder.com/acm/contest/6112/C description：有个n个数希望求一个x 使得每个数 +x 的gcd 值最大，求出gcd值和最小的x solution： gcd的性质： gcd(x,y) = gcd(x,y - x) 三...

2020-08-14

0 420

异或图位运算

Touch description: 题意有点难读具体化的讲就是有n个点，每个点有点权。用这n个点来构造q个无向图，对于每个无向图Ei来说规定属于Ei的点x,y. 满足Valx ^ Valy = k 就会有一条权值为1的边，问点x到点y的最短距离 solution: 首先是异或的一个性质 a ^ ...

2020-08-14

0 451

小黄鸭数学积分

https://ac.nowcoder.com/acm/contest/1085/F description：一个球浮在水面上，给出R,m，代表球的半径和质量，求浮在水面上的高度 solution：有浮力定律可得 pgV = mg ,p = 1 所以V = m我们设圆的方程为我们通过横截面圆根...

2020-08-12

0 501

区间求和莫队

https://ac.nowcoder.com/acm/contest/1085/G description： n个数m个询问 l,r 问 num(ai)为ai出现的次数 solution：这题区间问题可以很好的用莫队维护，设定一个vis[i]数组代表出现的次数，关于add操作，每出现一个...

2020-08-10

0 458