Problem A. 某种密码

考虑折半搜索即可。

/*
 * Author: chhokmah
 * Date: 2020-08-29 21:37:31
 */
#include <bits/stdc++.h>

using namespace std;

int n, m;
int a[45];
map<long long, int> mp;
long long ans;

void dfs(int l, int r, long long sum) {
  if (l > r) {
    mp[sum]++;
    return;
  }
  dfs(l + 1, r, sum + a[l]);
  dfs(l + 1, r, sum);
}

void Dfs(int l, int r, long long sum) {
  if (l > r) {
    ans += mp[m - sum];
    return;
  }
  Dfs(l + 1, r, sum + a[l]);
  Dfs(l + 1, r, sum);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    cin >> a[i];
  dfs(1, n / 2, 0);
  Dfs(n / 2 + 1, n, 0);
  cout << ans << '\n';
  return 0;
}

Problem B. 还教室

线段树维护区间平方和、区间和即可。

代码处理稍微有一点问题,要开 __int128_t 才能过。

/*
 * Author: chhokmah
 * Date: 2020-08-29 21:43:38
 */
#include <bits/stdc++.h>

using namespace std;

template <typename T>
void read(T& x) {
  x = 0;
  int c = 0, f = 0;
  for (; !isdigit(c); c = getchar()) f |= c == '-';
  for (; isdigit(c); c = getchar()) x = x * 10 + (c & 15);
  x = f ? -x : x;
}

template <typename T>
void write(T x) {
  if (x < 0)
    putchar('-'), x = -x;
  if (x > 9)
    write(x / 10);
  putchar(x % 10 + '0');
}

const int N = 1e5 + 5;

int n, m;
__int128_t a[N];

__int128_t gcd(__int128_t a, __int128_t b) {
  return !b ? a : gcd(b, a % b);
}

struct Node {
  __int128_t sum;
  __int128_t sumSq;
  __int128_t tag;
} seg[N << 2];

struct Frac {
  __int128_t x, y;

  Frac() {}

  Frac(__int128_t a, __int128_t b) {
    __int128_t g = gcd(a, b);
    x = (__int128_t)(a / g), y = (__int128_t)(b / g);
  }

  friend Frac operator+(Frac lhs, Frac rhs) {
    return Frac(lhs.x * rhs.y + lhs.y * rhs.x, lhs.y * rhs.y);
  }

  friend Frac operator-(Frac lhs, Frac rhs) {
    return Frac(lhs.x * rhs.y - lhs.y * rhs.x, lhs.y * rhs.y);
  }

  friend Frac operator*(Frac lhs, Frac rhs) {
    return Frac(lhs.x * rhs.x, lhs.y * rhs.y);
  }

  friend Frac operator*(Frac lhs, __int128_t v) {
    return Frac(lhs.x * v, lhs.y);
  }

  friend Frac operator/(Frac lhs, Frac rhs) {
    return Frac(lhs.x * rhs.y, lhs.y * rhs.x);
  }

  friend Frac operator/(Frac lhs, __int128_t v) {
    return Frac(lhs.x, lhs.y * v);
  }
};

Node operator+(Node lhs, Node rhs) {
  Node res;
  res.sum = lhs.sum + rhs.sum;
  res.sumSq = lhs.sumSq + rhs.sumSq;
  return res;
}

void build(int p, int l, int r) {
  if (l == r) {
    seg[p].sum = a[l];
    seg[p].sumSq = a[l] * a[l];
    return;
  }
  int mid = l + r >> 1;
  build(p << 1, l, mid);
  build(p << 1 | 1, mid + 1, r);
  seg[p] = seg[p << 1] + seg[p << 1 | 1];
}

void pushDown(int p, int l, int r) {
  if (seg[p].tag != 0) {
    int mid = l + r >> 1;
    seg[p << 1].sumSq += seg[p].tag * 2 * seg[p << 1].sum + seg[p].tag * seg[p].tag * (mid - l + 1);
    seg[p << 1 | 1].sumSq += seg[p].tag * 2 * seg[p << 1 | 1].sum + seg[p].tag * seg[p].tag * (r - mid);
    seg[p << 1].sum += seg[p].tag * (mid - l + 1);
    seg[p << 1 | 1].sum += seg[p].tag * (r - mid);
    seg[p << 1].tag += seg[p].tag;
    seg[p << 1 | 1].tag += seg[p].tag;
    seg[p].tag = 0;
  }
}

void modify(int p, int l, int r, int ql, int qr, __int128_t d) {
  if (ql <= l && r <= qr) {
    seg[p].sumSq += d * 2 * seg[p].sum + d * d * (r - l + 1);
    seg[p].sum += d * (r - l + 1);
    seg[p].tag += d;
    return;
  }
  pushDown(p, l, r);
  int mid = l + r >> 1;
  if (ql <= mid)
    modify(p << 1, l, mid, ql, qr, d);
  if (qr > mid)
    modify(p << 1 | 1, mid + 1, r, ql, qr, d);
  seg[p] = seg[p << 1] + seg[p << 1 | 1];
}

__int128_t querySum(int p, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr)
    return seg[p].sum;
  pushDown(p, l, r);
  int mid = l + r >> 1;
  __int128_t res = 0;
  if (ql <= mid)
    res += querySum(p << 1, l, mid, ql, qr);
  if (qr > mid)
    res += querySum(p << 1 | 1, mid + 1, r, ql, qr);
  return res;
}

__int128_t querySumSq(int p, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr)
    return seg[p].sumSq;
  pushDown(p, l, r);
  int mid = l + r >> 1;
  __int128_t res = 0;
  if (ql <= mid)
    res += querySumSq(p << 1, l, mid, ql, qr);
  if (qr > mid)
    res += querySumSq(p << 1 | 1, mid + 1, r, ql, qr);
  return res;
}

int main() {
  read(n), read(m);
  for (int i = 1; i <= n; i++)
    read(a[i]);
  build(1, 1, n);
  int opt, l, r;
  __int128_t d;
  for (int i = 1; i <= m; i++) {
    read(opt), read(l), read(r);
    if (opt == 1) {
      read(d);
      modify(1, 1, n, l, r, d);
    } else if (opt == 2) {
      Frac ave(querySum(1, 1, n, l, r), r - l + 1);
      if (ave.x == 0)
        puts("0/1");
      else
        write(ave.x), putchar('/'), write(ave.y), puts("");
    } else {
      Frac ave(querySum(1, 1, n, l, r), r - l + 1);
      Frac v2 = ave / (r - l + 1) * querySum(1, 1, n, l, r) * 2;
      Frac v3(querySumSq(1, 1, n, l, r), r - l + 1);
      Frac ans = ave * ave - v2 + v3;
      if (ans.x == 0)
        puts("0/1");
      else
        write(ans.x), putchar('/'), write(ans.y), puts("");
    }
  }
  return 0;
}

Problem C. 交通

每一个西边的点到东边的点一定是连续的一段,所以缩点后搜索即可。

不知道一般化问题有没有多项式复杂度解法。

/*
 * Author: chhokmah
 * Date: 2020-08-29 23:07:06
 */
#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 5;

struct Point {
  int x, y, id;
} p[N];

vector<int> g[N], gn[N];

int tin[N], low[N], bel[N], stk[N];
bool inStack[N];
int dfc, scc, top;
int n, m, a, b;
vector<int> west, east;

void tarjan(int u) {
  if (p[u].x == a)
    east.emplace_back(u);
  tin[u] = low[u] = ++dfc;
  inStack[u] = 1;
  stk[++top] = u;
  for (auto v : g[u]) {
    if (!tin[v]) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    } else if (inStack[v]) {
      low[u] = min(low[u], tin[v]);
    }
  }
  if (tin[u] == low[u]) {
    scc++;
    int v = 0;
    do {
      v = stk[top--];
      inStack[v] = 0;
      bel[v] = scc;
    } while (v != u);
  }
}

int mx[N], mi[N];
int ans[N];
bool vis[N];

void dfs(int u) {
  if (vis[u])
    return;
  vis[u] = 1;
  for (auto v : gn[u]) {
    dfs(v);
    mx[u] = max(mx[u], mx[v]);
    mi[u] = min(mi[u], mi[v]);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> a >> b;
  for (int i = 1; i <= n; i++) {
    cin >> p[i].x >> p[i].y;
    p[i].id = i;
    if (p[i].x == 0)
      west.emplace_back(i);
  }
  sort(west.begin(), west.end(), [&](int lhs, int rhs) {
    return p[lhs].y > p[rhs].y;
  });
  for (int i = 1, u, v, k; i <= m; i++) {
    cin >> u >> v >> k;
    g[u].emplace_back(v);
    if (k == 2)
      g[v].emplace_back(u);
  }
  for (auto i : west)
    if (!tin[i])
      tarjan(i);
  sort(east.begin(), east.end(), [&](int lhs, int rhs) {
    return p[lhs].y < p[rhs].y;
  });
  for (int u = 1; u <= n; u++)
    for (auto v : g[u])
      if (bel[u] != bel[v])
        gn[bel[u]].emplace_back(bel[v]);
  for (int i = 1; i <= scc; i++)
    mx[i] = 0, mi[i] = 1e9;
  for (int i = 0; i < (int)east.size(); i++) {
    mx[bel[east[i]]] = max(mx[bel[east[i]]], i);
    mi[bel[east[i]]] = min(mi[bel[east[i]]], i);
  }
  for (auto i : west) {
    dfs(bel[i]);
    cout << max(0, mx[bel[i]] - mi[bel[i]] + 1) << '\n';
  }
  return 0;
}
最后修改:2020 年 08 月 30 日 07 : 36 PM
如果觉得我的文章对你有用,请随意赞赏