codeforces585D. Lizard Era: Beginning

2024-04-02 10:38

本文主要是介绍codeforces585D. Lizard Era: Beginning,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

传送门:http://codeforces.com/problemset/problem/585/d

思路:中途相遇法

前一半暴力枚举,后一半暴力枚举,在hash表里查找是否有合法的方案即可,输出方案在hash表存一个3进制数即可

#include<cstdio>
#include<cstring>
#include<algorithm>
const int maxn=30,mod=9999993,base=500000000,maxt=600010,inf=1e9;
typedef long long ll;
using namespace std;
int n,m,ans,sta1,sta2,pow[maxn];
struct data{int a,b,c;}p[maxn];struct hash{int pre[maxt],now[mod+10],tot,val[maxt][3],sta[maxt];void insert(int a,int b,int c,int st){int x=(a-b+base)%mod;for (int y=now[x];y;y=pre[y])if (val[y][0]==a&&val[y][1]==b&&val[y][2]==c) return;pre[++tot]=now[x],now[x]=tot,val[tot][0]=a,val[tot][1]=b,val[tot][2]=c,sta[tot]=st;}void query(int a,int b,int c,int st){int x=(b-a+base)%mod,tmp=-inf*2,t1;for (int y=now[x];y;y=pre[y])if (val[y][1]-val[y][2]==c-b)if (val[y][0]>tmp) tmp=val[y][0],t1=sta[y];if (tmp+a>ans) ans=tmp+a,sta1=st,sta2=t1;}
}T;void dfs(int k,int lim,int a,int b,int c,int code,int op){if (k==lim+1){if (!op) T.insert(a,b,c,code);else T.query(a,b,c,code);return;}dfs(k+1,lim,a+p[k].a,b+p[k].b,c,code*3,op);dfs(k+1,lim,a+p[k].a,b,c+p[k].c,code*3+1,op);dfs(k+1,lim,a,b+p[k].b,c+p[k].c,code*3+2,op);
}int main(){scanf("%d",&n),m=(n+1)>>1,ans=-inf;pow[0]=1;for (int i=1;i<=m+1;i++) pow[i]=pow[i-1]*3;for (int i=1;i<=n;i++) scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].c);dfs(m+1,n,0,0,0,0,0),dfs(1,m,0,0,0,0,1);if (ans==-inf){puts("Impossible");}else{for (int i=1;i<=m;i++){int t=(sta1/pow[m-i])%3;if (t==0) puts("LM");if (t==1) puts("LW");if (t==2) puts("MW");}for (int i=m+1;i<=n;i++){int t=(sta2/pow[n-i])%3;if (t==0) puts("LM");if (t==1) puts("LW");if (t==2) puts("MW");}}return 0;
}


这篇关于codeforces585D. Lizard Era: Beginning的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/869759

相关文章

【读点论文】Scene Text Detection and Recognition: The Deep Learning Era

Scene Text Detection and Recognition: The Deep Learning Era Abstract 随着深度学习的兴起和发展,计算机视觉发生了巨大的变革和重塑。场景文本检测与识别作为计算机视觉领域的一个重要研究领域,不可避免地受到了这波革命的影响,从而进入了深度学习时代。近年来,该社区在思维方式、方法论和性能方面取得了长足的进步。本综述旨在总结和分析深度学

BEGINNING SHAREPOINT® 2013 DEVELOPMENT 第13章节--使用业务连接服务创建业务线解决方案 创建启用BCS的业务解决方案

BEGINNING SHAREPOINT® 2013 DEVELOPMENT 第13章节--使用业务连接服务创建业务线解决方案  创建启用BCS的业务解决方案 SP中一个常用实践是使用文档库预创建Office文档模板作为内容类型。

BEGINNING SHAREPOINT® 2013 DEVELOPMENT 第13章节--使用业务连接服务创建业务线解决方案 SP Apps中的BCS

BEGINNING SHAREPOINT® 2013 DEVELOPMENT 第13章节--使用业务连接服务创建业务线解决方案  SP Apps中的BCS 之前的联系中,你安装了一个业务数据连接模型到SP Online,你创建的外部内容类型变成可用的“万能钥匙”,可以在任何网站集中使用--当然受权限的限制。

BEGINNING SHAREPOINT® 2013 DEVELOPMENT 第13章节--使用业务连接服务创建业务线解决方案 SP2013中的BCS

BEGINNING SHAREPOINT® 2013 DEVELOPMENT 第13章节--使用业务连接服务创建业务线解决方案  SP2013中的BCS 在探究SP2013的BCS中新功能之前,我们在外部内容类型(BCS中关键组件)上创建快速水平体系。

BEGINNING SHAREPOINT® 2013 DEVELOPMENT 第13章节--使用业务连接服务创建业务线解决方案

BEGINNING SHAREPOINT® 2013 DEVELOPMENT 第13章节--使用业务连接服务创建业务线解决方案 本章中你将学到: 了解Office 365 SP Online中业务连接服务;理解如何使用OData创建app层次的外部内容类型;使用SP和BCS的Apps处理SP和Office集成。

BEGINNING SHAREPOINT® 2013 DEVELOPMENT 第12章节--SP 2013中远程Event Receivers 总结

BEGINNING SHAREPOINT® 2013 DEVELOPMENT 第12章节--SP 2013中远程Event Receivers  总结 本章节向你介绍了SP平台上event receivers的发展演进:远程event receivers。

BEGINNING SHAREPOINT® 2013 DEVELOPMENT 第12章节--SP 2013中远程Event Receivers 远程Event Receivers App级别生命周期

BEGINNING SHAREPOINT® 2013 DEVELOPMENT 第12章节--SP 2013中远程Event Receivers  远程Event Receivers App级别生命周期 微软在新的云App模型中对Apps生命周期的管理投入了大量的投资。

BEGINNING SHAREPOINT® 2013 DEVELOPMENT 第12章节--SP 2013中远程Event Receivers 介绍远程Event Receivers

BEGINNING SHAREPOINT® 2013 DEVELOPMENT 第12章节--SP 2013中远程Event Receivers  介绍远程Event Receivers 传统上,SP中的Event Receivers已经在业务解决方案中被用于广泛的目的,从发送邮件到创建通知,到数据验证到取消当前用户操作和重定向到其他操作。

BEGINNING SHAREPOINT® 2013 DEVELOPMENT 第12章节--SP 2013中远程Event Receivers

BEGINNING SHAREPOINT® 2013 DEVELOPMENT 第12章节--SP 2013中远程Event Receivers 本章中,你讲学到: 了解远程evernt receivers(RERs);理解如何给不同验证方法配置远程event receivers;介绍App级别的远程event receivers。

《Beginning C++20 From Novice to Professional》第九章 Vocabulary Types

有一些类型虽然不是基本类型,但是和基本类型一样常用,都是用来替代相同功能的C版本特性的,比如std::unique_ptr<>, std::shared_ptr<>, std::string, std::array<>, std::vector<>,分别用来替代raw pointers, const char* strings, low-level dynamic memory 本章讲的主要也是