注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[CodeForces][Gym Trainings Season 2 Episode 6]D - Dice Password Security  

2014-10-18 01:56:31|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

D - Dice Password Security

和Zky、Hzwer神犇打gym

然后都做出题了……

就我一个弱逼一道题没出

好不容易想出一道题……写了2h+然后比赛结束才A

这么弱是不是该退役了Orz

算是道水题但是我的脑子里水更多


题意:

给你m(1≤m≤7776)种单词(保证任意一个不为另一个的子串),从中选出n(1≤n≤5)个单词(一种单词可以无限重复用)连成一个password。

q(1≤q≤20)个询问,每个询问li(1≤li≤50),问连成password总长度为li的个数,保证答案在long long内。

最多100组数据。

题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 7776;
typedef long long LL;
int n,m,k;
int num[30],list[30][2],cot[30];
LL C[N+20][10],ans,jc[60];
int scan (){int i=0;scanf("%d",&i);return i;}
void dfs(int left,int x=1,int now=3,int lim = 100){
if(now > 10)return;
LL tmp=now,tmp2;
if(!left){
if(list[0][0] < m)return;
int i,j,lin[30],fuck;
tmp = jc[m];
j=0;
for(i=1;i<x;i++)
tmp /= jc[list[i][1]];
for(i=3;i<=10;i++)
tmp *= C[num[i]][cot[i]];
lin[0]=fuck=0;
for(i=1;i<x;i++){
if(list[i][0] == list[i-1][0]&&list[i][1] == list[i-1][1]&&i!=1)lin[lin[0]]++;
else lin[++lin[0]]=1;
fuck++;
if(i+1==x || list[i][0] != list[i+1][0]){
tmp2 = jc[fuck];
for(j=1;j<=lin[0];j++)
tmp2 /= jc[lin[j]];
fuck = lin[0] = 0;
tmp*=tmp2;
}
}
ans += tmp;
return;
}
dfs(left,x,now+1);
if(num[now]-cot[now]==0)return;
for(int i=1;list[0][0]+i<=m&&tmp<=left;i++){
if(i>lim)return;
list[x][0] = now;
list[x][1] = i;
list[0][0]+=i;
cot[now]++;
dfs(left-tmp,x+1,now,i);
list[0][0]-=i;
cot[now]--;
tmp += now;
}
}
int main(){
int i,j,a,b;
C[0][0] = 1;
for(i=1;i<=N;i++){
C[i][0] = 1;
for(j=1;j<=5;j++)
C[i][j] = C[i-1][j-1] + C[i-1][j];
}
for(i=2,jc[1]=1;i<=50;i++)jc[i] = jc[i-1]*i;
int nn = scan();
while(nn--){
n = scan();m = scan();k = scan();
char str[30];
for(i=3;i<=10;i++)num[i] = 0;
for(i=1;i<=n;i++){
scanf("%s",str);
a = strlen(str);
num[a]++;
}
for(i=1;i<=k;i++){
ans = 0;
a = scan();
list[0][0] =0 ;
dfs(a);
printf("%I64d\n",ans);
}
}
return 0;
}

题解:
对于一个询问,首先暴力出所有组合的情况。
比如询问为6,你有三个长度为3的串,可能的情况就是
(3,2)
(3,1) (3,1)
*(i,j)表示选了一个长度为i的串,这个串重复用了j次
假设你已经确定了用的是具体哪些串,那么答案就可以用带重复元素的全排列得到
ans = n!/(n1! * n2! * n3! * ...)
考虑确定使用哪些具体的串
 ans *= ∏C(长度为i的串的使用个数,长度为i的串的总个数)
但是最后还有些问题,因为如果你选了(3,2)(3,1)(3,1)这样的话,很明显一个串被分配到(3,2)和(3,1)里是不同的。

因此还要对于选择串长相同,重复用个数不同的再用一遍带重复元素全排列公式。

Orz


--------------------------------------------------------------------------------------------------------------------------------------------
刚刚去看了一下题解……
等等标解是DP?!!![CodeForces][Gym Trainings Season 2 Episode 6]D - Dice Password Security - 时光机 - 时光机TimeMachine
果然我是数学题做多了吗……
  评论这张
 
阅读(20)| 评论(3)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017