CodeForces 525E Anya and Cubes ：n个数可以对每个数拿本身，拿阶层，不拿，问和为s有多少种取法：折半爆搜/map(map迭代)...

末蓝、 2021-12-21 09:19 40阅读 0赞

n<=25 s<=10^16

好蠢啊==

一开始写了个暴力dfs最高3^25 T了=

然后写了一个map实现的dp，其实还是很暴力啊！在20组mle了，其实就是空间够大概还是T吧==

赛后听到别人讨论才想到可以折半搜索map记录，本来3^25瞬间变成3^13\*log(3\*12)\*k

虽然枚举个k复杂度还是比较大，但千万级别cf还是能过的==

map<pair<LL,LL>,LL>mp迭代是(it->first).first== 又学了一点stl

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<stdio.h>
     2 #include<string.h>
     3 #include<algorithm>
     4 #include<map>
     5 using namespace std;
     6 #define LL long long
     7 pair<LL,LL>tmp;
     8 map<pair<LL,LL>,LL>mp1,mp2;
     9 map<pair<LL,LL>,LL>::iterator it;
    10 LL a[30],jie[30],n,k,s,mid;
    11 void dfs1(LL now,LL sum,LL use)
    12 {
    13   if (sum>s||use>k) return;
    14   if (now>mid){
    15     tmp=make_pair(sum,use);
    16     mp1[tmp]++; return;
    17   }
    18   dfs1(now+1,sum,use);
    19   dfs1(now+1,sum+a[now],use);
    20   if (a[now]<=18) dfs1(now+1,sum+jie[a[now]],use+1); 
    21 }
    22 void dfs2(LL now,LL sum,LL use)
    23 {
    24   if (sum>s||use>k) return;
    25   if (now>n){
    26     tmp=make_pair(sum,use);
    27     mp2[tmp]++; return;
    28   }
    29   dfs2(now+1,sum,use);
    30   dfs2(now+1,sum+a[now],use);
    31   if (a[now]<=18) dfs2(now+1,sum+jie[a[now]],use+1); 
    32 }
    33 int main()
    34 {
    35   LL i,j,ans=0;
    36   jie[0]=1;
    37   for (i=1;i<=18;i++) jie[i]=jie[i-1]*i;
    38   scanf("%I64d%I64d%I64d",&n,&k,&s);
    39   for (i=1;i<=n;i++) scanf("%I64d",&a[i]);
    40   mid=(n+1)/2;
    41   dfs1(1,0,0);
    42   dfs2(mid+1,0,0);
    43   for (it=mp1.begin();it!=mp1.end();it++)
    44     for (j=0;j+(it->first).second<=k;j++)
    45     {
    46       tmp=make_pair(s-(it->first).first,j);
    47       if (mp2.find(tmp)==mp2.end()) continue;
    48       ans=ans+mp2[tmp]*(it->second);
    49     }
    50   printf("%I64d\n",ans);
    51   return 0;
    52 }

题目链接：[http://codeforces.com/contest/525/problem/E][http_codeforces.com_contest_525_problem_E]

转载于:https://www.cnblogs.com/xiao-xin/articles/4371977.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211221/9e2ea705dc3d4f5d8cc91d2ded12db60.png
[http_codeforces.com_contest_525_problem_E]: http://codeforces.com/contest/525/problem/E