试图写一篇很离谱的解法求条
  • 板块P1001 A+B Problem
  • 楼主goodzsq
  • 当前回复2
  • 已保存回复2
  • 发布时间2025/8/31 22:09
  • 上次更新2025/9/1 00:06:47
查看原帖
试图写一篇很离谱的解法求条
1342104
goodzsq楼主2025/8/31 22:09
#include <algorithm>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

struct Num {
  int v;
  Num(int x) : v(x) {}
};

int add_seq(int a, int b) {
  int r = a + b;
  return r;
}

int add_branch(int a, int b) {
  if (a >= 0 && b >= 0)
    return a + b;
  else if (a < 0 && b < 0)
    return -((-a) + (-b));
  else
    return (a > 0) ? (a - (-b)) : (b - (-a));
}

int add_loop(int a, int b) {
  int r = a;
  int s = b > 0 ? 1 : -1;
  for (int i = 0; i < abs(b); i++)
    r += s;
  return r;
}

int add_array(int a, int b) {
  int arr[2] = {a, b};
  return arr[0] + arr[1];
}

int add_string(int a, int b) {
  return stoi(to_string(a)) + stoi(to_string(b));
}

int add_struct(Num a, Num b) {
  return a.v + b.v;
}

int add_recur(int a, int b) {
  if (b == 0)
    return a;
  return (b > 0) ? add_recur(a + 1, b - 1) : add_recur(a - 1, b + 1);
}

int add_bit(int a, int b) {
  while (b) {
    int c = a & b;
    a ^= b;
    b = c << 1;
  }
  return a;
}

int add_dp(int a, int b) {
  vector<int> dp(abs(b) + 1);
  dp[0] = a;
  for (int i = 1; i <= abs(b); i++)
    dp[i] = dp[i - 1] + (b > 0 ? 1 : -1);
  return dp[abs(b)];
}

int add_bfs(int a, int b) {
  queue<pair<int, int>> q;
  int s = b > 0 ? 1 : -1;
  q.push({a, abs(b)});
  while (!q.empty()) {
    auto p = q.front();
    q.pop();
    if (p.second == 0)
      return p.first;
    q.push({p.first + s, p.second - 1});
  }
  return a;
}

int add_dfs(int a, int b) {
  if (b == 0)
    return a;
  return add_dfs(a + (b > 0 ? 1 : -1), b - (b > 0 ? 1 : -1));
}

int add_trie(int a, int b) {
  struct Trie {
    struct Node {
      int v;
      Node* c[2];
      Node() : v(0) { c[0] = c[1] = nullptr; }
    };
    Node* root;
    Trie() { root = new Node(); }
    void ins(int x) {
      Node* n = root;
      string s = to_string(x);
      for (char ch : s) {
        int i = ch - '0';
        if (!n->c[i % 2])
          n->c[i % 2] = new Node();
        n = n->c[i % 2];
      }
      n->v = x;
    }
    int get(int x) {
      Node* n = root;
      string s = to_string(x);
      for (char ch : s) {
        int i = ch - '0';
        if (!n->c[i % 2])
          return 0;
        n = n->c[i % 2];
      }
      return n->v;
    }
  };
  Trie t;
  t.ins(a);
  t.ins(b);
  return t.get(a) + t.get(b);
}

int add_kmp(int a, int b) {
  string s = to_string(b);
  int n = s.size();
  vector<int> lps(n, 0);
  for (int i = 1, len = 0; i < n;) {
    if (s[i] == s[len])
      lps[i++] = ++len;
    else if (len)
      len = lps[len - 1];
    else
      lps[i++] = 0;
  }
  int r = a;
  int step = b > 0 ? 1 : -1;
  for (int i = 0; i < abs(b); i++)
    r += step;
  return r;
}

int add_z(int a, int b) {
  string s = to_string(a) + "+" + to_string(b);
  int n = s.size();
  vector<int> z(n, 0);
  for (int i = 1, l = 0, r = 0; i < n; i++) {
    if (i <= r)
      z[i] = min(r - i + 1, z[i - l]);
    while (i + z[i] < n && s[z[i]] == s[i + z[i]])
      z[i]++;
    if (i + z[i] - 1 > r)
      l = i, r = i + z[i] - 1;
  }
  return a + b;
}

int add_graph(int a, int b) {
  map<int, set<int>> g;
  int step = b > 0 ? 1 : -1;
  for (int i = 0; i <= abs(b); i++) {
    int u = a + step * i;
    int v = a + step * (i + 1);
    g[u].insert(v);
  }
  int curr = a;
  for (int i = 0; i < abs(b); i++)
    curr = *g[curr].begin();
  return curr;
}

int add_mst(int a, int b) {
  vector<pair<int, pair<int, int>>> edges;
  int step = b > 0 ? 1 : -1;
  for (int i = 0; i < abs(b); i++) {
    int u = a + step * i;
    int v = a + step * (i + 1);
    edges.push_back({1, {u, v}});
  }
  sort(edges.begin(), edges.end());
  map<int, int> parent;
  function<int(int)> find = [&](int x) {
    if (!parent.count(x))
      parent[x] = x;
    return parent[x] == x ? x : parent[x] = find(parent[x]);
  };
  int total = 0;
  for (auto& e : edges) {
    int w = e.first, u = e.second.first, v = e.second.second;
    if (find(u) != find(v)) {
      parent[find(u)] = find(v);
      total += w;
    }
  }
  return a + b;
}

int add_lagrange(int a, int b) {
  double x0 = 0, y0 = a, x1 = 1, y1 = a + 1;
  double res = y0 * (b - x1) / (x0 - x1) + y1 * (b - x0) / (x1 - x0);
  return round(res);
}

int add_sa(int a, int b) {
  string s = to_string(a) + to_string(b);
  int n = s.size();
  vector<int> sa(n), rk(n), tmp(n), cnt(128, 0);
  for (int i = 0; i < n; i++)
    cnt[s[i]]++;
  for (int i = 1; i < 128; i++)
    cnt[i] += cnt[i - 1];
  for (int i = n - 1; i >= 0; i--)
    sa[--cnt[s[i]]] = i;
  rk[sa[0]] = 0;
  int k = 0;
  while (k < n) {
    int num = 0;
    for (int i = n - k; i < n; i++)
      tmp[num++] = i;
    for (int i = 0; i < n; i++)
      if (sa[i] >= k)
        tmp[num++] = sa[i] - k;
    fill(cnt.begin(), cnt.end(), 0);
    for (int i = 0; i < n; i++)
      cnt[rk[i]]++;
    for (int i = 1; i < n; i++)
      cnt[i] += cnt[i - 1];
    for (int i = n - 1; i >= 0; i--)
      sa[--cnt[rk[tmp[i]]]] = tmp[i];
    swap(rk, tmp);
    rk[sa[0]] = 0;
    num = 1;
    for (int i = 1; i < n; i++) {
      rk[sa[i]] =
          (tmp[sa[i - 1]] == tmp[sa[i]] && tmp[sa[i - 1] + k] == tmp[sa[i] + k])
              ? num - 1
              : num++;
    }
    if (num == n)
      break;
    k = k ? k * 2 : 1;
  }
  return a + b;
}

int main() {
  int a, b;
  cin >> a >> b;

  int c = add_seq(a, b) + add_branch(a, b) + add_loop(a, b) + add_array(a, b) +
          add_string(a, b) + add_struct(Num(a), Num(b)) + add_recur(a, b) +
          add_bit(a, b) + add_dp(a, b) + add_bfs(a, b) + add_dfs(a, b) +
          add_trie(a, b) + add_kmp(a, b) + add_z(a, b) + add_graph(a, b) +
          add_mst(a, b) + add_lagrange(a, b) + add_sa(a, b);
  c /= 18;
  cout << c << endl;
  return 0;
}

2025/8/31 22:09
加载中...