分类存档：默认分类

可能是积蓄了好久的。。。
先是第一天突然喉咙超痛，没什么其他症状。
第二天的开始觉着有点晕，晚修觉得不爽，去校医室一量，38.7°，被遣送回家。
然后回到家才发现好像真得挺严重的~打了两天针才退烧，然后现在喉咙依然好痛。
医生表示等喉咙好了才去上学。
然后算算 中秋3天 -> 6天上学 ->国庆7天。
其中6天上学现在已经过去4天，其中两天在打针与半昏迷状态中度过
还剩两天不知喉咙还好不好得了，汗~

恩，具体就是只有300分，有一题的情况是
打了个
#include 导致
#include 忘记打了，于是CE。
疼死了。。。

　　方向比努力重要。

　　现在是讲究绩效的时代，公司、企业、government，需要的是有能力且能与企业方向共同发展的人，而不是一味努力但却南辕北辙的人。自己 适 合哪些行业，哪些职业，有很多东西是先天决定的，只有充分地发掘自己的潜力，而不是总与自己的弱点对抗，一个人才能出人头地，就像现在很多企业的时候，他 们相信通过培训和教育可以让火鸡学会爬树，但是还是觉得选个松树方便一些。方向不对，再努力、再辛苦，你也很难成为你想成为的那种人。

　　能力比知识重要。

　　知识在一个人的构架里只是表象的东西，就相当于有些人可以在答卷上回答如何管理企业、如何解决棘手的问题、如何当好市长等等，但是在现实面前， 他们却 显得毫无头绪、不知所措，他们总是在问为什么会是这种情况，应该是哪种情况等等。他们的知识只是知识，而不能演化为能力，更不能通过能力来发掘他们的潜 力。现在很多企业都在研究能力模型，从能力的角度来观察应聘者能否胜任岗位。当然，高能力不能和高绩效直接挂钩，能力的发挥也是在一定的机制、环境、工作 内容与职责之内的，没有这些平台和环境，再高的能力也只能被尘封。

　　健康比成绩重要。

　　成绩只能代表过去，这是很多人已经认同的一句话。对于毕业后走入工作岗位的毕业生，学生阶段的成绩将成为永久的奖状贴在墙上，进入一个工作单 位，就预 示着新的竞赛，新的起跑线。没有健康的身心，如何应对变幻莫测的市场环境和人生变革，如何应对工作压力和个人成就欲的矛盾？而且在现代社会，拥有强健的身 体已经不是最重要的，健康的心理越来越被提上日程，处理复杂的人际关系、承受挫折与痛苦、缓解压力与抑郁，这些都将成为工薪族乃至学生们常常面对的问题。 为了防止英年早逝、过劳死，还是多注意一下身体和心理的健康投资吧。

　　生活比文凭重要。

　　曾经有一个故事，说有个记者问放羊的小孩，为什么放羊？答：为了挣钱，挣钱干啥？答：盖房子，盖房子干啥？答：娶媳妇，娶媳妇干啥？答：生孩子，生孩子干啥？答：放羊！

　　记得去年在人大听一个教授讲管理学基础课，他说你们虽然都是研究生，但很多人本质上还是农民！大家惊愕，窃窃私语。他说你们为什么读研究生，很 多人是 不是想找个好工作，找好工作为了什么，为了找个好老婆，吃喝住行都不错，然后生孩子，为了孩子的前途更光明，这些不就是农民的朴素想法吗？那个农民父母不 希望自己的子女比自己更好？说说你们很多人是不是农民思想，什么时候，你能突破这种思维模式，你就超脱了。当这个社会看重文凭的时候，假文凭就成为一种产

　　业，即使是很有能力的人，也不得不弄个文凭，给自己脸上贴点金。比起生活，文凭还重要吗？很多人找女朋友或者男朋友，把学历当作指标之一，既希 望对方能够给他/她伴侣的温暖与浪漫，又希望他/她知识丰富、学历相当或更高，在事业上能蒸蒸日上；我想说，你找的是伴侣，不是合作伙伴，更不是同事，生 活就是生 活，这个人适合你，即使你是博士他/她斗大字不识一个，那也无所谓，适合就会和谐融洽，人比文凭更重要。很多成功的人在回头的时候都说自己太关注工作和事 业了，最遗憾的是没有好好陪陪父母、爱人、孩子，往往还伤心落泪，何必呢，早意识到这些，多给生活一些空间和时间就可以了。我们没有必要活得那么累。

　　情商比智商重要。

　　这个就很有意思了，大家忽然一下子对情商重视了起来，因为在新的世纪，情商将成为成功领导中最重要的因素之一。比如在许多员工和自己的亲人因 KB袭击 丧生的时刻，某公司CEO Mark Loehr让自己镇定下来，把遭受痛苦的员工们召集到一起，说：我们今天不用上班，就在这里一起缅怀我们的亲人，并一一慰问他们和亲属。在那一个充满阴云

　　的星期，他用自己的实际行动帮助了自己和他的员工，让他们承受了悲痛，并把悲痛转化为努力工作的热情，在许多企业经营亏损的情况下，他们公司的 营业额却成倍上涨，这就是情商领导的力量，是融合了自我情绪控制、高度忍耐、高度人际责任感的艺术。曾经有个记者刁难一位企业家：听说您大学时某门课重考 了很多次还

　　没有通过。这位企业家平静地回答：我羡慕聪明的人，那些聪明的人可以成为科学家、工程师、律师等等，而我们这些愚笨的可怜虫只能管理他们。要成 为的成功者，不一定智商高才可以获得成功的机会，如果你情商高，懂得如何去发掘自己身边的资源，甚至利用有限的资源拓展新的天地，滚雪球似得积累自己的资 源，那你 也将走向。

　　在世界上出人头地的人，都能够主动寻找他们要的时势，若找不到，他们就自己创造出来。

【题目大意】
给定一个m*n的矩阵，每个格子有一个a[i][j]，求一个子矩阵，使得这个子矩阵里面的a[i][j]之和>0，使之面积最大。
输入m , n
然后m行，n列。表示a[i][j]。
m,n<=200
【算法分析】
我们枚举子矩阵的上边界i和下边界j。然后令w[k]=Sum{a[t][k]} i<=t<=j。
然后压成一维的情况。
先求出前缀和，Sum[i]=w[1]+w[2]+…+w[i]。特别地SUm[0]=0
然后变成求一个Max( (i-j) ) 其中 i>j 且 Sum[i]-Sum[j]>0
一、
对于红色的东西而言，
假设i>j && Sum[i]>Sum[j]，那么j就废了，不需要枚举作为右边界。（很显然吧T_T）
二、
对于蓝色的东西而言，
假设i、
、
于是我们开两个栈，
、一个以i递增序处理，搞出一个对于右边界有用的集合。（栈A）
另一个以i递减序处理，搞出一个对于左边界有用的集合。（栈B）
、
、
然后最后这两个栈里会有这样的性质：
栈A：从栈底到栈尾，关于i递增，同时关于Sum[i]递减。
栈B：从栈底到栈尾，关于i递减，同时关于Sum[i]递增。
、
、
好了，这样我们就可以很简单地用两个指针i，j，一个指针指着栈A元素，一个指针指着栈B元素。
然后双指针维护最长区间使得 pos[i]>pos[j] 且 Sum[pos[i]]-Sum[pos[j]]>0。
、
、
好了，解决了。这个一维问题的平摊复杂度为O(n)
【时间复杂度】O(m^2*n)
【空间复杂度】O(mn)
【其它】
嗯，其实我本不想写该题解题报告，
但是看到原来的解题报告的复杂度是O(m^2 * Sort(n) )
{其中Sort(n)，表示将n个64位整形排序的复杂度，其中n<=200}
我觉得这种规模，还是快排最好了，那么就是O(m^2 n lg n)。
然后为了更多人了解这种比原解题报告更优的方法，我就写了该篇解题报告T_T。
【解释】
程序中把栈A的元素用v数组标记为可行，然后继续用了Q这个数组T_T，希望大家看起来不会纠结。
【CODE】
#include #include #include #include #include using namespace std;
const int N=205;
typedef long long lld;
int m,n;
int a[N][N];
lld w[N],Sum[N];
int Q[N];
int v[N];

void init(){
scanf("%d%d",&m,&n);
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
}

void solve(){
int i,j,k,ans=0,t,p;
for (i=1;i<=m;i++)
for (j=i;j<=m;j++){
for (k=1;k<=n;k++)
if (i==j) w[k]=a[i][k];
else w[k]+=a[j][k];
Sum[0]=0;
for (k=1;k<=n;k++){
Sum[k]=Sum[k-1]+w[k];
v[k]=0;
}
t=0;
for (k=1;k<=n;k++){
while (t>0 && Sum[Q[t]]<=Sum[k]) t--;
Q[++t]=k;
}
for (k=1;k<=t;k++) v[Q[k]]=1; t=0;
for (k=n;k>=0;k–){
while (t>0 && Sum[Q[t]]>=Sum[k]) t–;
Q[++t]=k;
}
p=t;
for (k=1;k<=n;k++)
if (v[k]){
while (p>0 && Sum[k]-Sum[Q[p]]<=0) p--;
if (p<=0 || Sum[k]-Sum[Q[p]]<=0) continue;
ans>?=(j-i+1)*(k-Q[p]);
}
}
printf("%dn",ans);
}

int main(){
init();
solve();
return 0;
}