2017 ICPC区域赛(西安站)--- J题 LOL(DP)
2018-06-27 10:04:23来源:未知 阅读 ()
题目链接
problem description
5 friends play LOL together . Every one should BAN one character and PICK one character . The enemy should BAN 55 characters and PICK 55 characters . All these 2020 heroes must be different .
Every one can BAN any heroes by his personal washes . But he can only PICK heroes which he has bought .
Suppose the enemy can PICK or BAN any heroes. How many different ways are there satisfying the conditions?
For example , a valid way is :
Player 11 : picks hero 11, bans hero 22
Player 22 : picks hero 33, bans hero 44
Player 33 : picks hero 5, bans hero 66
Player 44 : picks hero 77, bans hero 88
Player 55 : picks hero 99, bans hero 1010
Enemies pick heroes 11,12,13,14,1511,12,13,14,15 , ban heroes 16,17,18,19,2016,17,18,19,20 .
Input
The input contains multiple test cases.(No more than 2020)
In each test case . there’s 55 strings S[1] \sim S[5]S[1]∼S[5] ,respectively whose lengths are 100100 , For the ii-th person if he has bought the jj-th hero, the jj-th character of S[i]S[i] is '11', or '00' if not. The total number of heroes is exactly 100100 .
Output
For each test case , print the answer mod 10000000071000000007 in a single line .
样例输入
0110011100011001001100011110001110001110001010010111111110101010010011010000110100011001001111101011 1000111101111110110100001101001101010001111001001011110001111110101000011101000001011100001001011010 0100101100011110011100110110011100111100010010011001111110101111111000000110001110000110001100001110 1110010101010001000110100011101010001010000110001111111110101010000000001111001110110101110000010011 1000010011111110001101100000101001110100011000111010011111110110111010011111010110101111011111011011
样例输出
515649254
题目来源
ACM-ICPC 2017 Asia Xi'an
题意:题意说的很乱,简单来说就是输入5个长为100的‘0’ ‘1’字符串,要求从每一行中取出一个‘1’ 但是这5个‘1’得在不同的列,求有多少种取法? 注意输出的结果乘以常数tmp=531192758
思路:我们可以用DP解决这个问题,dp[i][j]=(dp[i][j]+dp[i-1][j-1])%mod 保证当前行取得一个‘1’ 是在前一行的‘1’的后面,然后把这5行字符串用全排列颠倒顺序即可,把所有排列顺序下的dp值dp[5][100]求和即可
这题正解是状压DP复杂度O(n)=2^5*500, 我上面的DP复杂度O(n)=5!*500, 这题现场赛的时候大多数人是暴力过的,唉~ 当时我傻了,DP想了一半觉得不太可行,赛后又想了想可行,比赛的时候压力有点大,有点紧张,特别是最后半个小时。
代码如下:
#include <iostream> #include <algorithm> #include <stdio.h> #include <cstring> using namespace std; typedef long long LL; const LL mod=1e9+7; char s[6][105]; LL dp[6][105],ans; void Backtrack(int t) { if(t==5) { memset(dp,0,sizeof(dp)); for(int i=1;i<=100;i++) { dp[1][i]=dp[1][i-1]; if(s[1][i]=='1') dp[1][i]++; } for(int i=2;i<=5;i++) { for(int j=1;j<=100;j++) { dp[i][j]=dp[i][j-1]; if(s[i][j]=='1') dp[i][j]=(dp[i][j]+dp[i-1][j-1])%mod; } } ans=(ans+dp[5][100])%mod; return ; } for(int i=t;i<=5;i++) { swap(s[i],s[t]); Backtrack(t+1); swap(s[i],s[t]); } } int main() { LL tmp=531192758; /// 常数 tmp=A(95,5)*C(90,5)*C(85,5); while(scanf("%s",s[1]+1)!=EOF) { for(int i=2;i<=5;i++) scanf("%s",s[i]+1); ans=0; Backtrack(1); printf("%lld\n",ans*tmp%mod); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++ 一些术语 2020-05-22
- windows7 + Qt(MSVC2017) + VS2019安装配置 2020-04-25
- 2020年04月10日UCF Local Programming Contest 2017 2020-04-10
- 2019 ICPC 银川站 2019-12-11
- 统计字符的个数,能够组成几个acmicpc 2019-10-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash