連這種模擬題都能。。。orz

ex，太惡心了！

馳騁坑底這么久了，我明白了

開始吧！我發誓，這個超級兵，我就算用小書包平A都要A了它

題目

Vlatko喜歡使用整數數組，他在一張紙上寫下了兩個數組，每個數組一共n個元素。每一個元素可以是一個正整數，也可以是由一串小寫英文字母組成的字符串。由英文字母組成的序列可以替換為任意整數，如果同一字符串出現多次，那么這些字符串都必須用相同的整數進行替換。

Vlatko想知道是否可以用一些整數來替換所有的字符串，使得兩個數組相同。如果數組相同位置上的數字相同，則認為兩個數組相同。

輸入格式
第一行包含一個正整數n（1≤n≤50000），即每個數組中的元素數。
第二行包含第一個數組的n個元素。
第三行包含第二個數組的n個元素。

兩個數組中的每個元素都可以是：
1)小于1000的正整數或
2)表示變量的英文字母（不超過10個字符）的小寫字母字符串

輸出格式
如果兩個字符串可能相同，則輸出”DA”，否則，輸出”NE”。

樣例
樣例輸入1
3
3 1 2
3 1 x
樣例輸出1
DA
樣例輸入2
4
4 5 iks ipsilon
1 iks 3 iks
樣例輸出2
NE
樣例輸入3
5
x 3 x y 3
x y 2 z 3
樣例輸出3
DA
數據范圍與提示
在樣例3中，答案的解為x=2,y=3,z=3，此時兩個數組相等(2，3， 2， 3， 3)

題解

這道題沒有用到任何的知識點，你只要會用map會打include就可以了！
這道題就是一個純純的裸裸的的沒有裝飾的模擬題，矛盾就可以直接return 0
然而我爆零！orz

首先模擬考慮的幾種NE情況：
1.當ai，bi都是數字并且不相同
2.ai，bi其中有一個是數字，另一個是字母但是已經處理出了值，且與數字不相同
3.兩個都是字母，這個情況比較難搞！
（1）兩個字母都還沒有被處理，都是可變化的，這個時候我們要先勇敢跳過
（2）兩個字母都已經處理，并且值不相同
（3）有一個字母被處理了，另外一個字母可變化，這個時候就可以確定那個字母了

在一重循環之后，我們不能確定每一個字母都已經處理好了，
而且可能遇到以下幾種變態情況（卡了我n天啊！orz）
舉個栗子
1 b c d
b c d 2 這樣一個一個順次對應
a b c d 2
2 a b c d這樣一個一個逆次對應
a b c d 1 e f g h
z a b c d f g h d 這樣從中間斷開順逆對應

就是每一次循環只能更新出一個字母的極限情況，意思到了就行了！

而且為了get到這個字母可能與那些字母成為對應關系，我們就要用map套一個vector去存儲

你想想當n足夠大的時候，是不是要從頭和從尾都為起點跑一次，那這樣再循環中還要處理vector，
跟個兩重循環一樣，不T，天理不容

所以這一塊一定要想個優化，因為我們每次都是0~size-1進行循環處理，所以一旦這個父親有值過后，
一次循環就能讓這些0~size-1都有值，那么下一次碰到他們的時候，就沒有必要花個時間再詢問一遍
加個break，就能優化過AC！！
這個還是本仙女昨天想睡覺臨門一腳給想到的！！我都要拜倒在自己的石榴裙下了！！

這道題當然可以用并查集A，聽說代碼量也不是很黑人，但是我不會！尷尬ing
大佬們可以去寫寫，然后教教我這個無知的人！

直接上馬！

代碼實現

#include <map> #include <cstdio> #include <vector> #include <iostream> using namespace std; #define MAXN 50005 map < string, int > flag; map < string, vector < string > > G; bool isnum ( char x ) {if ( x >= '0' && x <= '9' ) return 1;return 0; } int n; string a[MAXN], b[MAXN]; int main() {scanf ("%d", &n );for ( int i = 1;i <= n;i ++ )cin >> a[i];for ( int i = 1;i <= n;i ++ )cin >> b[i];for ( int i = 1;i <= n;i ++ ) {if ( isnum ( a[i][0] ) && isnum( b[i][0] ) ) {if ( a[i] != b[i] ) return ! printf ( "NE" );}else {if ( isnum ( a[i][0] ) && ! isnum ( b[i][0] ) ) {int num = 0, len = a[i].length();for ( int j = 0;j < len;j ++ )num = ( num << 1 ) + ( num << 3 ) + ( a[i][j] - '0' );if ( flag[b[i]] && flag[b[i]] != num )return ! printf ( "NE" );flag[b[i]] = num;for ( int j = 0;j < G[b[i]].size();j ++ ) {if ( flag[G[b[i]][j]] && flag[G[b[i]][j]] != flag[b[i]] )return ! printf ( "NE" );else if ( flag[G[b[i]][j]] == flag[b[i]] ) break;flag[G[b[i]][j]] = flag[b[i]];}}else {if ( ! isnum ( a[i][0] ) && isnum ( b[i][0] ) ) {int num = 0, len = b[i].length();for ( int j = 0;j < len;j ++ )num = ( num << 1 ) + ( num << 3 ) + ( b[i][j] - '0' );if ( flag[a[i]] && flag[a[i]] != num )return ! printf ( "NE" );flag[a[i]] = num;for ( int j = 0;j < G[a[i]].size();j ++ ) {if ( flag[G[a[i]][j]] && flag[G[a[i]][j]] != flag[a[i]] )return ! printf ( "NE" );else if ( flag[G[a[i]][j]] == flag[a[i]] ) break;flag[G[a[i]][j]] = flag[a[i]];}}else {G[a[i]].push_back ( b[i] );G[b[i]].push_back ( a[i] );}}}}for ( int i = n;i >= 1;i -- ) {if ( ! isnum ( a[i][0] ) && ! isnum( b[i][0] ) ) {if ( flag[a[i]] && flag[b[i]] && flag[a[i]] != flag[b[i]] ) return ! printf ( "NE" );if ( ! flag[a[i]] && ! flag[b[i]] ) continue;if ( flag[a[i]] ) flag[b[i]] = flag[a[i]];else flag[a[i]] = flag[b[i]];for ( int j = 0;j < G[a[i]].size();j ++ ) {if ( flag[G[a[i]][j]] && flag[G[a[i]][j]] != flag[a[i]] )return ! printf ( "NE" );else if ( flag[G[a[i]][j]] == flag[a[i]] ) break;flag[G[a[i]][j]] = flag[a[i]];}for ( int j = 0;j < G[b[i]].size();j ++ ) {if ( flag[G[b[i]][j]] && flag[G[b[i]][j]] != flag[b[i]] )return ! printf ( "NE" );else if ( flag[G[b[i]][j]] == flag[b[i]] ) break;flag[G[b[i]][j]] = flag[b[i]];}}if ( ! isnum ( a[i][0] ) && isnum ( b[i][0] ) ) {int num = 0, len = b[i].length();for ( int j = 0;j < len;j ++ )num = ( num << 1 ) + ( num << 3 ) + ( b[i][j] - '0' );if ( ! flag[a[i]] ) flag[a[i]] = num;if ( flag[a[i]] != num ) return ! printf ( "NE" );for ( int j = 0;j < G[a[i]].size();j ++ ) {if ( flag[G[a[i]][j]] && flag[G[a[i]][j]] != flag[a[i]] )return ! printf ( "NE" );else if ( flag[G[a[i]][j]] == flag[a[i]] ) break;flag[G[a[i]][j]] = flag[a[i]];}}if ( ! isnum ( b[i][0] ) && isnum ( a[i][0] ) ) {int num = 0, len = a[i].length();for ( int j = 0;j < len;j ++ )num = ( num << 1 ) + ( num << 3 ) + ( a[i][j] - '0' );if ( ! flag[b[i]] ) flag[b[i]] = num;if ( flag[b[i]] != num ) return ! printf ( "NE" );for ( int j = 0;j < G[b[i]].size();j ++ ) {if ( flag[G[b[i]][j]] && flag[G[b[i]][j]] != flag[b[i]] )return ! printf ( "NE" );else if ( flag[G[b[i]][j]] == flag[b[i]] ) break;flag[G[b[i]][j]] = flag[b[i]];}}}for ( int i = 1;i <= n;i ++ ) {if ( ! isnum ( a[i][0] ) && ! isnum( b[i][0] ) ) {if ( flag[a[i]] && flag[b[i]] && flag[a[i]] != flag[b[i]] ) return ! printf ( "NE" );if ( ! flag[a[i]] && ! flag[b[i]] ) continue;if ( flag[a[i]] ) flag[b[i]] = flag[a[i]];else flag[a[i]] = flag[b[i]];for ( int j = 0;j < G[a[i]].size();j ++ ) {if ( flag[G[a[i]][j]] && flag[G[a[i]][j]] != flag[a[i]] )return ! printf ( "NE" );else if ( flag[G[a[i]][j]] == flag[a[i]] ) break;flag[G[a[i]][j]] = flag[a[i]];}for ( int j = 0;j < G[b[i]].size();j ++ ) {if ( flag[G[b[i]][j]] && flag[G[b[i]][j]] != flag[b[i]] )return ! printf ( "NE" );else if ( flag[G[b[i]][j]] == flag[b[i]] ) break;flag[G[b[i]][j]] = flag[b[i]];}}if ( ! isnum ( a[i][0] ) && isnum ( b[i][0] ) ) {int num = 0, len = b[i].length();for ( int j = 0;j < len;j ++ )num = ( num << 1 ) + ( num << 3 ) + ( b[i][j] - '0' );if ( ! flag[a[i]] ) flag[a[i]] = num;if ( flag[a[i]] != num ) return ! printf ( "NE" );for ( int j = 0;j < G[a[i]].size();j ++ ) {if ( flag[G[a[i]][j]] && flag[G[a[i]][j]] != flag[a[i]] )return ! printf ( "NE" );else if ( flag[G[a[i]][j]] == flag[a[i]] ) break;flag[G[a[i]][j]] = flag[a[i]];}}if ( ! isnum ( b[i][0] ) && isnum ( a[i][0] ) ) {int num = 0, len = a[i].length();for ( int j = 0;j < len;j ++ )num = ( num << 1 ) + ( num << 3 ) + ( a[i][j] - '0' );if ( ! flag[b[i]] ) flag[b[i]] = num;if ( flag[b[i]] != num ) return ! printf ( "NE" );for ( int j = 0;j < G[b[i]].size();j ++ ) {if ( flag[G[b[i]][j]] && flag[G[b[i]][j]] != flag[b[i]] )return ! printf ( "NE" );else if ( flag[G[b[i]][j]] == flag[b[i]] ) break;flag[G[b[i]][j]] = flag[b[i]];}}}printf ( "DA" );return 0; }

啊~AC了這道題，世界都有了光彩，真香！這里是決心把品牌做進世界前五百強的現場，
歡迎致電139紅酒白酒葡萄酒！

有任何問題，歡迎留言，xgg，xjj我們再見哦~

總結

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

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