昨晚三個(gè)人在創(chuàng)業(yè)吧做中大的程序設(shè)計(jì)比賽做的死去活來(lái)，今天打算把當(dāng)時(shí)超時(shí)的題目揪出來(lái)好好的看看題解

Triangle:斐波那契證明

這道題鴻哥糾結(jié)了很久，連getchar都出來(lái)了，事實(shí)證明還是沒(méi)有用，超時(shí)就是超時(shí)。
我們剛開始的想法是，三個(gè)循環(huán)，一個(gè)最小，一個(gè)次小，一i個(gè)最大，看最大的-最小的是否小于次小，還是超時(shí)。

• 首先要排序
• 當(dāng)且僅當(dāng)ai+ai+1>ai+2時(shí)可以輸出YES，但復(fù)雜的為O(nlogn)

• 分情況處理，對(duì)于n<100就可以按照上面的做法，n>100直接輸出YES：

  
  
  題解//看不懂ing

權(quán)哥證明

結(jié)論

給定一個(gè)非空的正整數(shù)集合A，若A中任意三個(gè)元素都不能構(gòu)成三角形，則A中的最大元素max A>= F|A|,其中|A|為集合A的元素個(gè)數(shù)，F(xiàn)|A|斐波那契數(shù)列的第n個(gè)元素(下標(biāo)從1開始)。

引理鋪墊

構(gòu)成三角形的充要條件：
任意兩邊之和大于第三邊 (1)
備注: 結(jié)論(1)與“任意兩邊之差小于第三邊”是等價(jià)的

假如已知三邊，且a<b<c。則(1)結(jié)論簡(jiǎn)化為：a+b>c (2)
因?yàn)檩^小的兩條邊相加都大于最長(zhǎng)那一條邊，那么其他任意兩邊相加肯定大于第三邊。

所以不能構(gòu)成三角形的充要條件為: a+b<=c
即如果a,b已知，則第三邊c最小只能為a+b

在證明開頭的結(jié)論之前再看一個(gè)例子

現(xiàn)有長(zhǎng)為144cm的鐵絲，要截成n小段（n>2），每段的長(zhǎng)度>=1cm，如果其中任意三小段都不能拼成三角形，則n的最大值為多少？
因?yàn)樯鲜鲱}目要求n盡量大，則我們每截一段都要在滿足題意(任意三段都不能構(gòu)成三角形)下盡可能的??！
因?yàn)槊恳欢巫钚?，所以一開始我們截取兩段都為1，作為基底。要使不能構(gòu)成三角形，根據(jù)結(jié)論可知第三段最小只能截取2。
現(xiàn)在截取的長(zhǎng)度序列{a}如下：
1 1 2 ...
為了使a2、a3和a4不構(gòu)成三角形，則a4最小為a2+a3=3。a4由a2、a3確定，只要a2、a3和a4不構(gòu)成三角形，a1、a2、a4就肯定不能構(gòu)成三角形。
因?yàn)檫@是個(gè)非遞減序列，a1<=a2<=a3<=a4,
又a2+a3<=a4 => a2,a3,a4不能構(gòu)成三角形
所以a1+a2<=a4顯然成立 => a1,a2,a4不能構(gòu)成三角形

同理往下填數(shù)，可以發(fā)現(xiàn)這是個(gè)斐波那契數(shù)列F:
1 1 2 3 5 8...
數(shù)列F中任意三個(gè)數(shù)不能構(gòu)成三角形，且Fi是滿足前提(任意三個(gè)數(shù)不能構(gòu)成三角形)的最小的數(shù)。

現(xiàn)在給定一個(gè)升序的有n個(gè)正整數(shù)的數(shù)列b，且這個(gè)數(shù)列任意三個(gè)數(shù)也不能構(gòu)成三角形，則對(duì)于相同的i，有bi>=Fi。(因?yàn)橹耙呀?jīng)證明Fi是滿足前提(任意三個(gè)數(shù)不能構(gòu)成三角形)的最小的數(shù))。

設(shè)max為數(shù)列b中最大的數(shù)(因?yàn)樯蚺帕校礊閎n)
bi>=Fi => bn>=Fn => max >= Fn

Monitor: 二維前綴和

• 題意：在一個(gè)面積不超過(guò)n*m的矩形上，有p個(gè)矩形A，問(wèn)之后的q個(gè)矩形B能否被之前的A全部覆蓋（每個(gè)B的點(diǎn)都在至少一個(gè)A中）
• 由于nm,p,q的范圍過(guò)大，于是考慮O(nm+p+q)的做法。
  對(duì)于A類矩形(x1,y1,x2,y2)，我們只需要在(x1,y1),(x2+1,y2+1)處+1，在（x1,y2+1）(x2+1,y1)處-1
• 之后對(duì)整個(gè)面積求一個(gè)前綴和。則大于0的地方就是被A類矩形覆蓋的點(diǎn)。這里什么意思
• 把值大于0的地方變成1，再一次求一次前綴和，處理好后即可在O(1)的時(shí)間算出一個(gè)矩形內(nèi)被覆蓋的點(diǎn)的數(shù)量。
• 雖然題解還是沒(méi)看懂，但參考了一下大佬的博客，寫了前綴和的相關(guān)文章，還是有點(diǎn)不清楚他是如何和前綴和聯(lián)系在一起的，想一想叭~

先呈現(xiàn)出代碼具體解釋看前例和例題

#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);
        //接下來(lái)才是真正的求面積
        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：直接模擬

一直以為這道題有捷徑的我醉了。
在輸入的時(shí)候要注意一下，有個(gè)坑，接著就直接x，y，z進(jìn)行模擬。

#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;
}