hdu2142题目链接 题意：有n个订单和可以在m小时内制作月饼 接下来是n个订单的信息:需要在mon月,d日,year年,h小时交付订单r个月饼 接下来一行t,s表示制作的月饼可以保质t天，每保质一天需要花费s的价值 接下来m行表示从第0小时开始在该时间制作月饼的花费的价值 求完成所有订单消耗的最小价值 思路：一开始毫无头绪。。因为读错题了。。。之后发现做月饼只能在整点做，即使是提前，也只能提前整数个小时做。 然后发现冰箱的容量是没有限制的，所以每个订单单独考虑即可。 那么对于每一个订单，我们要找到订单当天以及之前T天，这T+1天中做月饼花费最少的那天做月饼。 但是如果对于每个订单，如果每次都更新相应的价值，找一次最小值，复杂度会 …

poj 3368 题目链接 题意：给出n个非减的数a[i],求区间[l,r]中出现次数最多的数的出现的次数。 思路：由于数列非减，那么相等的数一定相邻。很容易系哪个到构造另一个数组f[i]，表示从当前位置向左边延伸最多延伸几个相等的数。 f[i] = f[i-1] + 1 (iff a[i]==a[i-1]) 然后查询的时候。 如果直接用ST算法查询rmq的话。。。 可能产生错误结果，原因是f[i]是从左边1到i这段连续区间里当前数出现的次数。 但是查询区间不一定是从1开始，所以查询区间内的第一段连续相等的数可能不完整。。。想了半天。。最后看了题解，发现是这部分暴力来搞。但是如果所有数列中所有数都相等，这样的复杂度就达到 …

poj2452题目链接 题意：给你一组数a[n]，求满足a[i] < a[k] < a[j] (i <= k <= j)的最大的j-i。 思路：大概能想到是rmq，然后想出了一个错误复杂度的错误思路，还直到对拍才发现== 转载一篇题解：poj2452解题报告 收获最大的是： 对于最大值和最小值返回val还是位置的转化竟然可以这样容易! 对于最大值和最小值返回val还是位置的转化竟然可以这样容易! 对于最大值和最小值返回val还是位置的转化竟然可以这样容易! 只要 int _min(int l,int r) { if (a[l]<a[r]) return l; return r; } 这样一个函数就可以 …

hdu3193题目链接 题意：给出n个price 和distance,找到一个集合，集合中的每对在全集中找不到比他price和distance都要小的元素。小于是严格的。 思路：一开始以为找到最小值就好。。。结果漏洞百出。。这题还找不到题解。。。大概是太简单了。。？ 看了一份代码大概看明白了。。。 /* *********************************************** Author :111qqz Created Time :2016年05月17日 星期二 19时20分14秒 File Name :code/hdu/r3193.cpp …

首先先生成三个程序： $ g++ a+b.cpp -o a+b $ g++ a+b2.cpp -o a+b2 $ g++ make.cpp -o make 然后生成数据 $ ./make > in.txt 然后运行两个程序 $ ./a+b < in.txt > out.txt $ ./a+b2 < in.txt > ans.txt 最后对拍 $ diff out.txt ans.txt 输出的结果可以man diff查阅一下相关文档中关于输出含义的内容 注：上面的$都是命令提示符，复制粘贴时不需要

lightoj 1081 题目链接 题意：和上一道一样，但是由于size变成了500，如果按照之前的做法会tle + mle... 很容易发现，由于是方阵，长宽是相等的，所以有一维是可以省略的。 也就是所谓的降维？ /* *********************************************** Author :111qqz Created Time :2016年05月16日 星期一 19时24分26秒 File Name :code/loj/1081.cpp ************************************************ */ #include <cstdio> …

poj2019题目链接 题意：给一个方阵，k个查询，每个查询求某个方阵的最大值和最小值之差。 思路：二维rmq.同时用到最大值和最小值的话可以把初始化写在一起。 /* *********************************************** Author :111qqz Created Time :2016年05月16日 星期一 18时31分23秒 File Name :code/poj/2019.cpp ************************************************ */ #include <cstdio> #include <cstring> …

hdu2888题目链接 题意：问某个矩阵内的最大值，并且问最大值是否是在四个角中出现。 思路：二维rmq.需要注意数组稍微开大1就会MLE,因为是四维数组，一维大一点，整个就会大很多==。 /* *********************************************** Author :111qqz Created Time :2016年05月16日 星期一 16时51分00秒 File Name :code/hdu/2888.cpp ************************************************ */ #include <cstdio> #include …

hdu3183题目链接 题意：n位长的数字串（n<=1000),删掉m个（m<=n），使得剩下的数字串表示的数字最小。 忽略前导0. 思路：暴力搞就可以。要注意每位数字是有一定位置的范围的。比如当前是第i位数字，后面还要取n-m-i位数字，那么第i位数字最多只能取到第k位，k=m+i,因为这样才能保证后面还有n-m-i位数字。 /* *********************************************** Author :111qqz Created Time :2016年05月16日 星期一 13时15分44秒 File Name :code/hdu/3183.cpp …

1636: [Usaco2007 Jan]Balanced Lineup Time Limit: 5 Sec Memory Limit: 64 MB Submit: 680 Solved: 493 [Submit][Status][Discuss] Description For the daily milking, Farmer John's N cows (1 <= N <= 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of …