题目链接:UVAive 5844 Leet
DES:大意是给出两个字符串。第一个字符串里的字符可以由1-k个字符代替。问这两个字符串是不是相等。因为1<=k<=3。而且第一个字符串长度小于等于15.所以。对第一个字符串里的每一个字符尝试匹配1-k个字符看是否有可能相等就好了。
比赛的时候想到这是dfs类暴力,但是map<char, char*>没用过。不知道怎么记录了。而且dfs本身就不太会用。依然感觉dfs很奇妙。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <map>
using namespace std; int k;
char s1[], s2[];
int len1, len2;
bool flag;
map<char, char *>mm; void dfs(int l1, int l2)
{
if (flag) return;
if (l1 == len1 && l2 == len2)
{
flag = true;
return;
}
if (l1 >= len1 || l2 >= len2) return;
if (mm[s1[l1]]) //如果这个字符以前出现过。像以前一样匹配。
{
char *temp = mm[s1[l1]]; // 这里用指针。不然不能直接赋值。
int lent = strlen(temp);
for (int i=, j=l2; i<lent; ++i, ++j) //是不是可以匹配。
{
if (temp[i] != s2[j])
return;
}
dfs(l1+, l2+lent); //继续匹配第一个字符串的下一个字符。
}
else //如果没出现过。匹配。
{
for (int i=; i<=k; ++i) //尝试把这个字符匹配给对应1-k个字符。k种。
{
char temp[]; //数组。用指针程序会崩。
memset(temp, , sizeof(temp));
for (int j=; j<i; ++j)
{
temp[j] = s2[l2+j];
}
mm[s1[l1]] = temp;
dfs(l1+, l2+i); //继续匹配下一个字符、
mm[s1[l1]] = ; //回溯。
}
}
} int main()
{
int t;
//ios::sync_with_stdio(false);
cin >> t;
//scanf("%d", &t);
while(t--)
{
//scanf("%d%s%s", &k, s1, s2);
cin >> k >> s1 >> s2;
flag = false;
mm.clear();
len1 = strlen(s1);
len2 = strlen(s2);
dfs(, );
if (flag) cout << << endl;
else cout << << endl;
}
return ;
}
(⊙o⊙)哦....学了一个新的东西....ios::sync_with_stdio(false);听说用了它..C++就可以接近C的时间啦。。。。。
试验了一下,,,,
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAmEAAABLCAIAAAC3P8dlAAAM5UlEQVR4nO2dPY6jTBCG6zItIXGTTog4B6FT7sABnHMCTsAFlgmJSCayZMnSytJKfAF/1dUFa2Pjgf3e0RNA89N4p5eHqmrGRLv8+fXr109fwmF+8G/1f/j5f/6W/9VP/a9+rkP8PP2PX7c1AAAAAHzgSAAAAEAHjgQAAAB04EgAAABAB44EAAAAdOBIAAAAQAeOBAAAAHTgSPABiiQkIqI4++krWbg8m/38lQAA9sVaR1YXQ/ekUlqyuKX4W+wvGov0TtSatHlP1/mNqGXchptdk4RDY3gpppOwdu9SwfupEkNkQvM5D1WJecLHcOTnGR6biChMis27W0+Rmul1cnmpmR22mLRQPtoeHwqLpCDKO0xyfe08hfzdZeVw8lJ+9oVNe+b9jlQ2td/Wafm21Nr45nrrwU47t3mO1E7FxNwkobM86Jm3g60oUkNks9wSGXdgbEOVmOduT3Dkp8ni8RdUJOE+XVIPlzcODPdSq8QQ2dzff/TlDj+aI7biy6zWZPFlKPcc2dj+hI2lnGwjNpFt6vqaGLFp32zgSEdCdd1FjdxhvdK+LbXeCFvVte5I9/z5rY8vq4uZAk3WDrZivFNk1nncHmQmnrjVRvbAzp7lM0tEobXDY7vNa+cpvteeeizrKE7gyM+SWW6X3B7lH79IzTiEstgdzB1VYvhn2dtHGx2mbc1KGeH5LT3XxBTW+nGk48iZjq6Jycl8ef90e2ULRwopSmVmcb+qZmXXdK06Uuw2rgopKlEveCtdojUtensJw3UWzO2QrZpv7A/0lh01mqQSceTisd1yL8s93cv+barE8IyCWN0xLPzNLBkzPY0N1y+kuLOPthw4PuzIIinINnqutYsXF3p5JXj9ETZxpLc84ySxaXXXTj1SuwZn9dvyUmh+k5lb8FaK1Ix3EL7cKVAmEuYbx2d2dhLuPHYsd+TcsU47cq2f5ZiO7EsG0zVPA1WMySm+/Fh94cGPMOOnPnGaT/VCv8XZuUgKtR45ho9zCdXG0qGCyHorR7IYsUjvcrbOfIi5smv+y07vLKeqOpLXNVsK72s8DR7F1Q8zUzcVQuhwoVH82LxWHWnSgjty7li3IzjysxzRkcJ28ppZ9pgXC0JjdjWu/DIh47E4kk/5IVGSzEqifChw+C68JuZoE3bqF979ENNwvBxmvyqKjmxCKakzTh9gOTvqxotKPdJFKBy8GX6/EEXBtXEk4+k4cuaccOSHOVg90okg1Y8gV9mBx5mz80Q9UpxqiBqnEyozdDLrz/E5Auvfj8ziVkSErmy0yat+cnVFOVAe0iThdE5+VTPzWhlItG5MF6550+K9TKlaetTrkdxnfj2StSv1SG8f1tHOb9P/GMeZ11pnsf52Cm/XJLq7ROvABu9+sMyqfMHD0ecUfR4o3frS3xDIYhYOegbyX4J85NXJJXiOlL0H6VzG3HuQYmKtfJMSbAE3Yo9jzXXzWqebUe+5JO7aDUv18xb1WMxr/VmO8n4kHzxzw8wdPLlVGsFhwd/ZAcfFzbUCAMC7gSPBcYEjAQDbAkeC4wJHAgC2BY4EAAAAdOBIAAAAQAeOBAAAAHTo0l4AAAAA4ANHAgAAADpwJAAAAKADRwIAAAA6cCQAAACgA0cCAAAAOnAkAAAAoANHgg9QnroveYjPP30lC5cXnX/+SgAA+2KtI6vfAf05VUrLOW4pvon9RWOZ/iFqg/T6nq7zu/u9zffhZnc9Td+N9bucTsLavUsF76c6BURBGHzOQ9UpeMLHcCT4G9UpoMC57YxPfu7DX5kG0/dohafy7VfyKuVp+v7I4HR97TyF/IDn6fsj5X/AhU175v2OVDa1t8hpuUXURvHd9daDnXZu8xypnYqJ+XoKneVBz7wdbEWZBkTROY9I3mW2oToFz8WscCSYpxtORO7oLU8hBWk5Lo/j7RyPA8lp3weO2MqvYLUmy6+Acs+RTdSfsIkop6gRmyhqLpfrKRCb9s0GjnQkdLl0USN3WK+0W0RtlL+ja92R7vnzex9fVr+DKdBk7WArxjvFOaLxtnK5tPzuw24lamN7jpRn83NERGEUDY/zUX5xnu577anHso7iExwJ/oKII6tTwAdMHqnjp0yDfYWSo8O0redSRnh+S8/1FBRR5MeRjiNnOrqegpyCr1K9hh2yhSOFFKUyz3G/qmZl13StOlLsNq4KKSpRL3grXaI1LXt7CcN1Fswj6veZb+wP9JYdNQanSsSRi8d2y70s4Ugwj3CkkKKSib3sMI5cDhwfdmR5Kihq9FxrFy8u9PJK8PojbOJIb3nGSWLT6q6deqR2Dc7qLeKl0PwuM7fgrZRpMCap+HKnQJlImG8cA1B2Eu48dix35NyxTjtyreBvSAu6SRFZRxiSGbsKIuf91CdO86le6Lc4OxenUq1HjuHjXEK1iehQQeRlK0eyGLFM/8jZOvMh5squ+S87/cNyqqojeV2zpfDPGk+DR3H1w8zUTW0QOlxoFD9RflEdGaQld+TcsW5HcCT4G36kyIsCYRAcJtc6Wwt8LI7kU35IlCTPJVE+FDh8F15PwdEm7FxeePdDTMPxcpj9qig6sgmlpM44fYDl7KgbLyr1SBehcPBm+H1EFAXXxpGMp+PImXPCkeBv6NnUnjIN9JzqTJ3y51ias/NEPVKcaogapxMqM3TOkT/H5wisfz/yHLciInRlo01e9ZOrK8qB8pDrKZzOya9qZl4rA4nWjenCNaYoVjXkhlNLj3o9kvvMr0eydqUe6e3DOtrZvQzsjAVHOonWc8QCx3O8u3TrJu9+sMyqfMHD0ecUfR4o3frS3xA4xywc9AzkvwT5yKuTS/AcKXsP0rmMufcgxcRa+SYl2AJuxB7HmuvmtU4y6z13irv2gKX6eYt6LOa1gseQuRCncOA/XQ1jj6VMwJHB39kBx8XNtQIAwLuBI8FxgSMBANsCR4LjAkcCALYFjgQAAAB04EgAAABAB44EAAAAdKhuawAAAAD4wJEAAACADhwJAAAA6MCRAAAAgA4cCQAAAOjAkQAAAIAOHAkAAADowJHgAxRJ97XscfbTV7JweTb7+SsBAOyLtY6sLobuSaW0ZHFL8bfYXzQW6Z2oNWnznq7zm/u9zbfhZtck03djXYrpJKzdu1TwfqrEEJnQfM5DVWKe8DEcCWYpUsO+6yopvB2yWAye4Ylwpw+FRTJ9f6RJrq+dp5D/INn0/ZHysy9s2jPvd6Syqf22Tsu3pdbGN9dbD3baf++jdKR2KibmJgmd5UHPvB1sRZEaIpvllsi4A2MbqsQ8d3uCI8EsWTwOjCIJ5bgaDOrsY9Jibv+fxhFb8WVWa7L4MpR7jmxsf8LGUk62EZvINnV9TYzYtG82cKQjobruokbusF5p35Zam7+ja92R7vnzWx9fVhczBZqsHWzFeKfILI23j7puB5mJJ261sc2s8iyfWSIKrR0e221eO0/x/Z1LPZZ1FCdwJHiEIjV8CPWrVWLGwcOX27rO7b7G1egwbWtWygjPb+m5Jqaw1o8jHUfOdHRNTE7mq1CvYYds4UghRanMLO5X1azsmq5VR4rdxlUhRSXqBW+lS7SmRW8vYbjOgrmlfp/5xv5Ab9lRo0kqEUcuHtst97Lc070M7BE3LswtGz/D4BFSrBLzmdzJYywHjg87skgKso2ea+3ixYVeXglef4RNHOktzzhJbFrdtVOP1K7BWf22vBSa32TmFryVIjVjipUvdwqUiYT5xjEAZSfhzmPHckfOHeu0I9cKlhmSE85gU2NHN1nysfrCY8z5qU+c5lO90G9xdi6SQq1HjuHjXEK1sXSoILLeypEsRizSu5ytMx9iruya/7LTO8upqo7kdc2WwvsaT4NHcfXDzNQVcoQOFxrFj81r1ZEmLbgj5451O4IjwUOMuVZ1XPVq5MWC0JhdjSu/TMh4LI7kU35IlCSzkigfChy+C6+JOdqEnfqFdz/ENBwvh9mviqIjm1BK6ozTB1jOjrrxolKPdBEKB2+G3y9EUXBtHMl4Oo6cOSccCR5DrS+KGiSjSM2B5uw8UY8UpxqixumEygydzPpzfI7A+vcjs7gVEaErG23yqp9cXVEOlIc0STidk1/VzLxWBhKtG9M9bjNFsaohN5xaetTrkdxnfj2StSv1SG8f1hEcCTQyyybpZLH2+secI3eWaB3Y4N0PllmVL3g4+pyizwOlW1/6GwJZzMJBz0D+S5CPvDq5BM+RsvcgncuYew9STKyVb1KCLeBG7HGsuW5eq1v7oTBJ4j7XxVL9vEU9FvNawUMMY4mlQATKXFZvsIHDgr+zA46Lm2sFAIB3A0eC4wJHAgC2BY4ExwWOBABsCxwJAAAA6MCRAAAAgA4cCQAAAOjAkQAAAIAOXdoLAAAAAHzgSAAAAEAHjgQAAAB04EgAAABA5z/4Chgm6S7IugAAAABJRU5ErkJggg==" alt="" />
分别是用STL & C++ , C, C++...