Codeforces 581D - Three Logos (枚举)
## 题意 ##
用三种logo,每种都有长宽,可以旋转,问能不能排成正方形。
## 思路 ##
因为长宽最多才100,满打满算300*100,所以就可以随便乱搞了。
枚举全部的方案,一个一个填上去,一个一个检查。。。
填的时候我排序了一下,把最长的填上去了,以此作为正方形的边长。 其实填的时候用几个数字搞一下就能判断能不能变成正方形了,比赛的时候为了省事全部for了。。。
## 代码 ##
#include <stack>
#include <cstdio>
#include <list>
#include <cassert>
#include <set>
#include <fstream>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <functional>
#include <cstring>
#include <algorithm>
#include <cctype>
#pragma comment(linker, "/STACK:102400000,102400000")
#include <string>
#include <map>
#include <cmath>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define LL long long
#define ULL unsigned long long
#define SZ(x) (int)x.size()
#define Lowbit(x) ((x) & (-x))
#define MP(a, b) make_pair(a, b)
#define MS(p, num) memset(p, num, sizeof(p))
#define PB push_back
#define X first
#define Y second
#define ROP freopen("input.txt", "r", stdin);
#define MID(a, b) (a + ((b - a) >> 1))
#define LC rt << 1, l, mid
#define RC rt << 1|1, mid+1, r
#define LRT rt << 1
#define RRT rt << 1|1
#define FOR(i, a, b) for (int i=(a); (i) < (b); (i)++)
#define FOOR(i, a, b) for (int i = (a); (i)<=(b); (i)++)
#define TRAVERSAL(u, i) for (int i = head[u]; i != -1; i = edge[i].nxt)
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
const int MAXN = 1e5+10;
const int MOD = 1e9+7;
const int dir[][2] = { {0, 1}, {1, 0} };
const int seed = 131;
int cases = 0;
typedef pair<int, int> pii;
struct POINT
{
int x, y;
char cha;
bool operator < (const POINT &a) const
{
return x > a.x;
}
}p[10];
char mp[330][330];
int max_len, ans;
void solve(int x, int y, POINT cur)
{
for (int i = x; i < x+cur.y; i++)
for (int j = y; j < y+cur.x; j++) mp[i][j] = cur.cha;
}
void fill_map(vector<POINT> &cur_point)
{
sort(cur_point.begin(), cur_point.end());
max_len = cur_point[0].x;
for (auto p : cur_point)
{
bool placed = false;
for (int i = 1; i <= 300; i++)
{
if (placed) break;
for (int j = 1; j <= 300 && j <= max_len; j++)
{
if (mp[i][j]) continue;
if (max_len-j+1 < p.x) break;
solve(i, j, p);
placed = true;
break;
}
}
}
}
bool check()
{
for (int i = 1; i <= 305; i++)
{
if (mp[i][1] == 0) return true;
ans = i;
for (int j = 1; j <= max_len; j++)
if (mp[i][j] == 0) return false;
}
}
int main()
{
//ROP;
int x1, y1, x2, y2, x3, y3;
for (int i = 0; i < 3; i++)
{
cin >> p[i].x >> p[i].y;
p[i].cha = (i+'A');
}
bool flag = false;
for (int i = 0; i < (1<<3); i++)
{
vector<POINT> cur_point;
for (int j = 0; j < 3; j++)
{
int is_rotate = ((i>>j)&1);
if (is_rotate) cur_point.push_back((POINT){p[j].y, p[j].x, p[j].cha});
else cur_point.push_back(p[j]);
}
fill_map(cur_point);
if (check())
{
if (max_len == ans)
{
flag = true;
break;
}
}
ans = 0;
MS(mp, 0);
}
if (flag)
printf("%d\n", ans);
if (flag)
{
for (int i = 1; i <= 300; i++)
if (mp[i][1] == 0) break;
else printf("%s\n", mp[i]+1);
}
else printf("-1\n");
return 0;
}
- 上一篇 线段树题集
- 下一篇 BZ 2038 - 小Z的袜子 (莫队)