BZOJ 1854: [Scoi2010]游戏

一个武器可以看成连接对应两个属性值的一条边
可以证明如果一个联通块中出现一个环
则整个联通块都可以取
否则会有一个点不能取
显然这个不取的点是最大的那个点= =
然后扫一遍看能取到哪就行了
找环和维护最大可以用并查集做

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
#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;
 
int n, fa[maxn], is[maxn];
 
int getfa(int now)
{
    return (!fa[now]) ? now : fa[now] = getfa(fa[now]);
}
 
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        u = getfa(u), v = getfa(v);
        if (u == v) is[u] = is[v] = 1;
        else
        {
            if (u < v)swap(u, v);
            if (is[u] || is[v]) is[u] = is[v] = 1;
            fa[v] = u;
            is[v] = 1;
        }
    }
    for (int i = 1; i < maxn; ++i)
        if (!is[i])
        {
            cout << i - 1;
            break;
        }
}

BZOJ 1576: [Usaco2009 Jan]安全路经Travel

先构出最短路径树(题目说唯一)
对于一个非树边(u,v) 一定使树构成一个环
并且使环上的点(除了lca(u,v))都有了一个次短路
对于点i 这个所谓次短路的长度就是dist[u]+dist[v]+value[u,v]-dist[i]
可以发现次短路大小长度跟u,v有关 跟i无关
所以对于一个非树边(u,v)设它的权值为dist[u]+dist[v]+value[u,v]
把这个权值按从小到大排序 每次把环上没被赋值过的点赋上值
快速实现上面那个 可以用并查集(不用多说了吧=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
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
#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 line
{
    int to, next, v;
}li[maxn * 10];
 
struct wtf
{
    int v, cost;
    wtf(int a, int b) : v(a), cost(b) {}
};
 
struct hh
{
    int u, v, va;
}t[maxn * 5];
 
int be[maxn], dist[maxn], fa[maxn], f[maxn], d[maxn], tot, ans[maxn], l, n, m, b[maxn];
priority_queue<wtf> q;
 
bool operator<(wtf a, wtf b)
{
    return a.cost > b.cost;
}
 
bool cmp(hh a, hh b)
{
    return a.va < b.va;
}
 
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;
}
 
int getfa(int now)
{
    return (!f[now]) ? now : f[now] = getfa(f[now]);
}
 
void re_ans(int u, int v, int va)
{
    int lastu = -1, lastv = -1;
    while (getfa(u) != getfa(v))
    {
        if (d[getfa(u)] < d[getfa(v)]) swap(u, v), swap(lastu, lastv);
        if (ans[u] == -1)
        {
            ans[u] = va - dist[u];
            if (lastu != -1)
                f[lastu] = u;
        }
        else
            if (lastu != -1)
                f[lastu] = getfa(u);
        lastu = getfa(u);
        u = fa[lastu];
    }
}
 
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i)
    {
        int fr, to, v;
        scanf("%d%d%d", &fr, &to, &v);
        makeline(fr, to, v);
        makeline(to, fr, v);
    }
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    d[1] = 1;
    q.push(wtf(1, 0));
    while (!q.empty())
    {
        while (!q.empty() && b[q.top().v]) q.pop();
        if (q.empty()) break;
        int now = q.top().v;
        b[now] = 1;
        for (int i = be[now]; i; i = li[i].next)
        {
            int to = li[i].to;
            if (b[to] || dist[to] <= dist[now] + li[i].v) continue;
            fa[to] = now;
            d[to] = d[now] + 1;
            dist[to] = dist[now] + li[i].v;
            q.push(wtf(to, dist[to]));
        }
    }/*
    for (int i = 1; i <= n; ++i)
        printf("%d\n", dist[i]);
    printf("\n\n");*/

    for (int i = 1; i <= n; ++i)
        for (int j = be[i]; j; j = li[j].next)
        {
            int to = li[j].to;
            if (to >= i || fa[to] == i || fa[i] == to) continue;
            t[tot].u = i, t[tot].v = to, t[tot].va = dist[i] + dist[to] + li[j].v;
            ++tot;
        }
    memset(ans, -1, sizeof(ans));
    sort(t, t + tot, cmp);
    for (int i = 0; i < tot; ++i)
        re_ans(t[i].u, t[i].v, t[i].va);
    for (int i = 2; i <= n; ++i)
        printf("%d\n", ans[i]);
}

BZOJ 3060: [Poi2012]Tour de Byteotia

对于两端都>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
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <sstream>
using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 1000005;

struct line
{
  int fr, to;
}li[maxn * 2];

int fa[maxn], n, m, k;

int getfa(int now)
{
  return (!fa[now]) ? now : fa[now] = getfa(fa[now]);
}

int main()
{
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 0; i < m; ++i)
  {
    scanf("%d%d", &li[i].fr, &li[i].to);
    if (li[i].fr > k && li[i].to > k)
      if (getfa(li[i].fr) != getfa(li[i].to))
        fa[getfa(li[i].fr)] = getfa(li[i].to);
  }
  int ans = 0;
  for (int i = 0; i < m; ++i)
    if (li[i].fr <= k || li[i].to <= k)
    {
      if (getfa(li[i].fr) != getfa(li[i].to))
        fa[getfa(li[i].fr)] = getfa(li[i].to);
      else ++ans;
    }
  printf("%d", ans);
}

BZOJ 3211: 花神游历各国

一个数n<=10^9 在被sqrt 7次左右就会变成1 所以这题可以用一个并查集维护一段连续为1的数 修改的时候暴力修改 遇到一个为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
97
98
99
100
101
102
103
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <sstream>
using namespace std;
typedef long long ll;
typedef long double ld;

const ll maxn = 100005;

ll a[maxn], t[maxn * 4], n, m, fa[maxn], b[maxn];

ll getfa(ll now)
{
  return (!fa[now]) ? now : (fa[now] = getfa(fa[now]));
}

void build(ll l, ll r, ll now)
{
  if (l == r)
  {
    t[now] = a[l];
    return;
  }
  ll mid = (l + r) / 2;
  build(l, mid, now * 2);
  build(mid + 1, r, now * 2 + 1);
  t[now] = t[now * 2] + t[now * 2 + 1];
}

void modify(ll l, ll r, ll now, ll lr, ll v)
{
  if (l == r)
  {
    t[now] = v;
    return;
  }
  ll mid = (l + r) / 2;
  if (lr <= mid) modify(l, mid, now * 2, lr, v);
  else modify(mid + 1, r, now * 2 + 1, lr, v);
  t[now] = t[now * 2] + t[now * 2 + 1];
}

ll query(ll l, ll r, ll now, ll lf, ll rt)
{
  if (l >= lf && r <= rt) return t[now];
  ll mid = (l + r) / 2, ans = 0;
  if (lf <= mid) ans += query(l, mid, now * 2, lf, rt);
  if (rt >= mid + 1) ans += query(mid + 1, r, now * 2 + 1, lf, rt);
  return ans;
}

ll sq(ll a)
{
  return (ll)floor(sqrt((double)a));
}

void modi(ll l, ll r)
{
  for (ll i = l; i <= r; i = (!b[i]) ? (i + 1) : (getfa(i) + 1))
  {
    if (b[i]) continue;
    a[i] = sq(a[i]);
    modify(1, n, 1, i, a[i]);
    if (a[i] <= 1)
    {
      b[i] = 1;
      if (b[i - 1]) fa[getfa(i - 1)] = i;
      if (b[i + 1]) fa[i] = getfa(i + 1);
    }
  }
}

int main()
{
  freopen("input.in", "r", stdin);
  freopen("output.out", "w", stdout);
  scanf("%lld", &n);
  for (ll i = 1; i <= n; ++i)
    scanf("%lld", &a[i]);
  build(1, n, 1);
  scanf("%lld", &m);
  for (ll i = 0; i < m; ++i)
  {
    ll x, l, r;
    scanf("%lld%lld%lld", &x, &l, &r);
    if (x == 1) printf("%lld\n", query(1, n, 1, l, r));
    else modi(l, r);
  }
  fclose(stdin);fclose(stdout);
}