题目链接
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4268
题意 给出化学元素周期表，然后给出一个字符串，判断字符串里面的字符，能不能够完全由元素周期表里面的元素构成
或者换一种说法，将字符串切割成若干个子串，能不能有一种切割的方式，使得切割下来的每一个子串都是元素周期表里面的元素
思路 其实可以发现 元素周期表里面的元素 不是一个字母的，就是两个字母的
其实 不管是搜索还是DP 思路都是差不多的
搜索： void dfs(int index)
表示 从 0 - index - 1 这个字段 是可以满足要求的
那么我们去判断 s[index] 是不是元素周期表的元素 如果是 那么0 - index 也是满足要求的 那么我们继续dfs(index + 1)
如果 s[index] + s[index + 1] 是元素周期表的元素 就dfs(index + 2)
Tips: 很重要的一点 ，一定要记得访问标记啊，不然会T到不知道什么样子。。。 如果这个当前下标的状态是访问过的，就不用再继续搜下去了
DP:
dp[i] 表示 从 0 - 第i 个字符构成的子段是否是满足要求的
那么有两种情况可以转移过来
如果 dp[i - 1] 是满足要求 并且 s[i] 是元素周期表里面的元素 那么 dp[i] 也是满足要求的
如果 dp[i - 2] 满足要求 并且 s[i - 1] 和 s[i] 构成的子段 是元素周期表里面的元素 那么 dp[i] 也是满足要求的
上面两个条件满足其中一个就可以了
AC代码
DP
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back #define bug puts("***bug***"); #define fi first #define se second #define stack_expand #pragma comment(linker, "/STACK:102400000,102400000") //#define bug //#define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <string, int> psi; typedef pair <string, string> pss; typedef pair <double, int> pdi; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int maxn = 5e4 + 10; const int MOD = 1e9 + 7; char single[25][2] = { "h","b","c","n","o","f","k","p","s","y","i","w","u","v" }; char ss[130][3] = { "he","li","be","ne","na","mg", "al","si","cl","ar","ca","sc","ti","cr","mn", "fe","co","ni","cu","zn","ga","ge","as","se", "br","kr","rb","sr","zr","nb","mo","tc","ru", "rh","pd","ag","cd","in","sn","sb","te","xe", "cs","ba","hf","ta","re","os","ir","pt","au", "hg","tl","pb","bi","po","at","rn","fr","ra", "rf","db","sg","bh","hs","mt","ds","rg","cn", "fl","lv","la","ce","pr","nd","pm","sm","eu", "gd","tb","dy","ho","er","tm","yb","lu","ac", "th","pa","np","pu","am","cm","bk","cf","es", "fm","md","no","lr" }; int len; char s[maxn]; int dp[maxn]; bool judge_single(int index) { for (int i = 0; i < 14; i++) { if (single[i][0] == s[index]) return true; } return false; } bool judge_tw(int index) { for (int i = 0; i < 100; i++) { if (ss[i][0] == s[index] && ss[i][1] == s[index + 1]) return true; } return false; } int main() { int t; cin >> t; while (t--) { scanf("%s", s); len = strlen(s); for (int i = 0; i < len; i++) dp[i] = 0; if (judge_single(0)) dp[0] = 1; if ((judge_single(1) && dp[0]) || judge_tw(0)) dp[1] = 1; for (int i = 2; i < len; i++) dp[i] = ((judge_single(i) && dp[i - 1]) || (judge_tw(i - 1) && dp[i - 2])); puts(dp[len - 1] ? "YES" : "NO"); } }DFS
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back #define bug puts("***bug***"); #define fi first #define se second #define stack_expand #pragma comment(linker, "/STACK:102400000,102400000") //#define bug //#define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <string, int> psi; typedef pair <string, string> pss; typedef pair <double, int> pdi; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int maxn = 5e4 + 10; const int MOD = 1e9 + 7; char single[20] = //14 { 'h', 'b', 'c', 'n', 'o', 'p', 's', 'v', 'k', 'y', 'i', 'u', 'f', 'w', }; char ss[105][3] { "he", "li", "be", "ne", "na", "mg", "al", "si", "cl", "ar", "ca", "sc", "ti", "cr", "mn", "fe", "co", "ni", "cu", "zn", "ga", "ge", "as", "se", "br", "kr", "rb", "sr", "zr", "nb", "mo", "tc", "ru", "rh", "pd", "ag", "cd", "in", "sn", "sb", "te", "xe", "cs", "ba", "hf", "ta", "re", "os", "ir", "pt", "au", "hg", "tl", "pb", "bi", "po", "at", "rn", "fr", "ra", "rf", "db", "sg", "bh", "hs", "mt", "ds", "rg", "cn", "fl", "lv", "la", "ce", "pr", "nd", "pm", "sm", "eu", "gd", "tb", "dy", "ho", "er", "tm", "yb", "lu", "ac", "th", "pa", "np", "pu", "am", "cm", "bk", "cf", "es", "fm", "md", "no", "lr", }; int len; char s[maxn]; bool judge_single(int index) { for (int i = 0; i < 14; i++) { if (single[i] == s[index]) return true; } return false; } bool judge_tw(int index) { for (int i = 0; i < 100; i++) { if (ss[i][0] == s[index] && ss[i][1] == s[index + 1]) return true; } return false; } int tag; int used[maxn]; void dfs(int index) { used[index] = 1; if (index == len) { tag = 1; return; } if (judge_single(index) && !used[index + 1]) dfs(index + 1); if (index + 1 < len && judge_tw(index) && !used[index + 2]) dfs(index + 2); } int main() { int t; cin >> t; while (t--) { scanf("%s", s); len = strlen(s); for (int i = 0; i <= len; i++) used[i] = 0; tag = 0; dfs(0); puts(tag ? "YES" : "NO"); } }BFS
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back #define bug puts("***bug***"); #define fi first #define se second #define stack_expand #pragma comment(linker, "/STACK:102400000,102400000") //#define bug //#define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <string, int> psi; typedef pair <string, string> pss; typedef pair <double, int> pdi; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int maxn = 5e4 + 10; const int MOD = 1e9 + 7; char single[20] = //14 { 'h', 'b', 'c', 'n', 'o', 'p', 's', 'v', 'k', 'y', 'i', 'u', 'f', 'w', }; char ss[105][3] { "he", "li", "be", "ne", "na", "mg", "al", "si", "cl", "ar", "ca", "sc", "ti", "cr", "mn", "fe", "co", "ni", "cu", "zn", "ga", "ge", "as", "se", "br", "kr", "rb", "sr", "zr", "nb", "mo", "tc", "ru", "rh", "pd", "ag", "cd", "in", "sn", "sb", "te", "xe", "cs", "ba", "hf", "ta", "re", "os", "ir", "pt", "au", "hg", "tl", "pb", "bi", "po", "at", "rn", "fr", "ra", "rf", "db", "sg", "bh", "hs", "mt", "ds", "rg", "cn", "fl", "lv", "la", "ce", "pr", "nd", "pm", "sm", "eu", "gd", "tb", "dy", "ho", "er", "tm", "yb", "lu", "ac", "th", "pa", "np", "pu", "am", "cm", "bk", "cf", "es", "fm", "md", "no", "lr", }; int len; char s[maxn]; int used[maxn]; bool judge_single(int index) { for (int i = 0; i < 14; i++) { if (single[i] == s[index]) return true; } return false; } bool judge_tw(int index) { for (int i = 0; i < 100; i++) { if (ss[i][0] == s[index] && ss[i][1] == s[index + 1]) return true; } return false; } bool bfs() { queue <int> q; if (judge_single(0)) q.push(1), used[1] = 1; if (1 < len && judge_tw(0)) q.push(2), used[2] = 1; while (!q.empty()) { int u = q.front(); q.pop(); if (u == len) return true; if (judge_single(u) && !used[u + 1]) q.push(u + 1), used[u + 1] = 1; if (u + 1 < len && judge_tw(u) && !used[u + 2]) q.push(u + 2), used[u + 2] = 1; } return false; } int tag; int main() { int t; cin >> t; while (t--) { scanf("%s", s); len = strlen(s); for (int i = 0; i <= len; i++) used[i] = 0; puts(bfs() ? "YES" : "NO"); } }转载于:https://www.cnblogs.com/Dup4/p/9433082.html
相关资源：VR_Chemist：VR Chemist是使用虚幻引擎构建的虚拟现实化学教育应用程序-源码