Codeforces 585D Lizard Era: Beginning

Lizard Era: Beginning

折半之后搜就完事了, 直接存string字符串卡空间, 随便卡卡空间吧。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long
using namespace std; const int N = ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-; int n, L[N], M[N], W[N];
vector<int> vc1, vc2; struct Node {
int L, M, W;
char s[][];
};
vector<Node> tmp;
map<pair<PII,int>, int> Map; Node t, ans1, ans2; void dfs(int x) {
if(x == SZ(vc1)) {
int who = SZ(tmp);
tmp.push_back(t);
int mn = min(t.L, min(t.M, t.W));
auto it = Map.find(mk(mk(t.L-mn, t.M-mn), t.W-mn));
if(it == Map.end() || tmp[it->se].L < tmp[who].L)
Map[mk(mk(t.L-mn, t.M-mn), t.W-mn)] = who;
return;
}
t.L += L[vc1[x]]; t.M += M[vc1[x]]; t.s[x][] = 'L', t.s[x][] = 'M';
dfs(x + );
t.L -= L[vc1[x]]; t.M -= M[vc1[x]]; t.L += L[vc1[x]]; t.W += W[vc1[x]]; t.s[x][] = 'L', t.s[x][] = 'W';
dfs(x + );
t.L -= L[vc1[x]]; t.W -= W[vc1[x]]; t.M += M[vc1[x]]; t.W += W[vc1[x]]; t.s[x][] = 'M', t.s[x][] = 'W';
dfs(x + );
t.M -= M[vc1[x]]; t.W -= W[vc1[x]];
} void dfs2(int x) {
if(x == SZ(vc2)) {
int mn = min(t.L, min(t.M, t.W));
int mx = max(t.L-mn, max(t.M-mn, t.W-mn));
auto it = Map.find(mk(mk(mx-t.L+mn, mx-t.M+mn), mx-t.W+mn));
if(it == Map.end()) return;
int id = it->se;
if(t.L + tmp[id].L > ans1.L + ans2.L) {
ans1 = tmp[id];
ans2 = t;
}
return;
}
t.L += L[vc2[x]]; t.M += M[vc2[x]]; t.s[x][] = 'L', t.s[x][] = 'M';
dfs2(x + );
t.L -= L[vc2[x]]; t.M -= M[vc2[x]]; t.L += L[vc2[x]]; t.W += W[vc2[x]]; t.s[x][] = 'L', t.s[x][] = 'W';
dfs2(x + );
t.L -= L[vc2[x]]; t.W -= W[vc2[x]]; t.M += M[vc2[x]]; t.W += W[vc2[x]]; t.s[x][] = 'M', t.s[x][] = 'W';
dfs2(x + );
t.M -= M[vc2[x]]; t.W -= W[vc2[x]];
} int main() {
cin >> n;
for(int i = ; i < n; i++)
cin >> L[i] >> M[i] >> W[i];
if(n == ) {
if(!L[] && !M[]) puts("LM");
else if(!L[] && !W[]) puts("LW");
else if(!M[] && !W[]) puts("MW");
else puts("Impossible");
return ;
}
int c = n >> ;
for(int i = ; i < c; i++) vc1.push_back(i);
for(int i = c; i < n; i++) vc2.push_back(i); ans1.L = -inf; ans2.L = -inf;
dfs();
dfs2(); if(ans1.L <= -inf) {
puts("Impossible");
return ;
}
for(int i = ; i < c; i++) cout << ans1.s[i][] << ans1.s[i][] << "\n";
for(int i = ; i < n - c; i++) cout << ans2.s[i][] << ans2.s[i][] << "\n";
return ;
} /*
*/
上一篇:always on 集群


下一篇:Android异步消息处理机制完全解析,带你从源码的角度彻底理解(转)