題目背景

Aldnoah

——火星上超古代文明留下的能量源，承認(rèn)初代火星移民雷伊·雷加利亞博士（即后來(lái)的薇瑟帝國(guó)初代皇帝）為正統(tǒng)繼承者，啟動(dòng)因子融入皇族的遺傳因子中，只有皇族天生具有Aldnoah的啟動(dòng)能力。可以把Aldnoah看成是有認(rèn)主能力的特殊礦產(chǎn)。在火星騎士的揚(yáng)陸城中，安置有Aldnoah的啟動(dòng)裝置。

題目描述

兩天前，被授予啟動(dòng)能力的斯雷因·特洛耶特伯爵準(zhǔn)備對(duì)啟動(dòng)裝置進(jìn)行加密，以防有人趁其不備破壞裝置。

他將這個(gè)任務(wù)交給了他的心腹哈庫(kù)萊特。忠實(shí)的哈庫(kù)萊特認(rèn)為，只需要輸入密碼就能解鎖的加密裝置實(shí)在是太不安全了，所以他決定用一個(gè)特別的加密裝置來(lái)對(duì)Aldnoah啟動(dòng)裝置進(jìn)行保護(hù)。

他精心設(shè)計(jì)了這樣一套加密裝置：

該裝置會(huì)給定解密者兩個(gè)字符串s,t，其中s只包含小寫(xiě)字母以及*，t只包含小寫(xiě)字母。解密者可以進(jìn)行任意多次操作，每次選擇s中的一個(gè)*，將它修改為任意多個(gè)（可以是0個(gè)）它的前一個(gè)字符。詢(xún)問(wèn)是否能將s修改為t。

聰明的哈庫(kù)萊特當(dāng)然不會(huì)只給予解密者一組數(shù)據(jù)啦，所以解密時(shí)會(huì)有多組數(shù)據(jù)出現(xiàn)，并且每組數(shù)據(jù)只有在規(guī)定時(shí)間內(nèi)答對(duì)才能夠繼續(xù)解密下一組數(shù)據(jù)。

今天他制作好了加密裝置交給了斯雷因·特洛耶特伯爵，斯雷因準(zhǔn)備先進(jìn)行測(cè)試過(guò)后再將它安裝在啟動(dòng)裝置上。他隨機(jī)制造了幾組測(cè)試數(shù)據(jù)輸入裝置，然后讓哈庫(kù)萊特進(jìn)行解密。哈庫(kù)萊特會(huì)怎么做呢？

輸入輸出格式

輸入格式：

?

第一行一個(gè)整數(shù)T表示數(shù)據(jù)組數(shù)。

每組數(shù)據(jù)兩行，第一行一個(gè)字符串s，第二行一個(gè)字符串t。

?

輸出格式：

?

每組數(shù)據(jù)輸出一行，如果能將s修改為t，輸出Yes，否則輸出No。

?

輸入輸出樣例

輸入樣例#1：
2 a* aaaa a* ab 輸出樣例#1：
Yes No

說(shuō)明

對(duì)于20%的數(shù)據(jù)，|s|,|t|<=7。

對(duì)于60%的數(shù)據(jù)，|s|,|t|<=300。

對(duì)于100%的數(shù)據(jù)，T<=100，|s|,|t|<=30000。

分析：這道題能拿多少分在于你枚舉什么.如果你枚舉每個(gè)*賦值多少個(gè)字母，那么就有20分，如果你枚舉兩個(gè)串，那么就有60分，如果你枚舉一個(gè)串，看看另外一個(gè)串是否符合要求就是滿(mǎn)分.

? ? ? 因?yàn)槊總€(gè)*只對(duì)同一字母有影響，所以把每一段字母相同的連同*分成一段，如果第二個(gè)字符串第i段有x個(gè)字母，那么第一個(gè)字符串中第i段也應(yīng)該有x個(gè)字母，如果里面有*號(hào)那么可以少于x個(gè)字母，否則就必須等于x個(gè)字母，否則匹配不成功，掃一遍就可以了.

? ? ? 多組數(shù)據(jù)一定要初始化！本來(lái)A掉的結(jié)果忘了初始化爆0了QAQ.

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm>using namespace std;int T; char s1[30010], s2[30010]; int len1, len2, cur, num; bool flag = false;bool pipei(int x, char biaozhun) {int res = 0;bool can = false;while (s1[cur] != biaozhun && cur <= len1){if (cur > len1)return false;if (s1[cur] == '*')can = 1;elseres++;cur++;}if (res < x && can)return true;if (res < x && !can)return false;if (res == x)return true;if (res > x)return false; }int main() {scanf("%d", &T);while (T--){num = 0;flag = 0;memset(s1, 0, sizeof(s1));memset(s2, 0, sizeof(s2));scanf("%s", s1 + 1);scanf("%s", s2 + 1);len1 = strlen(s1 + 1);cur = 1;len2 = strlen(s2 + 1);while (s1[cur] == '*' && cur <= len1)cur++;if (cur > len1){printf("No\n");continue;}if (s1[cur] != s2[1]){printf("No\n");continue;}for (int i = 1; i <= len2; i++){num++;if (s2[i] != s2[i + 1]){if (!pipei(num, s2[i + 1])){flag = 1;break;}num = 0;}}if (flag)printf("No\n");elseprintf("Yes\n");}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zbtrs/p/7671048.html

總結(jié)

以上是生活随笔為你收集整理的noip模拟赛 fateice-string的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。