- 博客(65)
- 收藏
- 关注
RSS订阅原创 2019沈阳网络赛(F)Honk's pool二分
As we all know, Honk has n pools, numbered as 1 ~ n . There is ai liters water in the i-th pool. Every day, Honk will perform the following operations in sequence.Find the pool with the most water (...
2019-09-22 21:43:17
250
原创 2019沈阳网络赛(C)Dawn-K's water完全背包
Dawn-K recently discovered a very magical phenomenon in the supermarket of Northeastern University: The large package is not necessarily more expensive than the small package.On this day, Dawn-K came...
2019-09-21 21:26:33
310
原创 2019上海网络赛(J)Stone gameDP背包
CSL loves stone games. He has n stones; each has a weight ai. CSL wants to get some stones. The rule is that the pile he gets should have a higher or equal total weight than the rest; however if he re...
2019-09-18 19:48:12
305
原创 2019上海网络赛(L)Digit sum枚举
A digit sum Sb(n)S_b(n)Sb(n) is a sum of the base-b digits of n. Such as S10(233)=2+3+3=8S_{10}(233) = 2 + 3 + 3 = 8S10(233)=2+3+3=8,S2(8)=1+0+0=1S_{2}(8)=1 + 0 + 0 = 1S2(8)=1+0+0=1, S2(7)=1+1+1=3S...
2019-09-16 20:10:32
172
原创 2019上海网络赛(B)Light bulbs差分
There are N light bulbs indexed from 0 to N-1. Initially, all of them are off.A FLIP operation switches the state of a contiguous subset of bulbs. FLIP(L, R)means to flip all bulbs x such that L≤x≤R*...
2019-09-16 19:42:13
211
原创 沉鱼落雁(思维题)
题目描述胖头鱼在苦恼“沉鱼落雁”是什么好吃的东西，这很显然是因为他成语没背够。于是他决定开始背成语。胖头鱼身为鱼界大佬，背成语的姿势自然也和常人不一：他会先将所有要背的成语一字排开，比较难背的成语会重复出现，最多重复 3 次 (也就是出现次数可能为 1, 2 或 3)。这样就得到了一个可能有重复元素的成语序列，然后他会将这个序列打乱顺序，并按打乱后的顺序背下去。为了均匀的背所有成语，提高背成...
2019-09-09 20:40:06
206
原创 POJ-1200Crazy Search(hash+进制)
Crazy SearchTime Limit: 1000MSMemory Limit: 65536KTotal Submissions: 35617Accepted: 9672DescriptionMany people like to solve hard puzzles some of which may lead them to madness. One ...
2019-09-09 12:13:52
142
原创 Acwing-138 兔子与兔子(Hash字符串)
Acwing-138. 兔子与兔子很久很久以前，森林里住着一群兔子。有一天，兔子们想要研究自己的 DNA 序列。我们首先选取一个好长好长的 DNA 序列（小兔子是外星生物，DNA 序列可能包含 26 个小写英文字母）。然后我们每次选择两个区间，询问如果用两个区间里的 DNA 序列分别生产出来两只兔子，这两个兔子是否一模一样。注意两个兔子一模一样只可能是他们的 DNA 序列一模一样。输入...
2019-08-05 10:13:10
159
原创 Acwing-139 回文子串的最大长度(Hash+二分)
Acwing-139. 回文子串的最大长度如果一个字符串正着读和倒着读是一样的，则称它是回文的。给定一个长度为N的字符串S，求他的最长回文子串的长度是多少。输入格式输入将包含最多30个测试用例，每个测试用例占一行，以最多1000000个小写字符的形式给出。输入以一个以字符串“END”（不包括引号）开头的行表示输入终止。输出格式对于输入中的每个测试用例，输出测试用例编号和最大回文子串...
2019-08-05 09:23:44
294
原创 莫队算法
莫队算法莫队算法是什么莫队算法主要是用来离线查询区间答案。一般分为两类：一是莫队维护区间答案，二是维护区间的数据结构。还有树上莫队，带修改莫队，二维莫队等等。一道例题：SPOJ-DQUERY - D-query题意：给你一个长度不大于30000的序列，其中数值都小于等于10610^6106，有1<m<200000次询问，每次询问区间[l,r][l,r]中数值个数（也就是去重...
2019-08-01 21:25:49
414
原创 Acwing-126. 最大的和（二维前缀和）
126. 最大的和给定一个包含整数的二维矩阵，子矩形是位于整个阵列内的任何大小为1 * 1或更大的连续子阵列。矩形的总和是该矩形中所有元素的总和。在这个问题中，具有最大和的子矩形被称为最大子矩形。例如，下列数组：0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 其最大子矩形为：9 2 -4 1 -1 8 它拥有最大和15。输入格式输入中...
2019-07-26 21:22:45
249
原创 Acwing-109 天才ACM(倍增+归并)
天才ACM给定一个整数 M，对于任意一个整数集合 S，定义“校验值”如下:从集合 S 中取出 M 对数(即 2∗M个数，不能重复使用集合中的数，如果 S 中的整数不够 M 对，则取到不能取为止)，使得“每对数的差的平方”之和最大，这个最大值就称为集合 SS 的“校验值”。现在给定一个长度为 N 的数列 A 以及一个整数 T。我们要把 A 分成若干段，使得每一段的“校验值”都不超过 T。求...
2019-07-25 20:48:31
237
原创 RMQ详解（ST表）
RMQ详解RMQ算法， 是一个快速求出区间最值的算法，预处理时间复杂度为O(n*log(n))，查询为O(1)。著名的ST算法就是倍增的产物。给定一个长度为N的数列A，ST算法能在O(n*logn)时间的预处理后，以O(1)的时间复杂度在线回答“数列A中下标在（l~r）之间的数的最大值是多少”这样的区间最值问题。预处理：设F[i][j]表示数列A从第i个数起连续2j2^j2j个数（[i,i...
2019-07-23 21:18:05
665
原创 POJ-3264 Balanced Lineup(RMQ)
Balanced LineupTime Limit: 5000MSMemory Limit: 65536KTotal Submissions: 73096Accepted: 33626Case Time Limit: 2000MSDescriptionFor the daily milking, Farmer John’s N cows (1 ≤ N...
2019-07-23 21:16:31
155
原创 BZOJ-3043 IncDec Sequence 差分
100. IncDec序列给定一个长度为 nn 的数列 a1,a2,…,an，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。输入格式第一行输入正整数nn。接下来n行，每行输入一个整数，第i+1行的整数代表ai。输出格式第一行输出最少操作次数。第二行输...
2019-07-20 21:33:35
185
原创 Acwing - 94 递归实现指数型枚举（递归）
递归实现指数型枚举从 1~n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。输入格式输入一个整数n。输出格式每行输出一种方案。同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。对于没有选任何数的方案，输出空行。本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。数据范围1≤n≤15输入样例：3输出样例：322 311 31 21...
2019-06-07 20:14:55
169
原创 POJ-2018 Best Cow Fences (二分+前缀和)
Best Cow FencesTime Limit: 1000MSMemory Limit: 30000KTotal Submissions: 15498Accepted: 4979DescriptionFarmer John’s farm consists of a long row of N (1 <= N <= 100,000)fields. ...
2019-05-30 12:14:46
245
原创 HDU-1205 吃糖果（蜂巢原理）
吃糖果Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 53764 Accepted Submission(s): 15320Problem DescriptionHOHO，终于从Speakless手上赢走...
2019-05-28 18:04:50
321
原创 POJ-1050 To the Max(最大子矩阵和)
To the MaxTime Limit: 1000MSMemory Limit: 10000KTotal Submissions: 54953Accepted: 29070DescriptionGiven a two-dimensional array of positive and negative integers, a sub-rectangle is ...
2019-05-22 20:32:06
326
原创 BZOJ-1213 [HNOI2004]高精度开根(大数二分)
1213: [HNOI2004]高精度开根Time Limit: 50 Sec Memory Limit: 162 MBSubmit: 2512 Solved: 851Description晓华所在的工作组正在编写一套高精度科学计算的软件，一些简单的部分如高精度加减法、乘除法早已写完了，现在就剩下晓华所负责的部分：实数的高精度开m次根。因为一个有理数开根之后可...
2019-05-18 12:21:53
250
原创 POJ-2288 Islands and Bridges(二进制状态压缩+DP)
Islands and BridgesTime Limit: 4000MSMemory Limit: 65536KTotal Submissions: 13134Accepted: 3487DescriptionGiven a map of islands and bridges that connect these islands, a Hamilton pa...
2019-05-17 21:42:35
204
原创 最短Hamilton路径(二进制状态压缩+dp)
最短Hamilton路径给定一张 nn 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。输入格式第一行输入整数n。接下来n行每行n个整数，其中第i行第j个整数表示点ii到jj的距离（记为a[i,j]）。对于任意的x,y,z，数据保证 a[x,x]=0，a[x,...
2019-05-17 17:16:08
350
原创 南昌网络赛I.Max answer(单调栈+线段树)
I. Max answerAlice has a magic array. She suggests that the value of a interval is equal to the sum of the values in the interval, multiplied by the smallest value in the interval.Now she is plannin...
2019-04-23 20:44:38
148
原创 糖果传递(中位数)
糖果传递有n个小朋友坐成一圈，每人有a[i]个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。求使所有人获得均等糖果的最小代价。输入格式第一行输入一个正整数n，表示小朋友的个数。接下来n行，每行一个整数a[i]，表示第i个小朋友初始得到的糖果的颗数。输出格式输出一个整数，表示最小代价。数据范围1≤n≤10000001≤n≤1000000输入样例：41...
2019-04-16 20:45:54
385
原创 Chino with Equation (隔板法+除法取模)
链接：https://ac.nowcoder.com/acm/contest/553/DChino的数学很差，因此Cocoa非常担心。今天，Cocoa要教Chino解不定方程。众所周知，不定方程的解有0个或者若干个。给出方程:Cocoa想知道这个不定方程的正整数解和非负整数解各有几个。题目对Chino来说太难啦，你能帮一帮Chino吗？输入描述:两个正整数m, n输出描述:题...
2019-04-08 18:37:46
375
原创 POJ-3186 Treats for the Cows（区间dp）
Treats for the CowsTime Limit: 1000MSMemory Limit: 65536KTotal Submissions: 8739Accepted: 4570DescriptionFJ has purchased N (1 <= N <= 2000) yummy treats for the cows who get ...
2019-04-05 19:18:29
196
原创 POJ-1845 Sumdiv（唯一分解定理，快速幂，约数和公式，同余模公式）
SumdivTime Limit: 1000MSMemory Limit: 30000KTotal Submissions: 31351Accepted: 7684DescriptionConsider two natural numbers A and B. Let S be the sum of all natural divisors of ...
2019-04-02 20:53:09
181
原创 51-Nod 1255字典序最小子序列(贪心)
字典序最小的子序列给出一个由a-z组成的字符串S，求他的一个子序列，满足如下条件：1、包含字符串中所有出现过的字符各1个。2、是所有满足条件1的串中，字典序最小的。例如：babbdcc，出现过的字符为：abcd，而包含abcd的所有子序列中，字典序最小的为abdc。输入输入1行字符串S，所有字符均为小写，字符串的长度为L。(1 <= L <= 100000)。输出输出包...
2019-03-31 21:06:56
893
原创 HDU 5914 Triangle(规律+斐波那契数列)
TriangleProblem DescriptionMr. Frog has n sticks, whose lengths are 1,2, 3⋯n respectively. Wallice is a bad man, so he does not want Mr. Frog to form a triangle with three of the sticks here. He de...
2019-03-28 19:30:59
304
原创 第九届蓝桥杯 日志统计（尺取法）
标题：日志统计小明维护着一个程序员论坛。现在他收集了一份"点赞"日志，日志共有N行。其中每一行的格式是：ts id表示在ts时刻编号id的帖子收到一个"赞"。现在小明想统计有哪些帖子曾经是"热帖"。如果一个帖子曾在任意一个长度为D的时间段内收到不少于K个赞，小明就认为这个帖子曾是"热帖"。具体来说，如果存在某个时刻T满足该帖在[T, T+D)这段时间内(注意是左闭右开区间)收到不少于K个...
2019-03-21 20:52:51
198
原创 LightOJ 1341 Aladdin and the Flying Carpet （唯一分解定理+素数筛）
Aladdin and the Flying CarpetLightOJ - 1341 ProblemIt’s said that Aladdin had to solve seven mysteries before getting the Magical Lamp which summons a powerful Genie. Here we are concerned about th...
2019-03-05 16:30:45
165
原创 HDU 4864 Task(贪心)
Task(贪心)Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 12763 Accepted Submission(s): 3136Problem DescriptionToday the company has m tas...
2019-03-04 17:16:38
184
原创 BZOJ 5039 序列维护 (线段树区间乘+区间加)
BZOJ 5039 序列维护https://www.lydsy.com/JudgeOnline/problem.php?id=5039DescriptionJYY 有一个维护数列的任务。 他希望你能够来帮助他完成。JYY 现在有一个长度为 N 的序列 a1,a2,…,aN，有如下三种操作：1、 把数列中的一段数全部乘以一个值；2、 把数列中的一段数全部加上一个值；3、 询问序列...
2019-03-04 16:34:06
243
原创 FZU1759 Super A^B mod C（欧拉降幂+快速幂）
Super A^B mod C题目链接： https://cn.vjudge.net/problem/FZU-1759题目：Given A,B,C, You should quickly calculate the result of A^B mod C. (1&lt;=A,C&lt;=1000000000,1&lt;=B&lt;=10^1000000).InputThere ar...
2019-03-03 20:57:45
276
原创 潍坊学院第三届程序设计竞赛题解
校赛题解A. Bit++题目链接：https://oj.7326it.club/problem/1047思路:定义一个变量初值为0，有加号变量+1，有减号变量-1。输出那个变量。。。代码：C/C++：#include<bits/stdc++.h>using namespace std;int main(){ int n; while(cin >>...
2018-12-09 18:38:53
652
原创 HDU-1506 Largest Rectangle in a Histogram(单调栈，DP)
Largest Rectangle in a HistogramSample Input7 2 1 4 5 1 3 34 1000 1000 1000 10000Sample Output84000题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=1506题意：求直方图中最大的矩形面积思路：有两种解法，个人感觉DP稍简单一点...
2018-11-25 20:48:09
290
原创 HDU-4333 Revolving Digits(KMP,扩展KMP)
Revolving DigitsProblem DescriptionOne day Silence is interested in revolving the digits of a positive integer. In the revolving operation, he can put several last digits to the front of the intege...
2018-11-24 10:07:15
155
原创 HDU-1166 敌兵布阵（树状数组）
树状数组(Binary Indexed Tree(B.I.T))是能够完成下述操作的数据结构。给一个初始值全为0的数列a1,a2,……,an给定i，计算a1+a2+…+ai (sum)给定i和x，执行ai += x (update)由上图所知：C[1]=A[1];C[2]=A[1]+A[2];C[3]=A[3];C[4]=A[1]+A[2]+A[3]+A[4];C[5]=...
2018-11-14 10:22:22
253
原创 第0届ACM算法竞赛热身赛 题解
A题（Hello World!）题目链接：http://116.62.114.238/problem/1037#include&amp;amp;lt;bits/stdc++.h&amp;amp;gt;using namespace std;int main(){ cout &amp;amp;lt;&amp;amp;lt; &amp;quot;Hello World!&amp;quot; &
2018-11-11 21:10:55
374
原创 洛谷2261 余数求和（数学题）
余数求和（数学题）题目描述给出正整数n和k，计算G(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值，其中k mod i表示k除以i的余数。例如G(10, 5)=5 mod 1 + 5 mod 2 + 5 mod 3 + 5 mod 4 + 5 mod 5 …… + 5 mod 10=0+1+2+1+0+5+5+5+5+5=29输入输出格式...
2018-10-31 22:01:41
350
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人