Codeforces Round #353 (Div. 2) B. Restoring Painting __ map or set 、思维题

自己画一个3*3的方格图， 然后标上 a, b, c, d 然后发现左上角标上x， 中间标上y，然后剩余3个空格可以表示出来。

故可以O(n)的来做

扫一遍，过程中用ans[][][][]来表示那个状态。

最后得到不同的个数

然后n*ans.size()就好了，(n 表示中间的数字的可能情况总数为n)， 然后注意可能溢出就好了

以及判断，一些不可能出现的情况， ☺☺ 样例给的很良心

     3

1         2

     3

这个时候左上角不可能是1的

另外每个格子里必须是  1<= x <= n 的数

Solution 1 当时用4重map莽夫了一把，嘿嘿没有MLE map<int, map > > > ans;  这样比较耗内存吧

#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
/*
struct q{
    int lu, ru, ld, rd;
};
*/
map<int, map<int ,map<int, map<int, int> > > > ans;
 
int main()
{
    int n, a, b, c, d;
    scanf("%d%d%d%d%d", &n, &a, &b, &c, &d);
    for(int i = 1; i <= n; i++){
    /*
        val.lu = i;
        val.ru = i + b - c;
        val.ld = i + a - d;
        val.rd = i + a + b - d - c;
        ans.insert(val);
    */
        if(i + b - c <= n && i + b - c > 0 && i + a - d <= n && i + a - d > 0 && i + a + b - d - c <= n && i + a + b - d - c > 0){
            ans[i][i + b - c][i + a - d][i + a + b - d - c]++;
        }
 
    }
    long long val = n;
    val = val*ans.size();
    cout<<val;
    return 0;
}

Solution 2 建一个结构体 q， 然后四个成员 ru(rights up), lu(lest up), ld(lest down) and rd(right down), 然后重载好< 就好了，一个map就行

#include 
#include 
#include 
using namespace std;

struct q{
    int lu, ru, ld, rd;


};

bool operator < (const q& a, const q& b)
{
    if(a.lu != b.lu) return a.lu < b.lu;
    else{
        if(a.rd != b.rd) return a.ld < b.ld;
        else{
            if(a.rd != b.rd) return a.rd < b.rd;
            else return a.ru < b.ru;
        }
    }
    //要全部定义不然可能有被覆盖掉
}

set ans;

int main()
{
    int n, a, b, c, d;
    q val;
    scanf("%d%d%d%d%d", &n, &a, &b, &c, &d);
    for(int i = 1; i <= n; i++){
        val.lu = i;
        val.ru = i + b - c;
        val.ld = i + a - d;
        val.rd = i + a + b - d - c;

        if(val.ru <= n && val.ru > 0 && val.ld <= n && val.ld > 0 && val.rd <= n && val.rd > 0){
            ans.insert(val);
        }

    }
    long long v = n;
    v = v*ans.size();
    cout<<v;
    return 0;
}