hnust_yangyanjun

题解

大数加法(1) 尺取法(1) 面经(4)

/ 注册

全部文章 / 题解（共119篇）

Bookshelves 来自专栏

题意：给你一个长度为n的数组，请你按顺序分成k份，然后将每一份的和进行位与操作，求结果最大为多少？思路：从高位到低位枚举结果，即如果加入该位后结果满足条件则将该位加入结果，否则舍弃该位。判断结果是否满足条件使用dp：dp[i][j]表示将前i个数分成j组是否满足条件；dp[i][j]=(dp[i]...

位操作 dp

2020-11-17

3 703

Vitya and Strange Lesson

题意：给你一个长度为n的数组，然后有m次询问，每次询问有一个值x，让数组的每一个值异或x后，求数组中不存在的最小非负整数。思路：先将数组中的元素按01trie树建立，然后每一次查询查询相当于原数组和（当前的值和前面次数的值异或）异或。01trie树上找答案：如果与当前位异或为0的点不存在则输出当...

01trie

2020-11-05

2 547

奶牛异或

题意：给你一个长度为n的序列，让你选择你个连续的子序列做Xor操作求最大值为多少？并且该区间是什么？（如果有多个解，则取右边界最小（第一关键词），区间长度最短（第二关键词））。思路：对数组求前缀异或和，即求[1,2][1,3]....[1,n]等区间的异或和，然后你将二个区间异或后可以发现是一个连...

01trie

2020-11-05

2 534

The XOR Largest Pair

题意：给你n个整数，让你选择两个数进行Xor操作后值最大为多少？思路：建一颗01trie树，从高位到低位，然后从遍历数组，利用01trie树求每一个数与其中某一个一个数Xor的最大值，然后取总的最大值。取法：如果该数在该位上是1则尽可能在01trie树该位取0使其Xor为1。如果该数在该位上是0则...

01trie

2020-11-05

2 610

起床困难综合症

题意：让你选择一个0-m的值，求出在经历n次位操作后最大值为多少？思路：进行位操作时，每一个位的值是独立的，所以我们可以按下列情况进行计算：①：如果该位为0时结果该位为1时该位取0。②：如果该位为0时结果为0且该位为1时结果为1时该位取1。（不超出m的范围，否则取0）③：如果该位为0和1时结果都为...

2020-10-24

6 596

What Goes Up Must Come Down

题意：给你一个长度为n的序列，使序列呈先升序再降序的最少操作次数为多少？每次操作可以交换相邻的两个数。思路：对于每一个数来说，它最终要么左边的数全比它小，要么右边的数全比他小，每次移动相邻两个位置，所以你只需要判断它左边比它大的数的个数和右边比它大的个数的最小值（哪边小与那边大于它的交换），用树状...

树状数组

2020-10-04

2 755

Stressful Training

题意：有n台笔记本电脑，它们有一个初始电量ai，和每分钟耗电量bi,有一场训练需要持续k分钟，在每一分钟开始时电量不能为负，你能使用一个多大功率的充电器使其能完成训练，如果没有，则输出-1. 思路：二分枚举答案，如果一个超大的功率都不行，则说明没有，输出-1，判断一个功率是否可行，可以记录在该功率时...

二分

2020-09-29

1 633

[SCOI2009]最长距离

题意：有一个n*m的地图，为1表示为有障碍物，你可以移走t个障碍物，求二个可以相互到达的点最大的欧几里德距离? 思路：dfs暴力求出每一个点在移走t个障碍物后能到达的点，然后暴力求最大距离。代码： #include <bits/stdc++.h> typedef long long l...

dfs

2020-09-28

0 552

List Of Integers

题意：给你x、p、k三个数，让你求大于x的第k个与p互素的数？思路：求出p的质因子，然后求小于等于x的与p互质的个数求出为j，题意就相当于求大于0的第k+j个与p互素的数了，二分枚举答案，求小于等于某一个数与p互质的个数使用容斥原理计算得出。代码： #include<cstdio> ...

二分容斥

2020-09-25

1 637

蚯蚓

题意：有n条蚯蚓，在m秒内每一秒选择最长的一条蚯蚓分成二份，其余蚯蚓增长q长度，然后按要求输出。思路：用二个队列进行模拟，维护二个队列的单调性，一个队列加入长的，另一个队列加入短的，这样二个队列就是单调的，队列中保持0时刻的长度。代码： ...

模拟队列

2020-09-01

2 669