topcoder srm 685 div1

problem1 link

依次枚举每个元素$x$，作为$S$中开始选择的第一个元素。对于当前$S$中任意两个元素$i,j$，若$T[i][j]$不在$S$中，则将其加入$S$，然后继续扩展；若所有的$T[i][j]$都在$S$中，则结束扩展。每次扩展结束之后保存$|S|$的最小值。

problem2 link

总的思路是搜索，分别枚举每一条边是在哪个集合中，进行如下的优化：

（1）使用并查集，当其中两个集合都联通时结束；当有一个集合联通时，直接判断剩下所有的边加入另一个集合能否使得另一个集合联通；

（2）如果当前剩下所有的边都加入到其中一个集合都不能使其联通时，结束搜索返回；

（3）当前边加入第一个集合使其联通分量减少时才进行加入的操作，否则不再继续搜索下去，而将其直接加入另一个集合。

problem3 link

随即生成1000个点数为12个图，然后计算最小生成树的个数。假设可以从中选出四个（可能是相同的）然后串联起来，那么答案就是$A_{1}*A_{2}*A_{3}*A_{4}$。$A_{i}$为选出的第$i$个图的最小生成树的个数。

code for problem1

#include <algorithm>

#include <vector>

class MultiplicationTable2 {

 public:

  int minimalGoodSet(const std::vector<int> &a) {

    int n2 = static_cast<int>(a.size());

    int n = 1;

    while (n * n != n2) {

      ++n;

    }

    std::vector<std::vector<int>> g(n, std::vector<int>(n));

    auto Compute = [&](int x) {

      if (g[x][x] == x) {

        return 1;

      }

      std::vector<int> s;

      std::vector<bool> h(n);

      s.push_back(x);

      h[x] = true;

      while (true) {

        bool ok = true;

        std::vector<int> ns = s;

        for (size_t i = 0; i < s.size(); ++i) {

          for (size_t j = 0; j < s.size(); ++j) {

            int k = g[s[i]][s[j]];

            if (!h[k]) {

              h[k] = true;

              ns.push_back(k);

              ok = false;

            }

          }

        }

        if (ok) {

          break;

        }

        s = ns;

      }

      return static_cast<int>(s.size());

    };

    for (int i = 0; i < n; ++i) {

      for (int j = 0; j < n; ++j) {

        g[i][j] = a[i * n + j];

      }

    }

    int result = n;

    for (int i = 0; i < n; ++i) {

      result = std::min(result, Compute(i));

    }

    return result;

  }

};

code for problem2

#include <string>

#include <vector>

constexpr int kMaxN = 10;

struct UnionSet {

  int a[kMaxN];

  int cnt;

  int n;

  void Init(int n) {

    this->n = n;

    for (int i = 0; i < n; ++i) {

      a[i] = i;

    }

    cnt = 0;

  }

  int Get(int x) {

    if (a[x] != x) {

      a[x] = Get(a[x]);

    }

    return a[x];

  }

  bool Update(int x, int y) {

    x = Get(x);

    y = Get(y);

    if (x == y) {

      return false;

    }

    if (x < y) {

      a[y] = x;

    } else {

      a[x] = y;

    }

    ++cnt;

    return true;

  }

  bool OK() { return cnt == n - 1; }

};

int n, m;

std::vector<int> a, b;

bool Check(UnionSet s, int id) {

  if (s.OK()) {

    return 1;

  }

  if (id >= m) {

    return 0;

  }

  for (int i = id; i < m && !s.OK(); ++i) {

    s.Update(a[i], b[i]);

  }

  return s.OK();

}

bool Dfs(int id, UnionSet s1, UnionSet s2) {

  if (s1.OK() && s2.OK()) {

    return 1;

  }

  if (s1.OK()) {

    return Check(s2, id);

  }

  if (s2.OK()) {

    return Check(s1, id);

  }

  if (!Check(s1, id) || !Check(s2, id)) {

    return false;

  }

  if (id >= m) {

    return false;

  }

  while (id < m) {

    if (s1.Get(a[id]) != s1.Get(b[id])) {

      UnionSet new_s1 = s1;

      new_s1.Update(a[id], b[id]);

      if (Dfs(id + 1, new_s1, s2)) {

        return 1;

      }

    }

    s2.Update(a[id], b[id]);

    ++id;

  }

  return false;

}

class FoxAirline2 {

 public:

  std::string isPossible(int node_number, const std::vector<int> &ea,

                         const std::vector<int> &eb) {

    n = node_number;

    a = ea;

    b = eb;

    m = static_cast<int>(a.size());

    UnionSet s1, s2;

    s1.Init(n);

    s2.Init(n);

    if (Dfs(0, s1, s2)) {

      return "Possible";

    }

    return "Impossible";

  }

};

code for problem3

#include <cstdlib>

#include <ctime>

#include <unordered_map>

#include <vector>

class MSTCounter {

 public:

  static int Pow(long long a, int b, int mod) {

    long long result = 1;

    while (b > 0) {

      if (b % 2 == 1) {

        result = result * a % mod;

      }

      a = a * a % mod;

      b /= 2;

    }

    return static_cast<int>(result);

  }

  static int Solver(const std::vector<std::vector<bool>> &g, int mod) {

    int n = static_cast<int>(g.size());

    std::vector<std::vector<int>> a(n, std::vector<int>(n));

    for (int i = 0; i < n; ++i) {

      for (int j = 0; j < n; ++j) {

        if (i != j && g[i][j]) {

          a[i][j] = mod - 1;

          a[i][i] += 1;

        }

      }

    }

    bool tag = false;

    for (int i = 1; i < n; ++i) {

      int k = 0;

      for (int j = i; j < n; ++j) {

        if (a[j][i] != 0) {

          k = j;

          break;

        }

      }

      if (i != k) {

        tag = !tag;

        std::swap(a[i], a[k]);

      }

      for (int j = i + 1; j < n; ++j) {

        long long t = 1ll * a[j][i] * Pow(a[i][i], mod - 2, mod) % mod;

        for (int k = i; k < n; ++k) {

          a[j][k] = static_cast<int>(mod - t * a[i][k] % mod + a[j][k]) % mod;

        }

      }

    }

    long long result = 1;

    for (int i = 1; i < n; ++i) {

      result = result * a[i][i] % mod;

    }

    if (tag) {

      result = mod - result;

    }

    return static_cast<int>(result);

  }

};

static constexpr int kMod = 1000000007;

static constexpr int kNode = 12;

static constexpr int kSampleNumber = 1024;

struct Graph {

  std::vector<std::vector<bool>> g;

  int result;

  void Construct() {

    g.resize(kNode);

    for (int i = 0; i < kNode; ++i) {

      g[i].resize(kNode);

    }

    for (int i = 0; i < kNode; ++i) {

      for (int j = i + 1; j < kNode; ++j) {

        bool t = (std::rand() & 1) == 1;

        g[i][j] = g[j][i] = t;

      }

    }

    result = MSTCounter::Solver(g, kMod);

  }

  void GetResult(int n, int start, std::vector<int> *result) {

    for (int i = 0; i < kNode; ++i) {

      for (int j = i + 1; j < kNode; ++j) {

        if (g[i][j]) {

          int u = i + start;

          int v = j + start;

          result->push_back(u * n + v);

        }

      }

    }

  }

};

Graph graph[kSampleNumber];

class InverseMatrixTree {

 public:

  std::vector<int> constructGraph(int r) {

    if (r == 0) {

      return {2};

    }

    std::srand(std::time(nullptr));

    for (int i = 0; i < kSampleNumber; ++i) {

      graph[i].Construct();

    }

    std::unordered_map<int, std::pair<int, int>> mapper;

    for (int i = 0; i < kSampleNumber; ++i) {

      for (int j = i; j < kSampleNumber; ++j) {

        int key =

            static_cast<int>(1ll * graph[i].result * graph[j].result % kMod);

        if (key != 0) {

          mapper[key] = {i, j};

        }

      }

    }

    for (const auto &e : mapper) {

      int key0 = e.first;

      int key1 = static_cast<int>(1ll * r *

                                  MSTCounter::Pow(key0, kMod - 2, kMod) % kMod);

      if (mapper.count(key1)) {

        int t[4] = {e.second.first, e.second.second, mapper[key1].first,

                    mapper[key1].second};

        int n = kNode * 4;

        std::vector<int> result = {n};

        for (int i = 0; i < 4; ++i) {

          graph[t[i]].GetResult(n, kNode * i, &result);

          if (i > 0) {

            int u = kNode * i;

            int v = u - 1;

            result.push_back(u * n + v);

          }

        }

        return result;

      }

    }

    return {};

  }

};

参考

http://uoj.ac/problem/75

http://vfleaking.blog.uoj.ac/blog/180

巴特西

topcoder srm 685 div1

最新文章

热门文章