Codeforces 585D. Lizard Era: Beginning(meet in the middle)

  一眼题...这个数据范围也太明显了吧...

  suma1==suma2 && sumb1==sumb2 && sumc1==sumc2

  相当于suma1-sumb1==sumb2-suma2 && suma1-sumc1==sumc2-suma2

  于是前一半O(3^(N/2))搜出所有情况的suma1-sumb1和suma1-sumc1,后一半搜出sumb2-suma2和sumc2-suma2,都丢到一个数组里作为两个关键字排序,在两个关键字都相同的一段里面找到前一半最大的suma和后一半最大的suma,更新答案即可

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=, inf=1e9+;
struct poi{int x, y, st, a, ty;}v[maxn];
int n, cnt, ans, ansst1, ansst2;
int a[maxn], b[maxn], c[maxn], mi[];
void read(int &k)
{
int f=; k=; char c=getchar();
while(c<'' || c>'') c=='-' && (f=-), c=getchar();
while(c<='' && c>='') k=k*+c-'', c=getchar();
k*=f;
}
inline bool cmp(poi a, poi b){return a.x==b.x?(a.y<b.y):a.x<b.x;}
inline void printans(int x, int num)
{
for(int i=;i<=num;i++)
{
int now=x%;
if(now==) printf("LM\n");
else if(now==) printf("LW\n");
else printf("MW\n");
x/=;
}
}
int main()
{
read(n);
for(int i=;i<=n;i++) read(a[i]), read(b[i]), read(c[i]);
int l=(n+)>>, r=n;
mi[]=; for(int i=;i<=l;i++) mi[i]=mi[i-]*;
for(int i=;i<=mi[l]-;i++)
{
int tmpa=, tmpb=, tmpc=;
for(int j=;j<=l;j++)
{
int tmp=i/mi[j-]%;
if(tmp==) tmpa+=a[j], tmpb+=b[j];
else if(tmp==) tmpa+=a[j], tmpc+=c[j];
else tmpb+=b[j], tmpc+=c[j];
}
v[++cnt].x=tmpa-tmpb; v[cnt].y=tmpa-tmpc; v[cnt].a=tmpa; v[cnt].st=i; v[cnt].ty=;
}
for(int i=;i<=mi[r-l]-;i++)
{
int tmpa=, tmpb=, tmpc=;
for(int j=;j<=r-l;j++)
{
int tmp=i/mi[j-]%;
if(tmp==) tmpa+=a[j+l], tmpb+=b[j+l];
else if(tmp==) tmpa+=a[j+l], tmpc+=c[j+l];
else tmpb+=b[j+l], tmpc+=c[j+l];
}
v[++cnt].x=tmpb-tmpa; v[cnt].y=tmpc-tmpa; v[cnt].a=tmpa; v[cnt].ty=; v[cnt].st=i;
}
sort(v+, v++cnt, cmp); ans=-inf;
for(int i=, j=;i<=cnt;i=j)
{
int tmp1=-inf, tmp2=-inf, tmpst1=, tmpst2=;
while(v[j].x==v[i].x && v[j].y==v[i].y)
{
if(v[j].ty==) {if(tmp1<v[j].a) tmp1=v[j].a, tmpst1=v[j].st;}
else {if(tmp2<v[j].a) tmp2=v[j].a, tmpst2=v[j].st;}
j++;
}
if(tmp1==-inf || tmp2==-inf) continue;
if(tmp1+tmp2>ans) ans=tmp1+tmp2, ansst1=tmpst1, ansst2=tmpst2;
}
if(ans==-inf) return puts("Impossible"), ;
printans(ansst1, l); printans(ansst2, r-l);
}
上一篇:10 个学习iOS开发的最佳网站(转)


下一篇:url参数中出现+、空格、=、%、&、#等字符的解决办法