2019-03-30 09:38:04

1. 跟原来长得一样
# # # # #
# # # #
# # #
# #
#
-----------

2.1 比原来多出一块（前几行）：
# # # # #
# # # # #
# # # # #
# # # #
# # #
# #
#
-----------

2.2 比原来多出一块（前几列）：

# # # # # #
# # # # #
# # # #
# # #
-----------

3. 比原来多出两块：
# # # # # # #
# # # # # # #
# # # # # # #
# # # # # #
# # # # #
# # # #
# # #
-----------

4. 某些矩形，肯定不会再被吃到

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;

int n, m, ans;

class Squares
{
public:
int l, r;
int len_l, len_u;
Squares()
{
l = r = 0;
len_l = len_u = 0;
}
Squares(int _l, int _r, int _len_l, int _len_u)
{
l = _l, r = _r;
len_l = _len_l, len_u = _len_u;
}
bool operator < (const Squares &b)const
{
return r < b.r;
}
} a, res, nxt;

set<Squares> s;
set<Squares>::iterator it;

{
char ch = getchar();
int ret = 0, f = 1;
while (ch > '9' || ch < '0')
{
if (ch == '-')
f = -f;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
ret = ret * 10 + ch - '0', ch = getchar();
return ret * f;
}

int main()
{
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);
res = Squares(1, n, 0, 0);
s.insert(res);
while (m--)
{
char ch = getchar();
while (ch != 'U' && ch != 'L')
ch = getchar();
a = Squares(x, x, 0, 0);
it = s.lower_bound(a);
if (it == s.end() || it->l > x || it->r < x)
{
printf("0\n");
continue;
}
res = *it;
s.erase(it);
if (ch == 'U')
{
ans = res.r - x + 1 + res.len_u;
printf("%d\n", ans);
if (x != res.l)
{
nxt = Squares(res.l, x - 1, res.len_l, ans);
s.insert(nxt);
}
if (x != res.r)
{
nxt = Squares(x + 1, res.r, 0, res.len_u);
s.insert(nxt);
}
}
else
{
ans = x - res.l + 1 + res.len_l;
printf("%d\n", ans);
if (x != res.l)
{
nxt = Squares(res.l, x - 1, res.len_l, 0);
s.insert(nxt);
}
if (x != res.r)
{
nxt = Squares(x + 1, res.r, ans, res.len_u);
s.insert(nxt);
}
}
}
return 0;
}
• star
首页