博弈

花了3天时间把博弈学了
学完博弈之后我回顾了一下我以前没学 最近才学的东西
发现全都是数论的= =;;;;;;;;;
其实之前果断数论基本没学啊啊啊啊啊啊
好吧、 现在好歹学得差不多了= =
这几天刷了poj的一堆博弈题 详见 :
http://hi.baidu.com/lydrainbowcat/item/f16e64103f8c5c088fbde44c
这里面各种数论的题都有

然后我的博弈是看这个的:
http://blog.csdn.net/liwen_7/article/details/7943210
还有就是09年jzh的论文:《组合游戏略述——浅谈SG游戏的若干拓展及变形》
09年还有一篇博弈的论文:cqx的《从“k倍动态减法游戏”出发探究一类组合游戏问题》
这个我暂时还没看 先mark在这把、 以后再看

——————————————–正文———————————————

—————–nim游戏————-
有n堆石头 每堆有ai个 两个人轮流取 每次可以在一堆取任意个石头 问先手是否有必胜策略

ans就是对所有ai求异或和
如果ans == 0 则后手必胜
否则先手必胜

证明:
博弈问题几乎都可以用一种统一的证明步骤:
对于你想出的一种判断必胜方法
须证明:
1.如果面临末状态为获胜则证明末状态为胜态 否则证明为败态
2.一个胜态必然能通过一步操作转为败态
3.一个败态不能通过一步操作转为另一个败态  即无论如何转移皆会转为胜态

对于这题:
1.首先末状态为0,0,0,0,0…. 异或和为0 为败态
2.当前异或和不为0,设为k 设k的二进制表示为(xn xn-1 .. x2 x1)2  (xi∈{1,0}, xn=1)
可以证明必然存在ai二进制下第n位为1 则把ai这堆石头取到剩下ai^k 显然ai^k<ai
这样取完后ai的异或和为0 为败态
3.当前异或和为0 又每次只能且必须改变一个ai 又ai对k的每一个二进制位只有1的影响
改变后必然导致k≠0 为胜态

————————-sg函数————————
首先定义mex(minimal excludant)运算,这是施加于一个集合的运算,表示最小的不属于这个集合的非负整数。
例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。
对于一个游戏的状态用u表示 一个可以被u转移到的状态用v表示 记为u->v
则有 sg[u]=mex(sg[v]) (u->v)
可以发现 如果一个状态没有状态可以转移 则它的sg值为0
而且如果一个状态的sg值为k 它可以转移到sg值为0~k-1的任意数 且必转不到k

这不就是nim吗- –

so 对于一个由n个子游戏组成的大游戏的sg值 就是所有子游戏sg值的异或和~~
——————————————–
然后就是各种题解了 个人觉得博弈题目的解题思想还是要考写博弈题目来总结
题解放在下一篇吧= =

传说中的——动态树。。

在apio题解中间插播一个动态树~~~

动态树是一个灰常神奇的thing,据说可以替代各种算法= = 。虽然我不会、
动态树一般用link-cut tree(就象平衡树用splay吧)
本来以为splay的代码是所有算法里最long的。。
现在发现TA弱爆了
动态数是用splay维护的= =。也就是说splay只是动态树的一小段代码~
so
我顺便写一个模板题都要200+行。。。
一个略难的代码写了快400行。。。。。。。。
感觉考试的时候就算有裸动态树我还是不怎么敢写- –
好吧。 不瞎扯了。切入正题
(正版动态树看yangzhe的《QTREE解法的一些研究》)
先给个模板题:
给一棵共有 n(n ≤ 10000) 个结点的树, 每条边都有一个权值, 要求维护一个数据结构, 支持如下操作:
1. 修改某条边的权值;
2. 询问某两个结点之间的唯一通路上的最大边权.
动态树的核心思想是:
引入了一个实边和虚边的概念 对于一个节点 到它的子节点 不一定有 但是仅有一条实边 其他的都是虚边
splay维护的就是一串连续的实边
在平衡树中 对于某个节点的左子树都是在从真正根到这个节点的路径上的点 右子树则是这个节点下面的点
也就是说 在平衡树中 节点的关键字就是节点的深度(在一棵平衡树中每个深度仅会出现一次)
不妨设实边是特殊的虚边
其实虚边把整个图连成了一个树
这棵数仅由每个节点对它的father的记忆组成 换句话说 在这棵数中对于每个节点都知道它的father
如果一个节点知道他的儿子 就说明这个节点和这个儿子在现实中有实边相连
如果只看实边 这棵数就是一个平衡数森林
动态树里一个主要的函数:access(int now)
用于吧从根到now的路径都变成实边(也称为访问now)
//下面用的是poj2763的程序
实现方法如下:
把now旋到所在的平衡树的根
while(now有father)
  把now的father旋到头 砍掉右子树(把对右子树的实边变为虚边)
  把father右子树赋值为now(把对now的虚边变为实边)
  吧now旋到根
end_while
然后讲下动态树各种操作的实现吧
query(int from, int to)//询问from节点到to节点的sum(或最小权或最大权什么的同理)
void query(int f, int t)
{
  int ans = 0;
  int o = lca(f, t);//lca也可以用动态树求 ==写。
  access(f);//访问f
  cut(a[f].r);//把f对右子树的实边变为虚边
  splay(o);//把公共祖先旋到根 (o必定在f所在的平衡数中)
  ans += a[a[o].r].sum;//因为f把他下面的边都砍掉了 所以当o是根时 o的右子树就是从f到o~~
  //下面同理
  access(t);
  cut(a[t].r);
  splay(o);
  ans += a[a[o].r].sum;
  printf(“%d\n”, ans);
}
———————求lca 感觉跟access挺像。。——————–
int getroot(int now)//求now所在实边树在现实中的根
{
  splay(now);
  while (a[now].l) now = a[now].l;
  return now;
}
int lca(int on, int tw)
{
  access(on);
  cut(a[on].r);
  int i = getroot(tw);
  while (i != 1)
  {
    tw = fa[i];
    i = getroot(tw);
  }
  return tw;
}
—————————————-change边权——————————————–
void up(int now) //更新now节点的sum
{
  a[now].sum = a[now].w+a[a[now].l].sum+a[a[now].r].sum;
}
void change(int now, int w)
{
  now = wt[now];//题目需要 一般没这句 求now这条边对应的节点
  splay(now);//把now旋到根 因为要更新now的权 如果不旋到根 会影响他father和father的的的……father的sum
  a[now].w = w;//change
  up(now);     //更新now节点的sum
}
———————————————————————————-
其实这两个操作用树链剖分做更快。。 动态树主要的功能是 可以改变原树的形状 (hdu4010)
这主要是需要一个操作:totop(int now)
让now变成原树的根(仅对于无根树)
思路为:
把从真根到now的路径变反
访问now 砍掉now的右子树(现在以now为根的树就是从根到now)
然后要用一个标记下传
————————————————————————————-
inline void rev(int x)
{
  if (!x) return;
  swap(a[x].l, a[x].r);//这就是吧边反向
  a[x].rev ^= 1;
}
inline void totop(int x)
{
  access(x);
  cuts(a[x].r);
  rev(x);
}
—————————————————————————-
如果一个节点的rev=1 说明他的子树的边都要反向
—————————–
如果用了标记下传 每次splay之前要吧平衡树根到now的根都down一次
inline void down(int x)
{
  if (!x) return;
  if (a[x].rev)
  {
    rev(a[x].l);
    rev(a[x].r);
    a[x].rev = false;
  }
}
inline void splay(int x)
{
  int tp = 0;
  int now = x;
  while (true)
  {
    be[tp++] = now;
    if (a[now].root) break;
    now = a[now].fa;
  }
  while (tp) down(be[–tp]);
  now = x;
  …
  …
  …
}
讲一个优化吧。。
虽然是splay的优化
在左旋右旋的时候可以不要up(now)
直到splay完一次up(now)就行了<spoj375 TLE到AC的优化啊 。。。。。。。。。。。。。。>
———————————————-code poj2763——————————————-
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 500000;
struct node
{
  int l, r, fa, w, sum;
  bool root;
}a[maxn];
struct line
{
  int to, v, next, num;
}li[maxn];
int be[maxn], wt[maxn], fa[maxn], l, n, m;
queue<int> q;
void makeline(int f, int t, int v, int num)
{
  l++;
  li[l].next = be[f];
  be[f] = l;
  li[l].to = t;
  li[l].v = v;
  li[l].num = num;
}
void maketree()
{
  q.push(1);
  a[1].root = true;
  while (!q.empty())
  {
    int f = q.front();
    q.pop();
    for (int i = be[f]; i; i = li[i].next)
    {
      int to = li[i].to;
      if (to == a[f].fa) continue;
      a[to].fa = f;
      fa[to] = f;
      a[to].w = li[i].v;
      a[to].sum = li[i].v;
      a[to].root = true;
      wt[li[i].num] = to;
      q.push(to);
    }
  }
}
void up(int now)
{
  a[now].sum = a[now].w+a[a[now].l].sum+a[a[now].r].sum;
}
void cut(int now)
{
  if (!now) return;
  int f = a[now].fa;
  if (!f) return;
  a[now].root = true;
  if (a[f].l == now) a[f].l = 0;
  if (a[f].r == now) a[f].r = 0;
  up(f);
}
void left(int now)
{
  int f = a[now].fa;
  a[now].fa = a[f].fa;
  if (a[a[f].fa].l == f) a[a[f].fa].l = now;
  if (a[a[f].fa].r == f) a[a[f].fa].r = now;
  a[f].fa = now;
  a[f].r = a[now].l;
  a[a[now].l].fa = f;
  a[now].l = f;
  up(f);
  a[now].root = a[f].root;
  a[f].root = false;
}
void right(int now)
{
  int f = a[now].fa;
  a[now].fa = a[f].fa;
  if (a[a[f].fa].l == f) a[a[f].fa].l = now;
  if (a[a[f].fa].r == f) a[a[f].fa].r = now;
  a[f].fa = now;
  a[f].l = a[now].r;
  a[a[now].r].fa = f;
  a[now].r = f;
  up(f);
  a[now].root = a[f].root;
  a[f].root = false;
}
void splay(int now)
{
  while (!a[now].root)
  {
    int f = a[now].fa;
    if (a[f].root)
    {
      if (a[f].l == now) right(now);
      else left(now);
    }
    else
      if (a[a[f].fa].l == f)
        if (a[f].l == now) right(f), right(now);
        else left(now), right(now);
      else
        if (a[f].l == now) right(now), left(now);
        else left(f), left(now);
  }
  up(now);
}
void access(int now)
{
  splay(now);
  while (a[now].fa)
  {
    int f = a[now].fa;
    splay(f);
    cut(a[f].r);
    a[f].r = now;
    a[now].root = false;
    up(f);
    splay(now);
  }
}
int getroot(int now)
{
  splay(now);
  while (a[now].l) now = a[now].l;
  return now;
}
int lca(int on, int tw)
{
  access(on);
  cut(a[on].r);
  int i = getroot(tw);
  while (i != 1)
  {
    tw = fa[i];
    i = getroot(tw);
  }
  return tw;
}
void query(int f, int t)
{
  int ans = 0;
  int o = lca(f, t);
  access(f);
  cut(a[f].r);
  splay(o);
  ans += a[a[o].r].sum;
  access(t);
  cut(a[t].r);
  splay(o);
  ans += a[a[o].r].sum;
  printf(“%d\n”, ans);
}
void change(int now, int w)
{
  now = wt[now];
  splay(now);
  a[now].w = w;
  up(now);
}
int main()
{
freopen(“poj2763.in”, “r”, stdin);
freopen(“poj2763.out”, “w”, stdout);
  int last;
  cin >> n >> m >> last;
  for (int i = 1; i < n; i++)
  {
    int f, t, v;
    scanf(“%d%d%d”, &f, &t, &v);
    makeline(f, t, v, i);
    makeline(t, f, v, i);
  }
  maketree();
  a[0].root = true;
  for (int i = 0; i < m; i++)
  {
    int qu;
    scanf(“%d”, &qu);
    if (qu)
    {
      int j, k;
      scanf(“%d%d”, &j, &k);
      change(j, k);
    }
    else
    {
      int k;
      scanf(“%d”, &k);
      query(last, k);
      last = k;
    }
  }
fclose(stdin);fclose(stdout);
}
—————————————spoj 375(QTREE)—————————————————-
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 100005;
queue<int> q;
struct line
{
  int to, next, v, num;
}li[maxn];
struct node
{
  int l, r, max, w, fa;
  bool root;
}a[maxn];
int n, m, fa[maxn], be[maxn], qu[maxn], l;
inline void makeline(int f, int t, int v, int num)
{
  l++;
  li[l].next = be[f];
  be[f] = l;
  li[l].to = t;
  li[l].v = v;
  li[l].num = num;
}
inline void bfs()
{
  q.push(1);
  while (!q.empty())
  {
    int f = q.front();
    q.pop();
    for (int i = be[f]; i != 0; i = li[i].next)
    {
      int to = li[i].to;
      if (to == a[f].fa) continue;
      qu[li[i].num] = to;
      a[to].fa = f;
      fa[to] = f;
      a[to].w = li[i].v;
      a[to].max = li[i].v;
      q.push(to);
    }
  }
}
inline int max(int a, int b, int c)
{
  int d = a > b ? a : b;
  return d > c ? d : c;
}
inline void up(int now)
{
  a[now].max = max(a[a[now].l].max, a[a[now].r].max, a[now].w);
}
inline void cut(int now)
{
  if (!now) return;
  int f = a[now].fa;
  if (!f) return;
  a[now].root = true;
  if (a[f].l == now) a[f].l = 0;
  if (a[f].r == now) a[f].r = 0;
  up(f);
}
inline void left(int now)
{
  int f = a[now].fa;
  a[now].fa = a[f].fa;
  if (a[a[f].fa].l == f) a[a[f].fa].l = now;
  if (a[a[f].fa].r == f) a[a[f].fa].r = now;
  a[f].fa = now;
  a[f].r = a[now].l;
  a[a[now].l].fa = f;
  a[now].l = f;
  up(f);
  a[now].root = a[f].root;
  a[f].root = false;
}
inline void right(int now)
{
  int f = a[now].fa;
  a[now].fa = a[f].fa;
  if (a[a[f].fa].l == f) a[a[f].fa].l = now;
  if (a[a[f].fa].r == f) a[a[f].fa].r = now;
  a[f].fa = now;
  a[f].l = a[now].r;
  a[a[now].r].fa = f;
  a[now].r = f;
  up(f);
  a[now].root = a[f].root;
  a[f].root = false;
}
inline void splay(int now)
{
  while (!a[now].root)
  {
    int f = a[now].fa;
    if (a[f].root)
    {
      if (a[f].l == now) right(now);
      else left(now);
    }
    else
      if (a[a[f].fa].l == f)
      {
        if (a[f].l == now) right(f), right(now);
        else left(now), right(now);
      }
      else
      {
        if (a[f].l == now) right(now), left(now);
        else left(f), left(now);
      }
  }
  up(now);
}
inline void access(int now)
{
  splay(now);
  while (a[now].fa)
  {
    int f = a[now].fa;
    splay(f);
    cut(a[f].r);
    a[f].r = now;
    a[now].root = false;
    up(f);
    splay(now);
  }
}
inline int getroot(int now)
{
  splay(now);
  while (a[now].l) now = a[now].l;
  return now;
}
inline int lca(int on, int tw)
{
  access(on);
  cut(a[on].r);
  int i = getroot(tw);
  while (i != 1)
  {
    tw = fa[i];
    i = getroot(tw);
  }
  return tw;
}
inline void query(int f, int t)
{
  int o = lca(f, t);
  access(f);
  cut(a[f].r);
  splay(o);
  int m1 = a[a[o].r].max;
  access(t);
  cut(a[t].r);
  splay(o);
  int m2 = a[a[o].r].max;
  printf(“%d\n”, max(m1, m2, 0));
}
inline void change(int now, int w)
{
  now = qu[now];
  splay(now);
  a[now].w = w;
  up(now);
}
int main()
{
freopen(“spoj375.in”, “r”, stdin);
freopen(“spoj375.out”, “w”, stdout);
  int test;
  cin >> test;
  while (test–)
  {
    l = 0;
    scanf(“%d”, &n);
    for (int i = 0; i <= n; i++)
    {
      be[i] = 0, a[i].l = 0, a[i].r = 0;
      a[i].fa = 0, a[i].max = 0, a[i].w = 0;
      a[i].root = true;
    }
    for (int i = 1; i < n; i++)
    {
      int fr, to, va;
      scanf(“%d%d%d”, &fr, &to, &va);
      makeline(fr, to, va, i);
      makeline(to, fr, va, i);
    }
    bfs();
    char s[10];
    scanf(“%s”, s);
    while (s[0] != ‘D’)
    {
      int j, k;
      scanf(“%d%d\n”, &j, &k);
      if (s[0] == ‘Q’) query(j, k);
      if (s[0] == ‘C’) change(j, k);
      scanf(“%s”, s);
    }
  }
fclose(stdin);fclose(stdout);
}
———————————————hdu4010————————————-
#include <cstdio>
#include <queue>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 300005;
queue<int> q;
struct node
{
  int lazy, l, r, fa, max, w;
  bool root, rev;
}a[maxn];
struct line
{
  int to, next;
}li[maxn*2];
int be[maxn], n, l;
inline void debug()
{
  for (int i = 0; i <= n; i++)
  cout << i << “-  lazy:” << a[i].lazy << ” l:” << a[i].l << ” r:” << a[i].r
   << ” fa:” << a[i].fa << ” max:” << a[i].max << ” w:” << a[i].w << ” root:” << a[i].root
    << ” rev:” << a[i].rev << endl;
    cout << endl;
}
inline void rev(int x)
{
  if (!x) return;
  swap(a[x].l, a[x].r);
  a[x].rev ^= 1;
}
inline void inc(int x, int w)
{
  if (!x) return;
  a[x].lazy += w;
  a[x].w += w;
  a[x].max += w;
}
inline int max(int a, int b, int c)
{
  int d = a > b ? a : b;
  return d > c ? d : c;
}
inline void makeline(int f, int t)
{
  l++;
  li[l].next = be[f];
  be[f] = l;
  li[l].to = t;
}
inline void maketree()
{
  q.push(1);
  while (!q.empty())
  {
    int f = q.front();
    q.pop();
    for (int i = be[f]; i != 0; i = li[i].next)
    {
      int to = li[i].to;
      if (to == a[f].fa) continue;
      q.push(to);
      a[to].fa = f;
    }
  }
}
inline void down(int x)
{
  if (!x) return;
  if (a[x].rev)
  {
    rev(a[x].l);
    rev(a[x].r);
    a[x].rev = false;
  }
  if (a[x].lazy)
  {
    int w = a[x].lazy;
    inc(a[x].l, w);
    inc(a[x].r, w);
    a[x].lazy = 0;
  }
}
inline void up(int x)
{
  a[x].max = max(a[a[x].l].max, a[a[x].r].max, a[x].w);
}
inline void cuto(int x)
{
  if (!x) return;
  int f = a[x].fa;
  if (!f) return;
  down(f);
  a[x].root = true;
  if (a[f].l == x) a[f].l = a[x].fa = 0;
  if (a[f].r == x) a[f].r = a[x].fa = 0;
  up(f);
}
inline void cuts(int x)
{
  if (!x) return;
  int f = a[x].fa;
  if (!f) return;
  down(f);
  a[x].root = true;
  if (a[f].l == x) a[f].l = 0;
  if (a[f].r == x) a[f].r = 0;
  up(f);
}
inline void left(int x)
{
  int fa = a[x].fa;
  a[x].fa = a[fa].fa;
  if (a[a[fa].fa].l == fa) a[a[fa].fa].l = x;
  if (a[a[fa].fa].r == fa) a[a[fa].fa].r = x;
  a[fa].fa = x;
  a[fa].r = a[x].l;
  a[a[x].l].fa = fa;
  a[x].l = fa;
  up(fa);
  up(x);
  a[x].root = a[fa].root;
  a[fa].root = false;
}
inline void right(int x)
{
  int fa = a[x].fa;
  a[x].fa = a[fa].fa;
  if (a[a[fa].fa].l == fa) a[a[fa].fa].l = x;
  if (a[a[fa].fa].r == fa) a[a[fa].fa].r = x;
  a[fa].l = a[x].r;
  a[a[x].r].fa = fa;
  a[x].r = fa;
  a[fa].fa = x;
  up(fa);
  up(x);
  a[x].root = a[fa].root;
  a[fa].root = false;
}
inline void splay(int x)
{
  int tp = 0;
  int now = x;
  while (true)
  {
    be[tp++] = now;
    if (a[now].root) break;
    now = a[now].fa;
  }
  while (tp) down(be[–tp]);
  now = x;
  while (!a[now].root)
  {
    int fa = a[now].fa;
    if (a[fa].root)
    {
      if (a[fa].l == now) right(now);
      else left(now);
    }
    else
      if (a[a[fa].fa].l == fa)
      {
        if (a[fa].l == now) right(fa), right(now);
        else left(now), right(now);
      }
      else
      {
        if (a[fa].l == now) right(now), left(now);
        else left(fa), left(now);
      }
  }
}
inline void access(int x)
{
  splay(x);
  while (a[x].fa)
  {
    int f = a[x].fa;
    splay(f);
    cuts(a[f].r);
    a[f].r = x;
    a[x].root = false;
    up(f);
    splay(x);
  }
}
inline void top(int x)
{
  access(x);
  cuts(a[x].r);
  rev(x);
}
inline int root(int x)
{
  access(x);
  while (a[x].l)
  {
    down(x);
    x = a[x].l;
  }
  down(x);
  return x;
}
inline void link(int f, int t)
{
  if (root(f) == root(t))
  {
    printf(“-1\n”);
    return;
  }
  top(f);
  a[f].fa = t;
  access(f);
}
inline void cut(int f, int t)
{
  if (f == t || root(f) != root(t))
  {
    printf(“-1\n”);
    return;
  }
  top(f);
  access(t);
  cuto(a[t].l);
}
inline int getroot(int x)
{
  splay(x);
  while (a[x].l)
  {
    down(x);
    x = a[x].l;
  }
  down(x);
  return x;
}
inline int getfa(int x)
{
  access(x);
  int i;
  for (i = a[x].l; a[i].r; i = a[i].r);
  return i;
}
inline int lca(int on, int tw)
{
  access(on);
  cuts(a[on].r);
  int i = getroot(tw);
  while (getfa(i))
  {
    tw = getfa(i);
    i = getroot(tw);
  }
  return tw;
}
inline void get(int f, int t)
{
  if (root(f) != root(t))
  {
    printf(“-1\n”);
    return;
  }
  int o = lca(f, t);
  access(f);
  cuts(a[f].r);
  splay(o);
  int m1 = a[a[o].r].max;
  access(t);
  cuts(a[t].r);
  splay(o);
  int m2 = a[a[o].r].max;
  printf(“%d\n”, max(m1, m2, a[o].w));
}
inline void change(int f, int t, int w)
{
  if (root(f) != root(t))
  {
    printf(“-1\n”);
    return;
  }
  int o = lca(f, t);
  access(f);
  cuts(a[f].r);
  splay(o);
  inc(a[o].r, w);
  access(t);
  cuts(a[t].r);
  splay(o);
  inc(a[o].r, w);
  a[o].w += w;
  a[o].max += w;
}
int main()
{
freopen(“hdu4010.in”, “r”, stdin);
freopen(“hdu4010.out”, “w”, stdout);
  while (cin >> n)
  {
    memset(a, 0, sizeof(a));
    l = 0;
    memset(be, 0, sizeof(be));
    memset(li, 0, sizeof(li));
    for (int i = 1; i < n; i++)
    {
      int f, t;
      scanf(“%d%d”, &f, &t);
      makeline(f, t);
      makeline(t, f);
    }
    for (int i = 1; i <= n; i++) scanf(“%d”, &a[i].w), a[i].max = a[i].w, a[i].root = true;
    a[0].root = true;
    maketree();
    int m;
    cin >> m;
    for (int i = 0; i < m; i++)
    {
      int t, j, k;
      scanf(“%d%d%d”, &t, &j, &k);
      if (t == 1) link(j, k);
      else
      if (t == 2) cut(j, k);
      else
      if (t == 3)
      {
        int l;
        scanf(“%d”, &l);
        change(k, l, j);
      }
      else get(j, k);
    }
    cout << endl;
  }
fclose(stdin);fclose(stdout);
}
↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑传说中的约等于400行代码↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑
!@#¥%#¥@……&……%*……&(&*)——&¥……#¥#@
话说。。spoj真nimus太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了太慢了
TLE还以为是死循环。。。 结果加个常数优化就过了。。。。。。
题目:
bzoj1036
bzoj2002
hdu4010
poj2763
poj3237
spoj375
spoj913
spoj QTREE3
===================================================================
又好长啊。。。。

网络流<一>–最大流模板

数组a为线段数组(链表) maxn为网络流最大点数   以下为sap各种优化后的最大流模板

   我一般在做网络流时copy至程序~<因为打得跟快排一样了、、so。>
(程序下面有说明- -)
——————————————————————————————————————–
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
struct line
{
  int to, v, opt, next;
};
const int maxn = 1000;
const int INF = 100000;
line a[100000];
int dist[maxn], note[maxn], be[maxn], l, n, s, t;
void makeline(int f, int t, int v, int opt)
{
  l++;
  a[l].next = be[f];
  be[f] = l;
  a[l].to = t;
  a[l].v = v;
  a[l].opt = opt;
}    //链表的加入线段函数
int min(int a, int b)
{
  if (a > b) return b;
  else return a;
}//min..
void clear()
{
  memset(a, 0, sizeof(a));
  memset(be, 0, sizeof(be));
  memset(dist, 0, sizeof(dist));
  memset(note, 0, sizeof(note));
  l = 0;
}   //清空函数 有多组数据的题目或要二分的网络流要用 不然。。。。。。。。
int sap(int now, int maxf)
{
  if (now == t) return maxf;    //判断现在节点是否为t(汇)
  int i = be[now];     //链表的开始、不解释= =
  int sum = 0;    //多流优化
  int minn = n;    //不知道叫什么的优化、本来我叫他dinic优化 据说不是- –
  while (i != 0)
  {
    if (dist[a[i].to]+1 == dist[now] && a[i].v > 0)
    {
      int d = sap(a[i].to, min(maxf-sum, a[i].v));
      sum += d;   //多流
      a[i].v -= d;
      a[a[i].opt].v += d;
      if (sum == maxf || dist[s] >= n) return sum;
    }
    if (a[i].v > 0) minn = min(minn, dist[a[i].to]);    //不知道的优化
    i = a[i].next;
  }
  if (sum == 0)
  {
    note[dist[now]]–;  
    if (note[dist[now]] == 0)    
    {
      dist[s] = n;
      return 0;                     
    }     
    dist[now] = minn+1;   //不知道优化1号
    note[dist[now]]++;   //note优化?、、又一个不知道叫什么的优化
  }
  return sum;
}   //SAP函数
int main()
{
  freopen(“poj.in”,”r”,stdin);
  freopen(“poj.out”,”w”,stdout);
    /*
      …
      …
    */
    s = 0;
    t = 999;
    note[0] = n;
    int ans = 0;
    while (dist[s] < n) ans += sap(s, INF);
    cout << ans;
  fclose(stdin);fclose(stdout);
}
——————————————————————————————————————–
sap:                  很像深搜。。找到一条可增广的路就增广之   这条路的容量减这次的增广大小
                      并把反向边容量加这次的增广大小   每次找到的容量加到ans   ans即为ans~
多流:                 原本的sap只要一遇到可增广的路直接马上增广   即上面sap中的变量d>0时  就把这条
                      路的容 量减这次的增广大小  并把反向边容量加这次的增广大小   返回d
                      多流则是把有连当前点的增光路能增广的都增广了   多了一个sum
                      为当前点已经增广的大小    显然sum不能大于maxf 。。
不知道优化1号:   用一个dist数组   记录每个点的一个值(其实是离t的距离)  当且仅当 当前点指向的
                        点的dist值等于当前点的dist值加1时   才增广这个点       如果一个都增广不到  
                        就把当前点的dist赋为所有当前点指向的所有点的dist值的最小值+1
不知道优化2号:这个优化是基于上面那个优化的优化  用一个note数组记录dist数组里的值的个数 
                        如果一个曾经在dist数组里出现的数 在某一时刻在整个dist数组里都没有了
                        就说明整个网络已经增广完 了
 
——————————————————————————————————————–
ps:以上优化皆有证明    自己百度= =
 
感想:其实网络流做了几题就会发现 网络流怎么写根本不是网络流的核心
          网络流真正的核心其实是——建图
          网络流打了几次之后就可以copy代码了= =  
          网络流在所有题目一般一个字母都不会变   
          而且又长
          比快排还需要考代码
          其实快排我从来没考过代码- –
          因为短
          而且每次用的数组名都不一样 = =
          可见网络流是多么不变
          连数组都固定= =
          ~

↑很像诗有木有

↑说到诗 我想到了斜率优化的一个题目= =

斜率优化就是跟网络流完全相反…

斜率优化是理解了+会打了 就无敌了。。。

↑…………………..

斜率优化

 

在被坑爹的斜率优化虐了1week之后。。终于出头了o(∩_∩)o…哈哈

 

在思考了一个晚上要怎么纪念悲剧的结束之后-写了一下这个boring的thing
——————————————————————————————————————–

1010: [HNOI2008]玩具装箱toy

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 2506  Solved: 834
[Submit][Status][Discuss]

 

 

 

 

Description

P教授要去看奥运,但是他舍不下他的玩具,于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩,其可以将任意物品变成一堆,再放到一种特殊的一维容器中。P教授有编号为1…N的N件玩具,第i件玩具经过压缩后变成一维长度为Ci.为了方便整理,P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具,那么两件玩具之间要加入一个单位长度的填充物,形式地说如果将第i件玩具到第j个玩具放到一个容器中,那么容器的长度将为 x=j-i+Sigma(Ck) i<=K<=j 制作容器的费用与容器的长度有关,根据教授研究,如果容器长度为x,其制作费用为(X-L)^2.其中L是一个常量。P教授不关心容器的数目,他可以制作出任意长度的容器,甚至超过L。但他希望费用最小.

Input

第一行输入两个整数N,L.接下来N行输入Ci.1<=N<=50000,1<=L,Ci<=10^7

Output

输出最小费用

Sample Input

5 4
3
4
2
1
4

Sample Output

1

HINT

Source

——————————————————————————————————————–
上面是一个经典的斜率优化题目。。
为了突出斜率优化的优势 不妨设n<=1000000~
此时nlgon就一边去吧~~
经过深思熟虑 不难得出本题的O(N^2)的方程:f[i]=min(f[j]+(c[i]-c[j]-L-1)^2)
其中 f[i]表示前i个玩具放完的最小$$
       c[i]=前i个玩具长的和+i
为什么这样定义?、因为如果直接用前i个玩具长的和的话 j+1~i 塞在一堆表示是c[i]-c[j]+i-j-1
so麻烦啊
so。。。
然后吧方程化开 =f[j]+(c[i]-1-L)^2+c[j]^2-2*c[i]*c[j]+2*c[j]+2*L*c[j];
再把所有项里跟j完全无关的都干掉(因为那些对于判断哪个j比较优没影响)
=>   f[j]+c[j]^2-2*c[i]*c[j]+2*c[j]+2*L*c[j]
<你不干掉也nothing。。但是还是干掉好。。。>
再把所有只和j有关的项扔在一起:
 f[j]+c[j]^2+2*c[j]+2*L*c[j]     -2*c[i]*c[j]
然后把只和j有关的项扔在一起的设为y , y=f[j]+c[j]^2+2*c[j]+2*L*c[j]
再设呢个有i有j的项里的和j有关的东西设为x,x=c[j]
然后~  f[i]=y-2*c[i]*x
       =>y=2*c[i]*x+f[i]
对于每个点i有一个在坐标系上的坐标(c[i],f[i]+c[i]^2+2*c[i]+2*L*c[i])
因为斜率(2*c[i])单调上升所以可以用单调队列维护一个凸壳(方程取min的是维护下凸壳  max为上)
判断head能不能用的方法就是:
对于现在的i可以设有一个斜率为2*c[i]的直线从灰常灰常远的地方灰了过来
 第一个切到那个凸壳的时刻 切到凸壳的那个角的值就是对于这个i最优的j
然后f[i]就可以出来啦~~~
怎么判断时候切到呢 先把队列的head和队列的head+1比较:
把斜率2*c[i]带入两个点 分边求出一个b(即为y=2*c[i]*x+f[i]中的f[i])
比较其大小 如图:psb
显然绿(head)的b>蓝(head+1)的b
下一个点同理
但是只要一到切点 就。。。。

psb (1)

 

蓝>绿~~~~

而且对于i上升 i的斜率也会上升 所以他们切那个凸壳的切点只会越来越后面
也就是对于前面删除的点 后面不用在考虑了~
最后一步是维护凸壳 相当于加入一个坐标(c[i],f[i]+c[i]^2+2*c[i]+2*L*c[i])
再把 i tail tail-1三个判断:向量tail -> i 指向 向量tail-1 -> tail的左或右
对于下凸壳 左就说明是凸壳 右就不是 要dec(tail)
对于上凸壳反之.
CODE:
 
#include <cstdio>
const int maxn=200005;
long long team[maxn],f[maxn],c[maxn],y[maxn];
bool work(int i,int j,int k)
{
  if (y[j]-2*c[i]*c[j]>y[k]-2*c[i]*c[k]) return true;else return false;
}
// 判断直线和凸壳的切点
//这段程序在别的程序各种变形都是差不多的 只是我们判断的方法不一样 结果是一样的~
bool del(int i,int j,int k)
{
  if ((c[j]-c[k])*(y[i]-y[j])-(c[i]-c[j])*(y[j]-y[k])<0) return true;
  else return false;
}
//维护凸壳
//向量的叉乘? 好像是叫这个 。。。
int main()
{
freopen(“bzoj1010.in”,”r”,stdin);
freopen(“bzoj1010.out”,”w”,stdout);
  int n;long long l;
  scanf(“%d%I64d”,&n,&l);
  for (int i=1;i<=n;i++)
  {
    scanf(“%I64d”,&c[i]);
    c[i]+=c[i-1];
  }
  int h=0;int t=0;
  //一开始让h=t可以让队列的第一个值代表j=0(就是全部玩具在一起) 就不用特判了
  for (int i=1;i<=n;i++) c[i]+=i;
  for (int i=1;i<=n;i++)
  {
    while (h<t && work(i,team[h],team[h+1])) h++;
    int j=team[h];
    f[i]=f[j]+(c[i]-c[j]-l-1)*(c[i]-c[j]-l-1); //team[h]直接就是对于i的最优解了
    y[i]=f[i]+c[i]*c[i]+2*c[i]*(l+1);
    while (h<t && del(i,team[t],team[t-1])) t–;
    t++;
    team[t]=i;
  }
  printf(“%I64d”,f[n]);
fclose(stdin);fclose(stdout);
}
ps:如果斜率不是递增的也是可以做的 但是要nlogn就是了 而且据说极其麻烦= =。。
 
再次ps:如果斜率递减就反过来做 就递增了~  注意维护凸包那里会不一样!<被这个坑了很久 …..>