D - String Equivalence（dfs+限制条件）

╰+哭是因爲堅強的太久メ 2023-07-18 06:54 16阅读 0赞

[D - String Equivalence][]

题意：  
定义s和t是一组长度为n的异形同构体(构成相同，字母不同)，比如abcac和zyxzx就是一组异形同构体：abcac中1 4都是a，3 5都是c；zyxzx中1 4都是z，3 5都是x。并且abcac是这种异形同构体类型的字典序最小表示。

问我们长度为n的所有异形同构体有哪些。

题解：  
dfs+限制条件  
不论长度为多少，他的开头肯定都是a，因为a是字典序最小的一个。  
往后的字母最大不能比前面的所有字母大2，我们要保证字典序最小，即对于第k个字母，最多比前k-1个字母的最大值大1。  
比如：n=3 ——> aaa aab aba abb abc

所以我们dfs的时候枚举到循环的最后一个数我们循环结束点+1就好了。这样保证了最后一个数只可能比前面的最大值大1。

code：

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<map>
    #include<queue>
    #include<vector>
    #include<set>
    #include<sstream>
    using namespace std;
    typedef long long ll;
    const ll maxn=1e6+10;
    const ll inf=0x3f3f3f3f3f3f3f3f;
    void io(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
    char s[maxn];
    ll n,ans=0;
    void dfs(ll num)
    { 
    	if(num==n)
    	{ 
    		for(int i=0;i<n;i++)	
    			cout<<s[i];
    		cout<<endl;
    		return ;
    	}
    	for(int i=0;i<=ans;i++)
    	{ 
    		s[num]='a'+i;
    		ll tmp=ans;
    		if(i==ans) ans++;
    		dfs(num+1);
    		ans=tmp;
    	} 
    } 
    int main()
    { 
    	io();
    	cin>>n;
    	dfs(0);
    	return 0;
    }

[D - String Equivalence]: https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_d

发表评论取消回复

表情：

评论列表（有 0 条评论，16人围观）

还没有评论，来说两句吧...

相关阅读

相关 String长度是否有限制？如果有,限制是多少？

一、前言话说Java中String是有长度限制的，听到这里很多人不禁要问，String还有长度限制？是的有，而且在JVM编译中还有规范，而且有的家人们在面试的时候也遇到

小灰灰/ 2024年04月01日 17:36/ 0 赞/ 99 阅读

相关 D - String Equivalence（dfs+限制条件）

[D - String Equivalence][] 题意：定义s和t是一组长度为n的异形同构体(构成相同，字母不同)，比如abcac和zyxzx就是一组异形同构体：a

╰+哭是因爲堅強的太久メ/ 2023年07月18日 06:54/ 0 赞/ 17 阅读

相关 D. AB-string——CF1238D

https://codeforces.com/problemset/problem/1238/D 思路： 1、每个字符存在回文串的最地条件是： AA ， BB， ABA

小灰灰/ 2023年06月06日 10:35/ 0 赞/ 42 阅读

相关 String长度有限制吗？

结论(针对JDK1.8) > 首先字符串的内容是由一个字符数组 `char[]` 来存储的，由于数组的长度及索引是整数，且String类中返回字符串长度的方法length

太过爱你忘了你带给我的痛/ 2022年11月07日 11:37/ 0 赞/ 38 阅读

相关 [Java] String 长度限制

一、Java String 变量长度限制根据 String 源码: ![这里写图片描述][SouthEast] 因此，理论上 String 变量长度限制为 int

本是古典何须时尚/ 2022年09月28日 11:42/ 0 赞/ 296 阅读

相关 element-ui选择时间范围限制条件

1. 组件属性 <el-date-picker v-model.trim="ruleForm.messTime" type="daterange" range-s

清疚/ 2022年08月31日 06:47/ 0 赞/ 333 阅读

相关 Query By Criteria的限制条件写法

[NHibernate（1） HQL 条件查询(QBC) - 条件限制][NHibernate_1_ HQL _QBC_ -] QBC (Query By Cr

深碍√TFBOYSˉ_/ 2022年08月02日 14:48/ 0 赞/ 170 阅读

相关 Oracle第二章：排序和条件限制

第二章：排序和条件限制 select \[distinct\] \{column\_name..|\|exp|alias\_name from table\_name

墨蓝/ 2022年05月14日 07:25/ 0 赞/ 179 阅读

相关 YApi限制mock的查询条件

YApi 怎么限制查询条件首先点击编辑在请求参数中设置好请求参数的名称和必须\] 添加期望值里选中要限制的参数和值 ![添加期望值里选中要限制的参数和值][

心已赠人/ 2022年04月08日 11:51/ 0 赞/ 218 阅读

相关 python3 -sqlite3限制条件查询

请注意10,11,24行的代码，是本条博客的精华，逻辑并不难，就是有些小语法问题比较纠结，记录一下。 import json import sqlite3

ゞ浴缸里的玫瑰/ 2021年12月18日 22:02/ 0 赞/ 268 阅读