iiiiikun - 个人主页动态 - 牛客网

发布(419) 评论刷题

2020-12-17 17:14

南开大学 Java

Points and Powers of Two

很难证明出这个合法数列最大值就是3。。 然后就好做了 假设存在四个数 x ， x+2^i ,x + 2^j , x + 2^l x+2^j - x-2^i = 2^j - 2^i 要是2的整数倍 j=i+1； 同理 l=j+1 那么第二个数和第四个数就不满足差值是2的幂了QUQ。 #include<iostream> #include<cstring> #include<vector> #include<algorithm> #include<map> #include<set> using namespace std;...

0 点赞评论收藏

分享

2020-12-17 17:14

南开大学 Java

New Year Parties

题意给定你n个点，每个点可以停在原地或者向左向右，问最多能有多少个不重合的点 还有 最少能有多少个点。 解题报告：看题目就感觉是dp题 但听大佬说不能dp做？ 但我抱着侥幸的心里写了写dp，一开始确实wa了，后来看了看状态转移 ，我们dp数组定义的是考虑前i个人并且第i个人的状态是向左、向右、不动 ，如果每个状态都能被三个状态转移的话 ，其实是有问题的，我们没有保证i-1个的坐标是比i要小于等于的，如果上一个人的坐标比i大 那么就会有问题 例如dp[i][2]还是会被dp[i][1]所更新到，所以我想把状态定义为以i为结尾，且i为最大的状态，保证前一个点<=后一个点就行了。 ac代码： ...

0 点赞评论收藏

分享

2020-12-17 17:13

南开大学 Java

题意：把0～n^2-1 之间的所有数填进n*n的矩阵，让整个矩阵的横向和纵向异或和相同。 思路： 小技巧就是偶数与它下一个数 异或和为1，偶数开始的4个异或和为0，然后我们突发奇想 构造一个 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 然后发现这个矩阵刚好符合。由于n能被4整除，我们可以分成n^2/16个矩阵，每个矩阵加上一个偏移量16就行了。由于后面的每个数 加上的偶数的16偏移量，对答案0是不影响的。 #include<iostream> #include<cstring> #include<queue> #includ...

0 点赞评论收藏

分享

2020-12-17 17:13

南开大学 Java

农民约翰正在指挥他的N头牛进行清理工作。 他将一天划分为了T个班次（1~T）。 每头牛都只能在一天中的某一个时间段内进行不间断的工作。 你需要帮助约翰排列出一个合理的奶牛的清理班次，使得每个班次都有奶牛在进行清理，而且动用的奶牛数量可以尽可能的少。 输入格式 第1行：两个空格隔开的整数N和T。 第2…N+1行：第i+1行包含两个整数，分别表示第i头牛可以进行工作的开始时间和结束时间。 输出格式 输出一个整数，表示在每个班次都有奶牛清理的情况下，所需的奶牛最小数量。 如果无法做到每个班次都有奶牛清理，则输出-1。 数据范围 1≤N≤25000, 1≤T≤106 输入样例： 3 1...

0 点赞评论收藏

分享

2020-12-17 17:13

已编辑

南开大学 Java

Balanced Bitstring

题意：判断长度为n的串中的每个长度为k的子串是否0和1相等，字符串中的问号既可以是1也可以是0。 解题思路： 例如n=10 ，k=4 对于 s[0~3] 和 s[1~4] 我们可以发现1～3的部分是相同的，那么不难发现0和4相同，同理可得s[2]和s[5]也是相同的因此若该串合理就一定是k循环节子串，最后我们只需要判断前k个字母是否可以构造出一半1和一半0 ，如果1或者0的个数已经大于一半了一定构造不出来，否则一定可以构造出来。 代码： #include<iostream> #include<algorithm> using namespace std; typed...

0 点赞评论收藏

分享

2020-12-17 17:12

已编辑

南开大学 Java

对顶堆P1801 黑匣子

题目链接：看看 对顶堆？如图 对顶堆就是由小根堆和大根堆所组成，小根堆的值都比大根堆的大，这种数据结构可以用来动态查询数组中的前k小值，我们要维护大根堆的数量是k，当大根堆的size大于小根堆，就把最大值push进小根堆，如果大根堆数量不够，就往小根堆里拿最小值。 代码： #include<iostream> #include<algorithm> #include<cstring> #include<queue> using namespace std; typedef long long ll; const int N=200010; in...

0 点赞评论收藏

分享

2020-12-17 17:12

已编辑

南开大学 Java

P4053 [JSOI2007]建筑抢修

题意：问能选取最大多少个数的建筑， 满足在规定时间内，每个建筑的建立都不能超过截止时间。 解题思路：先按照截止日期排序，如果能在截止日期内完成，那么我们就尽量往里扔，如果不能完成，那么我们选择大根堆中最大的看看它是不是比当前任务耗时大，如果耗时大，那么我们一定能把它抛下，并且完成任务，并且总耗时最少。 代码： #include<iostream> #include<algorithm> #include<cstring> #include<queue> #include<vector> using namespace std; ty...

0 点赞评论收藏

分享

2020-12-17 17:11

已编辑

南开大学 Java

张老师的旅行区间dp

区间dp，由于n很小，开两维，然后外加一维，最后遍历完所有区间内的点停在最左边还是最右边。 #include<stdio.h> #include<string.h> #include<algorithm> #include<map> #include<string> #include<math.h> #include<vector> #include<queue> #include<stack> #include<iostream> #include<sstream&...

0 点赞评论收藏

分享

2020-12-17 17:11

南开大学 Java

D. Rescue Nibel!

题意：总共有n个线段，问选择k条线段，使得他们相交于一点的方案数。 思路：用类似差分的思想，将每条线段的l和r+1放进数组里并且分别带有1和-1的权值，将数组按照坐标大小排序，如果坐标大小不同按照权制大小排序，权值小的放在前面，然后依次遍历下来，把方案定义为以第i个灯泡为末尾（即该灯泡的坐标在选的坐标里最大）的方案数，这些方案是不重不漏的，加起来就是答案了，然后模数不是质数，要用扩展欧几里得求，然后我忘了咋写了。 #include<iostream> #include<cstring> #include<vector> #include<algori...

0 点赞评论收藏

分享

2020-12-17 17:11

南开大学 Java

2020CCPC秦皇岛 k Kingdom’s Power

题意：有无数个军队可以从树根1出发，每花费一个点可以让军队走一步，问遍历完整个树的最小花费。 思路：先记录每个节点的高度，用节点根据它子树的高度的高度来排序，然后节点的高度为子树的最高高度+1，然后类似树形dp，从上往下递归h和与从下往上走的值取min。最后把所以的根节点的值加起来。 #include<iostream> #include<cstring> #include<vector> #include<algorithm> using namespace std; const int N=1000010; typedef long lon...

0 点赞评论收藏

分享

2020-12-17 17:10

南开大学 Java

题意翻译 用 n个点组成二叉树，问高度大于等于 h 的有多少个。 输入n和h 解题思路 ： 这道是一道dp题，看了题解，思路是问的什么dp转移的方程就是什么，那么我们设成考虑i个节点的子树，高度不大于j的方案数，最后可以通过容斥原理求出答案，答案就是f[n][n]-f[n][h-1] 初始化：当节点为空的时候方案数为1， f[0][i]=1; 代码： #include<iostream> #include<cstring> #include<map> #include<string.h> #include<algorithm> us...

0 点赞评论收藏

分享

2020-12-17 17:10

已编辑

南开大学 Java

最大子矩阵（小于等于某值）

思路：原来的思路就是枚举右下角点和左上角点，复杂度o（n^4)不太行，那我们我们把每一行的前缀和存下来，枚举两行然后枚举列结尾，二分出他前面最小的前缀和使得它大于等于sum-k，最后别忘记特判一下，如果最左边的l也能满足sum-k，l–。 #include<iostream> #include<cstring> #include<map> #include<string.h> #include<algorithm> using namespace std; typedef long long ll; const int N=252;...

0 点赞评论收藏

分享

2020-12-17 17:09

已编辑

南开大学 Java

P5200 [USACO19JAN]Sleepy Cow Sorting G

题意：给定一个排列 ，每次能让队头移动到后面任意的位置，问最后需要多少步可以变成升序排列。 思路：看到了一个很妙的思路，我们从末尾开始往前面扫如果遇到不是降序的那么它以及它前面的元素都需要往后移动，所以第一个答案就确定了。第二问要输出方案，我们仔细观察，每一头牛需要往后的距离=他后面还没有排队好的牛和已经排队好比他小的牛。如果暴力应该是n^2的，这时候我们想想在查询排队好比他小的牛的时候能不能拿数据结构优化一下，想到了树状数组，因为该题目里只有单点修改和查询区间，那么就好办了。 代码： #include<iostream> #include<cstring> usi...

0 点赞评论收藏

分享

2020-12-17 17:09

南开大学 Java

P1629 邮递员送信

有一个邮递员要送东西，邮局在节点 11。他总共要送 n-1n−1 样东西，其目的地分别是节点 22 到节点 nn。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 mm 条道路。这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。求送完这 n-1n−1 样东西并且最终回到邮局最少需要的时间。 输入格式 第一行包括两个整数，nn 和 mm，表示城市的节点数量和道路数量。 第二行到第 (m+1)(m+1) 行，每行三个整数，u,v,wu,v,w，表示从 uu 到 vv 有一条通过时间为 ww 的道路。 输出格式 输出仅一行，包含一个整数，为最少需要的时间。 输入输出样...

0 点赞评论收藏

分享

2020-12-17 17:08

南开大学 Java

CF296B Yaroslav and Two Strings

题意：有两个串，每个串的内容要么是数字要么是问号，一共多少种方案使得两个串中存在两个位置一个位置比另一个大，一个位置比另一个小。问号可以填0～9. 思路： 容斥原理，看一共有多少状态减去非法状态，一共的状态数等于10的问号次方，非法状态，要么就是全大于等于，要么就是全小于等于，要么就是全等于，假设res1,res2,res3是这三个解，total是一共的方案数，答案是total-res1-res2+res3,为什么要加上res3呢，因为我们一共要减去的是一个相等的方案数，然后res1,res2里面都包含了全部等于的情况，最后再减去res3。 #include<iostream> ...

0 点赞评论收藏

分享

关注他的用户也关注了：

牛客网
牛客企业服务