Description 翻译: 给定价格 和最晚可以卖掉的时间 ，求卖出的最大金额。 Solution1 几年前的老题目了，看了下数据范围，根本不用考虑优化。对商品按价格从大到小排序，每次选取当前最高价格的，然后从 开始往前找是否有哪一天还没用过，直接 暴力即可.PS: 并查集可以优化一下这个过程，懒得写了。 Code1 #include<bits/stdc++.h> using namespace std; typedef long long ll; const long long inf = 1e18; const int N = 5e5 + 5, mod = 99824435...

基于分治法的三维最近点对问题的研究 林泽瀚（1.广州大学 数学与信息科学学院， 广东， 广州） 摘要：最近点对问题被广泛应用于工程项目之中, 近年来, 由于大数据计算和人工智能等领域的兴起, 许多计算领域对三维最近点对问题的运用更加广泛. 分治法求解最近点对是计算几何领域的经典算法. 本论文通过对传统的二维最近点对问题进行分析并推广到三维空间下，利用分治法的思想和鸽巢原理，设计出两种高效求解三维最近点对的方法, 对比朴素做法，在时间复杂度上有显著的优化. 关键词：三维最近点对；计算几何；分治法；双指针; 鸽巢原理; 时间复杂度; 1. 引言 ​ 分治法在计算机科学领域中占据着重要的地位.分治即...

Description  终于Alice走出了大魔王的陷阱，可是现在傻傻的她忘了带武器了，这可如何是好???这个时候，一个神秘老人走到她面前答应无偿给她武器，但老人有个条件，需要将所选武器分别放在天平的两端，若天平平衡则可以将天平上的所有武器拿走，还好这个天平锈迹斑斑，只要两端重量相差小于等于m就会保持平衡，Alice傻傻的认为越重的武器越好，求Alice最多能拿走的武器总重量。（不限操作次数） Solution  分析了一下问题，情况很多，显然贪心做不了，考虑做 ， 令 为前 个物品取得天平两端相差 的最优策略, 那么有 . 加 是因为当 出现负数时，此时重量大的天平和重量小的天平一侧角色互...

1. 内容复述 Abstract ​ 基于字典的压缩方案提供了快速的解码操作，相比于统计学方法和基于概率的方法，一般应以降低压缩效率为代价。在这篇文章中，我们把基于字典的技术应用于倒排表列的压缩中，结果表明，这些整数序列对于字典方法的匹配表现出高度正则并且与某些类型的字典是匹配良好，能够在压缩效率和压缩效益之间实现一个新的权衡标准。我们通过对两个大型文本集合的文档级倒排索引和大量其他索引压缩实现结果作为参考点论述支撑我们的观察结果。实验证明压缩效率和压缩效益的差距可以大大缩小。 Keywords 倒排索引；效率；压缩；解码 1.1 Introduction ​ 压缩的倒排文件仍然是一个非常重要...

Description Applese有1个容量为v的背包，有n个物品，每一个物品有一个价值ai，以及一个大小bi然后他对此提出了自己的疑问，如果我不要装的物品装的价值最大，只是一定需要装m个物品，要使得求出来的物品价值的中位数最大Applese觉得这个题依然太菜，于是他把这个问题丢给了你当物品数量为偶数时，中位数即中间两个物品的价值的平均值 Solution 想起了之前也有道中位数的题，中位数问题可以用堆来优化，这道题要分类讨论，奇偶的情况不太一样对于中位数，我们可以维护左边 个最少花费和右边 个最少花费，然后遍历取最优最少花费可以维护一个前缀和与一个后缀和然后分奇偶  奇数: 直接做 偶数...

把会的题放一起吧，不然字数太少了。 A. 论如何出一道水题 Description 给定 n，求一对整数 (i,j)，在满足 1 ≤ i ≤ j ≤ n 且 \gcd(i,j)=1gcd(i,j)=1 的前提下，要求最大化 i+j 的值 Solution 打表，然后找到规律  Code #pragma GCC optimize(3) #include<bits/stdc++.h> using namespace std; const int mod = 100000000; const int N = 5e5 + 5; typedef long long ll; const dou...

争取每天早起一小时写一题emmm Description 这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵 不能相互重叠。 Solution 注意到 其实就是两列数字求最大连续子段和的变形我们可以枚举当前第一列所处位置 i, 第二列所处位置 j, 当前已经取了 k 个矩阵做 的状态转移我们可以枚举上一个矩阵的终点位置，然后利用预处理前缀和的思想对每个方案取max   第 k 个取第二列的情况  第 k 个取第一列的情况  i == j, 第 k 个取一个t * 2 的小矩阵  Code #pragma GCC optimize(3) #in...

Description 你有n种牌，第i种牌的数目为ci。另外有一种特殊的牌：joker，它的数目是m。你可以用每种牌各一张来组成一套牌，也可以用一张joker和除了某一种牌以外的其他牌各一张组成1套牌。比如，当n=3时，一共有4种合法的套牌：{1,2,3}, {J,2,3}, {1,J,3}, {1,2,J}。 给出n, m和ci，你的任务是组成尽量多的套牌。每张牌最多只能用在一副套牌里（可以有牌不使用）。 Solution 求最大的答案，首先考虑推公式，公式不好推，转而考虑二分答案然后去 。 我们二分一个答案，然后对于每一种牌去检验，如果当前的牌小于答案，那么就要用 去填充，最后注意我们二...

个人泛读后的理解概括 主要方向  搜索引擎系统关键技术。主要研究搜索引擎系统相关的数据索引、数据压缩、计算和优化等关键技术。 云存储系统及可靠性研究研究基于数据中心的云存储系统的数据布局、数据编码、数据迁移、重复数据删除和可靠性分析等内容。 面向大数据的GPU计算技术该课题针对生物信息学、图形图像等领域的大数据处理问题，研究基于GPU的并行算法。 应用数学、组合数学等领域的并行计算研究该课题针对相关领域的大规模计算问题，研究基于多核、众核及集群的并行计算方法。 云游戏系统及其资源管理问题研究该课题研究云游戏系统的设计与优化，以及云游戏系统中的请求调度、游戏布局、服务器提供等资源管理问题。 区块...

Description 德玛西亚是一个实力雄厚、奉公守法的国家，有着功勋卓著的光荣军史。这里非常重视正义、荣耀、职责的意识形态，这里的人民为此感到强烈自豪。有一天他们想去制裁邪恶的比尔吉沃特，于是派遣了自己最优秀的战士。结果比尔吉沃特领土太小，只有长为n宽为m共计n*m块土地，其中有些土地标记为0表示为高山峻岭或者深海湖泊，英雄们无法在其中站立，只有标记为1的土地才能容纳一个英雄。德玛西亚的英雄们战斗时有一个特点，他们不希望队友站在自己旁边显得很暧昧。请问最多能有多少种安排德玛西亚英雄的方法？ Solution 补题向，一点进来就看见状压dp关键词，看数据范围 确实也是状压dp考虑几种情况就可...

Description Cwbc和XHRlyb生活在s市，这天他们打算一起出去旅游。旅行地图上有n个城市，它们之间通过n-1条道路联通。Cwbc和XHRlyb第一天会在s市住宿，并游览与它距离不超过1的所有城市，之后的每天会选择一个城市住宿，然后游览与它距离不超过1的所有城市。他们不想住在一个已经浏览过的城市，又想尽可能多的延长旅行时间。XHRlyb想知道她与Cwbc最多能度过多少天的时光呢？聪明的你在仔细阅读题目后，一定可以顺利的解决这个问题！ Solution 树上最大独立集问题。树的最大独立集，就是这样的一个集合，这些集合里面的点在树中互不相邻。树形dp可以解决这个问题, 表示不在 的最...

Description 给定两个管道，任意取珠子，有 种情况，定义 为取 个珠子的方案数总和现在要求  Solution 对于 ，考虑其意义，从函数合成的角度，可以理解为两个相同的过程相互合成，即两次从管道取珠相同的方案数，那么这个计数问题我们可以用 去解决了，考虑 为第一个管道取了 个，第二个管道取了 个，第三个管道取了 个，第四个管道取了 个，显然空间复杂度过高，考虑优化一下， ， 可以少一维枚举，然后呢， 只会和 有关系，所以滚动数组优化一下，答案为 , 最终空间复杂度 , 时间复杂度为 另外，这道题卡常，可以试试开 O3 还有减少取模次数去优化常数。 Code #pragma GCC ...

Description 小A与小B这次两个人都被困在了迷宫里面的两个不同的位置，而他们希望能够迅速找到对方，然后再考虑如何逃离迷宫的事情。小A每次可以移动一个位置，而小B每次可以移动两次位置，小A移动的方向是上下左右左上左下右上右下8个方向，小B移动的方向是上下左右4个方向，请问他们最早什么时候能够找到对方，如果他们最终无法相遇，那么就输出“NO”。 Solution 这类问题通常都是用bfs做的，然后这道题比较特别的是小B可以连续移动两次，我们要考虑多种情况，一开始想的是走16(4 * 4)种情况，但是其实如果有障碍物的话，不能直接这样想，干脆让小B连续走两次，然后再更新他的step。这样的...

Description 小AA找到了一个数列，她想要知道这个数列中所有长度为偶数的区间异或和之和 。后来她发现这个问题太简单了，于是她加了一个限制，要求区间长度在[L,R]之间，然后她就不会了。。。请你告诉她问题的答案。 Solution  异或问题优先考虑二进制位，对于这个问题，我们需要考虑偶数长度的区间，那么先对 做处理，因为如果 , 是奇数其实加一/减一没有区别。然后处理一下前缀异或和, 因为我们有性质 。最后我们要找到哪些是有贡献的，我们考虑枚举右端点，如果当前点的异或是 1，那么需要在前面找异或为 0 的点才有贡献，反之如果当前点的异或是 0，那么要在前面找异或为 1 的点才有贡献，...