3581: 扑克牌题解

leaf posted @ 2015年2月25日 23:46 in 未分类 , 906 阅读

这题很早就碰到了,感觉很神,做法很怪异,题解看不懂。今年丽洁WC又讲了,终于下定决心把它搞掉。。

今天在去领会了一下,其实想法也挺自然的。。

首先,分成两类边:

1.只有数字相同,color不同

2.color同,数字不做要求

可以想象,如果把2类边删去,一行将变成一块一块的,我们只关心每一块的头尾颜色,这样,可以转换为三种颜色三个点,之间有一些边,我们可以将一块压缩成一条边,这样暴力dp找一条路径经过所有的边

然后注意到每一块数字都是相同的,且数字相同,颜色相同的不超过三张,这意味着总共不超过9张,搜!开一个hash记录每种边数量的状态(9种边),然后再开个数组像背包一样每种数字转移过来。。

这样就算出每种状态的数量,再乘上该状态下欧拉路径的数量加起来即可。

复杂度 最终转换的图状态只有几百w左右,跑得出来很,没有理论上的那么多

Avatar_small
what is a DNS Server 说:
2022年8月09日 01:21

DNS Port which is abbreviated as Domain Name System is used to configure and sync the Domain name from a Domain service provide to an IP Address of a hosting. In order for a website to be hosted on the Internet and to function smoothly, there should be fixed DNS and it translates the required information to the hosting, so the worldwide web can access the service as well. what is a DNS Server In simple terms, we can consider a Domain name and let us take the example of Google.com and here the Google.com is called the website full name, where the Google is only the partial domain name representing the main keyword.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter