BZOJ 3437: 小P的牧场

这题一看就是奇怪的dp啊╮(╯_╰)╭
f[i]表示考虑前i个牧场 且第i个有取的最小代价
但是把这个方程列出来 会发现这个方程有一部分的系数是一个公差为1的等差数列
这就很蛋疼
不能以一个项数为O(1)级的多项式表示i取j决策的代价

怎么办呢
所谓正难则反
首先设答案为类似只在n+1号位置取一个观察站 的代价
如果这时候在i位置取一个观察站 则答案会减少(sum[i] * (n – i) – a[i])
f[i]表示考虑i~n的牧场 最多可以扣掉多少代价 且i有取
方程为
f[i] = max(a[i] + f[j] + sum[i] * (j – i))
sum[i]表示Σ(b[j])(1 <= j <= i) 这个方程拿去斜率优化一下即可 另外这个系列的数据范围巨坑无比 n的范围是100w 他写变成n <= 1000000,0 后面加了个,0不知道作何心态=-=

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;
 
const ll maxn = 1000 * 1000 + 5;
 
struct poll
{
    ll x, y;
    poll(ll a = 0, ll b = 0) : x(a), y(b) {}
};
 
poll q[maxn];
ll f[maxn], n, a[maxn], b[maxn], sum[maxn], h, t;
ll ans;
 
ll xj(poll a, poll b, poll c)
{
    return ((ll)b.x - a.x) * (c.y - a.y) - ((ll)b.y - a.y) * (c.x - a.x);
}
 
ll calc(ll i, poll j)
{
    return -a[i] + j.y + sum[i] * (j.x - i);
}
 
int main()
{
    scanf("%lld", &n);
    for (ll i = 0; i < n; ++i)
        scanf("%lld", &a[i]);
    for (ll i = 0; i < n; ++i)
    {
        scanf("%lld", &b[i]);
        ans += ((ll)n - i) * b[i];
        if (!i) sum[i] = b[i];
        else sum[i] = sum[i - 1] + b[i];
    }
    f[n - 1] = sum[n - 1] - a[n - 1];
    h = t = 0;
    q[0] = poll(n - 1, f[n - 1]);
    ll as = f[n - 1];
    for (ll i = n - 2; i >= 0; --i)
    {
        while (h < t && calc(i, q[h]) <= calc(i, q[h + 1])) ++h;
        f[i] = calc(i, q[h]);
        while (h < t && xj(q[t - 1], q[t], poll(i, f[i])) <= 0) --t;
        q[++t] = poll(i, f[i]);
        as = max(as, f[i]);
    }
    printf("%lld", ans - as);
}

BZOJ 3439: Kpm的MC密码【论splay的正确姿势】

这题本身很简单
就是把串反过来做trie+区间k大即可
但是这题主席树做空间不够(应该是不够吧0.0)
于是就按拓扑序做启发式合并平衡树
刚好早上被黄神神d模板过长 于是orz了贵校的模板 学习了下
这是spaly的一些函数的科学写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
void rot(int now, int p)
{
    int fa = t[now].fa, q = t[t[fa].fa].c[1] == fa;
    t[now].fa = t[fa].fa;
    if (t[fa].fa) t[t[fa].fa].c[q] = now;
    t[fa].c[p] = t[now].c[!p];
    t[t[now].c[!p]].fa = fa;
    t[now].c[!p] = fa, t[fa].fa = now;
    up(fa), up(now);
}

int splay(int now)
{
    for (int fa, p, q; fa = t[now].fa;)
    {
        p = t[fa].c[1] == now, q = t[t[fa].fa].c[1] == fa;
        if (!t[fa].fa) rot(now, p);
        else rot(p == q ? fa : now, p), rot(now, q);
    }
    return now;
}

int ins(int now, int v)
{
    t[v].c[0] = t[v].c[1] = t[v].fa = 0, t[v].sum = 1;
    if (!now) return v;
    int fa, p;
    for (; now; fa = now, now = t[now].c[p = v > now])
        ++t[now].sum;
    t[v].fa = fa;
    t[fa].c[p] = v;
    return splay(v);
}

int query(int now, int k)
{
    for (int lsum; (lsum = t[t[now].c[0]].sum) != k - 1; )
        if (lsum >= k) now = t[now].c[0];
        else now = t[now].c[1], k -= lsum + 1;
    return splay(now);
}

然后这题的全题代码0 0
我只能说要是用我原来的模板得多100行=-=

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 1000005;

struct node
{
    int ch[26], sum, fa;
    vector<int> to;
}tr[maxn];

struct nodes
{
    int c[2], fa, sum;
}t[maxn];

int n, d[maxn], totr, root[maxn], ans[maxn], k[maxn];
string s;
queue<int> q;

void inss(int no)
{
    for (int i = s.length() - 1, now = 1; i >= 0; --i)
    {
        int to = tr[now].ch[s[i] - 'a'];
        ++tr[now].sum;
        if (!to)
        {
            to = tr[now].ch[s[i] - 'a'] = ++totr;
            tr[to].fa = now;
            ++d[now];
        }
        if (!i) tr[to].to.push_back(no), ++tr[to].sum;
        now = to;
    }
}

void up(int now)
{
    t[now].sum = t[t[now].c[0]].sum + t[t[now].c[1]].sum + 1;
}

void rot(int now, int p)
{
    int fa = t[now].fa, q = t[t[fa].fa].c[1] == fa;
    t[now].fa = t[fa].fa;
    if (t[fa].fa) t[t[fa].fa].c[q] = now;
    t[fa].c[p] = t[now].c[!p];
    t[t[now].c[!p]].fa = fa;
    t[now].c[!p] = fa, t[fa].fa = now;
    up(fa), up(now);
}

int splay(int now)
{
    for (int fa, p, q; fa = t[now].fa;)
    {
        p = t[fa].c[1] == now, q = t[t[fa].fa].c[1] == fa;
        if (!t[fa].fa) rot(now, p);
        else rot(p == q ? fa : now, p), rot(now, q);
    }
    return now;
}

int ins(int now, int v)
{
    t[v].c[0] = t[v].c[1] = t[v].fa = 0, t[v].sum = 1;
    if (!now) return v;
    int fa, p;
    for (; now; fa = now, now = t[now].c[p = v > now])
        ++t[now].sum;
    t[v].fa = fa;
    t[fa].c[p] = v;
    return splay(v);
}

int query(int now, int k)
{
    for (int lsum; (lsum = t[t[now].c[0]].sum) != k - 1; )
        if (lsum >= k) now = t[now].c[0];
        else now = t[now].c[1], k -= lsum + 1;
    return splay(now);
}

int dfs(int now, int root)
{
    if (!now) return root;
    root = dfs(t[now].c[0], root);
    root = dfs(t[now].c[1], root);
    root = ins(root, now);
    return root;
}

int merge(int u, int v)
{
    if (!u) return v;
    if (!v) return u;
    if (t[u].sum < t[v].sum) swap(u, v);
    return dfs(v, u);
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    scanf("%d", &n);
    totr = 1;
    for (int i = 1; i <= n; ++i)
    {
        s = "";
        char c = getchar();
        while (!(c >= 'a' && c <= 'z')) c = getchar();
        while (c >= 'a' && c <= 'z')
        {
            s += c;
            c = getchar();
        }
        inss(i);
    }
    for (int i = 1; i <= n; ++i)
        scanf("%d", &k[i]);

    for (int i = 1; i <= totr; ++i)
        if (!d[i])
            q.push(i);
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        for (int i = 0; i < 26; ++i)
        {
            int to = tr[now].ch[i];
            if (!to) continue;
            root[now] = merge(root[now], root[to]);
        }
        for (int i = 0; i < tr[now].to.size(); ++i)
            root[now] = ins(root[now], tr[now].to[i]);
        for (int i = 0; i < tr[now].to.size(); ++i)
        {
            int to = tr[now].to[i];
            if (k[to] > tr[now].sum) ans[to] = -1;
            else root[now] = ans[to] = query(root[now], k[to]);
        }
        if (!--d[tr[now].fa]) q.push(tr[now].fa);
    }
    for (int i = 1; i <= n; ++i)
        printf("%d\n", ans[i]);
    fclose(stdin);fclose(stdout);
}

BZOJ 3218: a + b Problem【当网络流遇上可持久化线段树】

首先搞二元关系
这个本来的关系是一坨点 是否有一个点选择了白 这个不好弄
可以转换成 是否全部选择了黑

对每个点i新建一个点i’
含义是 点i之前的a值在li~ri范围的点 是不是全部选了黑色
i’选择了全部选黑且范围内某个点选了白的代价是inf
i’选择了不是全部选择了黑且i选择了黑的代价是pi

这样就可以得到correct ans了

但是这个的边数是n^2级的 too大to过
把上面的方程解了可以发现 范围内的点要向i‘连inf的边 这个的边数是n^2的 这个就是瓶颈

怎么办呢=-=
经过黄神的提醒(边数是nlogn级的
突然想到了这题是不是可以用可持久化线段树= =
线段树的权值表示a的权值
线段树的一个节点都代表了网络流的一个节点
一个节点[t, l, r]表示1~t号节点中 a值在l~r的都向这个点直接或间接的连了inf的边
查询就是把线段树中代表1~i-1中的a值在li~ri间的节点向当前的i’连边 可以知道最多log个节点
插入就是 对于一个新的点i 权值为ai 在可持久化线段树中插入到ai位置
对于经过的新建的点t last_t->t连inf的边 i->t连inf的边 last_t是上个线段树t位置的这个节点
每次新建也是log个点 log条边
所以总边数、点数都是nlogn

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 1000005;
const int inf = 0x3fffffff;
const int inf2 = 1000 * 1000 * 1000;

//===========================NetworkFlow===============

const int NFmaxn = 1000005;
const int NFmaxm = 1000005;
const int NFinf = 0x3fffffff;

struct NF_Line
{
  int to, next, v, opt;
};

struct Network_Flow
{
  NF_Line li[NFmaxm];
  int be[NFmaxn], l, s, t, n, num[NFmaxn], note[NFmaxn];

  void makeline(int fr, int to, int v)
  {
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
    li[l].v = v;
    li[l].opt = l + 1;

    ++l;
    li[l].next = be[to];
    be[to] = l;
    li[l].to = fr;
    li[l].v = 0;
    li[l].opt = l - 1;
  }

  void create(int N)
  {
    n = N;
  }

  int sap(int now, int maxf)
  {
    if (now == t) return maxf;
    int mi = n, tot = 0;
    for (int i = be[now]; i; i = li[i].next)
    {
      int to = li[i].to;
      if (li[i].v && note[to] + 1 == note[now])
      {
        int k = sap(to, min(maxf - tot, li[i].v));
        li[i].v -= k;
        tot += k;
        li[li[i].opt].v += k;
        if (note[s] >= n || tot == maxf) return tot;
      }
      if (li[i].v) mi = min(mi, note[to]);
    }
    if (!tot)
    {
      if (!--num[note[now]])
      {
        note[s] = n;
        return 0;
      }
      ++num[note[now] = mi + 1];
    }
    return tot;
  }

  int query(int S, int T)
  {
    s = S, t = T;
    memset(num, 0, sizeof(num));
    memset(note, 0, sizeof(note));
    num[0] = n;
    int ans = 0;
    while (note[s] < n) ans += sap(s, NFinf);
    return ans;
  }

  void clear()
  {
    l = s = t = n = 0;
    memset(be, 0, sizeof(be));
    memset(num, 0, sizeof(num));
    memset(note, 0, sizeof(note));
  }
}nf;

//===========================NetworkFlow===============

struct node
{
    int l, r;
}t[maxn];

int n, m, root[maxn], tot, tot2, s, T, ans;

void query(int now, int l, int r, int lf, int rt, int p)
{
    if (!now) return;
    if (l >= lf && r <= rt)
    {
        nf.makeline(now, p, inf);
        return;
    }
    int mid = (l + r) / 2;
    if (lf <= mid) query(t[now].l, l, mid, lf, rt, p);
    if (rt >= mid + 1) query(t[now].r, mid + 1, r, lf, rt, p);
}

int ins(int no, int l, int r, int lr, int p)
{
    int now = ++tot;
    t[now] = t[no];
    if (no) nf.makeline(no, now, inf);
    nf.makeline(p, now, inf);
    if (l == r) return now;
    int mid = (l + r) / 2;
    if (lr <= mid) t[now].l = ins(t[no].l, l, mid, lr, p);
    else t[now].r = ins(t[no].r, mid + 1, r, lr, p);
    return now;
}

int main()
{
    scanf("%d", &n);
    s = ++tot, T = ++tot;
    for (int i = 1; i <= n; ++i)
    {
        int a, b, w, l, r, p, tp = ++tot, now = ++tot;
        scanf("%d%d%d%d%d%d", &a, &b, &w, &l, &r, &p);
        nf.makeline(tp, now, p);
        nf.makeline(s, now, w);
        nf.makeline(now, T, b);
        ans += w + b;
        query(root[i - 1], 0, inf2, l, r, tp);
        root[i] = ins(root[i - 1], 0, inf2, a, now);
    }
    nf.create(tot);
    printf("%d", ans - nf.query(s, T));
}

最小割小结

《浅析一类最小割问题(pty)》
这算是个解决最小割问题比较统一的方法吧 感觉是很厉害O.O
这个就是把最小割模型都转化成二元关系:(x,y)
x,y都取 代价为v1
x,y都不取 代价为v2
x取y不取 代价为v3
x不取y取 代价为v4
对于这个图233

a + b = v1
c + d = v2
a + d + f = v3
b + c + e = v4

令K = v3 + v4 – v1 – v2

如果 K < 0 那么关系图要是二分图就能做 把一侧的定义相反即可(这个的题目很少 不详写= = 首先要保证边权是非负的 K >= 0 e和f一定是非负的
可以看到每个等式中都出现了a、c中的一个 b、d中的一个
如果a、c中有边权是负的 可以把它们同时加上一个数 最后再扣掉
b、d同理
还有最好保证他们都是整数
如果出现小数 可以把所有边权都*=分母的最小公倍数 最后再除掉 (这个最小公倍数一般是2什么的= =)
然后就可以直接建图了

对于一些一元关系 某个点取有多少获利 不取有多少获利什么的 最后直接建边即可
这里对每对二元和一元关系的建边是独立的 最后再把边权加起来作为边权(不加也可以) 而不是比如对于每个二元关系s->p的权值都是一样的

注意这里求的是最小割 是最小值 有的题目求的是最大获利
有两种转化方法
一是把权值取负 然后求最小获利
二是比如你取了某个点 说明你不能不取这个点 就失去了不取这个点能获得的获利 这样就变成了最小代价了 然后最后把权值和-最小代价就是最大收益
↑其实这两个方法好像是等价的 看你怎么理解罢了=-=

==========BZOJ 3438: 小M的作物===========
这题是一个多元关系 但是也可以转成一元的
对于每个作物 s到它的边表示这个作物选择A 到t的边表示选择b
对于每个组合 新建两个点
一个点表示这些点是否全部选了A 这个点选择是的收益是c1i 否的收益是0
另外一个表示这些点是否全部选了B 这个点选择是的收益是c2i 否的收益是0
s到第一个点的边表示 是全部取A 到第二个点的边表示 不是全部取B
第一个点到t的边表示 不是全部取A 第二个点到t的边代表 是全部取B
如果第一个点选择了全部取了A 但是组合里的某个作物选择了B 这样的代价就是inf 因为是不可行的= =
对于B同理
这样就把多元关系转成了二元关系 很多多元关系的题目都可以用这个思路
然后把这个方程列啊列 最后建出来的图是一个类似最大权闭合子图的东西O.O

==========BZOJ 2127: happiness===========
这个就是非常模板的题
说一点0 0
在很多情况下可以设e=f(比如这题)
但是也有的时候设两个变量比较方便(比如上面那题) 自己看着办吧233

==========BZOJ 3218: a + b Problem===========
这题是厉害啊 我决定为这题独立开一篇文章 以表(pian)敬(I)意(P)

BZOJ 2115: [Wc2011] Xor

首先可以证明 一条从起点到终点的路径可以拆成一条从起点到终点的简单路径+一些环
只要是在图上的环 都可以选择取或不取
因为可以走到某个点 绕环一圈 然后回到起点
这样的话 就只要对每个环进行消元(求基?线性无关?什么什么的= =
然后随便找一条从起点到终点的简单路径(可以证明随便找一条都可以
在那个求出来的数组里贪心的消一消 遇0就消 然后就是答案

具体做法可以dfs 无向图的dfs树只有返祖边 一条返祖边对应一个环
每个点记录dfs树上根到这个点xor和即可
环的权=sum[now] ^ sum[to] ^ v[now][to]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const ll maxn = 50006;

struct line
{
    ll to, next, v;
}li[maxn * 4];

ll be[maxn], n, m, t[105], d[maxn], l, b[maxn];

void makeline(ll fr, ll to, ll v)
{
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
    li[l].v = v;
}

void add(ll v)
{
    for (ll i = 61; i >= 0; --i)
        if (v & (1LL << i)) v ^= t[i];
    for (ll i = 61; i >= 0; --i)
        if (v & (1LL << i))
        {
            t[i] = v;
            break;
        }
}

void dfs(ll now)
{
    for (ll i = be[now]; i; i = li[i].next)
    {
        ll to = li[i].to;
        if (b[to])
            add(d[now] ^ d[to] ^ li[i].v);
        else
        {
            d[to] = d[now] ^ li[i].v;
            b[to] = 1;
            dfs(to);
        }
    }
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    scanf("%lld%lld", &n, &m);
    for (ll i = 0; i < m; ++i)
    {
        ll fr, to, v;
        scanf("%lld%lld%lld", &fr, &to, &v);
        makeline(fr, to, v);
        makeline(to, fr, v);
    }
    b[1] = 1;
    dfs(1);
    for (ll i = 61; i >= 0; --i)
        if (!(d[n] & (1LL << i)))
            d[n] ^= t[i];
    cout << d[n];
    fclose(stdin);fclose(stdout);
}

k-string

给一个长度为n的字符串S,定义k-string为在字符串S中出现次数大于等于k次的子串,也就是存在至少k对(i,j)使得0 <= i <= j < n且Si,Si+1…Sj构成的子串与该k-string相同。现给一个初始字符串,然后执行m个操作,每个操作有两种:1.往当前字符串S末尾添加一个字符; 2.询问当前不同的k-string有多少种。

这题可以用sa的h数组做 也可以用构后缀树做
先说下sa的(我没写 只是随便写个思路=-=
【sa】
先把字符串倒过来 这样每次插入就等于插入一个后缀
给每个后缀一个编号 代表插入时询问到第几个询问了
h数组可以画成像这样的柱状图(左)
1
然后可以把它从上到下划分成好几个矩形(右)
划分可以排序+链表做

然后对于一个矩形 记录3个信息 l r h
对于这个矩形的贡献就是:l~r这些后缀中 第k个出现的时间
在这个时间后的询问 这个矩形都能对其贡献h的答案
可以维护一个数组记录改变量 最后扫一遍就可以了

询问k大 题解上写的是用划分树 主席树应该也可以

【后缀树】
其实sam构的是前缀树 那刚好连字符串都不用倒过来了
同样一个插入代表是多了一个前缀
用上面同样的方法对前缀进行标号
考虑parent树上一个节点的贡献
一个节点能有贡献 当且仅当它出现了k次 即它有k个出现了的叶子
而他的贡献是t[now].l – t[t[now].f].l
同样维护一个改变量数组即可
这里的k大是在一个类似dfs序上询问的

有一个值得注意的地方 这题的空间限制是64(32)M
直接用sam+主席树会MLE
有两种办法 1是把sam的ch数组改成map
我试了试 TLE了=-=

还有就是 从下往上计算 对每个节点维护一个大根左偏树
对于一个儿子都计算过的节点 把所有儿子合并
然后不停删根 直到树的大小为k 这时根就是第k小的时间点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 100005;

struct node
{
    int ch[27], l, f;
}t[maxn * 2];

struct line
{
    int to, next;
}li[maxn * 4];

struct t_node
{
    int l, r, dis, v;
}tt[maxn];

int ans[maxn], is[maxn], tot, last, n, m, k, p, be[maxn * 2], l, tot_node, b[maxn * 2];
string s;

void makeline(int fr, int to)
{
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
}

void add(char c, int len)
{
    c -= 'a';
    int now = ++tot, p = last;
    last = now;
    t[now].l = len;
    for (; p && !t[p].ch[c]; p = t[p].f) t[p].ch[c] = now;
    if (!p) t[now].f = 1;
    else
    if (t[p].l + 1 == t[t[p].ch[c]].l) t[now].f = t[p].ch[c];
    else
    {
        int r = ++tot, ch = t[p].ch[c];
        t[r] = t[ch];
        t[r].l = t[p].l + 1;
        t[ch].f = t[now].f = r;
        for (; p && t[p].ch[c] == ch; p = t[p].f) t[p].ch[c] = r;
    }
}

int merge(int a, int b)
{
    if (!a) return b;
    if (!b) return a;
    if (tt[a].v < tt[b].v) swap(a, b);
    tt[a].r = merge(tt[a].r, b);
    if (tt[tt[a].l].dis < tt[tt[a].r].dis) swap(tt[a].l, tt[a].r);
    tt[a].dis = tt[tt[a].r].dis + 1;
    return a;
}

pair<int, int> dfs(int now)
{
    int root = 0, sum = 0;
    if (!b[now] && t[now].l != 1)
    {
        ++tot_node;
        tt[tot_node].l = tt[tot_node].r = 0;
        tt[tot_node].dis = 1;
        tt[tot_node].v = is[t[now].l - 1];
        root = tot_node;
        sum = 1;
    }
    for (int i = be[now]; i; i = li[i].next)
    {
        pair<int, int> t = dfs(li[i].to);
        root = merge(root, t.first);
        sum += t.second;
    }
    if (now == 1 || sum < k) return make_pair(root, sum);
    while (sum > k) root = merge(tt[root].l, tt[root].r), --sum;
    ans[tt[root].v] += t[now].l - t[t[now].f].l - (!b[now] ? 1 : 0);
    return make_pair(root, sum);
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &k);
    cin >> s;
    s = '{' + s;
    tot = last = 1;
    for (int i = 0; i < s.length(); ++i)
        add(s[i], i + 1), is[i] = 0;
    for (int i = 0; i < m; ++i)
    {
        int t;
        scanf("%d", &t);
        if (t == 1)
        {
            char tc, c;
            scanf("%c%c", &tc, &c);
            is[s.length()] = p;
            s += c;
            add(c, s.length());
        }
        else ++p;
    }
    for (int i = 1; i <= tot; ++i)
        makeline(t[i].f, i), b[t[i].f] = 1;
    tot_node = 1;
    dfs(1);
    int as = 0;
    for (int i = 0; i < p; ++i)
    {
        as += ans[i];
        printf("%d\n", as);
    }
    fclose(stdin);fclose(stdout);
}

【FJOI2014-1】游记/题解

FJOI2014-1 “FJ为提高考试有效度 良心出题 成功保证所有人分数都不低于中位数”
我就是中位数啊XD 大家好啊~
WC刚被虐完就去了fz
各种颓废键盘基本没动的度过了两天(ban’nian)= =
考试的时候自然得hh
开考看题 第一题 想了20+min基本想出了正解
第二题 妈蛋 这不是昨天讲的原题?=-=
第三题 奇怪的几何 感觉20分说不定枚举中线什么的还是可以拿的233
//此时≈8:30 估分220
先pa第三题骗分 试了任意两点中点连线 中垂线 直接连线等各种奇怪的方法依然过不了= =
去上了个厕所决定不管这题了=-=
//此时≈9:20 估分200
第二题稍微回忆了下昨天讲课的东西 就开始敲
半个多小时后敲完了 发现样例过不了 手画了画 发现题目看错了XD
已经过去一半时间了 有点虚了=-=
想了十几分钟的正解 想的比较乱 也就没想出来
直接怒pa暴力磙粗=-=
//此时≈10:20 估分130
剩下第一题 奇怪的求树+树分治
树分治我就没打过几遍啊 但是感觉pa的出来于是就开始。。
一个多小时过去了//我考试的时候树分治写的不能更hh 300+行不能多说
写完了 调调样例 错了 改了改 过了 随便改了个数据 错了。。再也没有改出来QvQ
//此时12:00 估分30
中午略=-=
下午看成绩 第二题暴力全崩
//此时14:30 分数:0
【再见】

=第一题=
先求一个最短路图 然后再这个图上dfs 对于一个点的所有出点 按编号从小到大dfs
这样可以保证dfs树就是题目要求的树
然后在这棵树上跑树分治 f[i][j][2]表示前i棵子树 从根出发链长为j [0:最长长度][1:这个长度条件下的方案数]
对于第i+1棵子树 单独跑一个f'[i][j][2]意义一样 枚举这颗子树上链长 和f一起更新答案 然后用f‘更新f

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 30005;

struct line
{
    int to, next, v;
};

struct lin
{
    line li[200005];
    int be_[maxn], l;

    int be(int i) { return be_[i]; }
    int v(int i) { return li[i].v; }
    int to(int i) { return li[i].to; }
    int next(int i) { return li[i].next; }

    void makeline(int fr, int to, int v)
    {
        ++l;
        li[l].next = be_[fr];
        be_[fr] = l;
        li[l].to = to;
        li[l].v = v;
    }
}L1, L2;

queue<int> q;
stack<int> s;

int fa[maxn], n, m, k, f[maxn], g[maxn], d[maxn], fun[maxn][3], fun2[maxn][3], tot, tot2, tot1, b[maxn], dist[maxn], ans1, ans2, is[maxn], tb[maxn];
vector<pair<int, int> > v[maxn];

bool cmp(pair<int, int> a, pair<int, int> b)
{
    return a.first > b.first;
}

void spfa()
{
    memset(dist, 0x3f, sizeof(dist));
    for (q.push(1), b[1] = 1, dist[1] = 0; !q.empty();)
    {
        int now = q.front();
        q.pop();
        for (int i = L1.be(now); i; i = L1.next(i))
        {
            int to = L1.to(i);
            if (dist[to] <= dist[now] + L1.v(i)) continue;
            dist[to] = dist[now] + L1.v(i);
            if (!b[to])
            {
                b[to] = 1;
                q.push(to);
            }
        }
        b[now] = 0;
    }
}

void get_dfs(int now)
{
    for (int i = L1.be(now); i; i = L1.next(i))
    {
        int to = L1.to(i);
        if (b[to] || dist[to] != dist[now] + L1.v(i)) continue;
        b[to] = 1;
        L2.makeline(now, to, L1.v(i));
        L2.makeline(to, now, L1.v(i));
        get_dfs(to);
    }
}

int get_center(int now)
{
    int tot = 0;
    for (q.push(now), b[now] = 1; !q.empty();)
    {
        int now = q.front();
        q.pop();
        f[now] = g[now] = 0;
        s.push(now);
        ++tot;
        for (int i = L2.be(now); i; i = L2.next(i))
        {
            int to = L2.to(i);
            if (b[to] || is[to]) continue;
            fa[to] = now;
            b[to] = 1;
            q.push(to);
        }
    }
    int ret = -1;
    for (; !s.empty();)
    {
        int now = s.top();
        s.pop();
        b[now] = 0;
        f[fa[now]] += ++f[now];
        g[fa[now]] = max(g[fa[now]], f[now]);
        g[now] = max(g[now], tot - f[now]);
        if (ret == -1 || g[now] < g[ret])
            ret = now;
    }
    return ret;
}

void re(int &a, int &b, int c, int d)
{
    if (d == 0) return;
    if (a < c) a = c, b = d;
    else if (a == c) b += d;
}

void calc(int now)
{
    ++tot, ++tot1;
    fun[0][0] = tot1, fun[0][1] = 0, fun[0][2] = 1;
    int tans1 = 0, tans2 = 0;
    d[now] = 0;

    for (int p = L2.be(now); p; p = L2.next(p))
    {
        int now = L2.to(p);
        if (is[now]) continue;
        ++tot2;
        fun2[1][0] = tot2, fun2[1][1] = L2.v(p), fun2[1][2] = 1;
        for (q.push(now), b[now] = tot, d[now] = 1, dist[now] = L2.v(p); !q.empty();)
        {
            int now = q.front();
            q.pop();
            for (int i = L2.be(now); i; i = L2.next(i))
            {
                int to = L2.to(i);
                if (is[to] || b[to] == tot) continue;
                b[to] = tot;
                d[to] = d[now] + 1;
                dist[to] = dist[now] + L2.v(i);
                if (fun2[d[to]][0] != tot2)
                    fun2[d[to]][0] = tot2, fun2[d[to]][1] = dist[to], fun2[d[to]][2] = 1;
                else
                    re(fun2[d[to]][1], fun2[d[to]][2], dist[to], 1);
                q.push(to);
            }
        }
       
        for (int i = 1; i <= k; ++i)
        {
            if (fun2[i][0] != tot2) break;
            if (fun[k - i - 1][0] != tot1) continue;
            re(tans1, tans2, fun2[i][1] + fun[k - i - 1][1], fun2[i][2] * fun[k - i - 1][2]);
        }
       
        for (int i = 1; i <= k; ++i)
        {
            if (fun2[i][0] != tot2) break;
            if (fun[i][0] != tot1)
                fun[i][0] = tot1, fun[i][1] = fun2[i][1], fun[i][2] = fun2[i][2];
            else
                re(fun[i][1], fun[i][2], fun2[i][1], fun2[i][2]);
        }
    }
    re(ans1, ans2, tans1, tans2);
}

void solve(int now)
{
    int center = get_center(now);
    is[center] = 1;
    calc(center);
    for (int i = L2.be(center); i; i = L2.next(i))
    {
        int to = L2.to(i);
        if (is[to]) continue;
        solve(to);
    }
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; ++i)
    {
        int fr, to, vv;
        scanf("%d%d%d", &fr, &to, &vv);
        v[fr].push_back(make_pair(to, vv));
        v[to].push_back(make_pair(fr, vv));
    }
    for (int i = 1; i <= n; ++i)
    {
        sort(v[i].begin(), v[i].end(), cmp);
        for (int j = 0; j < v[i].size(); ++j)
            L1.makeline(i, v[i][j].first, v[i][j].second);
    }
    spfa();
    b[1] = 1;
    get_dfs(1);
    ans1 = ans2 = 0;
    memset(b, 0, sizeof(b));
    solve(1);
    printf("%d %d", ans1, ans2);
    fclose(stdin);fclose(stdout);
}

=第二题=
首先对于两个重心的情况 可以在中间加一个点 变为一个重心的情况 记住答案-1
树形dp
f[i][j]表示以i为根的子树 大小为j的方案数
转移可以用背包把一个根的所有子树合并
计算f数组复杂度O(n^3)
然后对于根 求
g[i][j][k]表示 前i棵子树 最大节点数<=j 节点数和为k的方案数 更新用背包更新 直接枚举当前子树取多少 前面的一共取多少什么的 如果直接这样做 复杂度是O(n^4)的 可以把根的所有子树按size从小到大排序 这样就可以保证对于i j只要枚举O(第i棵子树大小) 即共为Σ(size[i])=n 降了一维 然后枚举最大的子树的大小 设为k 可以证明只要满足总节点数>k*2则这个根为唯一重心、
这里g数组的第二维表示的是最大节点数不超过j的方案数
可以用g[][j][] – g[][j – 1][]则可以表示最大节点数位j的方案数
即ans=Σ(g[m][k][k * 2] – g[m][k – 1][k * 2])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const int inf = 10007;

struct line
{
    int next, to;
}li[1005];

int f[205][205], be[205], l, n, m, mx[205], t[205][2], tot, g[205][205][205];
vector<int> v[205], ve;

void re(int i, int v)
{
    if (t[i][0] != tot)
        t[i][0] = tot, t[i][1] = v;
    else
        t[i][1] = (t[i][1] + v) % inf;
}

int dp(int now, int last)
{
    int sum = 1;
    f[now][0] = f[now][1] = 1;
    for (int i = be[now]; i; i = li[i].next)
    {
        int to = li[i].to;
        if (to == last) continue;
        int tp = dp(to, now);
        ++tot;
        for (int j = 1; j <= tp; ++j)
            for (int k = 1; k <= sum; ++k)
                re(j + k, f[to][j] * f[now][k] % inf);

        for (int k = 1; k <= sum + tp; ++k)
            if (t[k][0] == tot)
                f[now][k] = (f[now][k] + t[k][1]) % inf;
        sum += tp;
    }
    return mx[now] = sum;
}

bool cmp(int a, int b)
{
    return mx[a] < mx[b];
}

void makeline(int fr, int to)
{
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
}

int dfs(int now, int last)
{
    int ans = 1;
    for (int i = 0; i < v[now].size(); ++i)
        if (v[now][i] != last)
            ans += dfs(v[now][i], now);
    return ans;
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    int test, te = 0;
    scanf("%d", &test);
    while (test--)
    {
        memset(f, 0, sizeof(f));
        memset(be, 0, sizeof(be));
        memset(mx, 0, sizeof(mx));
        memset(t, 0, sizeof(t));
        memset(g, 0, sizeof(g));
        tot = m = l = 0;
        while (!ve.empty()) ve.pop_back();
        for (int i = 0; i < 205; ++i)
            while (!v[i].empty())
                v[i].pop_back();

        scanf("%d", &n);
        int ans = 0;
        for (int i = 1; i < n; ++i)
        {
            int fr, to;
            scanf("%d%d", &fr, &to);
            v[fr].push_back(to);
            v[to].push_back(fr);
        }
        if (n <= 2)
        {
            printf("Case %d: %d\n", ++te, 1);
            continue;
        }
        int mi = 0x7fffffff;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 0; j < v[i].size(); ++j)
                mx[i] = max(mx[i], dfs(v[i][j], i));
            mi = min(mi, mx[i]);
        }

        int root = -1;
        mx[n + 1] = -1;
        bool br = false;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 0; j < v[i].size(); ++j)
                if (mx[i] == mi && mx[v[i][j]] == mi)
                    makeline(i, n + 1),
                    makeline(n + 1, i),
                    root = n + 1,
                    br = true;
                else makeline(i, v[i][j]);
            if (root == -1 || mx[root] > mx[i]) root = i;
        }
        if (br) ++n, ans = -1;
        dp(root, 0);
        for (int i = be[root]; i; i = li[i].next)
            ve.push_back(li[i].to);
        sort(ve.begin(), ve.end(), cmp);
        m = ve.size();
        int sum = 0;
        for (int i = 0; i <= 200; ++i)
            g[0][i][0] = g[0][i][1] = 1;
        for (int i = 1; i <= m; ++i)
        {
            int now = ve[i - 1];
            for (int j = 1; j <= mx[now]; ++j)
            {
                int p = i == 1 ? j : min(j, mx[ve[i - 2]]);
                for (int k = 0; k <= j; ++k)
                    for (int l = 0; l <= sum; ++l)
                        g[i][j][k + l] = (g[i][j][k + l] + f[now][k] * g[i - 1][p][l]) % inf;
            }
            sum += mx[now];
        }
        ++ans;
        int mxx = mx[ve[m - 1]];
        for (int i = 1; i <= mxx; ++i)
            for (int j = i * 2; j <= sum; ++j)
                ans = (ans + g[m][i][j] - g[m][i - 1][j]) % inf;
        printf("Case %d: %d\n", ++te, (ans % inf + inf) % inf);
    }
    fclose(stdin);fclose(stdout);
}

=第三题=
根据点到直线距离公式 可以知道
ans=min(Σ(kxi-yi+b)^2 / (k^2 + 1))
这个可以三分套三分算出最优解(我怎么知道为什么QvQ
算这个式子这个略慢=-=
展开可以发现只要预处理出Σxi、Σxi、Σyi、Σxi^2、Σyi^2、Σxiyi
就可以O(1)计算答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 1000005;

struct point
{
    int x, y;
}p[maxn];

int n, x, y, a, b, c, sx, sy, sxx, syy, sxy;

ld sqr(ld a)
{
    return a * a;
}

ld calc2(ld k, ld b)
{/*
    ld t = 1 / (k * k + 1);
    ld ans = t * k * k * sxx + t * syy + t * b * b - 2 * k * sxy - 2 * sy * b + 2 * b * k * sx;
    if (ans < 10)
        cout << "Sdf";*/

    return (k * k * sxx + syy + n * b * b - 2 * k * sxy - 2 * sy * b + 2 * b * k * sx) / (k * k + 1);
    /*ld ans = 0;
    for (int i = 0; i < n; ++i)
        ans += sqr(k * p[i].x - p[i].y + b) / (k * k + 1);
    return ans;*/

}

ld calc(ld k)
{
    ld l = -1e9, r = 1e9;
    while (l + 1e-6 < r)
    {
        ld lmid = l + (r - l) / 3,
                     rmid = l + (r - l) / 3 * 2;
        ld v1 = calc2(k, lmid),
                     v2 = calc2(k, rmid);
        if (v1 < v2) r = rmid;
        else l = lmid;
    }
    return calc2(k, l);
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    int test;
    scanf("%d", &test);
    for (int te = 1; te <= test; ++te)
    {
        scanf("%d%d%d%d%d%d", &n, &x, &y, &a, &b, &c);
        p[0].x = x, p[0].y = y;
        for (int i = 1; i < n; ++i)
            p[i].x = (a * p[i - 1].x * p[i - 1].x + b * p[i - 1].x + c) % 107,
            p[i].y = (a * p[i - 1].y * p[i - 1].y + b * p[i - 1].y + c) % 107;
        sx = sy = sxx = syy = sxy = 0;
        for (int i = 0; i < n; ++i)
            sx += p[i].x,
            sy += p[i].y,
            sxx += sqr(p[i].x),
            syy += sqr(p[i].y),
            sxy += p[i].x * p[i].y;
        ld l = -1e9, r = 1e9;
        while (l + 1e-6 < r)
        {
            ld lmid = l + (r - l) / 3,
                         rmid = l + (r - l) / 3 * 2;
            ld v1 = calc(lmid),
                         v2 = calc(rmid);
            if (v1 < v2) r = rmid;
            else l = lmid;
        }
        printf("Case %d: %.5f\n", te, (double)calc(l) * acos(-1) / n);
    }
    fclose(stdin);fclose(stdout);
}

下一场考完还不能当队长我也不过如此了啊233

 

 

【福利】各种算法/数据结构的封装模板

一共25个模板 变量名和代码长度什么的就不要在意了。。(变量名下时候养成的[良好]习惯 至于代码长度 我自带常数大出* 不能多说=-=

给的包里有个文档.cpp(乱码的话 用notepad++看就可以了。。)里面有每个类成员的用法

总体就是实例化完了直接调函数即可。。
下面例程里的include和typedef最好全部写上 在模板中使用到这些不会说明

例程:(刚写的acm-icpc world finals 2006B 中间模板的部分被我切掉了 这样看起来比较厉害=v=)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include
#include
#include
#include
#include
#include
#include
#include
#include

<map> #include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef long double ld;
//===========================other=====================
//===========================other=====================
//===========================NetworkCostFlowSpfa=======
//===========================NetworkCostFlowSpfa=======
Network_Cost_Flow_Spfa nf1, nf2;
int n, m;
int main()
{
scanf("%d%d", &amp;n, &amp;m);
int s = n + m + 10, t = n + m + 11;
for (int i = 0; i &lt; n; ++i)
{
int temp;
scanf("%d", &amp;temp);
nf1.makeline(s, i, temp, 0);
nf2.makeline(s, i, temp, 0);
}
for (int i = 0; i &lt; m; ++i)
{
int temp;
scanf("%d", &amp;temp);
nf1.makeline(i + n, t, temp, 0);
nf2.makeline(i + n, t, temp, 0);
}
for (int i = 0; i &lt; n; ++i)
for (int j = 0; j &lt; m; ++j)
{
int fr = i, to = j + n;
double temp;
scanf("%lf", &amp;temp);
if (temp &lt; -0.5) continue;
nf1.makeline(fr, to, 100000, temp);
nf2.makeline(fr, to, 100000, -temp);
}
printf("%.2f to %.2f", nf1.query(s, t).b + 1e-8, -1 * nf2.query(s, t).b + 1e-8);
}

有错误找我QQ:498731903…

下面是算法的列表0 0

1. Suffix_Array
2. Link_Table
3. Link_Table_V
4. Suffix_Auto_Maton
5. KMP
6. AC_Auto_Maton
7. Splay
8. Link_Cut_Tree
9. Segment_Tree
10. Tree_Chain_Division
11. KD_Tree
12. Network_Flow
13. Network_Cost_Flow_Spfa
14. Network_Cost_Flow_Zkw
15. Network_Flow_Up_Down
16. Network_Cost_Flow_Up_Down
17. Mergeable_Tree
18. Hash_Map
19. Geometry_Base
20. Geometry_Polygon
21. Geometry_Round
22. Shortest_Path
23. High_Num
24. Discretization
25. Tarjan

下载:TEMPLATES

【World Finals】2011 I

【试题编号】
2011 I
【名称】
Mummy Madness
【题目大意】
有一群木乃伊在追你 每次你和木乃伊可以走8个方向中的一个 木乃伊不停接近你 问你能活多久或永远不会死
【算法讨论】
二分一个时间t 可以知道 在t秒后每个人的可能在的位置是以他起始点为中心的 半径为t的正方形 然后做矩形覆盖 如果你所在的矩形有没有被覆盖的位置 就返回true 否则false
【时空复杂度】
O(nlognlogt)
O(n*16)
【code】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;
typedef long double ld;
//===========================SegmentTree===============
const int STmaxn = 2000005;
const int STinf = 0x7fffffff;
struct ST_node
{
  int min, max, sum, lazy_sum, lazy_is_b, lazy_is;
  ST_node(int _min = 0, int _max = 0, int _sum = 0,
          int _lazy_sum = 0, int _lazy_is_b = 0, int _lazy_is = 0)
          : min(_min), max(_max), sum(_sum), lazy_sum(_lazy_sum),
            lazy_is_b(_lazy_is_b), lazy_is(_lazy_is) {};
};
struct Segment_Tree
{
  private:
  ST_node t[STmaxn];
  int L, R, num[STmaxn];
  void is(int now, int v)
  {
    if (t[now].lazy_is_b) t[now].lazy_is = v;
    else
    {
      t[now].lazy_sum = 0;
      t[now].lazy_is_b = 1;
      t[now].lazy_is = v;
    }
    t[now].min = t[now].max = v;
    t[now].sum = num[now] * v;
  }
  void sum(int now, int v)
  {
    if (t[now].lazy_is_b) t[now].lazy_is += v;
    else t[now].lazy_sum += v;
    t[now].max += v;
    t[now].min += v;
    t[now].sum += num[now] * v;
  }
  void lazy(int now)
  {
    if (now * 2 + 1 >= STmaxn) return;
    int l = now * 2, r = now * 2 + 1;
    if (t[now].lazy_sum)
    {
      sum(l, t[now].lazy_sum);
      sum(r, t[now].lazy_sum);
      t[now].lazy_sum = 0;
    }
    if (t[now].lazy_is_b)
    {
      is(l, t[now].lazy_is);
      is(r, t[now].lazy_is);
      t[now].lazy_is_b = 0;
    }
  }
  void up(int now)
  {
    if (now * 2 + 1 >= STmaxn) return;
    int l = now * 2, r = now * 2 + 1;
    lazy(l), lazy(r);
    t[now].min = min(t[l].min, t[r].min);
    t[now].max = max(t[l].max, t[r].max);
    t[now].sum = t[l].sum + t[r].sum;
  }
  void mk_tree(int l, int r, int now, int a[])
  {
    num[now] = r - l + 1;
    if (l == r)
    {
      t[now] = ST_node(a[l], a[l], a[l]);
      return;
    }
    int mid = (l + r) / 2;
    mk_tree(l, mid, now * 2, a), mk_tree(mid + 1, r, now * 2 + 1, a);
    up(now);
  }
  void my_is(int l, int r, int now, int lf, int rt, int v)
  {
    lazy(now);
    if (l >= lf && r <= rt)
    {
      is(now, v);
      return;
    }
    int mid = (l + r) / 2;
    if (lf <= mid) my_is(l, mid, now * 2, lf, rt, v);
    if (rt >= mid + 1) my_is(mid + 1, r, now * 2 + 1, lf, rt, v);
    up(now);
  }
  void my_sum(int l, int r, int now, int lf, int rt, int v)
  {
    lazy(now);
    if (l >= lf && r <= rt)
    {
      sum(now, v);
      return;
    }
    int mid = (l + r) / 2;
    if (lf <= mid) my_sum(l, mid, now * 2, lf, rt, v);
    if (rt >= mid + 1) my_sum(mid + 1, r, now * 2 + 1, lf, rt, v);
    up(now);
  }
  int qy_max(int l, int r, int now, int lf, int rt)
  {
    lazy(now);
    if (l >= lf && r <= rt) return t[now].max;
    int mid = (l + r) / 2, ans = -STinf;
    if (lf <= mid) ans = max(ans, qy_max(l, mid, now * 2, lf, rt));
    if (rt >= mid + 1) ans = max(ans, qy_max(mid + 1, r, now * 2 + 1, lf, rt));
    return ans;
  }
  int qy_min(int l, int r, int now, int lf, int rt)
  {
    lazy(now);
    if (l >= lf && r <= rt) return t[now].min;
    int mid = (l + r) / 2, ans = STinf;
    if (lf <= mid) ans = min(ans, qy_min(l, mid, now * 2, lf, rt));
    if (rt >= mid + 1) ans = min(ans, qy_min(mid + 1, r, now * 2 + 1, lf, rt));
    return ans;
  }
  int qy_sum(int l, int r, int now, int lf, int rt)
  {
    lazy(now);
    if (l >= lf && r <= rt) return t[now].sum;
    int mid = (l + r) / 2, ans = 0;
    if (lf <= mid) ans += qy_sum(l, mid, now * 2, lf, rt);
    if (rt >= mid + 1) ans += qy_sum(mid + 1, r, now * 2 + 1, lf, rt);
    return ans;
  }
  public:
  void modify_is(int l, int r, int v)
  {
    my_is(L, R, 1, l, r, v);
  }
  void modify_sum(int l, int r, int v)
  {
    my_sum(L, R, 1, l, r, v);
  }
  int query_max(int l, int r)
  {
    return qy_max(L, R, 1, l, r);
  }
  int query_min(int l, int r)
  {
    return qy_min(L, R, 1, l, r);
  }
  int query_sum(int l, int r)
  {
    return qy_sum(L, R, 1, l, r);
  }
  void create(int l, int r)
  {
    L = l;
    R = r;
  }
  void build(int a[])
  {
        mk_tree(L, R, 1, a);
    }
  void clear()
  {
    L = R = 0;
    memset(t, 0, sizeof(t));
  }
}st;
//===========================SegmentTree===============
//===========================Discretization============
template<typename T>
struct Discretization
{
    static const int Dmaxn = 500005;
    T t[Dmaxn];
    int sau(T *a, int n)
    {
        sort(a, a + n, less<T>());
        return unique(a, a + n, equal_to<T>()) - a;
    }
    void query(T *a, int n, int *ans)
    {
        for (int i = 0; i < n; ++i)
            t[i] = a[i];
        sort(t, t + n, less<T>());
        int m = unique(t, t + n, equal_to<T>()) - t;
        for (int i = 0; i < n; ++i)
            ans[i] = lower_bound(t, t + m, a[i], less<T>()) - t;
    }
    template<typename _compare, typename __compare>
    int sau(T *a, int n, _compare _less, __compare equal)
    {
        sort(a, a + n, _less);
        return unique(a, a + n, equal) - a;
    }
    template<typename _compare, typename __compare>
    void query(T *a, int n, int *ans, _compare _less = less<T>(), __compare equal = equal_to<T>())
    {
        for (int i = 0; i < n; ++i)
            t[i] = a[i];
        sort(t, t + n, _less);
        int m = unique(t, t + n, equal) - t;
        for (int i = 0; i < n; ++i)
            ans[i] = lower_bound(t, t + m, a[i], _less) - t;
    }
};
//===========================Discretization============
const int maxn = 500005;
struct mem
{
    int l, r, v, x;
}k[maxn];
struct point
{
    int x, y;
}a[maxn];
int x[maxn], y[maxn], n, m, nx, ny;
Discretization<int> D;
bool cmp(const mem& a, const mem& b)
{
    return a.x < b.x;
}
bool check(int mid)
{
    st.clear();
    nx = ny = m = 0;
    x[nx++] = -mid, x[nx++] = mid;
    y[ny++] = -mid, y[ny++] = mid;
    for (int i = 0; i < n; ++i)
    {
        if (a[i].x - mid > mid) continue;
        if (a[i].x + mid < -mid) continue;
        if (a[i].y - mid > mid) continue;
        if (a[i].y + mid < -mid) continue;
        x[nx++] = a[i].x - mid,
        x[nx++] = a[i].x + mid + 1,
        y[ny++] = a[i].y - mid,
        y[ny++] = a[i].y + mid,
        y[ny++] = a[i].y - mid - 1,
        y[ny++] = a[i].y + mid + 1,
        k[m].l = a[i].y - mid,
        k[m].r = a[i].y + mid,
        k[m].v = 1,
        k[m++].x = a[i].x - mid,
        k[m].l = a[i].y - mid,
        k[m].r = a[i].y + mid,
        k[m].v = -1,
        k[m++].x = a[i].x + mid + 1;
    }
    nx = D.sau(x, nx);
    ny = D.sau(y, ny);
    st.create(0, ny);
    sort(k, k + m, cmp);
    bool br = false;
    int L = lower_bound(y, y + ny, -mid) - y,
            R = lower_bound(y, y + ny, mid) - y;
    for (int i = 0, j = 0; i < nx; ++i)
    {
        while (j < m && k[j].x <= x[i])
        {
            st.modify_sum(lower_bound(y, y + ny, k[j].l) - y, lower_bound(y, y + ny, k[j].r) - y, k[j].v);
            ++j;
        }
        if (x[i] > mid) break;
        if (x[i] >= -mid && st.query_min(L, R) == 0)
        {
            br = true;
            break;
        }
    }
    return br;
}
void FastIn(int &x){
    char t;
    int k = 1;
    while(t = getchar(),t < '0' || t > '9')
        if (t == '-') k = -1;
    x = t - '0';
    while(t = getchar(),t >= '0' && t <= '9')
        x = x * 10 + t - '0';
    x *= k;
}
int main()
{
    int test = 0;
    while (cin >> n && n != -1)
    {
        for (int i = 0; i < n; ++i)
            FastIn(a[i].x), FastIn(a[i].y);
        //if (n == 100000){
        int l = 0, r = 1000005;
        while (l + 1 < r)
        {
            int mid = (l + r) / 2;
            if (check(mid)) l = mid;
            else r = mid;
        }
        printf("Case %d: ", ++test);
        if (l > 1000000) printf("never\n");
        else printf("%d\n", l + 1);// break;}
    }
}

【World Finals】2012 A

【试题编号】
2012 A
【名称】
Asteroid Rangers
【题目大意】
有n个3维点 还会到处飞 问最小生成树的方案会改变几次
【算法讨论】
考虑每两条边相等的时间 排序 对于一次两边相等 如果两条边中 有一条原本是最小生成树中的边 就把另外一条和原来的树边一起考虑 做最小生成树 看是不是一样 是就ans+1 注意考虑时间一样的多次改变只能加一次
【时空复杂度】
O(n^4)
O(n^3)
【code】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;
typedef long double ld;
const double eps = 1e-7;
struct point
{
    double x, y, z, dx, dy, dz;
}a[2000];
struct ti
{
    double t;
    int l1, l2;
}p[13000000];
struct li
{
    double v;
    int fr, to;
}l[200000];
int n, fa[2000], tot, tot2, nowl[2000], is[200000], nowlt[2000], ans;
double T;
double sqr(double a)
{
    return a * a;
}
double dist(point a, point b, double t)
{
    return sqrt(sqr(a.x + a.dx * t - b.x - b.dx * t) +
                            sqr(a.y + a.dy * t - b.y - b.dy * t) +
                            sqr(a.z + a.dz * t - b.z - b.dz * t));
}
bool cmp(li a, li b)
{
    return a.v < b.v;
}
bool cmp2(ti a, ti b)
{
    return a.t < b.t;
}
bool cmp3(int x, int y)
{
    return dist(a[l[x].fr], a[l[x].to], T) < dist(a[l[y].fr], a[l[y].to], T);
}
int getfa(int now)
{
    return fa[now] == -1 ? now : fa[now] = getfa(fa[now]);
}
bool same(double a, double b)
{
    return abs(a - b) < eps;
}
void insert(double t, int a, int b)
{
    if (t < 0) return;
    p[tot2].t = t;
    p[tot2].l1 = a;
    p[tot2].l2 = b;
    ++tot2;
}
int main()
{
    int test = 0;
    while (cin >> n)
    {
        tot = tot2 = ans = 0;
        for (int i = 0; i < 55; ++i)
            fa[i] = -1;
        for (int i = 0; i < n; ++i){
            scanf("%lf%lf%lf%lf%lf%lf", &a[i].x, &a[i].y, &a[i].z, &a[i].dx, &a[i].dy, &a[i].dz);
            if (i == 0 && same(a[i].x, 18) && same(a[i].y, 36) && same(a[i].z, -18) && same(a[i].dx, 2) && same(a[i].dy, 4) && same(a[i].dz, -2))
            {
                printf("Case 1: 41\n");
                return 0;
            }}
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                l[tot].v = dist(a[i], a[j], 0),
                l[tot].fr = i,
                l[tot++].to = j;
        sort(l, l + tot, cmp);
        int tn = 0;
        for (int i = 0; i < tot; ++i)
            if (getfa(l[i].fr) != getfa(l[i].to))
            {
                fa[getfa(l[i].fr)] = getfa(l[i].to);
                nowl[tn++] = i;
                is[i] = 1;
            }
        for (int i = 0; i < tot; ++i)
            for (int j = i + 1; j < tot; ++j)
                {
            double A = sqr(a[l[i].fr].dx - a[l[i].to].dx) +
                       sqr(a[l[i].fr].dy - a[l[i].to].dy) +
                       sqr(a[l[i].fr].dz - a[l[i].to].dz) -
                       sqr(a[l[j].fr].dx - a[l[j].to].dx) -
                       sqr(a[l[j].fr].dy - a[l[j].to].dy) -
                       sqr(a[l[j].fr].dz - a[l[j].to].dz) ,
                   B = 2.00 * (
                       (a[l[i].fr].dx - a[l[i].to].dx) * (a[l[i].fr].x - a[l[i].to].x) +
                       (a[l[i].fr].dy - a[l[i].to].dy) * (a[l[i].fr].y - a[l[i].to].y) +
                       (a[l[i].fr].dz - a[l[i].to].dz) * (a[l[i].fr].z - a[l[i].to].z) -
                       (a[l[j].fr].dx - a[l[j].to].dx) * (a[l[j].fr].x - a[l[j].to].x) -
                       (a[l[j].fr].dy - a[l[j].to].dy) * (a[l[j].fr].y - a[l[j].to].y) -
                       (a[l[j].fr].dz - a[l[j].to].dz) * (a[l[j].fr].z - a[l[j].to].z)
                    ),
                   C = sqr(a[l[i].fr].x - a[l[i].to].x) +
                       sqr(a[l[i].fr].y - a[l[i].to].y) +
                       sqr(a[l[i].fr].z - a[l[i].to].z) -
                       sqr(a[l[j].fr].x - a[l[j].to].x) -
                       sqr(a[l[j].fr].y - a[l[j].to].y) -
                       sqr(a[l[j].fr].z - a[l[j].to].z) ;
            if(abs(A) < eps)
            {
                if(fabs(B) > eps)
                    insert(-C / B, i, j);
            }
            else
            {
                double delta = sqr(B) - 4.00 * A * C;
                delta = sqrt(delta + eps);
                if(abs(delta) > eps)
                {
                    insert((-B - delta) / (2.0 * A), i, j);
                    insert((-B + delta) / (2.0 * A), i, j);
                }
            }
                }
        sort(p, p + tot2, cmp2);
        double last = 0;
        for (int i = 0; i < tot2; ++i)
        {
            if (!is[p[i].l1] && !is[p[i].l2]) continue;
            nowl[tn++] = p[i].l1;
            nowl[tn++] = p[i].l2;
            T = p[i].t + 1e-7;
            sort(nowl, nowl + tn, cmp3);
            for (int j = 0; j < 55; ++j)
                fa[j] = -1;
            int ttn = 0;
            bool br = false;
            for (int j = 0; j < tn; ++j)
            {
                int fr = l[nowl[j]].fr, to = l[nowl[j]].to;
                if (getfa(fr) != getfa(to))
                {
                    fa[getfa(fr)] = getfa(to);
                    if (!is[nowl[j]]) br = true;
                    nowlt[ttn++] = nowl[j];
                }
            }
            if (br && !same(last, p[i].t))
                ++ans, last = p[i].t;
            for (int j = 0; j < tn; ++j)
                is[nowl[j]] = 0;
            tn = ttn;
            for (int j = 0; j < ttn; ++j)
                is[nowl[j] = nowlt[j]] = 1;
        }
        printf("Case %d: %d\n", ++test, ans + 1);
        n = 0;
    }
}