PTA训练题 7-5 Equivalent Passwords （等效密码） (10分) dfs二进制枚举+哈希表

Yesterday you arrived at the hotel, and you kept all your valuable stuff in your room’s safe. Unfortunately, you forgot the password. But you have a very long list of passwords (each password is at most 5 digits), and you are sure that your password is one of them.

昨天你到达酒店，把所有贵重物品都放在房间的保险箱里。不幸的是，你忘了密码。但是你有一个很长的密码列表(每个密码最多是5位数字)，而且你要确定你的密码就是其中之一。

The safe will consider some passwords equivalent. Two passwords A and B are considered equivalent, if they are of the same length, and |A[i] - B[i]| is the same for all possible values of i, where X[i] is the i-th digit of X and |Y| is the absolute value of Y.

保险柜会考虑一些等效的密码。两个密码A和B的长度相同，|A[i] - B[i]|对于i的所有可能值都相同，其中X[i]是X的第 i 位，|Y|是Y的绝对值。

You will go through the list of passwords in the given order. For each password, you will do the following:

您将按照给定的顺序遍历密码列表。对于每个密码，您将执行以下操作:

1.If the same password or any of its equivalent passwords were typed before, skip this password.

2.Otherwise, type this password into the safe.

3.If it’s the correct password (or any of its equivalent passwords), the safe will open and you will stop any further processing.

如果之前输入了相同的密码或任何等效的密码，请跳过此密码。

否则，请在保险箱中键入此密码。

如果它是正确的密码(或任何与其相当的密码)，保险箱将打开，您将停止任何进一步的处理。

Now given the list of all passwords, you would like to know, in the worst case scenario, what is the maximum number of passwords you will have to type?

现在给出了所有密码的列表，您想知道，在最坏的情况下，您必须键入的最大密码数量是多少?
Note

In the first test case: 在第一个测试用例中:

all passwords are equivalent to each other. This means that the first password will open the safe for sure.

所有密码彼此相等。这意味着第一个密码将肯定打开保险箱。

In the second test case: 在第二个测试用例中:

If the first password is the correct one, you will type 1 password.
If the second password is the correct one, you will type 2 passwords.
If the third password is the correct one, you will type 2 passwords (because the second password is equivalent to the third one).
If the fourth password is the correct one, you will type 1 password (because the first password is equivalent to the fourth one).

如果第一个密码是正确的，您将键入1个密码。
如果第二个密码是正确的，您将键入2个密码。
如果第三个密码是正确的，您将键入2个密码(因为第二个密码是相当于第三个)。
如果第四个密码是正确的，您将键入1个密码(因为第一个密码是相当于第四个)。

In the third test case: 在第三个测试用例中:

If the first password is the correct one, you will type 1 password.
If the second password is the correct one, you will type 1 password (because the first password is equivalent to the second one).
If the third password is the correct one, you will type 2 passwords. Even though the third password is equivalent to the second password, the second password was skipped, and therefore you should type the third password.

如果第一个密码是正确的，你将输入一个密码。
如果第二个密码是正确的，您将键入1个密码(因为第一个密码等于第二个密码)。
如果第三个密码是正确的，你将输入2个密码。尽管第三个密码相当于第二个密码，但第二个密码被跳过，因此应该跳过输入第三个密码。

Input:

Your program will be tested on one or more test cases. The first line of the input will be a single integer T(1 ≤ T ≤ 50) representing the number of test cases.

您的程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数T(1≤T≤50)表示测试用例的数量。

Followed by T test cases. Each test case starts with a line will containing an integer N (1 ≤ N ≤ 100,000) representing the number of passwords, followed by N lines, each one will contain a non-empty string of at most 5 digits (from ‘0’ to ‘9’), representing a password (might contain leading zeros).

接下来是T测试用例。每个测试用例开始的一行将包含一个整数N(1≤N≤100,000)，表示密码的数量，然后是N行，每个行将包含一个不超过5位的非空字符串(从‘0’到‘9’)，表示一个密码(可能包含前导零)。
Output:

For each test case print a single line containing “Case n: ” (without quotes) where n is the test case number (starting from 1) followed by a space then the maximum number of passwords you will have to type.

对于每个测试用例，打印包含“case n: ”(不带引号)的单行代码，其中n是测试用例号(从1开始)后面跟着空格，然后是你需要输入的最大密码数。
Sample Input:

3
3
000
111
222
4
1111
123
214
2222
3
43434
54545
45454

Sample Output:

Case 1: 1
Case 2: 2
Case 3: 2

作者
ICPC-2014
单位
贵州工程应用技术学院
代码长度限制
16 KB
时间限制
10000 ms
内存限制
64 MB

---

题意：

如果两个密码A和B是等效的，
则abs(A[0]-B[0]) == abs(A[1]-B[1]) == abs(A[2]-B[2]) == abs(A[3]-B[3])...，
例如11111和22222和33333和00000都是等效的

给定很多个密码，如果已经输入过等效密码了，就跳过当前密码，问最多要输入多少次密码？

---

1. 当输入一个密码后，就把所有等效密码加入到unordered_set标记为以访问，
   如果当前密码已经在unordered_set里了就跳过

2. 用dfs枚举所有等效密码，大约有10*(2^5)个，
   先枚举POS=abs(A[i]-B[i])，POS从1到10枚举，
   再枚举每个位置+POS或-POS即可(2^5)

3. 这里采用枚举二进制的方式dfs，
   二进制位为1代表+POS，为0代表-POS

c++代码

// #define debug
#ifdef debug
#include <time.h>
#include "win_majiao.h"
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_set>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>

#define MAXN ((int)1e5+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)
// typedef vector<vector<int> > VVI;

using namespace std;

#define show(x...) \
	do { \
	   cout << "\033[31;1m " << #x << " -> "; \
	   err(x); \
	} while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

namespace FastIO{

	char print_f[105];
	void read() {}
	void print() { putchar('\n'); }

	template <typename T, typename... T2>
	   inline void read(T &x, T2 &... oth) {
		   x = 0;
		   char ch = getchar();
		   ll f = 1;
		   while (!isdigit(ch)) {
			   if (ch == '-') f *= -1; 
			   ch = getchar();
		   }
		   while (isdigit(ch)) {
			   x = x * 10 + ch - 48;
			   ch = getchar();
		   }
		   x *= f;
		   read(oth...);
	   }
	template <typename T, typename... T2>
	   inline void print(T x, T2... oth) {
		   ll p3=-1;
		   if(x<0) putchar('-'), x=-x;
		   do{
				print_f[++p3] = x%10 + 48;
		   } while(x/=10);
		   while(p3>=0) putchar(print_f[p3--]);
		   putchar(' ');
		   print(oth...);
	   }
} // namespace FastIO
using FastIO::print;
using FastIO::read;

int n, m, Q, K;

void dfs(string& s, int num, unordered_set<string>& vis) {
	vis.insert(s); //记得不要漏掉自己
	for(int i=0; i<=32; i++) { //枚举二进制即可
		int p = i, q = 0, flag;
		string tmp = s;
		for( ; q<s.length(); q++) {
			flag = (p&1) ? num : -num;
			tmp[q] += flag;
			if(tmp[q]<'0' || tmp[q]>'9') { goto OUT; }
			p >>= 1;
		}
		vis.insert(tmp);
		// show(s, tmp);
		OUT : ;
	}
}

signed main() {
#ifdef debug
	freopen("test.txt", "r", stdin);
	clock_t stime = clock();
#endif
	// string s = "1111";
	// unordered_set<string> vis;
	// dfs(s, vis);
	scanf("%d ", &Q);
	int cas = 0;
	while(Q--) {
		scanf("%d ", &n);
		char str[8] = { 0 };
		int ans = 0;
		unordered_set<string> vis; //用来标记是否访问过了
		string s;
		for(int i=1; i<=n; i++) {
			scanf("%s ", str);
			s = str;
			if(vis.count(s)) { continue ; } //输入过等效密码就跳过
			ans ++;
			for(int num=1; num<=10; num++) //枚举POS = abs(A[0]-B[0])的值
				dfs(s, num, vis); //dfs搜索每一位+POS或-POS的值，都为等效密码
		}
		printf("Case %d: %d\n", ++cas, ans);
	}





#ifdef debug
   clock_t etime = clock();
   printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
   return 0;
}

java代码，应该是对的把，但是MLE了

import sun.swing.SwingUtilities2;

import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;

public class Main {
    public static final boolean debug = false;
    public static String INPATH = "C:\\Users\\majiao\\Desktop\\test.txt",
            OUTPATH = "C:\\Users\\majiao\\Desktop\\out.txt";
    public static StreamTokenizer tok;
    public static BufferedReader cin;
    public static PrintWriter cout;

    public static long start_time = 0, out_time = 0;
    public static int n, m, K, Q, MAXN = (int)2, INF = 0x3f3f3f3f,
            pre[] = new int[MAXN], sum[] = new int[MAXN], POS = 50000;
    public static byte buf[] = new byte[MAXN];

    public static int fa(int x) { return pre[x]==x ? x : (pre[x]=fa(pre[x])); }

    public static void union_xy(int x, int y) {
        x = fa(x); y = fa(y);
        if(x != y) {
            sum[x] += sum[y];
            pre[y] = x;
        }
    }

    public static void dfs(String s, int num, Set<String> vis) {
        vis.add(s);
        for(int i=0; i<=32; i++) {
            char[] ch = s.toCharArray();
            int p = i, q = 0, flag = 0, len = s.length();
            boolean ok = true;
            for(q=0; q<len; q++) {
                flag = ((p&1) == 1) ? num : (-num);
                ch[q] += flag;
                if(ch[q]<'0' || ch[q]>'9') { ok = false; }
                p >>>= 1;
            }
            if(ok) { vis.add(new String(ch));
                }
        }
    }

    public static void main(String[] args) throws IOException {
        main_init();
        if(debug) { start_time = System.currentTimeMillis(); }
        if(false) { System.setOut(new PrintStream(OUTPATH)); }

        Scanner scan = new Scanner(cin);
        Q = scan.nextInt();
        int cas = 0;
        while(Q-- > 0) {
            n = scan.nextInt();
            int ans = 0;
            Set<String> vis = new HashSet<>();
            for(int i=1; i<=n; i++) {
                String s = scan.next();
                if(vis.contains(s)) { continue ; }
                ans ++;
                for(int num=1; num<=10; num++)
                    dfs(s.toString(), num, vis);
            }
            System.gc();
            cout.printf("Case %d: %d\n", ++cas, ans);
        }










        if(debug) {
            out_time = System.currentTimeMillis();
            cout.printf("run time : %d ms\n", out_time-start_time);
        }
        cout.flush();
    }

    public static void show(List<Object> list, Object... obj) {
        cout.printf("%s : ", obj.length>0 ? obj[0] : "");
        for(Object x : list) {
            cout.printf("[%s] ", x);
        }
        cout.printf("\n");
    }

    public static void show(Map<Object, Object> mp, Object... obj) {
        cout.printf("%s : ", obj.length>0 ? obj[0] : "");
        Set<Map.Entry<Object, Object>> entries = mp.entrySet();
        for (Map.Entry<Object, Object> en : entries) {
            cout.printf("[%s,%s] ", en.getKey(), en.getValue());
        }
        cout.printf("\n");
    }

    public static<T> void forarr(T arr[], int ...args) {
        int lef = 0, rig = arr.length - 1;
        if(args.length > 0) { lef = args[0]; rig = args[1]; }
        cout.printf(" : ");
        for( ; lef<=rig; lef++) {
            cout.printf("[%s] ", args[lef]);
        }
        cout.printf("\n");
    }

    public static void main_init() {
        try {
            if (debug) {
                cin = new BufferedReader(new InputStreamReader(
                        new FileInputStream(INPATH)));
            } else {
                cin = new BufferedReader(new InputStreamReader(System.in));
            }
            cout = new PrintWriter(new OutputStreamWriter(System.out));
//            cout = new PrintWriter(OUTPATH);
            tok = new StreamTokenizer(cin);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public static String next_str() {
        try {
            tok.nextToken();
            if (tok.ttype == StreamTokenizer.TT_EOF)
                return null;
            else if (tok.ttype == StreamTokenizer.TT_NUMBER) {
                return String.valueOf((int)tok.nval);
            } else if (tok.ttype == StreamTokenizer.TT_WORD) {
                return tok.sval;
            } else return null;
        } catch (Exception e) {
            e.printStackTrace();
            return null;
        }
    }

    public static int read_int() {
        String tmp_next_str = next_str();
        return null==tmp_next_str ? -1 : Integer.parseInt(tmp_next_str);
    }
    public static long read_long() { return Long.parseLong(next_str()); }
    public static double read_double() { return Double.parseDouble(next_str()); }
    public static BigInteger read_big() { return new BigInteger(next_str()); }
    public static BigDecimal read_dec() { return new BigDecimal(next_str()); }


    static class Edge implements Comparable<Edge> {
        int u, v, w;
        @Override
        public int compareTo(Edge o) { return w - o.w; }
    }
    static Edge a[] = new Edge[MAXN];

    class Pair implements Comparable<Pair>{
        int fst, sec;
        public Pair() { }
        public Pair(int fst, int sec) {
            this.fst = fst;
            this.sec = sec;
        }
        @Override
        public int compareTo(Pair o) {
            return fst - o.fst == 0 ? sec - o.sec : fst - o.fst;
        }
    }
}