首页 / 算法 / NIT算法导论 字母序列
NIT算法导论 字母序列
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了NIT算法导论 字母序列，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2226字，纯文字阅读大概需要4分钟。
内容图文
NIT算法导论 字母序列
Description
考虑由两个字母A和B构成的词所组成的这样一个序列：序列中的第一个词是“A”，第k个词是由第k-1个词经过下面的变换得到：每个A替换为AAB，以及每个B替换为A。容易看出每个词是它的下一个词的起始部分，这些词的起始部分相当于给出了一个字母序列AABAABAAABAABAAB……。问你第n个字母A在哪一个位置出现？
Input
一个正整数N,(1<=N<=1000000)
Output
位置序号。
Sample Input
? 1000
Sample Output
? 1414
解题思路：
一开始读完题没处下手，看看数据范围蛮小的就打了个暴力，后来发现这玩意是个贝蒂定理，假设\(A\)第\(i\)次出现的位置是\(A_i\),\(B\)第\(i\)次出现的位置是\(B_i\)，打个表发现\(B_i-A_i=2i\),那么由令\(b=a+2\),代入贝蒂定理\(\frac{1}{a}+\frac{1}{b}=1\)得\(a=\sqrt 2,b=\sqrt 2+2\)那么\(a_i=\lfloor \sqrt2 i\rfloor\)，其实\(b_i\)也知道了是\(b_i=\lfloor(\sqrt2 +2)i \rfloor\) 话说这题目描述的样例就是来坑人的
代码：
答案就是\(\lfloor \sqrt2 i\rfloor\)没啥意思 贴个之前模拟的解法吧
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
// freopen("k.in", "r", stdin);
// freopen("k.out", "w", stdout);
// clock_t c1 = clock();
// std::cerr << "Time:" << clock() - c1 <<"ms" << std::endl;
//#pragma comment(linker, "/STACK:1024000000,1024000000")
mt19937 rnd(time(NULL));
#define de(a) cout << #a << " = " << a << endl
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define ls ((x) << 1)
#define rs ((x) << 1 | 1)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<char, char> PCC;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
#define inf 0x3f3f3f3f
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 1e6 + 7;
const int MAXM = 4e5 + 7;
const ll MOD = 1e9 + 7;
const double eps = 1e-7;
const double pi = acos(-1.0);
int main()
{
int n;
while (~scanf("%d", &n))
{
int ans;
string a = "A";
for (int i = 1; i <= n; i++)
{
string temp = "";
int cnt = 0;
for (int j = 0; j < a.size(); j++)
{
if (a[j] == 'A')
{
temp += "AAB";
cnt++;
}
else
temp += "A";
if (cnt == n)
{
ans = j + 1;
goto where;
}
}
a = temp;
}
where:
printf("%d\n", ans);
}
return 0;
}
内容总结
以上是互联网集市为您收集整理的NIT算法导论 字母序列全部内容，希望文章能够帮你解决NIT算法导论 字母序列所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。