洛谷P9752

考场上暴力100

题目传送门

思路

考虑到 \(n\) 很小，于是暴力，但不是枚举每个5位数再判断，而是把所有状态的可能正解用桶存个数，然后数量为 \(n\) 的就是一种方案

代码

#include <bits/stdc++.h>
using namespace std;

const int Maxn = 10;
long long n, a[Maxn][Maxn], cnt, vis[Maxn * Maxn * Maxn * Maxn * Maxn * Maxn + 5];//vis 是桶

int ts(int a, int b, int c, int d, int e) {
  return a * 10000 + b * 1000 + c * 100 + d * 10 + e;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  //	feropen("lock.in","r",stdin);
  //	feropen("lock.out","w",stdout);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i][1] >> a[i][2] >> a[i][3] >> a[i][4] >> a[i][5];
    vis[ts(a[i][1], a[i][2], a[i][3], a[i][4], a[i][5])] = -114514;//所有状态均不为正确密码
  }
  //只动一位
  for (int mmt = 1; mmt <= n; mmt++) {
    for (int i = 1; i <= 9; i++) {
      vis[ts((a[mmt][1] + i) % 10, a[mmt][2], a[mmt][3], a[mmt][4], a[mmt][5])]++;
    }
    for (int i = 1; i <= 9; i++) {
      vis[ts(a[mmt][1], (a[mmt][2] + i) % 10, a[mmt][3], a[mmt][4], a[mmt][5])]++;
    }
    for (int i = 1; i <= 9; i++) {
      vis[ts(a[mmt][1], a[mmt][2], (a[mmt][3] + i) % 10, a[mmt][4], a[mmt][5])]++;
    }
    for (int i = 1; i <= 9; i++) {
      vis[ts(a[mmt][1], a[mmt][2], a[mmt][3], (a[mmt][4] + i) % 10, a[mmt][5])]++;
    }
    for (int i = 1; i <= 9; i++) {
      vis[ts(a[mmt][1], a[mmt][2], a[mmt][3], a[mmt][4], (a[mmt][5] + i) % 10)]++;
    }
  }
  for (int mmt = 1; mmt <= n; mmt++) {
    for (int i = 1; i <= 9; i++) {
      (vis[ts((a[mmt][1] + i) % 10, a[mmt][2], a[mmt][3], a[mmt][4], a[mmt][5])] == n) && (cnt++, vis[ts((a[mmt][1] + i) % 10, a[mmt][2], a[mmt][3], a[mmt][4], a[mmt][5])] = 0);
    }
    for (int i = 1; i <= 9; i++) {
      (vis[ts(a[mmt][1], (a[mmt][2] + i) % 10, a[mmt][3], a[mmt][4], a[mmt][5])] == n) && (cnt++, vis[ts(a[mmt][1], (a[mmt][2] + i) % 10, a[mmt][3], a[mmt][4], a[mmt][5])] = 0);
    }
    for (int i = 1; i <= 9; i++) {
      (vis[ts(a[mmt][1], a[mmt][2], (a[mmt][3] + i) % 10, a[mmt][4], a[mmt][5])] == n) && (cnt++, vis[ts(a[mmt][1], a[mmt][2], (a[mmt][3] + i) % 10, a[mmt][4], a[mmt][5])] = 0);
    }
    for (int i = 1; i <= 9; i++) {
      (vis[ts(a[mmt][1], a[mmt][2], a[mmt][3], (a[mmt][4] + i) % 10, a[mmt][5])] == n) && (cnt++, vis[ts(a[mmt][1], a[mmt][2], a[mmt][3], (a[mmt][4] + i) % 10, a[mmt][5])] = 0);
    }
    for (int i = 1; i <= 9; i++) {
      (vis[ts(a[mmt][1], a[mmt][2], a[mmt][3], a[mmt][4], (a[mmt][5] + i) % 10)] == n) && (cnt++, vis[ts(a[mmt][1], a[mmt][2], a[mmt][3], a[mmt][4], (a[mmt][5] + i) % 10)] = 0);
    }
  }
	// 同时动两位
  for (int mmt = 1; mmt <= n; mmt++) {
    for (int i = 1; i <= 9; i++) {
      vis[ts((a[mmt][1] + i) % 10, (a[mmt][2] + i) % 10, a[mmt][3], a[mmt][4], a[mmt][5])]++;
    }
    for (int i = 1; i <= 9; i++) {
      vis[ts(a[mmt][1], (a[mmt][2] + i) % 10, (a[mmt][3] + i) % 10, a[mmt][4], a[mmt][5])]++;
    }
    for (int i = 1; i <= 9; i++) {
      vis[ts(a[mmt][1], a[mmt][2], (a[mmt][3] + i) % 10, (a[mmt][4] + i) % 10, a[mmt][5])]++;
    }
    for (int i = 1; i <= 9; i++) {
      vis[ts(a[mmt][1], a[mmt][2], a[mmt][3], (a[mmt][4] + i) % 10, (a[mmt][5] + i) % 10)]++;
    }
  }
  for (int mmt = 1; mmt <= n; mmt++) {
    for (int i = 1; i <= 9; i++) {
      (vis[ts((a[mmt][1] + i) % 10, (a[mmt][2] + i) % 10, a[mmt][3], a[mmt][4], a[mmt][5])] == n) && (cnt++, vis[ts((a[mmt][1] + i) % 10, (a[mmt][2] + i) % 10, a[mmt][3], a[mmt][4], a[mmt][5])] = 0);
    }
    for (int i = 1; i <= 9; i++) {
      (vis[ts(a[mmt][1], (a[mmt][2] + i) % 10, (a[mmt][3] + i) % 10, a[mmt][4], a[mmt][5])] == n) && (cnt++, vis[ts(a[mmt][1], (a[mmt][2] + i) % 10, (a[mmt][3] + i) % 10, a[mmt][4], a[mmt][5])] = 0);
    }
    for (int i = 1; i <= 9; i++) {
      (vis[ts(a[mmt][1], a[mmt][2], (a[mmt][3] + i) % 10, (a[mmt][4] + i) % 10, a[mmt][5])] == n) && (cnt++, vis[ts(a[mmt][1], a[mmt][2], (a[mmt][3] + i) % 10, (a[mmt][4] + i) % 10, a[mmt][5])] = 0);
    }
    for (int i = 1; i <= 9; i++) {
      (vis[ts(a[mmt][1], a[mmt][2], a[mmt][3], (a[mmt][4] + i) % 10, (a[mmt][5] + i) % 10)] == n) && (cnt++, vis[ts(a[mmt][1], a[mmt][2], a[mmt][3], (a[mmt][4] + i) % 10, (a[mmt][5] + i) % 10)] = 0);
    }
  }
  cout << cnt;
  return 0;
}

时间复杂度

暴力者切记，超时无敌（听双节棍听的）

\(\ \ \ \ O(2 \times 5 \times n \times 10 + 2 \times 4 \times 8 \times 10 + 8 \times 5)\)

\(=O(2 \times 5 \times 8 \times 10 + 2 \times 4 \times 8 \times 10+ 8 \times 5)\)

\(=O(1480)\)