[LibreOJ 2100][TJOI2015]线性代数

颓一波式子可以发现答案就是\(ABA^T-CA^T\)。然后发现对于一个\(B\)中的元素\(B_{i, j}\)要对答案做出贡献要求\(A_i\)和\(A_j\)都为1,而\(A_i\)为1会导致答案减去一个\(C_i\)。

因此我们可以分别对\(B\)中元素和\(A\)中元素建点。\(B\)中元素会带来收益,但是要求依赖两个\(A\)中元素。而\(A\)中元素会带来一定的笋丝。这个就已经事很明显的最大权闭合子图力,,,

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
const int maxn = 505;
const int maxno = 500 * 500 + 500 + 5;
const int maxm = 2 * (500 * 500 * 3 + 500 + 5);
int first[maxno];
int next[maxm], to[maxm], flow[maxm], cap[maxm];
int gcnt = 0;
void add_edge(int u, int v, int c) {
  gcnt ++;
  next[gcnt] = first[u]; first[u] = gcnt;
  to[gcnt] = v; cap[gcnt] = c; flow[gcnt] = 0;
}
void ins_edge(int u, int v, int c) {
  add_edge(u, v, c); add_edge(v, u, 0);
}
int rev(int i) {
  if(1 & i) {
    return i + 1;
  } else {
    return i - 1;
  }
}

int d[maxno];
int s, t, num;
bool bfs() {
  static bool vis[maxno];
  std::fill(vis, vis + num + 1, false);
  std::fill(d, d + num + 1, 0);
  std::queue<int> Q; Q.push(s);
  d[s] = 1; vis[s] = true;
  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;
        Q.push(v); vis[v] = true;
      }
    }
  }
  return vis[t];
}
int cur[maxno];
int dfs(int x, int a) {
  if(a == 0 || x == t) return a;
  int ret = 0;
  for(int &i = cur[x]; i; i = next[i]) {
    int v = to[i], f;
    if(d[v] == d[x] + 1 && (f = dfs(v, std::min(a, cap[i] - flow[i]))) > 0) {
      ret += f; a -= f;
      flow[i] += f; flow[rev(i)] -= f;
      if(a == 0) break;
    }
  }
  if(a > 0) d[x] = -1;
  return ret;
}
int dinic() {
  int ret = 0;
  while(bfs()) {
    for(int i = 0; i <= num; i ++) cur[i] = first[i];
    ret += dfs(s, 0x7f7f7f7f);
  }
  return ret;
}

int n;
int main() {
  int ans = 0;
  scanf("%d", &n);
  s = 0, t = n * n + n + 1;
  num = t;
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= n; j ++) {
      int u = (i - 1) * n + j; int val; scanf("%d", &val);
      ans += val; ins_edge(s, u, val);
      ins_edge(u, n * n + i, 0x7f7f7f7f);
      ins_edge(u, n * n + j, 0x7f7f7f7f);
    }
  }
  for(int i = 1; i <= n; i ++) {
    int val; scanf("%d", &val);
    ins_edge(n * n + i, t, val);
  }
  ans -= dinic();
  printf("%d\n", ans);
  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;
}

[BZOJ 3171][TJOI2013]循环格

流量平衡入门中……

我竟然想民白了……

这个题就是要求每个点在且仅在一个环中,这样每个点的入、出度都是1。出度肯定是1,接下来我们想想怎么保证入度为1。

我们建两排点(也可以说是拆点?),一排表示流出,一排表示接受。然后流出点向相邻的接收点连边,费用的话考虑是否和原来这一格的方向不一样就行了。

这个不需要判断是否满流啥的……因为一定有解(比如说每个行构成一个环啥的)。

代码:

/**************************************************************
	Problem: 3171
	User: danihao123
	Language: C++
	Result: Accepted
	Time:28 ms
	Memory:13844 kb
****************************************************************/

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
const int maxn = 20;
typedef long long ll;
char S[maxn][maxn];
int tot = 0; int num[maxn][maxn][2];
int R, C;
char D[4] = {'L', 'R', 'U', 'D'};
int tow(int i, int j, char dir, int flag) {
  int dx = 0, dy = 0;
  if(dir == 'L') {
    dx = -1;
  } else if(dir == 'R') {
    dx = 1;
  } else if(dir == 'U') {
    dy = -1;
  } else if(dir == 'D') {
    dy = 1;
  }
  int nx = (i + dy + R) % R;
  int ny = (j + dx + C) % C;
  return num[nx][ny][flag];
}
const int maxno = 100005;
const int maxe = 400005;
int first[maxno];
int next[maxe], from[maxe], to[maxe], flow[maxe], cap[maxe];
ll cost[maxe];
int gcnt = 0;
void add_edge(int u, int v, int f, ll c) {
  gcnt ++;
  next[gcnt] = first[u];
  first[u] = gcnt;
  from[gcnt] = u; to[gcnt] = v;
  cap[gcnt] = f; flow[gcnt] = 0;
  cost[gcnt] = c;
}
int rev(int i) {
  return ((i - 1) ^ 1) + 1;
}
void ins_edge(int u, int v, int f, ll c = 0LL) {
#ifdef LOCAL
  printf("Inserting Edge (%d, %d, %d, %lld)\n", u, v, f, c);
#endif
  add_edge(u, v, f, c);
  add_edge(v, u, 0, -c);
}

const ll LINF = 0x7f7f7f7f7f7f7f7fLL;
bool spfa(int s, int t, int &f, ll &c) {
  static ll d[maxno];
  static bool inq[maxno];
  static int a[maxno], p[maxno];
  std::fill(d, d + tot + 1, LINF);
  std::fill(inq, inq + tot + 1, false);
  std::fill(a, a + tot + 1, 0);
  std::fill(p, p + tot + 1, 0);
  d[s] = 0;
  std::queue<int> Q; Q.push(s); inq[s] = true;
  a[s] = 0x7fffffff;
  while(!Q.empty()) {
    int u = Q.front(); Q.pop();
    inq[u] = false;
    for(int i = first[u]; i; i = next[i]) {
      if(cap[i] > flow[i]) {
        int v = to[i];
        if(d[v] > d[u] + cost[i]) {
          d[v] = d[u] + cost[i];
          a[v] = std::min(a[u], cap[i] - flow[i]); p[v] = i;
          if(!inq[v]) {
            Q.push(v); inq[v] = true;
          }
        }
      }
    }
  }
  if(a[t] == 0) return false;
  f += a[t];
  c += (ll(a[t])) * d[t];
  for(int e = p[t]; e; e = p[from[e]]) {
    flow[e] += a[t];
    flow[rev(e)] -= a[t];
  }
  return true;
}
void mcmf(int s, int t, int &f, ll &c) {
  while(spfa(s, t, f, c));
}

int main() {
  tot = 1; int s = 0, t = 1;
  scanf("%d%d", &R, &C);
  for(int i = 0; i < R; i ++) {
    scanf("%s", S[i]);
    for(int j = 0; j < C; j ++) {
      num[i][j][0] = ++ tot;
      num[i][j][1] = ++ tot;
    }
  }
  for(int i = 0; i < R; i ++) {
    for(int j = 0; j < C; j ++) {
      ins_edge(s, num[i][j][0], 1);
      ins_edge(num[i][j][1], t, 1);
      for(int it = 0; it < 4; it ++) {
        int u = num[i][j][0];
        int v = tow(i, j, D[it], 1);
        ins_edge(u, v, 1, (D[it] == S[i][j]) ? 0LL : 1LL);
      }
    }
  }
  int f = 0; ll c = 0;
  mcmf(s, t, f, c);
  printf("%lld\n", c);
  return 0;
}

[BZOJ 3172]单词

首先……出题人语文不太好……估计和我这种语文很差的人还有差距……

这个提的意思是,给你若干个单词,输出每个单词在所有单词(而不是把所有单词连起来)中出现的次数。

然后肯定要AC自动机上失配函数搞一波辣……把BFS序倒过来搜,传递出现次数即可。还有这个题的数据范围好像也比给出的小很多……

代码:

/**************************************************************
    Problem: 3172
    User: danihao123
    Language: C++
    Result: Accepted
    Time:232 ms
    Memory:115080 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
const int maxn=205;
const int maxnode=1*1e6+5;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
int cnt[maxnode];
 
namespace ACAutomate{
    // Trie
    const int sigma_size=26;
    int Tree[maxnode][sigma_size];
    int siz;
    inline int idx(char c){
        return c-'a';
    }
    void InitAC(){
        siz=0;
        CL_ARR(Tree[0],0);
    }
    int Insert(char *s){
        register int i,n=strlen(s);
        register int u=0,c;
        REP(i,n){
            c=idx(s[i]);
            if(!Tree[u][c]){
                siz++;
                Tree[u][c]=siz;
                CL_ARR(Tree[siz],0);
            }
            u=Tree[u][c];
            cnt[u]++;
        }
        return u;
    }
    // AC Automate
    int f[maxnode];
    int Q[maxnode];
    void InitFail(){
        register int i,u,x,v,head=0,tail=0;
        f[0]=0;
        REP(i,sigma_size){
            u=Tree[0][i];
            if(u){
                f[u]=0;
                Q[tail++]=u;
            }
        }
        while(head<tail){
            u=Q[head];
            head++;
            REP(i,sigma_size){
                x=Tree[u][i];
                if(!x){
                    continue;
                }
                Q[tail++]=x;
                v=f[u];
                while(v && !Tree[v][i])
                    v=f[v];
                f[x]=Tree[v][i];
            }
        }
        for(i=tail-1;i>=0;i--)
            cnt[f[Q[i]]]+=cnt[Q[i]];
    }
};
 
char buf[maxnode];
int pos[maxn];
int main(){
    int n;
    register int i;
    scanf("%d",&n);
    ACAutomate::InitAC();
    REP_B(i,n){
        scanf("%s",buf);
        pos[i]=ACAutomate::Insert(buf);
    }
    ACAutomate::InitFail();
    REP_B(i,n){
        printf("%d\n",cnt[pos[i]]);
    }
    return 0;
}