游游定义一个字符串是“好串”，当且仅当该字符串相邻的字符不相等。例如"arcaea"是好串，而"food"不是好串。
游游拿到了一个字符串，她可以将该字符串的各个字符顺序随意打乱。她想知道一共可以生产多少种不同的好串？
[编程题]游游的字符重排
虽然这题暴力即可，但这题一看就有组合DP做法，而且系数固定，显然可以用多项式科技优化，遂让AI写了一下此做法。这是一个基于容斥原理结合生成函数的组合计数问题，使用NTT进行优化。算法思路容斥原理转化：我们要计算没有相邻字符相等的排列数。直接计算比较困难，我们使用容斥原理。对于每种字符 ，假设它的出
展开全文
思路字符串长度很短，可以用dfs，先将每个字符的数量存起来，然后枚举新串每个字符。记得回溯。ACnode
#include<bits/stdc++.h>
using namespace std;
map<char,int>cnt;
int len;//字符串长度
int an
展开全文
//最后一舞
#include<bits/stdc++.h>
using namespace std;
#define out(x) cout << #x << '=' << (x) << endl
#define out2(x, y) c
展开全文
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define all(a) a.begin(), a.end()
void solve() {
string s;cin >
展开全文
因为很小，直接dfs枚举就可以，主要是看如何去重这里是一种去重思路，将原来字符串排序然后直接看上一个是否使用过，如果没有使用过那说明这两个（多个）都不能用，所以不考虑放入
#include <iostream>
#include <vector>
#include <c
展开全文
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using ld = long double;
using PII=pair<ll,ll>;
using PIII=pair<
展开全文
数据范围很小，极端情况下全是不同的字母，那么有种情况，直接dfs搜索所有可能即可。
import sys
from collections import Counter
# 输入加速
input = sys.stdin.readline
if __name__ == '__main__':
展开全文
注意到，长度不大于十所以能够直接全排列草过去
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll
展开全文
算法思路
本题要求统计给定字符串（长度 ≤ 10）的所有不同排列中，满足“相邻字符不相等”（即好串）的排列个数。由于长度很小，可以直接枚举所有可能的排列，但需注意重复字符会导致重复排列，因此采用回溯法 + 剪枝：
先统计每个字符出现的频率，然后通过深度优先搜索（DFS）构造字符串。
构造过程中，每
展开全文
问题信息
难度：
2条回答
14收藏
24浏览
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
