Problem A. 序列

对于操作$2$,会构成若干个联通块,联通块的内部存在以下性质:

  • 在满足一联通块内所有节点的和不变的情况下,每个节点可以随意修改。

满足这个性质就意味着我们只需要让对应的联通块的和相同即可。

对于操作$1$,考虑在连通块之间建边,然后构成的图存在以下两种情况

  • 生成图为二分图,那么在满足左右两边点集和的差值不变的情况下随意修改。
  • 生成图不为二分图,在满足总点集和的奇偶性不变的情况下随意修改

时间复杂度 $O(n)$

#include <bits/stdc++.h>
using namespace std;
template <class T>
void chkmax(T& x, T y) {
  x = x > y ? x : y;
}
template <class T>
void chkmin(T& x, T y) {
  x = x < y ? x : y;
}
const int N = 1e5 + 5; 
struct DSU {
  int p[N], n; 
  long long sum[2][N];
  void init(int x) {
    n = x; 
    for (int i = 1; i <= n; i++) {
      p[i] = i, sum[0][i] = sum[1][i] = 0;
    }
  }
  int get(int x) {
    return x == p[x] ? x : p[x] = get(p[x]);
  }
  void merge(int x, int y) {
    p[x] = y, sum[0][y] += sum[0][x], sum[1][y] += sum[1][x];
  }
} dsu;
int n, m, tot;
bool ntBip;
pair<int, int> opt[N];
vector<int> g[N];
int sum[2][2];
int col[N], a[N], b[N];
void init() {
  tot = 0;
  dsu.init(n);
  for (int i = 1; i <= n; i++) {
    g[i].clear(), col[i] = -1;
  }
}
void dfs(int u, int c) {
  col[u] = c, sum[0][c] += dsu.sum[0][u], sum[1][c] += dsu.sum[1][u];
  for (auto v : g[u]) {
    if (col[v] == -1) {
      dfs(v, c ^ 1);
    } else if (col[v] != (c ^ 1)) {
      ntBip = 1;
    }
  }
}
void solve() {
  cin >> n >> m; 
  init();
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    dsu.sum[0][i] = a[i];
  }
  for (int i = 1; i <= n; i++) {
    cin >> b[i];
    dsu.sum[1][i] = b[i];
  }
  for (int i = 1; i <= m; i++) {
    int type, x, y; 
    cin >> type >> x >> y; 
    if (type == 1) {
      opt[++tot] = make_pair(x, y);
    } else {
      int ap1 = dsu.get(x), ap2 = dsu.get(y);
      if (ap1 != ap2) {
        dsu.merge(ap1, ap2);
      }
    }
  }
  for (int i = 1; i <= tot; i++) {
    int u = dsu.get(opt[i].first), v = dsu.get(opt[i].second); 
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= n; i++) {
    if (dsu.get(i) == i && col[i] == -1) {
      ntBip = 0;
      memset(sum, 0, sizeof sum);
      dfs(i, 0);
      if (ntBip && (sum[0][0] + sum[0][1]) % 2 != (sum[1][0] + sum[1][1]) % 2) {
        cout << "NO" << '\n';
        return;
      } else if (!ntBip && sum[0][0] - sum[1][0] != sum[0][1] - sum[1][1]) {
        cout << "NO" << '\n';
        return;
      }
    }
  }
  cout << "YES" << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t; 
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

Problem B. 冒泡排序

定义$cnt_i$为$\sum_{j=1}^{i-1}[a_j>a_i]$

逆序对总个数就是$\sum cnt_i$

考虑修改,只需要根据前后两个数的大小进行分类讨论即可。

考虑查询,每一次冒泡排序后会将前面的一个最大值转移到最后。

所以所有的$cnt_i$都会$-1$,查询的答案就是$\sum_{k\leq c_i}(c_i-k)$

时间复杂度 $O((n+m)Log_2 n)$

#include <bits/stdc++.h>
using namespace std;
template <class T>
void chkmax(T& x, T y) {
  x = x > y ? x : y;
}
template <class T>
void chkmin(T& x, T y) {
  x = x < y ? x : y;
}
template <class T>
void read(T& x) {
  x = 0; char ch = 0; int f = 1;
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
  x *= f;
}
template <class T>
void write(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + 48);
}
template <class T>
void writeln(T x) {
  write(x), puts("");
}
const int N = 2e5 + 5;
template <class T> 
struct Fenwick {
  T tr[N], n;
  void init(int x) {
    n = x; 
    memset(tr, 0, sizeof tr);
  }
  void modify(int p, T v) {
    if (!p) {
      return;
    }
    for (; p <= n; p += p & -p) {
      tr[p] += v; 
    }
  }
  T query(int p) {
    T res = 0;
    for (; p; p -= p & -p) {
      res += tr[p];
    }
    return res;
  } 
  T query(int l, int r) {
    return query(r) - query(l - 1);
  }
};
Fenwick<long long> bit, bit2;
int n, m;
int a[N];
long long cnt[N];
int main() {
  read(n), read(m);
  bit.init(n);
  for (int i = 1; i <= n; i++) {
    read(a[i]);
    cnt[i] = i - 1 - bit.query(a[i]);
    bit.modify(a[i], 1);
  }
  bit.init(n), bit2.init(n);
  for (int i = 1; i <= n; i++) {
    bit.modify(cnt[i], 1);
    bit2.modify(cnt[i], cnt[i]);
  }
  for (int i = 1; i <= m; i++) {
    int type, c; 
    read(type), read(c);
    c = min(c, n);
    if (type == 1) {
      if (a[c] < a[c + 1]) {
        bit.modify(cnt[c], -1), bit2.modify(cnt[c], -cnt[c]);
        swap(a[c], a[c + 1]), swap(cnt[c], cnt[c + 1]);
        cnt[c + 1]++;
        bit.modify(cnt[c + 1], 1), bit2.modify(cnt[c + 1], cnt[c + 1]);
      } else {
        bit.modify(cnt[c + 1], -1), bit2.modify(cnt[c + 1], -cnt[c + 1]);
        swap(a[c], a[c + 1]), swap(cnt[c], cnt[c + 1]);
        cnt[c]--;
        bit.modify(cnt[c], 1), bit2.modify(cnt[c], cnt[c]);
      }
    } else {
      writeln(bit2.query(c + 1, n) - bit.query(c + 1, n) * c);
    }
  }
  return 0;
}

Problem C. 最小环

对于一次询问$k$,我们会得到一个环

$$tk \equiv 0(\mod n)$$

最小解显然是$\frac n{gcd(n,k)}$,这就意味着查询的是一个长度为$\frac n{gcd(n,k)}$。

因此考虑枚举环长,预处理答案。

对$a_i$排序后,我们生成环的方法是奇偶分组后大和大相连,小和小相连。

考虑多组,结论是从小到大连续分组。

时间复杂度 $O(nd(n))$

#include <bits/stdc++.h>
using namespace std;
template <class T>
void chkmax(T& x, T y) {
  x = x > y ? x : y;
}
template <class T>
void chkmin(T& x, T y) {
  x = x < y ? x : y;
}
template <class T>
void read(T& x) {
  x = 0; char ch = 0; int f = 1;
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
  x *= f;
}
template <class T>
void write(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + 48);
}
template <class T>
void writeln(T x) {
  write(x), puts("");
}
const int N = 2e5 + 5;
int n, m; 
long long a[N], ans[N];
long long calc(int len) {
  long long res = 0;
  for (int i = 1; i <= n; i += len) {
    int j, lst = 0;
    for (j = i; j <= i + len - 1; j += 2) {
      if (!lst) {
        lst = a[j];
      } else {
        res += lst * a[j], lst = a[j];
      }
    }
    j -= 2;
    if (j + 1 <= i + len - 1) {
      j++;
    } else {
      j--;
    }
    for (; j >= i; j -= 2) {
      res += lst * a[j], lst = a[j];
    }
    j += 2;
    res += a[j] * a[i];
  }
  return res;
}
int gcd(int n, int m) {
  return !m ? n : gcd(m, n % m);
}
int main() {
  read(n), read(m);
  for (int i = 1; i <= n; i++) {
    read(a[i]);
  }
  sort(a + 1, a + 1 + n);
  for (int i = 1; i <= n; i++) {
    ans[0] += a[i] * a[i];
  }
  for (int i = 1; i <= n; i++) {
    if (n % i == 0) {
      ans[i] = calc(i);
    }
  }
  while (m--) {
    int k; 
    read(k);
    if (!k) {
      writeln(ans[0]);
    } else {
      writeln(ans[n / gcd(n, k)]);
    }
  }
  return 0; 
} 
最后修改:2020 年 03 月 09 日 10 : 41 AM
如果觉得我的文章对你有用,请随意赞赏