iis 建设网站,大连金州开发区,济南网络营销外包,推广页面这道题呢#xff01; 算了#xff0c;不要让这玩意儿活着祸害众生吧#xff01;让我们来拯救苍生于苦海之中#xff01;#xff01; 骚话连篇ing
题目
由小写英文字母和问号组成的字符串成为参数化单词#xff08;例如#xff1a;??cd,bcd,??#xff09;。如果两…这道题呢 算了不要让这玩意儿活着祸害众生吧让我们来拯救苍生于苦海之中 骚话连篇ing
题目
由小写英文字母和问号组成的字符串成为参数化单词例如??cd,bcd,??。如果两个单词中的问号符号可以由英语字母表的任意小写字母替换则这两个参数化单词可以认为是相似的可以得到相同的字符串。例如现在有两个参数化单词a???和?b?a我们可以通过置换两个单词中的问号获得单词abba。
Mirko最近获得了一组参数化单词集合在这个集合一共有N个单词Mirko对这N的单词中存在多少对相似参数化单词很感兴趣。集合中的所有单词的长度都为M且集合中同一个单词可能出现多次。
输入格式 第一行输入两个数字N1≤N≤50000和M1≤M≤6 接下来输入N行字符串每行的长度为M表示输入的参数化单词。 输出格式 输出相似的参数化单词的对数。
样例 样例输入1 3 3 ??b c?? c?c 样例输出1 2 样例输入2 4 6 ab??c? ??kll? a?k??c ?bcd?? 样例输出2 3 样例输入3 5 2 ?? b? c? ?g cg 样例输出3 8 数据范围与提示 在第一组样例中相似的两对参数化单词为??b,c??和c??,c?c。
题解
这道题map为TLEstring为MLE需要unordered_maphash才行orz 首先由数据范围可知n很大m很小 那么我们就可以对m进行一个hash操作 由于总共的字母数是26个小于2^5 即如果我们把每一位的字母都通过乘以2^5*j数据范围也是在int内的。
那么我们对每一行的字母都可以处理出一个hash值 由于会存在有?的情况我们可以另外开一个数组用于验证这个位置是否为?。 其实用map就可以搞定
接着找两行如果第i行的字母hash值和第j行的验证串取与操作得到的答案和第j行的字母hash值和第i行的验证串取于得到的答案相同 因为如果验证串验证的那个位置有字母 则全是1取与得到的值就是那个位置字母的值 如果验证串那个位置无字母则全是0取与得到的也全是0则答案也全是为0 则ans。
也可以这么理解 假设当前串为?a??b?c??对于之前的串管它有多少‘’ 只要abc三个位置为“abc”,“ab?”,“a?b”,“a??”,?bc,?bc…… 就可以匹配了所以记录某些位置上为各种情况的方案数即可
unordered_map的头文件是#includeunordered_map 但是如果你的C编译器比较low像本仙女的一样 就很容易报错bits万能头文件都没有用
如果报错可以换为以下写法
#if(__cplusplus 201103L)
#include unordered_map
#include unordered_set
#else
#include tr1/unordered_map
#include tr1/unordered_set
namespace std {using std::tr1::unordered_map;using std::tr1::unordered_set;
}
#endif删掉set也是OK哒亲(づ3)づ╭❤
#if(__cplusplus 201103L)
#include unordered_map
#else
#include tr1/unordered_map
namespace std {using std::tr1::unordered_map;
}
#endif好了话不多说屁不多放上马
代码实现
#include cstdio
#include iostream
#if(__cplusplus 201103L)
#include unordered_map
#else
#include tr1/unordered_map
namespace std {using std::tr1::unordered_map;
}
#endif
using namespace std;
#define LL long long
#define MAXN ( 1 7 ) 5
int n, m, opt, num;
char str[7];
LL result;
unordered_map int, int vis[MAXN];
int Hash ( string x ) {int len x.length();int ans 0;for ( int i 0;i len;i )if ( x[i] ? ) ans ans * 27 26;else ans ans * 27 ( x[i] - a );return ans;
}
int main() {scanf ( %d %d\n, n, m );string tmp, res; for ( int i 1;i n;i ) {scanf ( %s, str );opt 0;num 0;tmp ;for ( int j 0;j m;j ) {if ( str[j] ! ? ) {opt | ( 1 j );num ( num 1 ) | 1;tmp str[j];}}if ( tmp )result i - 1;else {for ( int j 0;j num;j ) {res ;for ( int k 0;( 1 k ) num;k ) {if ( j ( 1 k ) ) res tmp[k];else res ?;}if ( vis[opt].count ( Hash ( res ) ) )result ( LL ) vis[opt][Hash ( res )];}}for ( int j 0;j ( 1 m );j ) {tmp ;for ( int k 0;k m;k ) {if ( j ( 1 k ) ) tmp str[k];}vis[j][Hash ( tmp )] ;}}printf ( %lld, result );return 0;
}好了好好理解这份代码哦~ 有任何问题都可以留言我要我们的公司做到世界五百强
