[BZOJ 3156]防御准备

又做了一个简单的斜率优化题TAT

首先,设\(f_i\)表示最后一个放塔的点事\(i\)时的最优解,那么将原方程化简得:

\[f_i = a_i + \frac{i^2 - i}{2} + max(-ij + \frac{j^2 + j}{2} + f_j)\]

然后求直线形式,得到:

\[ij + d_i = f_j + \frac{j^2 + j}{2}\]

用类似于玩具装箱(上一篇题解)的方式搞一搞即可。

代码:

/**************************************************************
	Problem: 3156
	User: danihao123
	Language: C++
	Result: Accepted
	Time:2496 ms
	Memory:16480 kb
****************************************************************/

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <deque>
#include <cmath>
#include <climits>
typedef long long ll;
typedef ll T;
struct Point {
  T x, y;
  Point(T qx = 0LL, T qy = 0LL) {
    x = qx; y = qy;
  }
};
typedef Point Vector;
Vector operator +(const Vector &a, const Vector &b) {
  return Vector(a.x + b.x, a.y + b.y);
}
Vector operator -(const Point &a, const Point &b) {
  return Vector(a.x - b.x, a.y - b.y);
}
Vector operator *(const Vector &a, T lam) {
  return Vector(a.x * lam, a.y * lam);
}
Vector operator *(T lam, const Vector &a) {
  return Vector(a.x * lam, a.y * lam);
}
inline T dot(const Vector &a, const Vector &b) {
  return (a.x * b.x + a.y * b.y);
}
inline T times(const Vector &a, const Vector &b) {
  return (a.x * b.y - a.y * b.x);
}

const int maxn = 1000005;
T f[maxn], a[maxn];
int n;
void dp() {
  f[1] = a[1];
  std::deque<Point> Q;
  Q.push_back(Point(1LL, f[1] + 1LL));
  for(T i = 2; i <= n; i ++) {
    T k = i;
    Vector st(1LL, k);
    while(Q.size() > 1 && times(Q[1] - Q[0], st) > 0LL) {
      Q.pop_front();
    }
    f[i] = a[i] + ((i * i - i) / 2LL);
    f[i] += Q.front().y - Q.front().x * i;
    Point ins(i, f[i] + ((i * i + i) / 2LL));
    while(Q.size() > 1 && times(ins - Q.back(), Q.back() - Q[Q.size() - 2]) > 0LL) {
      Q.pop_back();
    }
    Q.push_back(ins);
  }
}

int main() {
  scanf("%d", &n);
  for(int i = n; i >= 1; i --) {
    scanf("%lld", &a[i]);
  }
  dp();
  ll ans = f[n];
#ifdef LOCAL
  printf("f[n] : %lld\n", ans);
#endif
  for(T i = 1; i < n; i ++) {
#ifdef LOCAL
    printf("f[%d] : %lld\n", i, f[i]);
#endif
    ans = std::min(ans, f[i] + (n - i + 1LL) * (n - i) / 2LL);
  }
  printf("%lld\n", ans);
  return 0;
}

[BZOJ 1010][HNOI2008]玩具装箱toy

很久之前是学过并写过斜率优化的……但是很快就忘了。现在感觉自己理解了,感觉是真的懂了……抽空写篇文章解释一下吧……

先单独说这一个题。将DP方程完全展开,并且设\(P_i = S_i + i\),\(c = L + 1\),可得:

\[f_i = c^2 + P_i^2 - 2P_i c + max(P_j^2 + 2P_j c + f_j - 2P_i P_j)\]

然后\(c^2 + P_i^2 - 2P_i c\)这部分是常数项不需要管了,我们就想想max里面那些(姑且设之为\(d_i\))咋整好了。

设\(d_i = P_j^2 + 2P_j c + f_j - 2P_i P_j\),稍作移项,得:

\[2P_i P_j + d_i = P_j^2 + 2P_j c + f_j\]

于是乎,\(d_i\)可以看做斜率为\(2P_i\)的直线过点\((P_j, P_j^2 + 2P_j c + f_j)\)得到的截距。而那些点我们之前都知道了,问题就变成了已知斜率,求过某点集中的点的最大截距。

想象一个固定斜率的直线从下往上扫,那么碰到的第一个点就是最优解。首先这个点一定在下凸壳上,其次下凸壳上这点两侧的线段的斜率肯定一个比\(2P_i\)大另一个比它小。并且最好的一点是这个斜率还是单调的,那么分界点一定是单调递增的。

代码:

/**************************************************************
    Problem: 1010
    User: danihao123
    Language: C++
    Result: Accepted
    Time:132 ms
    Memory:2416 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <deque>
#include <cmath>
typedef long long ll;
typedef ll T;
struct Point {
  T x, y;
  Point(T qx = 0LL, T qy = 0LL) {
    x = qx; y = qy;
  }
};
typedef Point Vector;
Vector operator +(const Vector &a, const Vector &b) {
  return Vector(a.x + b.x, a.y + b.y);
}
Vector operator -(const Point &a, const Point &b) {
  return Vector(a.x - b.x, a.y - b.y);
}
Vector operator *(const Vector &a, T lam) {
  return Vector(a.x * lam, a.y * lam);
}
Vector operator *(T lam, const Vector &a) {
  return Vector(a.x * lam, a.y * lam);
}
inline T dot(const Vector &a, const Vector &b) {
  return (a.x * b.x + a.y * b.y);
}
inline T times(const Vector &a, const Vector &b) {
  return (a.x * b.y - a.y * b.x);
}
 
const int maxn = 50005;
T C[maxn], S[maxn], P[maxn];
T f[maxn];
int n; ll c;
void process() {
  for(int i = 1; i <= n; i ++) {
    S[i] = S[i - 1] + C[i];
    P[i] = S[i] + (ll(i));
  }
}
void dp() {
  std::deque<Point> Q;
  Q.push_back(Point(0LL, 0LL));
  for(int i = 1; i <= n; i ++) {
    ll k = 2 * P[i];
    Vector st(1, k);
    while(Q.size() > 1 && times(Q[1] - Q[0], st) > 0LL) {
      Q.pop_front();
    }
    f[i] = c * c + P[i] * P[i] - 2LL * P[i] * c;
    f[i] += Q.front().y - k * Q.front().x;
#ifdef LOCAL
    printf("f[%d] : %lld\n", i, f[i]);
#endif
    Vector ins(P[i], f[i] + P[i] * P[i] + 2LL * P[i] * c);
    while(Q.size() > 1 && times(ins - Q.back(), Q.back() - Q[Q.size() - 2]) > 0LL) {
#ifdef LOCAL
      printf("Deleting (%lld, %lld)...\n", Q.back().x, Q.back().y);
#endif
      Q.pop_back();
    }
    Q.push_back(ins);
#ifdef LOCAL
    printf("Inserting (%lld, %lld)...\n", ins.x, ins.y);
#endif
  }
}
 
int main() {
  scanf("%d%lld", &n, &c); c ++;
  for(int i = 1; i <= n; i ++) {
    scanf("%lld", &C[i]);
  }
  process(); dp();
  printf("%lld\n", f[n]);
  return 0;
}

[BZOJ 2561]最小生成树

窝只会做水体了qwq

因为这条边既存在在最大生成树里,又存在在最小生成树里。那就说明\(u\)到\(v\)的路径上,在最大生成树上这条边是最小的,在最小生成树上这条边是最大的。

所以说我们不能用大于\(L\)的边来联通\(u\)和\(v\),也不能用小于\(L\)的边,于是乎……跑两次最小割即可。

代码:

/**************************************************************
	Problem: 2561
	User: danihao123
	Language: C++
	Result: Accepted
	Time:1528 ms
	Memory:15952 kb
****************************************************************/

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <utility>
#include <algorithm>
#include <queue>
const int maxn = 20005;
const int maxm = 200005;
const int maxe = maxm << 2;
int n, m;
int first[maxn];
int next[maxe], to[maxe], flow[maxe], cap[maxe];
int gcnt = 0;
inline void init_graph() {
  gcnt = 0;
  std::fill(first + 1, first + 1 + n, 0);
}
inline void add_edge(int u, int v, int f) {
  gcnt ++;
  next[gcnt] = first[u];
  first[u] = gcnt;
  to[gcnt] = v;
  flow[gcnt] = 0; cap[gcnt] = f;
}
inline int rev(int i) {
  return (((i - 1) ^ 1) + 1);
}
inline void ins_edge(int u, int v, int f) {
  add_edge(u, v, f);
  add_edge(v, u, 0);
}

int line[maxm][3];
int d[maxn];
int s, t;
inline bool bfs() {
  static bool vis[maxn];
  std::fill(vis + 1, vis + 1 + n, false);
  std::fill(d + 1, d + 1 + n, 0);
  std::queue<int> Q;
  Q.push(s); vis[s] = true; d[s] = 1;
  while(!Q.empty()) {
    int u = Q.front(); Q.pop();
    for(int i = first[u]; i; i = next[i]) {
      int v = to[i];
      if(!vis[v] && cap[i] > flow[i]) {
        d[v] = d[u] + 1; vis[v] = true;
        Q.push(v);
      }
    }
  }
  return vis[t];
}
int cur[maxn];
int dfs(int x, int a) {
  if(a == 0 || x == t) return a;
  int ans = 0;
  for(int &i = cur[x]; i; i = next[i]) {
    int v = to[i];
    int f;
    if(d[v] == d[x] + 1 && (f = dfs(v, std::min(a, cap[i] - flow[i]))) > 0) {
      ans += f; a -= f;
      flow[i] += f; flow[rev(i)] -= f;
      if(a == 0) break;
    }
  }
  if(a > 0) d[x] = -1;
  return ans;
}
int dinic() {
  int ans = 0;
  while(bfs()) {
    for(int i = 1; i <= n; i ++) cur[i] = first[i];
    ans += dfs(s, 0x7fffffff);
  }
  return ans;
}

int main() {
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i ++) {
    int *l = line[i];
    scanf("%d%d%d", &l[0], &l[1], &l[2]);
  }
  int L; scanf("%d%d%d", &s, &t, &L);
  for(int i = 1; i <= m; i ++) {
    int *l = line[i];
    if(l[2] < L) {
      ins_edge(l[0], l[1], 1);
      ins_edge(l[1], l[0], 1);
    }
  }
  int ans = dinic();
  init_graph();
  for(int i = 1; i <= m; i ++) {
    int *l = line[i];
    if(l[2] > L) {
      ins_edge(l[0], l[1], 1);
      ins_edge(l[1], l[0], 1);
    }
  }
  ans += dinic();
  printf("%d\n", ans);
  return 0;
}

[LibreOJ 2197][SDOI2014]向量集

xjb写了写……我评测时候心脏跳得贼快(逃

考虑如果知道了那一段区间的凸包那么怎么做。首先如果向量是往上指的话,一定在上凸壳上找点比较好,反之则在下凸壳上找点比较好(放到坐标系里脑补一下?)。然后我们观察一点,在上凸壳上的最优解往两边的点会越来越劣,所以这玩意是个上凸函数,可以三分答案(我才学的整数三分啊)。

但区间凸包求起来复杂度很爆炸啊……考虑用线段树搞?观察到一点,我们区间查询所使用的线段树节点一定是只包含了已经加进来的点。所以说,一个线段树节点的凸包需要被求的情况只有一种,那就是这个节点完全已加入点被覆盖了。那每次修改之后看是否一个节点完全被已加入点覆盖,如果被完全覆盖的话才去求它的凸包。

这样一来,线段树上每个节点之多会被求一次凸包。线段树有\(\log n\)层,每一层所有节点的大小加起来是\(n\),所以求凸包耗费的总复杂度是\(n\log^2 n\)级别的。

其实这就是用线段树模拟二进制分组?

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
#include <climits>
#include <cassert>
using ll = long long;
using T = ll;
struct Point {
  T x, y;
  Point(T qx = 0LL, T qy = 0LL) {
    x = qx; y = qy;
  }
};
using Vector = Point;
Vector operator +(const Vector &a, const Vector &b) {
  return Vector(a.x + b.x, a.y + b.y);
}
Vector operator -(const Point &a, const Point &b) {
  return Vector(a.x - b.x, a.y - b.y);
}
Vector operator *(const Vector &a, T lam) {
  return Vector(a.x * lam, a.y * lam);
}
Vector operator *(T lam, const Vector &a) {
  return Vector(a.x * lam, a.y * lam);
}
inline T dot(const Vector &a, const Vector &b) {
  return (a.x * b.x + a.y * b.y);
}
inline T times(const Vector &a, const Vector &b) {
  return (a.x * b.y - a.y * b.x);
}
inline bool cmp(const Point &a, const Point &b) {
  if((a.x - b.x) == 0LL) {
    return a.y < b.y;
  } else {
    return a.x < b.x;
  }
}
inline void andrew(Point *P, int L, std::vector<Point> &bot, std::vector<Point> &top) {
  std::sort(P + 1, P + 1 + L, cmp);
  for(int i = 1; i <= L; i ++) {
    if(i != 1 && (P[i].x - P[i - 1].x) == 0LL) continue;
    while(bot.size() > 1 && (times(P[i] - bot.back(), bot.back() - bot[bot.size() - 2])) >= 0LL) {
      bot.pop_back();
    }
    bot.push_back(P[i]);
  }
  for(int i = L; i >= 1; i --) {
    if(i != L && (P[i].x - P[i + 1].x) == 0LL) continue;
    while(top.size() > 1 && (times(P[i] - top.back(), top.back() - top[top.size() - 2])) >= 0LL) {
      top.pop_back();
    }
    top.push_back(P[i]);
  }
  std::reverse(top.begin(), top.end());
}

const int maxn = 400005;
const int maxno = maxn << 2;
const int N = 400000;
bool zen[maxno];
std::vector<Point> bot[maxno], top[maxno];
Point P[maxn];
inline void maintain(int o, int L, int R) {
  static Point tmp[maxn];
  const int lc = o << 1, rc = o << 1 | 1;
  const bool used = zen[o];
  zen[o] = (zen[lc] && zen[rc]);
  if(zen[o] != used) {
    std::copy(P + L, P + R + 1, tmp + 1);
    int len = R - L + 1;
    andrew(tmp, len, bot[o], top[o]);
  }
}
void modify(int o, int L, int R, const int &p, const Point &v) {
  if(L == R) {
    zen[o] = true;
    P[L] = v;
    bot[o].push_back(v); top[o].push_back(v);
  } else {
    const int M = (L + R) / 2;
    if(p <= M) {
      modify(o << 1, L, M, p, v);
    } else {
      modify(o << 1 | 1, M + 1, R, p, v);
    }
    maintain(o, L, R);
  }
}
inline T search(const std::vector<Point> &vec, const Point &p) {
  int l = 0, r = vec.size() - 1;
  while(r - l > 2) {
    int lm = (l * 2 + r) / 3, rm = (2 * r + l) / 3;
    if(dot(p, vec[lm]) > dot(p, vec[rm])) {
      r = rm;
    } else {
      l = lm;
    }
  }
  T ans = LLONG_MIN;
  for(int i = l; i <= r; i ++) {
    ans = std::max(ans, dot(p, vec[i]));
  }
  return ans;
}
T query(int o, int L, int R, const int &ql, const int &qr, const Point &p) {
  if(ql <= L && R <= qr) {
    if(p.y > 0LL) {
      return search(top[o], p);
    } else {
      return search(bot[o], p);
    }
  } else {
    int M = (L + R) / 2;
    T ans = LLONG_MIN;
    if(ql <= M) {
      ans = std::max(ans, query(o << 1, L, M, ql, qr, p));
    }
    if(qr > M) {
      ans = std::max(ans, query(o << 1 | 1, M + 1, R, ql, qr, p));
    }
    return ans;
  }
}

inline int decode(int x, long long lastans) {
  return x ^ (lastans & 0x7fffffff);
}
int main() {
  int q; char buf[4]; scanf("%d%s", &q, buf);
  bool typ_E = (buf[0] == 'E' && buf[1] == char(0));
  T las = 0LL;
  int tot = 0;
  while(q --) {
    char op[4]; scanf("%s", op);
    if(op[0] == 'A') {
      T x, y; scanf("%lld%lld", &x, &y);
      if(!typ_E) {
        x = decode(x, las); y = decode(y, las);
      }
      tot ++;
      modify(1, 1, N, tot, Point(x, y));
    } else {
      T x, y, l, r; scanf("%lld%lld%lld%lld", &x, &y, &l, &r);
      if(!typ_E) {
        x = decode(x, las); y = decode(y, las);
        l = decode(l, las); r = decode(r, las);
      }
      las = query(1, 1, N, l, r, Point(x, y));
      printf("%lld\n", las);
    }
  }
  return 0;
}

[LibreOJ 2102][TJOI2015]弦论

xjbYY了一下竟然就艹过去了……

如果说是我们知道了每个点出发能得到的串有多少个,我们就能用类似树上求\(k\)大的求法来搞了。问题来了,怎么知道这个?

我先说一下不重复的情况吧,首先到达这个点就有一种串了,然后我们加上他的出边(注意是转移边!)指向的点的值就行了。重复的情况我们考虑一下\(|Right(x)|\)就能搞出来了

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <utility>
#include <queue>
#include <algorithm>
#include <set>
const int maxn = 500005;
const int maxno = maxn * 4;
const int bufsiz = 50 * 1024 * 1024;
typedef long long ll;

int fa[maxno], ch[maxno][26];
int len[maxno];
ll ans[maxno][2], val[maxno];
int rt, last;
int cur;
inline void init_sam() {
  rt = last = 1;
  cur = 1;
  ans[1][0] = ans[1][1] = -1LL;
}
inline int alloc_node(int l = 0, int f = 0) {
  int ret = ++ cur;
  len[ret] = l; fa[ret] = f;
  ans[ret][0] = ans[ret][1] = -1LL;
  return ret;
}
inline int idx(char c) {
  return c - 'a';
}
inline void extend(char cx) {
  int c = idx(cx);
  int np = alloc_node(len[last] + 1);
  val[np] = 1LL;
  int p = last;
  while(p && !(ch[p][c])) ch[p][c] = np, p = fa[p];
  if(!p) {
    fa[np] = rt;
  } else {
    int q = ch[p][c];
    if(len[q] == len[p] + 1) {
      fa[np] = q;
    } else {
      int nq = alloc_node(len[p] + 1, fa[q]);
      memcpy(ch[nq], ch[q], sizeof(ch[q]));
      fa[q] = fa[np] = nq;
      while(p && ch[p][c] == q) ch[p][c] = nq, p = fa[p];
    }
  }
  last = np;
}
int lc[maxno], rb[maxno];
inline void add_edge(int c, int f) {
  rb[c] = lc[f];
  lc[f] = c;
}
void dfs_1(int x) {
  for(int i = lc[x]; i; i = rb[i]) {
    dfs_1(i);
    val[x] += val[i];
  }
}
void dfs_2(int x) {
  if(ans[x][0] != -1LL) return;
  ans[x][0] = 1LL; ans[x][1] = val[x];
  for(int c = 0; c < 26; c ++) {
    int v = ch[x][c];
    if(v) {
      dfs_2(v);
      ans[x][0] += ans[v][0];
      ans[x][1] += ans[v][1];
    }
  }
}
inline void process() {
  for(int i = 2; i <= cur; i ++) {
    add_edge(i, fa[i]);
  }
  dfs_1(1); dfs_2(1);
#ifdef LOCAL
  for(int i = 1; i <= cur; i ++) {
    printf("ans[%d] : (%lld, %lld)\n", i, ans[i][0], ans[i][1]);
  }
#endif
}
char ret[maxno];
void search(ll k, int typ) {
  static ll val_0[maxno];
  for(int i = 1; i <= cur; i ++) {
    val_0[i] = 1;
  }
  ll *self[2] = {val_0, val};
  k += self[typ][1];
  if(k > ans[1][typ]) {
    ret[0] = '-', ret[1] = '1';
    return;
  }
  int cnt = 0;
  int u = 1;
  while(k > self[typ][u]) {
    int used = 0;
    k -= self[typ][u];
    for(int c = 0; c < 26; c ++) {
      int v = ch[u][c];
      if(!v) continue;
      used ++;
      if(k > ans[v][typ]) {
        k -= ans[v][typ];
      } else {
        ret[cnt ++] = c + 'a';
#ifdef LOCAL
        printf("Towardsing %d with %c\n", v, c + 'a');
        printf("k : %lld\n", k);
#endif
        u = v; break;
      }
    }
    // if(used == 0) break;
  }
}

int main() {
  static char S[maxn];
  scanf("%s", S); int n = strlen(S);
  int typ; ll k; scanf("%d%lld", &typ, &k);
  init_sam();
  for(int i = 0; i < n; i ++) {
    extend(S[i]);
  }
  process();
  search(k, typ);
  puts(ret);
  return 0;
}

[SPOJ]LCS

震惊!SAM与AC自动机间的神秘关系,竟然是为了……

考虑到是子串嘛,我们建立\(A\)的后缀自动机,考虑把\(B\)放在上面进行匹配。然后考虑当前节点下面再加一个字符,如果有这个字符的转移那么直接走过去即可。如果没有呢?

观察到SAM上的父亲其实就是一个被儿子包含了的子串,所以这一步走不下去,可以考虑去找父亲解决。所以找到最低的有该转移的祖先,转移过去即可。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
const int maxn = 250005;
const int maxsiz = 30000005;
char buf[maxsiz];
char *cur = buf;
void *alloc(size_t size) {
  if(cur - buf + size > maxsiz) {
    return malloc(size);
  } else {
    void *ret = (void*)cur;
    cur += size;
    return ret;
  }
}

int idx(char c) {
  return c - 'a';
}
struct Node {
  Node *fa;
  int len;
  Node *ch[26];
};
Node *alloc_node(int len = 0, Node *fa = NULL) {
  Node *ret = (Node*)alloc(sizeof(Node));
  ret -> len = len; ret -> fa = fa;
  memset(ret -> ch, 0, sizeof(ret -> ch));
  return ret;
}
Node *rt, *last;
void init_sam() {
  rt = alloc_node();
  last = rt;
}
void extend(char c) {
  int i = idx(c);
  Node *np = alloc_node(last -> len + 1);
  Node *p = last;
  while(p != NULL && p -> ch[i] == NULL) {
    p -> ch[i] = np;
    p = p -> fa;
  }
  if(p == NULL) {
    np -> fa = rt;
  } else {
    Node *q = p -> ch[i];
    if(q -> len == p -> len + 1) {
      np -> fa = q;
    } else {
      Node *nq = alloc_node(p -> len + 1, q -> fa);
      memcpy(nq -> ch, q -> ch, sizeof(q -> ch));
      np -> fa = q -> fa = nq;
      while(p != NULL && p -> ch[i] == q) {
        p -> ch[i] = nq;
        p = p -> fa;
      }
    }
  }
  last = np;
}

char A[maxn], B[maxn];
int search() {
  int n = strlen(B);
  Node *u = rt;
  int ans = 0, len = 0;
  for(int i = 0; i < n; i ++) {
    int c = idx(B[i]);
    if(u -> ch[c]) {
      u = u -> ch[c];
      len ++;
    } else {
      while(u != NULL && u -> ch[c] == NULL) u = u -> fa;
      if(u == NULL) {
        u = rt; len = 0;
      } else {
        len = u -> len + 1;
        u = u -> ch[c];
      }
    }
    ans = std::max(ans, len);
  }
  return ans;
}

int main() {
  scanf("%s%s", A, B);
  int n = strlen(A);
  init_sam();
  for(int i = 0; i < n; i ++) {
    extend(A[i]);
  }
  printf("%d\n", search());
  return 0;
}

[LibreOJ 2033][SDOI2016]生成魔咒

辣鸡爆炸OJ又被卡了说好的修bug呢说好的新OJ呢哼我去loj交了

本题的正解是SA,但很显然可以用SAM搞过去(逃

首先字符集过大?我们可以考虑开map解决转移的问题。

然后思考一个点加入后对答案会有什么影响。一个点的对答案的贡献,就是他自己的最大表示范围减去他父亲的。因为更小的长度在之前都已经被表示过了。即使之后这个点被拆成了两个,那这两个点对答案的总贡献是不会变的。所以每次加完点,把贡献加到答案里即可。

代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <map>
typedef long long ll;
#define REP(i, l, r) for(int i = (l); i <= (r); i ++)
struct Node {
  Node *fa;
  std::map<int, Node*> *ch;
  int len;
  Node() {
    fa = NULL;
    ch = new std::map<int, Node*>();
  }
  Node(int l) {
    fa = NULL;
    ch = new std::map<int, Node*>();
    len = l;
  }
  ~Node() {
    delete ch;
  }
};
Node *rt, *last;
void init() {
  rt = new Node(0);
  // rt -> tl = 1;
  last = rt;
}
ll ans = 0;
void insert(int c) {
  static int clk = 1;
  Node *np = new Node();
  np -> len = last -> len + 1;
  Node *p = last;
  while(p != NULL && p -> ch -> count(c) == 0) {
    p -> ch -> insert(std::make_pair(c, np));
    p = p -> fa;
  }
  if(p == NULL) {
    np -> fa = rt;
  } else {
    Node *q = (*(p -> ch -> find(c))).second;
    if(q -> len == p -> len + 1) {
      np -> fa = q;
    } else {
      Node *nq = new Node(p -> len + 1);
      nq -> fa = q -> fa;
      nq -> ch -> insert(q -> ch -> begin(), q -> ch -> end());
      // nq -> ch -> insert(std::make_pair(c, np));
      np -> fa = q -> fa = nq;
      while(p != NULL && ((*(p -> ch -> find(c))).second) == q) {
        p -> ch -> erase(p -> ch -> find(c));
        p -> ch -> insert(std::make_pair(c, nq));
        p = p -> fa;
      }
    }
  }
  last = np;
  ans += np -> len - np -> fa -> len;
}
 
int main() {
  int n; scanf("%d", &n);
  init();
  REP(i, 1, n) {
    int c; scanf("%d", &c);
    insert(c);
    printf("%lld\n", ans);
  }
  return 0;
}

[SPOJ]NSUBSTR

第一次做了一道有一定难度的SAM题……

考虑每个SAM上的结点\(x\),他的子串表示范围一定是一个区间\([Min(x), Max(x)]\),然后他的\(Right(x)\)的大小就是该点所代表的每个子串的出现次数。

那么考虑怎么搞出这个\(|Right(x)|\)。我们把每个“实点”(就是在SAM每一次插入后成为\(last\)的结点)的点权钦定为1,其他搞成0。然后每个点的\(|Right(x)|\)就是\(x\)在Right树上的子树的点权和。

然后接下来看上去可以直接做……但是区间chkmax这种黑暗操作,是不是要涉及毒瘤数据结构?

答案是否定的。任何短的子串都是某一个长子串的子串,所以说我们只需要在\(Max(x)\)那个地方chkmax,然后搞个后缀最大值即可。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
const int maxn = 250005;
const int sigma_siz = 26;
struct Node {
  int maxl, rs;
  Node *fa;
  Node *ch[sigma_siz];
};
Node pool[maxn << 1]; Node *tot = pool;
Node *rt = tot, *last = tot;
void extend(int c) {
  Node *np = ++ tot;
  np -> maxl = last -> maxl + 1; np -> rs = 1;
  Node *p = last;
  while(p != NULL && p -> ch[c] == NULL) {
    p -> ch[c] = np;
    p = p -> fa;
  }
  if(p == NULL) {
    np -> fa = rt;
  } else {
    Node *q = p -> ch[c];
    if(q -> maxl == p -> maxl + 1) {
      np -> fa = q;
    } else { 
      Node *nq = ++ tot;
      nq -> maxl = p -> maxl + 1; nq -> fa = q -> fa;
      memcpy(nq -> ch, q -> ch, sizeof(q -> ch));
      q -> fa = np -> fa = nq;
      while(p != NULL && p -> ch[c] == q) {
        p -> ch[c] = nq;
        p = p -> fa;
      }
    }
  }
  last = np;
}

int first[maxn << 1];
int next[maxn << 2], to[maxn << 2];
int gcnt = 0;
void add_edge(int u, int v) {
  gcnt ++;
  next[gcnt] = first[u];
  first[u] = gcnt;
  to[gcnt] = v;
}
int len[maxn << 1], siz[maxn << 1];
int F[maxn];
void dfs(int x) {
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    dfs(v);
    siz[x] += siz[v];
  }
  F[len[x]] = std::max(F[len[x]], siz[x]);
}

int main() {
  static char S[maxn];
  scanf("%s", S);
  int n = strlen(S);
  for(int i = 0; i < n; i ++) {
    extend(S[i] - 'a');
  }
  for(int i = 0; i <= (tot - pool); i ++) {
    Node *p = pool + i;
    len[i] = p -> maxl;
    siz[i] = p -> rs;
    if(p -> fa) {
      int fa = (p -> fa) - pool;
      add_edge(fa, i);
    }
  }
  dfs(0);
  for(int i = n - 1; i >= 0; i --) {
    F[i] = std::max(F[i], F[i + 1]);
  }
  for(int i = 1; i <= n; i ++) {
    printf("%d\n", F[i]);
  }
  return 0;
}

[BZOJ 3158]千钧一发

好有意思的题呢qwq

首先观察到一点,我们可以把所有装置按照\(a_i\)的奇偶性进行分类(也可以说是黑白染色?)。容易发现任意偶数的最大公约数都至少是2,所以任意偶数间不会互相冲突。然后任意两个奇数的平方和一定不是完全平方数,可以这么证一下(感谢金爷!):

那两个奇数可以分别设成\(2x + 1\)和\(2y + 1\),然后他们的平方和就是\(4(x^2 + y^2 + x + y) + 2\)。然后思考一点,就是一个奇数的平方一定是奇数,所以说那个平方和是一个偶数。但是,如果一个完全平方数是偶数,那么它的算术平方根一定是偶数。然而,一个偶数的平方一定是4的倍数。但我们求出的平方和膜4得2,所以不行。

所以说冲突只存在于奇偶性不同的数中。然后用无限大的边来表示冲突关系,最小割高一波即可。

代码(常数卡卡卡……只能用pb_ds的蛤希表了):

/**************************************************************
	Problem: 3158
	User: danihao123
	Language: C++
	Result: Accepted
	Time:9676 ms
	Memory:130460 kb
****************************************************************/

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
typedef long long ll;
ll gcd(ll a, ll b) {
  if(!b) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}
__gnu_pbds::gp_hash_table<ll, bool> S2;
void process_S2() {
  for(ll i = 1LL; i * i <= 2000000000000LL; i ++) {
    S2[i * i] = true;
  }
}


const int maxno = 1050;
const int maxm = 2000500;
int first[maxno];
int next[maxm], to[maxm], cap[maxm], flow[maxm];
int gcnt = 0;
void add_edge(int u, int v, int f) {
  gcnt ++;
  next[gcnt] = first[u];
  first[u] = gcnt;
  to[gcnt] = v;
  cap[gcnt] = f;
  flow[gcnt] = 0;
}
int rev(int i) {
  if(1 & i) {
    return i + 1;
  } else {
    return i - 1;
  }
}
void ins_edge(int u, int v, int f) {
  add_edge(u, v, f); add_edge(v, u, 0);
}

int n;
int s, t;
int d[maxno];
bool bfs() {
  static bool vis[maxno];
  memset(vis, 0, sizeof(vis));
  d[s] = 1; vis[s] = true;
  std::queue<int> Q; Q.push(s);
  while(!Q.empty()) {
    int u = Q.front(); Q.pop();
    for(int i = first[u]; i; i = next[i]) {
      int v = to[i];
      if(cap[i] > flow[i] && !vis[v]) {
        d[v] = d[u] + 1; vis[v] = true;
        Q.push(v);
      }
    }
  }
  return vis[t];
}
int cur[maxno];
int dfs(int u, int a) {
  if(a == 0 || u == t) return a;
  int fl = 0;
  for(int &i = cur[u]; i; i = next[i]) {
    int v = to[i]; int f;
    if(d[v] == d[u] + 1 && (f = dfs(v, std::min(cap[i] - flow[i], a))) > 0) {
      fl += f; a -= f;
      flow[i] += f; flow[rev(i)] -= f;
      if(a == 0) break;
    }
  }
  if(a > 0) d[u] = -1;
  return fl;
}
int tot;
int dinic() {
  int ans = 0;
  while(bfs()) {
    for(int i = 0; i <= tot; i ++) cur[i] = first[i];
    ans += dfs(s, 0x7fffffff);
  }
  return ans;
}

const int maxn = 1005;
ll A[maxn]; int B[maxn];
int main() {
  process_S2();
  scanf("%d", &n); tot = n + 1;
  s = 0, t = tot;
  std::vector<int> odd, even;
  for(int i = 1; i <= n; i ++) {
    scanf("%lld", &A[i]);
    if(1LL & A[i]) {
      odd.push_back(i);
    } else {
      even.push_back(i);
    }
  }
  int ans = 0;
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &B[i]); ans += B[i];
    if(1LL & A[i]) {
      ins_edge(i, t, B[i]);
    } else {
      ins_edge(s, i, B[i]);
    }
  }
  for(int i = 0; i < even.size(); i ++) {
    int p1 = even[i];
    for(int j = 0; j < odd.size(); j ++) {
      int p2 = odd[j];
      if(gcd(A[p1], A[p2]) == 1LL && S2.find(A[p1] * A[p1] + A[p2] * A[p2]) != S2.end()) {
        ins_edge(p1, p2, 0x7f7f7f7f);
      }
    }
  }
  ans -= dinic();
  printf("%d\n", ans);
  return 0;
}

[LibreOJ 2174][FJOI2016]神秘数 & [CC]FRBSUM

震惊!省选惊现CodeChef原题……竟然是为了……出原题难道不是普遍现象吗

这个题的思想肥肠喵啊(我膜了很长时间题解才看懂)……我争取给各位读者讲懂。

首先对于最后的答案\(x + 1\),一定说明\([1, x]\)都会被凑出来。那么我们可以考虑去维护这个前缀区间。

考虑把数从小到大加入。假设当前我们的可凑出来的前缀区间是\([1, r]\),那么加入一个数\(x\),如果说\(x > r + 1\),那么把之前所有可能的子集和都加上这个\(x\),一定凑不出来\(r + 1\)。并且这之后加入的数会越来越大,那个\(r\)不会再变大了,所以那个\(r\)就是答案了。

如果说\(x\leq r + 1\)呢?那么把前缀区间的每个数加上\(x\)都是可凑成数。所以前缀区间会变成\([1, r + x]\)。

然后观察出来这种性质之后,我们发现我们要考虑区间中不同的数,可以考虑主席树。我们建立一排主席树,对于查询\([L, R]\),不妨假设当前的前缀区间是\([1, r]\),然后考虑将其扩大。首先再加上大于\(r + 1\)的数是对扩大\(r\)没有意义的,所以我们就考虑在\([L, R]\)中找到所有权值处于\([1, r + 1]\)的数字的和(主席树可以派上用场),这样就是一个新的答案了。如果发现转移过去之后答案没有变大,那么以后也不会变大了,跳出来即可。

考虑分析一波复杂度。对于每一个\(r\),转移到更大的\(r\)会让他至少加上\(r + 1\),所以转移的次数是\(\log_2 s\)(这里假设\(s\)是所有数的和),然后每次一次转移的复杂度是\(\log_2 n\),所以单次查询复杂度可以大致认为是\(\log^2 n\)。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
typedef long long ll;
const int maxn = 100005;
const int maxsiz = maxn * 40;
ll sumv[maxsiz]; int tot = 0;
int lc[maxsiz], rc[maxsiz];
int build_tree(int L, int R) {
  int ret = ++ tot;
  if(L < R) {
    int M = (L + R) / 2;
    lc[ret] = build_tree(L, M);
    rc[ret] = build_tree(M + 1, R);
  }
  return ret;
}
int update(int o, int L, int R, int p, int v) {
  int ret = ++ tot;
  sumv[ret] = sumv[o] + (ll(v));
  lc[ret] = lc[o], rc[ret] = rc[o];
  if(L < R) {
    int M = (L + R) / 2;
    if(p <= M) {
      lc[ret] = update(lc[ret], L, M, p, v);
    } else {
      rc[ret] = update(rc[ret], M + 1, R, p, v);
    }
  }
  return ret;
}
ll query(int o, int L, int R, int ql, int qr) {
  if(ql <= L && R <= qr) {
    return sumv[o];
  } else {
    int M = (L + R) / 2;
    ll ans = 0;
    if(ql <= M) ans += query(lc[o], L, M, ql, qr);
    if(qr > M) ans += query(rc[o], M + 1, R, ql, qr);
    return ans;
  }
}

int n;
ll A[maxn], A2[maxn];
int cnt;
void discretiz() {
  std::sort(A2 + 1, A2 + n + 1);
  cnt = std::unique(A2 + 1, A2 + 1 + n) - A2 - 1;
}
int get_p(ll v) {
  int ret = (std::lower_bound(A2 + 1, A2 + 1 + cnt, v) - A2);
  if(A2[ret] > v) ret --;
  return ret;
}

int T[maxn];
void init_tree() {
  T[0] = build_tree(1, cnt);
  for(int i = 1; i <= n; i ++) {
    T[i] = update(T[i - 1], 1, cnt, get_p(A[i]), A[i]);
  }
}
const ll INF = 1000000000LL;
ll calc_sum(int l, int r, int typ) {
  if(typ == 0) return 0LL;
  return query(T[r], 1, cnt, 1, typ) - query(T[l - 1], 1, cnt, 1, typ);
}
ll calc(int l, int r) {
  ll maxv = 0LL, R = 1LL;
  maxv = calc_sum(l, r, get_p(R));
  while(maxv >= R && R < INF) {
    R = std::min(maxv + 1LL, INF);
    maxv = calc_sum(l, r, get_p(R));
  }
  return maxv + 1LL;
}
int main() {
  scanf("%d", &n);
  for(int i = 1; i <= n; i ++) {
    scanf("%lld", &A[i]); A2[i] = A[i];
  }
  discretiz(); init_tree();
  int q; scanf("%d", &q);
  while(q --) {
    int l, r; scanf("%d%d", &l, &r);
    printf("%lld\n", calc(l, r));
  }
  return 0;
}