【Codeforces】 CF79D Password

这篇具有很好参考价值的文章主要介绍了【Codeforces】 CF79D Password。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目链接

CF方向
Luogu方向

题目解法

看到区间异或,一个经典的套路是做差分,我们即在 l l l 处异或一次,在 r + 1 r+1 r+1 处异或一次,然后前缀和起来
于是我们可以将问题转化成:有一个序列初始全 0 0 0,每次可以把相隔 a i a_i ai 的数都 ⊕ 1 \oplus 1 1,求最少将其变成一个状态的步数
考虑 k k k 的范围很小,所以为 1 1 1 的地方一共只有 2 k 2k 2k
这里有一个非常重要的 t r i c k trick trick:在异或操作中,如果需要把 x , y x,y x,y 同时异或 1 1 1,其他不变,每次可以同时修改相隔 a i a_i ai 的位置的异或值,那么这个问题等价于建出图来从 x x x y y y 的最短路
然后发现直接状压跑最短路即可,时间复杂度 O ( 2 k k 2 ) O(2^kk^2) O(2kk2)
不难优化成 O ( 2 k k ) O(2^kk) O(2kk),但我直接 998 m s 998ms 998ms O ( 2 k k 2 ) O(2^kk^2) O(2kk2) 的做法艹过去了,就懒得改了
O ( 2 k k 2 ) O(2^kk^2) O(2kk2) 的代码:文章来源地址https://www.toymoban.com/news/detail-718372.html

#include <bits/stdc++.h>
using namespace std;
const int N=10100,M=2000100;
int n,m,k,a[110],x[30],dis[N];
int f[(1<<20)+100],D[30][30];
int e[M],ne[M],h[N],idx;
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
queue<int> que;
void bfs(int S){
    memset(dis,0x3f,sizeof(dis));
    que.push(S),dis[S]=0;
    while(!que.empty()){
        int u=que.front();que.pop();
        for(int i=h[u];~i;i=ne[i]) if(dis[u]+1<dis[e[i]])
            dis[e[i]]=dis[u]+1,que.push(e[i]);
    }
}
void add(int x,int y){ e[idx]=y,ne[idx]=h[x],h[x]=idx++;}
int main(){
    n=read(),k=read(),m=read();
    for(int i=0;i<k;i++) x[i]=read();
    for(int i=1;i<=m;i++) a[i]=read();
    for(int i=0;i<k;i++) x[i+k]=x[i]+1;
    memset(h,-1,sizeof(h));
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n-a[i]+1;j++)
            add(j,j+a[i]),add(j+a[i],j);
    for(int i=0;i<k<<1;i++){
        bfs(x[i]);
        for(int j=0;j<k<<1;j++) D[i][j]=dis[x[j]];
    }
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int S=0;S<1<<(k<<1);S++)
        for(int i=0;i<k<<1;i++) if(S>>i&1)
            for(int j=0;j<k<<1;j++) if(S>>j&1) if(i!=j)
                f[S]=min(f[S],f[S^(1<<i)^(1<<j)]+D[i][j]);
    printf("%d\n",f[(1<<(k<<1))-1]>1e9?-1:f[(1<<(k<<1))-1]);
    fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
    return 0;
}

到了这里,关于【Codeforces】 CF79D Password的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 文心一言 VS 讯飞星火 VS chatgpt (79)-- 算法导论7.4 4题

    首先,为了证明RANDOMIZED-QUICKSORT的期望运行时间是Ω(nlg n),我们需要证明在最坏的情况下,该算法的运行时间是O(nlg n)。然后,我们需要证明在最坏的情况下,算法的期望运行时间是Ω(nlg n)。 RANDOMIZED-QUICKSORT算法是基于快速排序的一种随机化版本,其中在每次递归分割时,随机

    2024年02月12日
    浏览(56)
  • PBKDF2(Password-Based Key Derivation Function 2)算法

    一、引言 在当今数字时代,保护用户数据和隐私的安全变得越来越重要。为实现这一目标,加密和密钥管理技术发挥着关键作用。PBKDF2(Password-Based Key Derivation Function 2)算法作为一种基于密码的密钥生成方法,广泛应用于各种安全场景。本文将从各个方面介绍和解释PBKDF2算

    2024年02月04日
    浏览(32)
  • x79主板配什么cpu好 x79主板组装电脑教程

    英特尔x79主板可以说是很早之前就出来的一款产品了,目前很多已经停产。有些网友在组装电脑的时候,用到了英特尔x79主板,不知道英特尔x79主板配什么cpu合适。下面小编就给大家介绍下英特尔x79主板支持什么cpu x79主板配什么cpu?x79是很多朋友们喜欢的主板型号,那么这款

    2024年02月08日
    浏览(43)
  • 79. Word Search

    79. Word Search how to store the location that previously visited

    2024年02月04日
    浏览(38)
  • 【LeetCode】79.单词搜索

    给定一个  m x n  二维字符网格  board  和一个字符串单词  word  。如果  word  存在于网格中,返回  true  ;否则,返回  false  。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不

    2024年02月15日
    浏览(42)
  • 79. 单词搜索

    题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台  解题思路:递归+回溯 首先遍历每一个board中的字符,如果该字符和word的第一个字符相等,就从这个位置进行匹配搜索,如果能够找到word,就返回true,board中可能存在多个字符合word中的第一个字符相等的情况,

    2024年02月13日
    浏览(32)
  • 力扣79. 单词搜索

    思路: 定义函数 check(i,j,k) 为网格 (i,j) 位置出发能够搜索到单词 word(k),如果搜索到返回 true,否则返回 false; 搜索规则: 【R1】如果 board[i][j] != word[k],直接返回 false; 【R2】如果当前已经访问到字符串的末尾,且对应字符依然匹配,此时直接返回 true; 【R3】否则,遍历

    2024年01月18日
    浏览(39)
  • 79.SpringBoot的核心注解

    @SpringBootApplication注解:这个注解标识了一个SpringBoot工程,它实际上是另外三个注解的组合,这三个注解是: @SpringBootConfiguration:这个注解实际就是一个@Configuration,表示启动类也是一个配置类 @EnableAutoConfiguration:向Spring容器中导入了一个Selector,用来加载ClassPath下SpringFact

    2024年02月22日
    浏览(37)
  • 【LeetCode-中等题】79. 单词搜索

    需要一个标记数组 来标志格子字符是否被使用过了 先找到word 的第一个字符在表格中的位置,再开始递归 递归的结束条件是如果word递归到了最后一个字符了,说明能在矩阵中找到单词 剪枝条件 就是如果已经找到单词了 res = true 了 后面就不需要递归了,还有如果下标越界、

    2024年02月09日
    浏览(38)
  • 力扣每日一题79:单词搜索

    给定一个  m x n  二维字符网格  board  和一个字符串单词  word  。如果  word  存在于网格中,返回  true  ;否则,返回  false  。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不

    2024年02月07日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包