- 博客(31)
- 收藏
- 关注
RSS订阅原创 洛谷P3842线段【JAVA实现】
题面分析只要弄懂每下一层时起点要不是上一层的左端点或者右端点。就是一个简单的DP设dp[i][0/1],表示走到第i层的线段并站在左/右端点上所需要走的最短长度。设L[i],R[i].表示第i层端点位置。边界情况：dp[1][0/1]可以直接求的。注意走完线段之后到左右端点。显而易见dp公式dp[i][0/1]=Math.min(dp[i-1][0]+Math.abs(L[i-1]-R/L[i])+R[i]-L[i],dp[i-1[1]+Math.abs(R[i-1]-R/L[i])+R
2020-05-29 23:04:11
144
原创 洛谷聪明的质监员【JAVA实现】
题面分析二分+前缀和优化求解二分可以看出来,W越大，被选上的矿石越少，则对应的Y值越小。即随着W的增大，Y值减小。 这就单调性我们可以在二分过程中求解与s相差最小的Y值，前缀和在计算Y值时需要操作区间和，通过前缀和可以优化时间复杂度。设L[i],R[i]为需要操作区间的左右端点。pren[i]为0到第i个被选中的矿石数量，prev[i]为到第i个为止被选中的 矿石的总价值。则Yj=（pren[R[j]]-pren[L[j]-1]）*（prev[R[j]]-prev[L[j]-1]）
2020-05-29 22:36:42
163
原创 CNSlidingWindowJAVA实现
题目分析按题面，直接上单调队列可以用两个单调队列求解，一个队列单减来维护区间最大，一个队列单增来维护区间最小。代码import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.io.PrintWriter;import java.io.StreamTokenizer;p
2020-05-28 20:43:34
132
原创 NCLaptopJAVA实现
题目分析两个关键字都是从大到小排序，可以保证左边的第一关键字比右边大，在此基础上从左到右维护一个最大第二关键字判断当前笔记本是否被完虐，可以求出被碾压的笔记本数 。做法很简单。假设内存为a,速度为b,题目要求我们求ai<aj，bi<bj的j有多少 。根据上面的排序方法，从左到右a是单减的，然后只要从左到右枚举，只要考虑当前元素的b小于前面的b就会被完爆。代码import java.util.Arrays;import java.util.Scanner;public
2020-05-27 10:16:49
255
原创 NC分数线划定JAVA实现
题目分析根据两个关键字排序之后，按题目输出就完事了首先排好序，过笔试的人为m*1.5，int类型下自动向下取整，可以求得分数线。然后枚举大于等于分数线，得到真实过笔试人数，然后输出这些符合要求的人即可。代码import java.util.Arrays;import java.util.Scanner;public class 分数线 { public static class off implements Comparable<off>{ private int
2020-05-26 19:16:39
354
原创 NC小C的记事本JAVA实现
题目分析用栈来存储每次操作之后的结果，出栈代表回滚到上一次操作字符串不大，可以用栈来存储每次的操作后的结果，出栈后的栈顶为上次操作之前的字符串。 维护一个当前字符串S。操作1：把S与要加的字符串相连，然后入栈。 操作2：按题意来更新S，然后入栈。操作3：直接输出当前S的第k个字符。操作4：出栈回滚，更新当前字符串S。PS:是多组输入,快读快输（开始没看到，被坑到吐QAQ）代码import java.io.BufferedReader;import java.io.BufferedW
2020-05-25 18:46:18
130
原创 NC兔子的逆序对JAVA实现
题目分析树状数组求解逆序对，至于后面的反转区间，通过化解公式可知与（R-L+1）*(R-L)/2的奇偶有关先求解总的逆序对，求法很多我用的数组数组，通过求出顺序对，然后和总序对相减求出总的逆序对。反转区间，可以看出它不影响反转区间之外的逆序对，只会影响内部。通过公式 总序对=逆序对+顺序对 可知 ，假设此区间左右区间端点为L,R，区间的逆序对为X，而总序对可知为（R-L+1）(R-L)/2）。如果反转，逆序对变为（R-L+1）(R-L)/2）-X.与之前逆序对数相差（R-L+1）(R-L)
2020-05-24 16:21:12
98
原创 NC华华教月月做数学JAVA实现
题目分析快速幂+龟速乘KO一眼过去可以知道是个快速幂能秒的题。然后看下数据范围P<=10^18,这会导致相乘的时候可能超long long。于是需要龟(快)速乘来解决。代码import java.util.Scanner;public class 华华数学 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int t=sc.nextInt(); long a,
2020-05-24 15:42:01
96
原创 NC糖糖别胡说，我真的不是签到题目JAVA实现
题目分析从后往前枚举每个糖糖是否会被消灭。讨论每个糖糖被消灭的情况是，后面的糖糖有不是同组且能力值比它高。然后发功时间，可以预处理出n秒后假设糖糖没死的能力值。由前面可知，被消灭只与后面的糖糖有关，假设第i个糖糖被后面的第j个糖糖消灭，以第j个糖糖的视角来看，自它之后发的功都不影响它消灭第i个糖糖。所以预处理出的i，j糖糖能力值可以看成在第j秒时，第i个糖糖的能力值加上之后发的功，第j个糖糖的能力值加上之后发的功。之后的功不受影响，只要第j秒时第j个糖糖的能力值大于第i个且不同组。简单的说
2020-05-23 14:43:37
153
原创 NC奇♂妙拆分JAVA实现
题目分析枚举1一直到根号n，找到因子，就把n变成n/因数，答案+1。（不要忘记最后的n自身也是一个因子）为拆成最多的且不重复的自然数乘积，所以尽量从小的自然数拆起，从1开始枚举到根号N（防止遇到大素数这种情况，N为目前数），是否为满足条件（因子）的自然数。代码import java.util.Scanner;public class Main{ public static void main(String[] args) { Scanner sc=new Scanner(Syste
2020-05-23 14:04:37
154
原创 NC数学考试JAVA实现
题目分析通过前缀和来求取区间分数和，从左到又枚举区间，答案及当前区间与之前最大区间之和的最优值。通过前缀和优化时间复杂度，然后本题题意是求两个不连续区间最大和，及两个固定长度区间最少间距为1的最大区间与次小区间之和。我们可以枚举一个区间，把它看做最大区间或次小区间。求它与它之前符合条件的最大区间之和更新最终答案。为什么没有之后符合条件的呢？因为如果之后有更优的区间选择的话，枚举到后面这个区间时会更新答案，避免重复计算。代码import java.util.Scanner;publi
2020-05-22 13:20:16
138
原创 Dinic算法JAVA模板
笔者学习来源：https://www.cnblogs.com/SYCstudio/p/7260613.html 在这个信息爆炸的时代，本着达者为师的态度在大佬的博客中取的Dinic模板之经。 为在下以后愉快的玩耍板子，写写学习经验总坛。Dinic算法 相较于EK算法，dinic多了一个分层的概念； dinic做法,首先用bfs把图分层，分深度，即每个节点都有他...
2019-07-23 10:32:22
588
2
原创 洛谷【模板】网络最大流JAVA实现
运用EK算法轻松解决模板问题（只会模板qwq）！前提会的算法：广度优先搜索 ，数据结构我用的是链式前向星存边；推荐播客：（前向星）https://blog.csdn.net/ZHangFFYY/article/details/77871897（网络流）http://www.sohu.com/a/243746046_100201031（Dininc算法）https://www.cnb...
2019-07-12 19:40:03
327
原创 洛谷摆花JAVA实现
题目：https://www.luogu.org/problemnew/show/P1077开始简单的暴力枚举结果得了10分吧（时间爆表）qwq。想必应该用动态规划才能破局了。动态总的说就是以前面的状态推后面的状态；后面的状态是以前面为基础的；（使劲水）手动滑稽.jpg我们设置状态f[i][j],表示在放置完第i种花的时候总共放了j盆花的方案数，我们可以看做按编号一种花一种花来种，...
2019-07-12 14:34:53
222
原创 洛谷兔八哥与猎人JAVA实现
此题的坑点是坑不到我的。--严肃地说在此就不画图解释了，相信大家（大大）们可以想到，两者直接有东西的话，科学的说就是两者横纵坐标之差的决对值不互质。简单的讲，有两种可能兔八哥不死，通常的是他们虽然在同一条x或y轴上但至少隔离一颗树。第二种就是如前前面所讲的两者坐标之差的比，如果存在有这种“比”还比他们数值小的话，兔八哥不死。就比如说4:8，就有2:4，比他们数值小。总结的说就是...
2019-07-10 19:57:14
157
原创 洛谷排行榜JAVA实现
此题我就简单的用了下Arraylist就过了。我想是数据小吧。(￣_,￣ )开心的偷懒每一个down的歌单意味着往上升，“保险”地看法是升的过程中顺序不变，以免无法全部满足，大家至少都可以往上挤一挤；而down的同上嘛，根据题意可知不变的就让他不变在前面的基础上插（挤）进去就好。用三个数组存up ，down，same。down和 up先后放入链表中，然后same的数组往里面一插，...
2019-07-10 19:12:19
1103
原创 洛谷食物链JAVA实现
本题我所用方法为补集法; 这是一个巧妙的方法,相当于几个并查集合并;取经于https://blog.csdn.net/qq_35786326/article/details/79234930适用于解决此类问题,请放心食用;import java.util.Scanner;public class Main { static int x[],sum=0;publi...
2019-04-16 22:54:21
314
原创 洛谷倒水JAVA实现
数据开的有点大，开始没注意，错的时候以为只是要大一点，还是用int类型数组，结果qwq。这时才醒悟用的long类型来存大数据；本题两两合并成一个，可以看出是个与二进制有关的题；开始建立long类型数组从而表示出当前瓶子表示的二进制数；为取最小瓶子数，即从最小位开始遍历抵消多余的瓶子的总数；即假设没有那些多余的瓶子下进1位的所需瓶子数-那些多余的瓶子数；import...
2019-04-08 20:46:18
167
原创 洛谷装箱问题JAVA实现
相信大家看过很多大神关于动态规划的解释不做解释（不会解释 ）重在一步一步理解import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc =new Scanner(System.in); while(sc.hasNext()){ int m=sc...
2018-12-20 21:23:36
448
原创 洛谷疯狂的采药JAVA实现
完全背包问题import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); while(sc.hasNext()){ int m=sc.nextInt(); int n=sc.nextInt();...
2018-12-20 21:19:11
309
原创 洛谷小A点菜JAVA实现
一维数组版import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int n = sc.nextInt(); int m = sc.ne...
2018-12-20 21:17:01
172
原创 洛谷最大公约数和最小公倍数问题JAVA实现
功力不够；代码行数来凑；若有大神路过；还请指点；import java.util.Scanner;public class a2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int a = sc.nextInt...
2018-12-11 21:14:27
140
原创 洛谷幂次方JAVA实现
话不多说直接上代码import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc= new Scanner(System.in); int a=sc.nextInt(); pow(a); } public static void p...
2018-12-09 23:47:12
212
原创 洛谷拼数JAVA实现
此题难点为排序的判断两个以字符串形式的数从左到右比较大小；如果是两个长度不同的“数”就按循环比较大小；即判断哪个放前面更大；还有就是特殊情况考虑；import java.util.Scanner;public class a1 { public static void main(String[] args) { Scanner sc = new Scanner(System.i...
2018-12-04 20:04:34
299
原创 洛谷[USACO1.3]混合牛奶 Mixing MilkJAVA实现
开始没想到还有单价一样的情况还是太年轻（没经验）了；对于这种情况我用识别解决；import java.util.Arrays;import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); whi...
2018-12-04 14:30:49
168
原创 洛谷纪念品分组JAVA实现
这题贪心第一步排序import java.util.Arrays;import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int m =...
2018-12-03 19:22:22
296
原创 洛谷排队接水JAVA实现
不会什么排序方法编号；运用土办法编号；还待优化；import java.util.Arrays;import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext(...
2018-12-02 21:21:24
584
原创 洛谷均分纸牌JAVA实现
简单的贪心一路往后推即可；多了往后递少了往后借；import java.util.Scanner;public class p1031 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int n = sc.nextI...
2018-12-02 20:26:31
152
原创 洛谷潜伏者JAVA实现
勉强过的代码希望路过的大神或同志提提建议import java.util.Arrays;import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); char x[] = new char[91...
2018-11-30 22:18:31
233
原创 洛谷宇宙总统JAVA实现
本人第一次写希望多提建议 import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); String x[] = new String[n +...
2018-11-30 19:30:41
239
4
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人