昨晚三个人在创业吧做中大的程序设计比赛做的死去活来，今天打算把当时超时的题目揪出来好好的看看题解
Triangle:斐波那契证明
这道题鸿哥纠结了很久，连getchar都出来了，事实证明还是没有用，超时就是超时。
我们刚开始的想法是，三个循环，一个最小，一个次小，一i个最大，看最大的-最小的是否小于次小，还是超时。
- 首先要排序
- 当且仅当ai+ai+1>ai+2时可以输出YES，但复杂的为O(nlogn)
-
分情况处理，对于n<100就可以按照上面的做法，n>100直接输出YES：
题解//看不懂ing
权哥证明
结论
给定一个非空的正整数集合A，若A中任意三个元素都不能构成三角形，则A中的最大元素max A>= F|A|,其中|A|为集合A的元素个数，F|A|斐波那契数列的第n个元素(下标从1开始)。
引理铺垫
构成三角形的充要条件：
任意两边之和大于第三边 (1)
备注: 结论(1)与“任意两边之差小于第三边”是等价的假如已知三边，且a<b<c。则(1)结论简化为：a+b>c (2)
因为较小的两条边相加都大于最长那一条边，那么其他任意两边相加肯定大于第三边。所以不能构成三角形的充要条件为: a+b<=c
即如果a,b已知，则第三边c最小只能为a+b
在证明开头的结论之前再看一个例子
现有长为144cm的铁丝，要截成n小段（n>2），每段的长度>=1cm，如果其中任意三小段都不能拼成三角形，则n的最大值为多少？
因为上述题目要求n尽量大，则我们每截一段都要在满足题意(任意三段都不能构成三角形)下尽可能的小！
因为每一段最小为1，所以一开始我们截取两段都为1，作为基底。要使不能构成三角形，根据结论可知第三段最小只能截取2。
现在截取的长度序列{a}如下：
1 1 2 ...
为了使a2、a3和a4不构成三角形，则a4最小为a2+a3=3。a4由a2、a3确定，只要a2、a3和a4不构成三角形，a1、a2、a4就肯定不能构成三角形。
因为这是个非递减序列，a1<=a2<=a3<=a4,
又a2+a3<=a4 => a2,a3,a4不能构成三角形
所以a1+a2<=a4显然成立 => a1,a2,a4不能构成三角形同理往下填数，可以发现这是个斐波那契数列F:
1 1 2 3 5 8...
数列F中任意三个数不能构成三角形，且Fi是满足前提(任意三个数不能构成三角形)的最小的数。现在给定一个升序的有n个正整数的数列b，且这个数列任意三个数也不能构成三角形，则对于相同的i，有bi>=Fi。(因为之前已经证明Fi是满足前提(任意三个数不能构成三角形)的最小的数)。
设max为数列b中最大的数(因为升序排列，即为bn)
bi>=Fi => bn>=Fn => max >= Fn
Monitor: 二维前缀和
- 题意：在一个面积不超过n*m的矩形上，有p个矩形A，问之后的q个矩形B能否被之前的A全部覆盖（每个B的点都在至少一个A中）
- 由于nm,p,q的范围过大，于是考虑O(nm+p+q)的做法。
对于A类矩形(x1,y1,x2,y2)，我们只需要在(x1,y1),(x2+1,y2+1)处+1，在（x1,y2+1）(x2+1,y1)处-1 - 之后对整个面积求一个前缀和。则大于0的地方就是被A类矩形覆盖的点。这里什么意思
- 把值大于0的地方变成1，再一次求一次前缀和，处理好后即可在O(1)的时间算出一个矩形内被覆盖的点的数量。
- 虽然题解还是没看懂，但参考了一下大佬的博客，写了前缀和的相关文章，还是有点不清楚他是如何和前缀和联系在一起的，想一想叭~
先呈现出代码具体解释看前例和例题
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define ll long long
using namespace std;
int a[1001][1001];
void qian(int x,int y){
for(int i=1;i<=x;i++)
for(int j=1;j<=y;j++){
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
}
}
int main()
{
freopen("data","r",stdin);
int n,m,N,M,x1,x2,y1,y2;
scanf("%d%d",&n,&m);
cin>>N;
memset(a,0,sizeof(a));
for(int i=0;i<N;i++){
cin>>x1>>y1>>x2>>y2;
a[x1][y1]+=1,a[x2+1][y2+1]+=1,a[x2+1][y1]-=1,a[x1][y2+1]-=1;
}
qian(n,m);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
if(a[i][j]>0)
a[i][j]=1;
qian(n,m);
//接下来才是真正的求面积
cin>>M;
for(int i=0;i<M;i++){
cin>>x1>>y1>>x2>>y2;
int sum1=(y2-y1+1)*(x2-x1+1);
int sum2=a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];
if(sum1==sum2)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
Clumsy Keke：直接模拟
一直以为这道题有捷径的我醉了。
在输入的时候要注意一下，有个坑，接着就直接x，y，z进行模拟。
#include<iostream>
#include<cstdio>
using namespace std;
int a[105][105],b[105][105],c[105][105];
int main()
{
int x,y,z,i,j,k;
while(scanf("%d%d%d",&x,&y,&z)!=EOF)
{
for(i=0;i<x;i++)
for(j=0;j<y;j++)
scanf("%d",&a[i][j]);
for(i=0;i<y;i++)
for(j=0;j<z;j++)
scanf("%d",&b[i][j]);
for(i=0;i<z;i++)
for(j=0;j<x;j++)
scanf("%d",&c[i][j]);
int ans=0;
for(i=0;i<x;i++)
{
for(j=0;j<y;j++)
{
for(k=0;k<z;k++)
{
if(a[i][j]&&b[j][k]&&c[k][i])
ans++;
}
}
}
printf("%d\n",ans);
}
return 0;
}