P1003 [NOIP2011 提高组] 铺地毯 ,简单又不简单的题

传送门
好吧,作为一道提高组的题,难度只有普及-,大家是不是会很不屑.
但实际上…

本题第一思路
模拟,模拟,直接模拟;
来,就让我们看看模拟的代码(* ^▽*)

#include 
using namespace std;
int ditan[1000][1000];
int main(int argc, char** argv) {
	int l=1,x,y,n,a,b,g,k;
	for(int i=0;i<1000;i++){
		for(int j=0;j<1000;j++){
			ditan[i][j] = -1;
		}
	}
	cin>>n;
	for(int i=0;i
		cin>>a>>b>>g>>k;
		for(int i=a;i
			for(int j=b;j
				ditan[i][j]=l;
			}
		}
		l++;
	} 
	cin>>x>>y;
	cout< 
例题的数据都过了,
 你一提交,顿时,满屏的RE浮现在你眼前.
 不就是数组开太小了嘛!
 
#include 
using namespace std;
int ditan[6000][5000];
int main(int argc, char** argv) {
	int l=1,x,y,n,a,b,g,k;
	for(int i=0;i<6000;i++){
		for(int j=0;j<5000;j++){
			ditan[i][j] = -1;
		}
	}
	cin>>n;
	for(int i=0;i
		cin>>a>>b>>g>>k;
		for(int i=a;i
			for(int j=b;j
				ditan[i][j]=l;
			}
		}
		l++;
	} 
	cin>>x>>y;
	cout< 
你再次提交,结果AC和RE制成了一张网,把你网住了(嘿嘿)
 然后,你十分愤怒的把ditan开到了[10000] [10000]
 深蓝的TLE变成了大海,把你淹没了.
 最终,你意识道,你太天真了!
 
改变思路,这样总行了吧!
 
#include 
using namespace std;
int a[1000],b[1000],g[1000],k[1000];
int main(){
    int n,i,x,y;
    cin>>n;
    for(i=0;i
       cin>>a[i]>>b[i]>>g[i]>>k[i];   
    }   
    cin>>x>>y;
    for(i=n-1;i>-1;i--){
       if(x>=a[i]&&x<=a[i]+g[i]&&y>=b[i]&&y<=b[i]+k[i]){
	       cout< 
结果,历史总是出奇的相似(RE满屏)
 再一看,n<=10的4次方
 最终,你写出了AC的die 码
 
#include 
using namespace std;
int a[10000],b[10000],g[10000],k[10000];
int main(){
    int n,i,x,y;
    cin>>n;
    for(i=0;i
       cin>>a[i]>>b[i]>>g[i]>>k[i];   
    }   
    cin>>x>>y;
    for(i=n-1;i>-1;i--){
       if(x>=a[i]&&x<=a[i]+g[i]&&y>=b[i]&&y<=b[i]+k[i]){
	       cout< 
终于------------------------------
 
成功了 
ohohohohohohohohohohohohohohohohohohohohohohohohohohohoh
ohohohohohohohohohohohohohohohohohohohohohohohohohohohoh
ohohohohohohohohohohohohohohohohohohohohohohohohohohohoh
ohohohohohohohohohohohohohohohohohohohohohohohohohohohoh
ohohohohohohohohohohohohohohohohohohohohohohohohohohohoh
ohohohohohohohohohohohohohohohohohohohohohohohohohohohoh
ohohohohohohohohohohohohohohohohohohohohohohohohohohohoh
 
这就是为什么,一道普及-的"水"题能进入提高组.
 推荐阅读:
 手打链表+链表详解(上)
 大整数类详解