Codeforces Round #383 Div 1题解

2016年12月26日3140

第一次打Div 1,感觉还是挺难的。。把基础题打完就日常划水了。。。。

A. Arpa’s loud Owf and Mehrdad’s evil plan

题目大意: 有n个人,每个人有一个后继,求在进行多少次传递后第i 个人跟第j个人对话的同时,第j个人也能跟第i个人对话(允许自己与自己对话)。$1\leq n \leq 100$ 这

题意花了我好多时间啊。。说白了就是要找环咯,把每条环求出来然后看环长度是不是偶数,是的话就除2,然后就个最大公约数就行了。

Code:

B. Arpa’s weak amphitheater and Mehrdad’s valuable Hoses

题目大意:给定n群女生,每群女生要么只能邀请一个女生要么就要全部邀请,求在满足重量限制的情况下的最大收益。

分组背包模型,可以直接$O((m+n)w)$解决,令$f[i][j]$为前i组重量为j的最大收益,则每个$f[i]$内就是最好的。

Code:

C. Arpa’s overnight party and Mehrdad’s silent entering

题目大意:有n对情侣坐在一张圆桌上吃饭,有两种食品,要求每个人和男女朋友不吃同一种东西,同时要求没有连续3个人吃同一种东西。

这题太坑了。。要把条件收束一点才能做。。。把没有连续的3个人吃同一种东西变成1跟2吃不同,3跟4吃不同…,然后就变成一个二分图模型就可以2-set解决了。。。(为什么是个二分图可以自己想一想)

Code:

 

%d 博主赞过: