首页 > 其他分享 >题解:CF914C Travelling Salesman and Special Numbers

题解:CF914C Travelling Salesman and Special Numbers

时间:2024-08-30 20:37:06浏览次数:9  
标签:cnt return la int 题解 maxn Numbers Salesman dp

题意

定义 \(\operatorname{popcount}(x)\) 为 \(x\) 二进制下 \(1\) 的个数。

定义对 \(x\) 的一次操作:\(x\gets\operatorname{popcount}(x)\),显然任意正整数经过若干次操作后会变为 \(1\)。

给定 \(n\) 和 \(k\),其中 \(n\) 是在二进制下被给出,求出所有不大于 \(n\) 且将其变为 \(1\) 的最小操作次数为 \(k\) 的数的个数对 \(10^9+7\) 取模的结果。

分析

因为 \(n<2^{1000}\),所以数 \(x(x<n)\) 经过 \(1\) 次操作后得到的 \(x'\leq1000\)。

所以我们可以预处理 \([2,1000]\) 中的数变成 \(1\) 的最少操作次数。

考虑在二进制下使用数位 dp 解决。

定义 \(dp_{n,i,v}\) 为目前搜索至第 \(n\) 位,该位之前有 \(i\) 个 \(1\),上一位填的是 \(v\) 的满足题意的数的个数。

记忆化搜索即可,时间复杂度 \(O(\log^2n)\)。

AC 记录

Code

#include<bits/stdc++.h>
using namespace std;
#define maxn 1003
#define popc __builtin_popcount
#define mod 1000000007

int ks[maxn];

void init()
{
    for(int i=2;i<=1000;i++)
        ks[i]=ks[popc(i)]+1;

}

string s;
bitset<maxn> bs;
int dp[maxn][maxn][2], k;

int dfs(int n, int cnt=0, bool la=0, bool lim=1)
{
    if(!lim&&~dp[n][cnt][la]) return dp[n][cnt][la];
    if(!n) return cnt==1&&la?0:cnt&&ks[cnt]==k-1;
    int ret=0, up=lim?bs[n]:1;
    for(int i=0;i<=up;i++)
        ret=(ret+dfs(n-1, cnt+i, i, lim&&i==up))%mod;
    if(!lim) dp[n][cnt][la]=ret;
    return ret;
}

int main()
{
    init();
    memset(dp, -1, sizeof dp);
    cin>>s>>k;
    if(k==0) return cout<<1, 0;
    for(int i=0;i<s.size();i++)
        bs[s.size()-i]=s[i]^48;
    cout<<dfs(s.size());
}

标签:cnt,return,la,int,题解,maxn,Numbers,Salesman,dp
From: https://www.cnblogs.com/redacted-area/p/18389465

相关文章

  • 题解:CF915G Coprime Arrays
    题意我们称一个大小为\(n\)的数组\(a\)互质,当且仅当\(\gcd(a_1,a_2,\cdots,a_n)=1\)。给定\(n,k\),对于每个\(i\)\((1\lei\lek)\),你都需要确定这样的数组的个数——长度为\(n\)的互质数组\(a\),满足对每个\(j\)\((1\lej\len)\),都有\(1\lea_j\lei\)。分析......
  • [COCI2012-2013#2] INFORMACIJE 题解
    前言题目链接:洛谷。题意简述你需要构造一个\(1\simn\)的排列\(a\),满足\(m\)个条件,格式如下:1xyv:\(\max\limits_{i=l}^ra_i=v\)。2xyv:\(\min\limits_{i=l}^ra_i=v\)。题目分析首先这个最值很难受,考虑能不能转化成我们喜欢的二元关系......
  • Luogu P10997 Partition 题解 [ 蓝 ] [ 轮廓 dp ]
    Partition:一道dp神题,用到了以轮廓线的轨迹来做dp的技巧,和敲砖块这题的状态设计有点相似。观察首先观察样例,发现整张图可以看作是被两条线分隔开的。同时每个颜色的四个方向上又存在一大堆奇怪的性质,很容易发现这两条线一条是从左上到右下的线,另一条是从右下到左上的线。暴......
  • CF603E 题解
    题意给定一个\(n\)个结点的无向图,初始没有边。接下来有\(m\)个询问,每次向图中加入一条连接\((u,v)\)权值为\(w\)的边。每次加边后,查询是否存在一个边集\(E\),满足当图中只有\(E\)中的边时,所有点的度数均为奇数。同时你还要最小化\(\max\limits_{(u,v,w)\inE}......
  • 【Mysql】mysql count主键字段很慢超时 执行计划Select tables optimized away ,最终调
     背景: mysql表 主键字段count,速度很慢,耗时将近30s   从执行计划可以看出:explainSELECTCOUNT(rule_id)ASdataCountFROM`sku_safe_stock_rule`;   原理分析:SelecttablesoptimizedawaySELECT操作已经优化到不能再优化了(MySQL根本没有遍历......
  • CF891E Lust 题解
    题目链接点击打开链接题目解法会不了\(egf\)/ll我们把贡献变成\(\prod\limits_{j\neqi}a_j=\prod\limits_{j=1}^na_j-\prod\limits_{j=1}^n(a_i-[i=j])\)即答案为一开始的乘积\(-\)\(k\)次操作之后所有数乘积的期望因为有顺序,所以用\(egf\)的形式表示最后乘积的期......
  • UVA12421 (Jiandan) Mua (I) - Lexical Analyzer题解
    没什么废话、超级珂爱的大模拟。本蒟蒻写了2h才过。其实就是按题意模拟即可,不需要什么高深的算法。本人就是错在了符号中的“=”,因为如果是连续的两个等于号,只能输出“==”,而不能输出“=”“==”,然后本人就卡在这个地方卡了1.5h。代码量也不大,主要是毒瘤细节模拟题。......
  • P6192 【模板】最小斯坦纳树 题解
    Description给定一个包含\(n\)个结点和\(m\)条带权边的无向连通图\(G=(V,E)\)。再给定包含\(k\)个结点的点集\(S\),选出\(G\)的子图\(G'=(V',E')\),使得:\(S\subseteqV'\);\(G'\)为连通图;\(E'\)中所有边的权值和最小。你只需要求出\(E'\)中所有边的权值......
  • BZOJ 4403序列统计题解
    缅怀zxc......
  • CSP-J 2021 初赛试题解析(第三部分:完善程序(2))
    完善程序二完整程序代码#include<iostream>usingnamespacestd;structpoint{intx,y,id;};boolequals(pointa,pointb){returna.x==b.x&&a.y==b.y;}boolcmp(pointa,pointb){returna.x!=b.x?a.x<b.x:a.y<b.y;}......