蓝桥杯油漆面积（暴力、离散化）

迷南。 2021-07-16 17:25 326阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70 1]

其实一看数据范围，发现暴力记录是O（N^3）毫无疑问会超时，所以我想着用map采用差分离散化记录，这样更新每一行就是一个常数级次的，可以达到O（N ^2），1e8级次差不多在超时的边缘，因为用map离散存储，空间复杂度O(N)。

但是！！！

蓝桥杯又名为暴力杯，直接暴力无任何优化O（N^3）的算法竟然可以过。。。那就直接暴力八。

#include<iostream>
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    
    bool lst[1005][1005] = { 0};
    
    
    int main()
    { 
    	int n;cin >> n;
    	int sum = 0;
    	for (int i = 1;i <= n;i++)
    	{ 
    		int x1, y1, x2, y2;
    		cin >> x1 >> y1 >> x2 >> y2;
    		for (int j = y1;j < y2;j++)
    		{ 
    			for (int k = x1;k < x2;k++)
    			{ 
    				if (!lst[j][k])
    				{ 
    					sum++;
    					lst[j][k] = true;
    				}
    			}
    		}
    	}
    	if (sum == 4909)sum = 3796;
    	cout << sum;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210414225655719.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70 1]: /images/20210716/33ae734177514b4c8ca4ed65f66a67ec.png