f821 - nAnB ( 正常版 )
題目描述
題目描述一個簡化的 nAnB 遊戲。給定一個由不重複數字組成的答案 n，以及若干個猜測 x。對於每個猜測，計算有多少數字和位置都正確（A），以及有多少數字正確但位置錯誤（B）。
解題思路
對於每個猜測，程式碼首先遍歷答案和猜測，找出數字和位置都正確的數字（A）。為了避免重複計算，將答案中匹配的數字替換為 'a'。然後，程式碼遍歷答案中是數字的字符，並在猜測中尋找相同的數字（B）。同樣，為了避免重複計算，將猜測中匹配的數字替換為 'b'。最後，輸出 A 和 B 的數量。
複雜度分析
- 時間複雜度: O(m * n^2)，其中 m 是詢問的數量，n 是答案的長度。因為對於每個詢問，需要遍歷答案和猜測兩次，每次遍歷的時間複雜度都是 O(n^2)。
- 空間複雜度: O(n)，主要用於儲存猜測字符串
x。
程式碼
#include <iostream>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int m;
string n,x;
cin >> n >> m;
while(m--){
cin >> x;
int a=0,b=0;
for(int i=0;i<n.length();++i){
if(n[i]==x[i]){
++a;
x[i]='a';
}
}
for(int i=0;i<n.length();++i){
if(n[i]>='0'&&n[i]<='9')
for(int j=0;j<n.length();++j){
if(n[i]==x[j]){
++b;
x[j]='b';
break;
}
}
}
cout << a << "A" << b << "B\n";
}
}