常州做网站公司排名,做旅游销售网站平台ppt,网站建设更新,南昌诚推网络技术有限公司题意#xff1a;给一个元素周期表的元素符号#xff08;114种#xff09;#xff0c;再给一个串#xff0c;问这个串能否有这些元素符号组成#xff08;全为小写#xff09;。 解法1#xff1a;动态规划 定义#xff1a;dp[i]表示到 i 这个字符为止#xff0c;能否有… 题意给一个元素周期表的元素符号114种再给一个串问这个串能否有这些元素符号组成全为小写。 解法1动态规划 定义dp[i]表示到 i 这个字符为止能否有元素周期表里的符号构成。 则有转移方程dp[i] (dp[i-1]f(i-1,1)) || (dp[i-2]f(i-2,2)) f(i,k):表示从i开始填入k个字符这k个字符在不在元素周期表中。 dp[0] 1 代码 //109ms 0KB
#include iostream
#include cstdio
#include cstring
#include cmath
#include algorithm
#include string
using namespace std;
#define N 50007string single[25] {h,b,c,n,o,f,k,p,s,y,i,w,u,v};
string ss[130] {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 vis[30][30],tag[30];
int dp[N];
char st[N];void init()
{memset(vis,0,sizeof(vis));memset(tag,0,sizeof(tag));for(int i0;i14;i)tag[single[i][0]-a] 1;for(int i0;i100;i)vis[ss[i][0]-a][ss[i][1]-a] 1;
}int main()
{int t,len,i;init();scanf(%d,t);while(t--){scanf(%s,st1);len strlen(st1);memset(dp,0,sizeof(dp));dp[0] 1;for(i0;ilen;i){if(dp[i]){if(tag[st[i1]-a])dp[i1] 1;dp[i2] | vis[st[i1]-a][st[i2]-a];}}if(dp[len])puts(YES);elseputs(NO);}return 0;
} View Code 解法2DFS 搜索时循环的是元素周期表的符号个数。详见代码 代码 306ms #include iostream
#include cstdio
#include cstring
#include cmath
#include algorithm
#include string
using namespace std;
#define N 50007string ss[130] {h,b,c,n,o,f,k,p,s,y,i,w,u,v,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 vis[N];
int len[140];
char st[N];
int Length;
bool Tag;void init()
{int i;for(i0;i14;i)len[i] 1;for(i14;i114;i)len[i] 2;
}void dfs(int u)
{if(u Length)Tag 1;if(Tag)return;for(int i0;i114;i){int flag 1;if(ulen[i] Length !vis[ulen[i]]){for(int j0;jlen[i];j){if(ss[i][j] ! st[uj]){flag 0;break;}}if(flag){vis[ulen[i]] 1;dfs(ulen[i]);}}}
}int main()
{init();int t,i;scanf(%d,t);while(t--){scanf(%s,st);Length strlen(st);memset(vis,0,sizeof(vis));Tag 0;dfs(0);if(Tag)puts(YES);elseputs(NO);}return 0;
} View Code 解法3乱搞模拟。 分成 单个元素存在与否与前面匹不匹配与后面匹不匹配总共2^3 8种情况然后O(n)扫过去代码很长。。。 代码586ms #include iostream
#include cstdio
#include cstring
#include cmath
#include algorithm
#include string
using namespace std;
#define N 50007string single[25] {h,b,c,n,o,f,k,p,s,y,i,w,u,v};
string ss[130] {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};char st[N];
int vis[N];int main()
{int t,len,i,j,k;scanf(%d,t);while(t--){scanf(%s,st);len strlen(st);int flag 1;memset(vis,0,sizeof(vis));for(i0;ilen;i){if(vis[i])continue;string S ;S st[i];for(j0;j14;j){if(single[j] S)break;}if(j 14) //not single{if(i 0 !vis[i-1]){S st[i-1]S;for(j0;j100;j){if(ss[j] S)break;}if(j ! 100) //pre match{if(i len-1){string ks ;ks st[i];ks st[i1];for(k0;k100;k){if(ss[k] ks)break;}if(k ! 100) //back matchvis[i] 0;else //back not matchvis[i] 1;}}else //pre not match{if(i len-1){string ks ;ks st[i];ks st[i1];for(k0;k100;k){if(ss[k] ks)break;}if(k ! 100) //back matchvis[i1] 1;else //back not match{flag 0;break;}}else{flag 0;break;}}}else{if(i len-1){string ks ;ks st[i];ks st[i1];for(k0;k100;k){if(ss[k] ks)break;}if(k ! 100) //back matchvis[i1] 1;else //back not match{flag 0;break;}}else{flag 0;break;}}}else //single{if(i 0 !vis[i-1]){S st[i-1]S;for(j0;j100;j){if(ss[j] S)break;}if(j ! 100) //pre match{if(i len-1){string ks ;ks st[i];ks st[i1];for(k0;k100;k){if(ss[k] ks)break;}if(k ! 100) //back matchvis[i] 0;else //back not matchvis[i] 1;}}else //pre not match{if(i len-1){string ks ;ks st[i];ks st[i1];for(k0;k100;k){if(ss[k] ks)break;}if(k ! 100) //back matchvis[i] 0;else //back not matchvis[i] 1;}elsevis[i] 1;}}else{if(i len-1){string ks ;ks st[i];ks st[i1];for(k0;k100;k){if(ss[k] ks)break;}if(k ! 100) //back matchvis[i] 0;else //back not matchvis[i] 1;}elsevis[i] 1;}}}if(flag)puts(YES);elseputs(NO);}return 0;
} View Code 转载于:https://www.cnblogs.com/whatbeg/p/3876636.html
