Description(凑字数) VMware实习生小V酷爱数学，有一天她在数学书上看到了这样一道题：，她很快解决了这个问题。现在，她在思考，对于更一般的情况，存在多少本质不同的整数解： 答案对 取模。两组解本质不同当且仅当一组解无法通过交换变量的取值变成另一组。 Solution 计数题, 考虑 做法, 首先 能被拆成多个 相加, 那么举个例子如:, 而 则拆不了, 只有一种方案可以得出结论: 要被拆成多个 相加, 必须能表示成 其中 是 的因子中能够被开方的最大因子 , 可以通过质因数分解求出那么此时我们可以选择 个数字，使得他们构成 其实也就等价于选择 个数字的和能够等于 令 表示当前和...

直接写个合集吧, 单独写可能300字都不够(迫真 A. 青蛙过河 题目太长了, 去看了下别人解释的题意简单来说就是在石墩上青蛙可以类似Hanoi问题(汉诺塔)地叠着我们想叠得越多越好，显然我们既然有办法把它叠起来，用叠的逆过程就可以把它们全部合法的放到河对岸  , 每个荷叶一只青蛙，一只青蛙直接跳到对岸，有 只 , 在石墩上放 只青蛙, 问题被分解为  于是很容易得到每多一个石墩, 都可以把原来 个石墩的青蛙转移到上面来, 数量翻倍得到答案  #include<bits/stdc++.h> typedef long long ll; using namespace std; con...

Translation(from 洛谷) 奶牛贝西想连续看L (1 <= L <= 100,000,000)分钟的电影，有 N (1 <= N <= 20)部电影可供选择，每部电影会在一天的不同时段放映。 贝西可以在一部电影播放过程中的任何时间进入或退出放映厅。但她不愿意重复看到一部电影，所以每部电影她最多看到一次。她也不能在看一部电影的过程中，换到另一个正在播放相同电影的放映厅。 请帮贝西计算她能够做到从0到L分钟连续不断地观看电影，如果能，请计算她最少看几部电影就行了。 Solution 看见 的时候我就猜要用状压 , 但是继续读题读不懂题意果断跑去洛谷看翻译, 恍...

最近作业越来越多了啊, 每天写个每日一题都是奢求 Solution 观察题目数据范围 石子的数目很少 , 青蛙跳的步幅 但是总长度 却是 级别的假如 很小的话, 我们很容易考虑 表示第 这个位置踩的最小石头数有转移方程 考虑上图的情况, 在 高达 的时候, 每个石头之间的距离 将会很大但是这个距离 有很多是无用的情况为什么呢? 我们可以通过不断的跳缩短距离, 最后决定是否要踩到石头的仅仅是一小段距离前面的都能通过不停地往前跳抵消掉那么最后一小段距离最大有多少呢? 我这里取了 , 因为 是 到 的最小公倍数我们对石头进行缩点, 相邻的距离过大的先对 取模(因为大于等于 总可以通过弹跳抵消)缩点后...

我哭了, 一大早起床本来想做个题后写作业, 结果被这道题搞了几个小时满脑子都是乱的还做不出来, 跑去看了题解 Solution 大致思想其实挺好想的(注意!是大致!) 因为题目保证不会存在 与城市节点重合的情况我们先处理出 左右两个城市的位置(注意一下边界的处理)然后很显然的, 我们可以找到从当前位置去到两个距离小的城市进行反复移动令 为 到所枚举城市的距离, 为还需要访问多少个城市, 为到枚举点途径的城市数有 , 最终结果就是 , 其中 为所枚举的终点城市设移动到左边最近城市后枚举为方案1, 移动到右边最近城市后枚举为方案2比较两个方案的 大小即可这道题就做完了......吗?其实没有!因为...

Solution 根据题目给的限制关系, 很容易就联想到线性的动态规划令 表示第 位是当前位有/无火的方案数 (这里我的 代表无火, 代表有火)但是这道题对 的限制范围不止来自 , 还来自 因此无法二维表示这种状态关系的转移考虑多加一维, 令 表示第 位当前有/无火, 后一位() 有无火而 的限制可以由 来表示, 这样我们就找到了状态转移方程        好多, 累死我，其实就是根据题意很显然的就能列出来了转移方程的具体含义我在代码注释里写出来了, 很好理解这道题的难点在于如何表示状态, 一旦找到状态表示方法只要根据题意做转移就行了最后的答案就是 即最后一个位置有火的方案数加上最后一个位置没...

太棒了, 学到了许多.jpg Solution 题意要求 次区间查询小于等于 的数有多少个, 区间问题首先就想到线段树/树状数组优先考虑树状数组(常数小, 写法简单), 但是我们做不到直接一边查询一边插入然后用 求解因为原序列是无序的, 每次查询 时, 都未知, 因此很难处理注意到问题给的区间是定的, 区间查询的先后不会影响结果那么我们考虑一下离线操作, 对询问的值进行排序, 再对原序列按权值排序预处理出区间 中满足题意的元素再查询此时我们从序列中最小的元素(第一个)开始, 只要当前的值小于所查询的值那么它就可能有贡献, 我们把它插在它原序列的位置上, 直到出现序列的值大于当前的值我们停止插入...

Solution 看了一圈题解都是优先队列, 这里给个不正经的做法观察到人数只会在 到 我们考虑会不会出现一个峰值使得结果最大即这个结果是不是满足凹凸函数的定义我们考虑三分人数大小, 这样可以取得一个局部极值然后在这个局部极值的附近找是否有最优的问题在于三分出人数后如何去check贡献因为我们已经知道了人数于是那些 比当前人数小的都不能选剩下的那些只需要按 排序一个一个选即可虽然我觉得我的做法很假但是就是过了啊hhhh update 被 了老老实实写优先队列吧首先按 排序, 然后以 值建立一个小根堆(优先队列)然后对于当前的 先进入队列(注意这一步很重要, 判断完再进队是错的)为什么是错的? ...

Solution 一看数据范围, 肯定是个 了但是这个数据范围做不了状压 考虑普通的 这个问题的难点在于他是二维的情况(多个木块)那么如果是一维的情况怎么做呢?我们先考虑一下令 表示第 个木板粉刷 次涂了前面 个格子的正确格子数因为只有两种颜色, 对于某一块木板, 我们可以维护一个前缀和 表示第 个木板的第 个格子前蓝色格子的数目对于单个木板有 表示对第 块木板涂了 次, 此时到第 个位置可以从第 块木板的涂了 次的第 个位置转移过来对于要么取蓝色, 要么取红色, 我们取个 即可, 是 的蓝色格子 是 的红色格子此时再考虑多个木板情况显然有 表示到第 个木板涂了 次可以从 第个木板涂了 次转移...

Solution 先给一个非常规的解法, 打暴力找 直接看 (公式), 有 这时候点进去找 是什么, 得到下面结果令 有递推式子 于是 打暴力Code int ans, n; int maze[105][105]; void dfs(int x) { if(x == n + 1) { int flag = 0; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(maze[i][j] != maze[j][i]) { flag = 1; } } } if(!flag) ans++; return ; } fo...

Solution 挺简单的一道题, 虽然带着异或的皮, 看起来很复杂, 但其实只要我们从二进制位考虑就不难了因为题目所给的数据是 因此二进制位上最多也就 位, , 我们考虑能否有的做法观察递推式前面两个可以 完成不用管重点是后面那个累加式子, 我们把它们拆开其实也就是     从贡献方面考虑, 异或只会留下和这个数二进制位上不同的那些位, 那么我们只需要统计二进制位的出现情况然后对于当前数字, 如果二进制位是 , 那么前面该位为 的数字就有贡献反之， 如果二进制位是 , 那么前面该位为 的数字就有贡献贡献为 令    表示前面的 数组中二进制第 位为 的数目  表示前面的 数组中二进制第 位为...

Solution 这题在洛谷上是紫题, 但是好像没有想象中那么难很容易看出这题是要求从点 开始扩展的最小生成树因为有一个高度的限制, 不能直接求如果用 的话好像不知道怎么下手这个时候想到了用堆优化的 在优先队列里我们多加一个条件即先往高度大的地方走, 不行再往当前连通块的最近点走即可注意题目没给数据范围, 数组要开到  Code /* autor: Kurisu 2020年4月30日16:48:49 */ #include<bits/stdc++.h> using namespace std; const long long inf = 1e18; const int N = 1e...

Solution 经典0-1背包问题, 题目的输入描述有点问题  第3-n+2行 -> 第 3 - m + 2 行  直接做背包是错的, 因为这里多了一个时间的限制, 价值随着时间而变化同样是背包但是先进背包和后进背包有区别因此需要考虑贪心策略下背包对于两个物体 , , 先取 物体比先取 物体优当且仅当 化简一下就是 排序后进行背包就行了注意题目要求必须至少做一道菜, 这里有个人尽皆知的小技巧把 数组赋值为无穷小, , 这样可以保证 满足至少取一个 Code /* autor: Kurisu 2020年4月30日08:59:23 */ #include<bits/stdc++.h&...

Solution 看数据范围, 显然是一道dp计数题令 表示前 个数字中去除 个数字的种类那么有递推式子 但是这样子计算显然会有重复情况出现本题的难点在于如何解决重复的比如序列删去区间 的数字和删去区间 得到的结果是一样的但是会被计算两次注意到出现这种情况是因为出现了两个 即如果一个数字它出现两次, 那么可能就有重复情况出现观察发现, 假设当前数字为 , 当前位置为 , 上一次出现的位置为 那么如果我们删去 , 剩下的方案都是重复的直接减去这一部分即可, 于是递推式子改成了 我搞了一个序列自动机找上一个元素的位置另外看到很多人的题解初始化的时候 好像越界了为什么没有报错.... , 初始化 不...