這道題呢！

算了，不要讓這玩意兒活著禍害眾生吧！讓我們來拯救蒼生于苦海之中！！
騷話連篇ing

題目

由小寫英文字母和問號組成的字符串成為參數化單詞（例如：??cd,bcd,??）。如果兩個單詞中的問號符號可以由英語字母表的任意小寫字母替換，則這兩個參數化單詞可以認為是相似的，可以得到相同的字符串。例如：現在有兩個參數化單詞a???和?b?a，我們可以通過置換兩個單詞中的問號，獲得單詞abba。

Mirko最近獲得了一組參數化單詞集合，在這個集合一共有N個單詞，Mirko對這N的單詞中存在多少對相似參數化單詞很感興趣。集合中的所有單詞的長度都為M，且集合中同一個單詞可能出現多次。

輸入格式
第一行輸入兩個數字N（1≤N≤50000）和M（1≤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為TLE，string為MLE，需要unordered_map+hash才行！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的頭文件是#include<unordered_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; }

好了，好好理解這份代碼哦~
有任何問題都可以留言，我要我們的公司做到世界五百強 ！

總結

以上是生活随笔為你收集整理的[COCI 2018#5]Parametriziran的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。