danihao123's Blog

给你一棵\(n\)个点的树，要求你滋磁以下操作（共\(m\)次）：

• 对于给定的点对\((x, y)\)和\((u, v)\)，删除边\((x, y)\)，添加边\((u, v)\)。保证操作时\((u, v)\)存在，并且保证操作后的图还是一棵树。
• 向集合\(S\)中加入一个点对\((u, v)\)。
• 从\(S\)中删除一个点对。
• 给定一条边\((x, y)\)（保证在当前树中存在），求问是否所有\((u, v)\in S\)都满足\(u\)到\(v\)的路径经过了\((x, y)\)。

\(1\leq n\leq 10^5, 1\leq m\leq 300000\)。

一张\(n\)个点的图，初始没边，然后要求你支持以下操作：

• 给定\((x, y)\)，在\(x\)和\(y\)两点间添加一条长度为\(i\)的边（假设这是第\(i\)次操作）。
• 给定\(k\)，删除当前图中边权最大的\(k\)条边。
• 撤销上一次操作。保证存在上一次操作且不是撤销操作。

共\(m\)次操作，每次操作后输出当前图最小生成树的边权和（不存在的话输出\(0\)）。

\(1\leq n\leq 300000, 1\leq m\leq 500000\)。

给你一个集合\(S\)（保证其中元素都为小于\(n\)的自然数），定义一棵合法的树为一棵编号满足堆的性质，且非叶子节点都一定有两个可能非叶子的儿子，同时有\(c(c\in S)\)个一定为叶子的儿子。对于所有\(i = 1\ldots n\)，求有多少大小为\(i\)的形态不同的合法的树。

\(n\leq 200000\)。

啊啊啊爽到力，，，

过去太池沼力，没有做出来惹。现在看了看可能比较简单罢……

定义状态\(d_{i, S}\)表示当前已经被覆盖的点集为\(S\)，然后当前的生成树已经考虑到了第\(i\)层，转移看起来很毒……

所以预处理一个点集到另一个点集只走一步边来扩展，最优解是多少，然后转移就方便力……

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
const int maxn = 12;
int G[15][15];
const int INF = 0x3f3f3f3f;
void add_edge(int u, int v, int d) {
  G[u][v] = std::min(G[u][v], d);
  G[v][u] = std::min(G[v][u], d);
}

int n;
int g1[(1 << maxn)][15], g2[(1 << maxn)][(1 << maxn)];
void process() {
  for(int s = 1; s < (1 << n); s ++) {
    for(int i = 1; i <= n; i ++) {
      g1[s][i] = INF;
      for(int j = 0; j < n; j ++) {
        if((1 << j) & s) {
          g1[s][i] = std::min(g1[s][i], G[j + 1][i]);
        }
      }
    }
  }
  for(int s = 1; s < (1 << n); s ++) {
    int k = (1 << n) - 1; k = k & (~s);
    for(int t = k; t > 0; t = (t - 1) & k) {
      g2[s][t] = 0;
      for(int i = 1; i <= n; i ++) {
        if((1 << (i - 1)) & t) {
          if(g1[s][i] == INF) {
            g2[s][t] = INF; break;
          }
          g2[s][t] += g1[s][i];
        }
      }
    }
  }
}

using ll = long long;
ll d[14][(1 << maxn)];
ll dp() {
  for(int s = 0; s < (1 << n); s ++) {
    d[1][s] = INF;
  }
  for(int i = 0; i < n; i ++) {
    d[1][(1 << i)] = 0;
  }
  for(int i = 2; i <= n; i ++) {
    for(int s = 1; s < (1 << n); s ++) {
      d[i][s] = INF;
      for(int t = (s - 1) & s; t != 0; t = (t - 1) & s) {
        d[i][s] = std::min(d[i][s], d[i - 1][t] + (ll(i - 1)) * g2[t][s ^ t]);
      }
    }
  }
  ll ans = INF;
  for(int i = 1; i <= n; i ++) {
    ans = std::min(ans, d[i][(1 << n) - 1]);
  }
  return ans;
}

int main() {
  memset(G, 0x3f, sizeof(G));
  int m; scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i ++) {
    int u, v, w; scanf("%d%d%d", &u, &v, &w);
    add_edge(u, v, w);
  }
  process(); printf("%lld\n", dp());
  return 0;
}

ETT野蛮，LCT文明，，，

换生长结点这个操作非常的麻烦。所以考虑给每个生长操作建立一个虚点，每个实点（就是在树中真实存在的点）向他之前最晚建立的一个虚点认父。

然后虚点初始的时候应该向上一次的那个虚点认父（我们可以近似的认为第一个虚点就是1）。然后我们用类似于扫描线的做法，等到了虚点存在的区间里就把它爸爸改成相应的实点，出去了相应区间之后就再改回来。这样这题就很好做了，我们认为虚点点权为0，实点点权为1，然后查询就好做了。

然后还有一点细节问题……比如说换生长结点的时候如何处理x在某一棵树里不存在的情况。但这个不难处理，因为同一个编号的结点一定分布编号连续的一段树里，所以真实起作用的操作范围可以认定为数据给出的操作范围和x的分布区间的交。

再有一点就是查询的时候……如果直接查询两点间splay的和的话，可能会忽略掉一些本来在原图上该有的实点。所以我们要求两点到根的距离，再用LCA去掉不需要的。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <vector>
#include <utility>
const int maxn = 100005;
const int maxm = 200005;
const int maxs = maxm + maxm;
struct Node {
  Node *fa, *ch[2];
  int val, sumv;
  bool rev;
  int d() {
    return ((this == fa -> ch[1]) ? 1 : 0);
  }
  void sc(Node *c, int dir) {
    ch[dir] = c;
    c -> fa = this;
  }
  void maintain() {
    sumv = ch[0] -> sumv + ch[1] -> sumv + val;
  }
  void paint() {
    rev = !rev;
    std::swap(ch[0], ch[1]);
  }
  void pushdown() {
    if(rev) {
      ch[0] -> paint();
      ch[1] -> paint();
      rev = false;
    }
  }
};
Node pool[maxs];
Node *nil, *cur;
void init_pool() {
  nil = cur = pool;
  nil -> val = nil -> sumv = 0;
  nil -> rev = false;
  nil -> fa = nil -> ch[0] = nil -> ch[1] = nil;
}
#define T(x) (pool + (x))
Node *refresh(Node *x, int val = 0) {
  x -> val = x -> sumv = val;
  x -> rev = false;
  x -> fa = x -> ch[0] = x -> ch[1] = nil;
  return x;
}

bool is_root(Node *x) {
  return (x -> fa == nil || (x -> fa -> ch[0] != x && x -> fa -> ch[1] != x));
}
void zig(Node *x) {
  Node *y = x -> fa; int d = x -> d();
  if(is_root(y)) {
    x -> fa = y -> fa;
  } else {
    y -> fa -> sc(x, y -> d());
  }
  y -> sc(x -> ch[1 ^ d], d);
  x -> sc(y, 1 ^ d);
  y -> maintain(); x -> maintain();
}
void splay(Node *x) {
  while(!is_root(x)) {
    Node *y = x -> fa;
    if(!is_root(y)) y -> fa -> pushdown();
    y -> pushdown(); x -> pushdown();
    if(!is_root(y)) {
      if((x -> d()) ^ (y -> d())) {
        zig(x);
      } else {
        zig(y);
      }
    }
    zig(x);
  }
  // x -> maintain();
}
Node *access(Node *x) {
  Node *nx = x, *y = nil;
  Node *ct = T(1);
  while(x != nil) {
    splay(x); x -> pushdown();
    if(x -> fa == nil) ct = x;
    x -> sc(y, 1); x -> maintain();
    y = x; x = x -> fa;
  }
  splay(nx); return ct;
}
Node *evert(Node *x) {
  access(x); x -> paint();
  return x;
}
void link(Node *x, Node *y) {
  evert(x); x -> fa = y;
}
void cut(Node *x) {
  access(x);
  x -> ch[0] -> fa = nil;
  x -> ch[0] = nil; x -> maintain();
}
void cut(Node *x, Node *y) {
  evert(x); access(y);
  int d = x -> d();
  y -> ch[d] = nil; y -> maintain();
  x -> fa = nil;
}

int ans[maxm];
using pii = std::pair<int, int>;
int n;
pii seg_and(int a, int b, int x, int y) {
  if(a > x) {
    std::swap(a, x), std::swap(b, y);
  }
  if(b < x) return std::make_pair(n + 1, n + 1);
  if(b >= y) return std::make_pair(x, y);
  return std::make_pair(x, b);
}

int ope[maxm][4];
int seg[maxm][2];
Node *bef[maxm];
std::vector<int> beg[maxn], end[maxn];
std::vector<int> query[maxn];
// #define OUTP
// #define LOCAL
int main() {
#ifdef OUTP
  freopen("forest1.in", "r", stdin);
  freopen("out", "w+", stdout);
#endif
  int m; scanf("%d%d", &n, &m);
  init_pool(); refresh(T(1), 1);
  int cnt0 = 1, cnt1 = 0, cnt2 = 0;
  Node *last1 = T(1);
  seg[1][0] = 1; seg[1][1] = n;
  for(int i = 1; i <= m; i ++) {
    scanf("%d%d%d", &ope[i][0], &ope[i][1], &ope[i][2]);
    if(ope[i][0]) {
      scanf("%d", &ope[i][3]);
    }
    if(ope[i][0] == 0) {
      int c = ++ cnt0;
      refresh(T(c), 1);
      link(last1, T(c));
      seg[c][0] = ope[i][1]; seg[c][1] = ope[i][2];
#ifdef LOCAL
      printf("Node %d : (%d, %d)\n", c, seg[c][0], seg[c][1]);
#endif
    } else if(ope[i][0] == 1) {
      Node *n1 = T(m + i);
      refresh(n1); link(n1, bef[i] = last1);
      int l = ope[i][1], r = ope[i][2], x = ope[i][3];
      auto s = seg_and(l, r, seg[x][0], seg[x][1]);
      l = s.first, r = s.second;
#ifdef LOCAL
      printf("Change : (%d, %d) -> %d\n", l, r, x);
#endif
      beg[l].push_back(i); end[r + 1].push_back(i);
      last1 = n1;
    } else {
      int x = ope[i][1], u = ope[i][2], v = ope[i][3];
      query[x].push_back(i);
    }
  }
  for(int i = 1; i <= n; i ++) {
    for(auto id : end[i]) {
      Node *n1 = T(m + id);
      cut(n1, T(ope[id][3])); link(n1, bef[id]);
    }
    for(auto id : beg[i]) {
      Node *n1 = T(m + id);
      cut(n1, bef[id]); link(n1, T(ope[id][3]));
    }
    for(auto id : query[i]) {
      int u = ope[id][2], v = ope[id][3];
      evert(T(1)); access(T(u));
      int ret = T(u) -> sumv;
      Node *lca = access(T(v));
      ret += T(v) -> sumv;
      access(lca);
      ret -= lca -> sumv;
      ret -= lca -> sumv - 1;
      ans[id] = ret - 1;
    }
  }
  for(int i = 1; i <= m; i ++) {
    if(ope[i][0] == 2) {
      printf("%d\n", ans[i]);
    }
  }
  return 0;
}

神哎……

既然与的优先级比或高，那么我们就可以用或把程序切成若干段，每一段的值决定了最后的取值。

考虑从左往右计算某一段。如果有一个手机某一段运算结果为0，那么它会继续往下运算，反之则会停止运算。

对于每一个在前\(i\)段的值都是0，然后开始跑第\(i + 1\)段的手机。他们都会额外产生\(l\)（这一段的fork个数）个手机，并且由于这些手机一被生产出来的返回值就是0，所以新的这些手机在这一段取值为0。而原来的老手机，在这一段的取值事1，于是之后的运算就不会接着做了。

这样一来，我们就可以动态维护在之前的段里的返回值全是0的手机，然后就可以做了。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
using ll = long long;
const int maxn = 100005;
const ll ha = 998244353LL;

bool op[maxn];
int main() {
  std::vector<int> vec;
  int last = 0;
  int n; scanf("%d", &n);
  for(int i = 1; i <= (n - 1); i ++) {
    char buf[5]; scanf("%s", buf);
    if(buf[0] == '|') {
      vec.push_back(i - last);
      last = i;
    }
  }
  vec.push_back(n - last);
  ll pre0 = 1LL;
  ll ans = 1LL;
  for(auto x : vec) {
    ans += (pre0 * (ll(x))) % ha; ans %= ha;
    pre0 = (pre0 * (ll(x))) % ha;
  }
  printf("%lld\n", ans);
  return 0;
}

先去考虑两个变量的sgcd怎么求……我们先求出他们的gcd，然后在除掉一个最小的质因子即可。

那么我们先把\(a_1\)分解质因数，然后所有数和它求一个gcd，然后去去掉一个尽可能小的质因子。注意到一个数\(p\)的质因子数量是\(O(\log p)\)级别的，所以每一个数找到要除的那个最小的质因子只需要\(O(\log a_1)\)的时间。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
#include <cmath>
const int maxn = 100005;
using ll = long long;
ll V[maxn]; int vcnt = 0;
void des(ll x) {
  ll m = (ll)sqrt(x + 0.5);
  for(ll i = 2; i <= m; i ++) {
    if(x % i == 0) {
      V[vcnt ++] = i;
      while(x % i == 0) x /= i;
    }
  }
  if(x > 1LL) V[vcnt ++] = x;
}
ll gcd(ll a, ll b) {
  if(!b) return a;
  else return gcd(b, a % b);
}

ll A[maxn];
int main() {
  int n; scanf("%d", &n);
  for(int i = 1; i <= n; i ++) {
    scanf("%lld", &A[i]);
  }
  des(A[1]);
  for(int i = 1; i <= n; i ++) {
    if(i > 1) putchar(' ');
    ll bs = gcd(A[i], A[1]);
    if(bs == 1) {
      printf("-1"); continue;
    }
    for(int j = 0; j < vcnt; j ++) {
      if(A[i] % V[j] == 0) {
        bs /= V[j];
        break;
      }
    }
    printf("%lld", bs);
  }
  puts("");
  return 0;
}

神题啊……

考虑让答案最小不好做，那么我们想，把连续的一段空格变成一个TAB（假设TAB长度为\(x\)）就是减少\(x - 1\)空格，那么我们尝试去最大化减小的空格的量。

然后考虑枚举\(x\)是啥，然后去算减少的空格的量。对于任意\(a_i\)，减少的空格量就是\((x-1)\lfloor\frac{a_i}{x}\rfloor\)，这似乎可以整除分块哎……

但是会被T掉。我们想，其实我们对任意\(x\)，我们去枚举\(\lfloor\frac{a_i}{x}\rfloor\)就行啦，要查询满足条件的\(a_i\)数量可以预处理一个权值前缀和然后就能\(O(1)\)做啦、

假设\(X = \max\{a_i\}\)，那么每一个\(x\)对时间复杂度的贡献就是\(O(\frac{X}{x})\)。这不就是调和级数吗？所以时间复杂度事\(O(X\ln X)\)。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
const int maxn = 1000005;
typedef long long ll;
int a[maxn], C[maxn];
int n, bd;
void process() {
  for(int i = 1; i <= n; i ++) {
    C[a[i]] ++;
  }
  for(int i = 1; i <= bd; i ++) {
    C[i] += C[i - 1];
  }
}
ll sum;
ll query(int x, int p) {
  int l = x * p;
  int r = x * (p + 1) - 1;
  if(r > bd) r = bd;
  return (C[r] - C[l - 1]);
}
ll calc(int x) {
  ll delta = 0;
  for(int i = 1; i <= (bd / x); i ++) {
    ll cnt = query(x, i);
    delta += (ll(i)) * cnt * (ll(x - 1));
  }
#ifdef LOCAL
  printf("ans of %d : %lld\n", x, sum - delta);
#endif
  return (sum - delta);
}

int main() {
  scanf("%d", &n);
  sum = 0LL; bd = 0;
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &a[i]);
    bd = std::max(bd, a[i]);
    sum += a[i];
  }
  process();
  ll ans = sum;
  for(int i = 1; i <= bd; i ++) {
    ans = std::min(ans, calc(i));
  }
  printf("%lld\n", ans);
  return 0;
}

一年前看的反演神题……（然后现在才A）

第一次做subtask题= =其实这题也没啥难度吧

其实就是两个subtask……

对于第一个subtask，就是满足\(1\leq n\leq 100\)且\(1\leq a\leq b\leq n\)。我们应该优先满足高位为\(0\)，于是乎可以贪心，从高位枚举到低位，看是否能在满足之前几位的限制条件的同时满足这一位答案为\(0\)。这个判定过程的话，可以设计状态\(d[i][k]\)表示前\(i\)位割成\(k\)段是否满足约束条件，枚举断点\(O(n)\)转移。

第二个subtask，虽然有\(n\leq 2000\)但是满足\(a = 1\)。这意味着分段数想怎么小就怎么小，所以我们可以直接去求这个序列要满足限制条件的话最少可以割成几段，这样的话第二维就可以省掉了。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
typedef long long ll;
const int maxn = 2005;
ll Y[maxn], S[maxn];
int n, a, b;
const int maxb = 41;
ll st = 0;
namespace Task1 {
  bool d[105][105];
  bool dp(int bi) {
    memset(d, 0, sizeof(d));
    d[0][0] = true;
    for(int i = 1; i <= n; i ++) {
      for(int k = 1; k <= b; k ++) {
        for(int j = 0; j < i; j ++) {
          ll sum = S[i] - S[j];
          if((sum & (st | (1LL << bi))) == 0LL) {
            d[i][k] = (d[i][k] || d[j][k - 1]);
          }
        }
      }
    }
    for(int k = a; k <= b; k ++) {
      if(d[n][k]) return true;
    }
    return false;
  }
};
namespace Task2 {
  int d[maxn];
  bool dp(int bi) {
    d[0] = 0;
    for(int i = 1; i <= n; i ++) {
      d[i] = 0x3f3f3f3f;
      for(int j = 0; j < i; j ++) {
        ll sum = S[i] - S[j];
        if(!(sum & (st | (1LL << bi)))) {
          d[i] = std::min(d[i], d[j] + 1);
        }
      }
    }
    return (d[n] <= b);
  }
};

ll solve() {
  ll ans = 0;
  for(int i = maxb; i >= 0; i --) {
    bool flag = n <= 100 ? Task1::dp(i) : Task2::dp(i);
    if(flag) {
      st |= (1LL << i);
    } else {
      ans |= (1LL << i);
    }
  }
  return ans;
}

int main() {
  scanf("%d%d%d", &n, &a, &b);
  for(int i = 1; i <= n; i ++) {
    scanf("%lld", &Y[i]);
    S[i] = S[i - 1] + Y[i];
  }
  printf("%lld\n", solve());
  return 0;
}