首页 > 其他分享 >dfs P1019 [NOIP2000 提高组] 单词接龙

dfs P1019 [NOIP2000 提高组] 单词接龙

时间:2024-09-04 21:26:06浏览次数:9  
标签:NOIP2000 int dfs 单词 start 接龙 ans

题目大意:

单词接龙,找出最长的长度的单词。

题解:

由于数据量较小,单词可多次使用,使用后可回溯,考虑dfs。

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;

int n, used[N], ans;
string a[N], start;

void dfs(string word){
    int ls = word.length();
    ans = max(ans, ls);
    for(int i = 1; i <= n; i ++){
        int rs = a[i].length();
        if(used[i] < 2){
            for(int j = 1; j < ls && j < rs; j ++){
                if(used[i] < 2 && word.substr(ls - j) == a[i].substr(0, j)){
                    used[i] ++;
                    dfs(word + a[i].substr(j));
                    used[i] --;
                }
            }
        }
    }
}

void solve(){
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    cin >> start;
    start = "*" + start;
    dfs(start);
    cout << ans - 1;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int _ = 1; //cin >> _;
    while(_--) solve();
    return 0;
}

 

标签:NOIP2000,int,dfs,单词,start,接龙,ans
From: https://www.cnblogs.com/Amire/p/18397361

相关文章

  • 微信群接龙怎么发起图片收集接龙?看完就会
    无论是群活动报名、收集信息还是学习打卡收集,微信群都发挥着重要作用。其中,图片收集接龙是一种高效的方式,能让我们快速收集图片。微信群接龙怎么发起图片收集接龙?下面就为您详细介绍如何使用龙艺秀接龙小程序在微信群发起图片收集接龙:群内人员点击就可以参与接龙打卡,团......
  • CF 2002 D1. DFS Checker (Easy Version) (*1900)思维
    CF2002D1.DFSChecker(EasyVersion)(*1900)思维题目链接题意:给你一棵\(n\)个节点组成的完全二叉树,并给出一个排列\(p\)。接下来进行\(q\)次询问。每次询问给你\(x\)和\(y\),你需要交换\(p_x\)和\(p_y\)。并且回答交换之后的排列\(p\)是否是这棵完全二叉树......
  • 分享丨【题单】链表、二叉树与一般树(前后指针/快慢指针/DFS/BFS/直径/LCA)
    作者:灵茶山艾府链接:https://leetcode.cn/circle/discuss/K0n2gO/一、链表注:由于周赛中的链表题可以转成数组处理,难度比直接处理链表低,故不标明难度分。带着问题去做下面的题目:在什么情况下,要用到哨兵节点(dummynode)?在什么情况下,循环条件要写while(node!=null)?什么情况......
  • Linux | Ubuntu 16.04.4 通过docker安装单机FastDFS
    Ubuntu16.04.4通过docker安装单机fastdfs前言很久没有写技术播客了,这是一件很不应该的事情,做完了事情应该有沉淀的。我先说一点前情提要,公司的fastdfs突然就挂了,做过的操作就是日志文件太大了,所以把日志文件给删了,理论上这个动作应该不影响程序运行才对。然后tracker怎么都......
  • Hadoop生态圈(三)- HDFS(分布式文件系统)
    目录设计目标特性HDFS基本原理NameNode概述DataNode概述HDSF读写操作HDFS写数据流程HDFS读数据流程HDFS元数据管理HDFSshellHDFS解决的是海量存储的问题设计目标:故障是常态,因此故障的检测和自动快速恢复是核心适合批量处理,注重数据访问的高吞吐量。一旦写入......
  • c++算法3-广度优先搜索算法dfs
    搜索算法众所周知,搜索算法分为常见的两种深度优先搜索算法(dfs)广度优先搜索算法(bfs)深度优先搜索算法深度优先搜索算法就是一条道走到黑,如迷宫问题,重复不断地向前探索如果碰到死胡同就说明前面已经没有路了,这时候就可以想其他方向搜索,最终走到终点。回溯回溯是一种搜索算法......
  • 图论:图的遍历(DFS vs. BFS)
    文章目录引言基本概念无向图示例绘制图形深度优先搜索(DFS)基本概念可视化DFS过程深度优先搜索(DFS)DFS应用场景广度优先搜索(BFS)基本概念可视化BFS过程广度优先搜索(BFS)应用场景DFSvs.BFS基本概念对比性能对比场景分析**总结对比**社交网络图遍历使用DFS使用BFS......
  • LeetCode 690. 员工的重要性(哈希表、深度优先搜索dfs)
    题目:690.员工的重要性思路:先用哈希表map将每个员工的信息映射到员工ID对应的下标位置。接着使用深度优先搜索dfs,来记录总和即可。细节看注释/*//DefinitionforEmployee.classEmployee{public:intid;intimportance;vector<int>subordinates;......
  • [RT-Thread记录]DFS虚拟文件系统文件夹操作异常
    项目场景:系统:RT-Thread5.0.2硬件:STM32H743问题描述1.文件系统打开文件夹再关闭后,申请的内存没有释放2.elm-fatFs文件系统重复操作同一个文件夹,如复制,会引起系统崩溃原因分析:        DFS虚拟文件系统文件打开关闭逻辑错误,文件系统版本升级更新后,dfs_file结......
  • 牛客小白月赛99 C-迷宫(DFS)
    题目描述给定一个n×m\mathrm{n\timesm}n×m的迷宫,迷宫由"#"与"."两种字符组成。其中"#"代表障碍物,"."表示空地。迷宫中还有一个起点"S"和一个终点"E",它们都可以视为空地。 由于近期迷宫发生了塌方,导致起点和终点之间可能并不连通。幸运的是,你拥有一种超能......