15.10.02【并查集、线段树、倍增+Floyd】

OI&ACM, OI训练
  1. 1.旅行
  2. 2.魔法序列
  3. 3.仓鼠

0+50+15

1.旅行

【问题描述】 如果说旅行是令人愉悦的话，对于强迫症患者可不一定如此。 Alice最近得到了一张旅行地图，其中详细标明A市内的N个景点，共有M条双向路连接着N个景点。由于Alice的精力有限，她实在无法将N个景点全部游遍，于是只好算了一个数字K，她只想详细游览前K个景点。受到强迫症的困扰，Alice特别害怕会在某个环上重复走来去而导致可的事情发生，所以她希望在地图上删去一些边，使得编号不大于K的所有景点都不在环上。

• 考虑将前k个点和后N-k个点分成两个A,B点集 • 对于仅连接前k个点的边，用并查集合并，遇环则删除 • 对于仅连接后N-k个点的边，用并查集无条件合并 • 对于连接A和B的边，用并查集合并，遇环则删除

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
#include<cstdio>
using namespace std;
int n,m,k,x,y,z,ans,tot,fa[1000001],xx[2000001],yy[2000001];
int father(int x)
{
	return fa[x]==x?x:fa[x]=father(fa[x]);
}
void unionn(int x,int y)
{
	fa[father(x)]=father(y);
}
int main()
{
	freopen("tour.in","r",stdin);
	freopen("tour.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		if(x>y) z=x,x=y,y=z;
		if(y<=k)
		{
			if(father(x)==father(y)) ans++;
		    else unionn(x,y);
		}
		else if(x>k) unionn(x,y);
		else xx[++tot]=x,yy[tot]=y;
	}
	for(int i=1;i<=tot;i++)
	{
		x=xx[i];y=yy[i];
		if(father(x)==father(y)) ans++;
		else unionn(x,y);
	}
	printf("%d",ans);
}

2.魔法序列

【问题描述】 Bob最近得到了一个序列，最初他以为这个序列只是一个普通的序列，结果正当他研究区[l,r]内的元素时，Cindy不知说了一句什么话，结果区间[l,r]的元素竟然全部被开了平方。 Bob对这个现象十分感兴趣，但他并不打算深究为什么会出现这种现象，而打算玩一玩这个魔法序列。 Bob会进行两个操作：选定一个区间并将其中的每一个元素开平方（下取整），或询问一个区间内所有元素的和。而你需要告诉Bob他每次询问后的结果是什么。

不符合区间修改（lazy） 因为数据范围是10^12,所以最多开6次方就会降到1 所以暴力对区间内每个大于1的数开方 然而我还是只拿了50 还要用并查集维护每个数之前（包括它）最近的大于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
#include<cmath>
#include<cstdio>
using namespace std;
const int N=100000;
struct node
{
   int lc,rc,l,r;
   long long sum;
}t[3*N];	
int tot=1,f[N],fa[N];
long long a[N];
int father(int x)
{
	return fa[x]==x?x:fa[x]=father(fa[x]);
}
void unionn(int x,int y)
{
	fa[father(x)]=father(y);
}
void build(int x,int l,int r)
{
	t[x].l=l; t[x].r=r;
	if(l==r)
	{
		t[x].sum=a[l];
		return;
	}
	int mid=(l+r)/2;
	t[x].lc=++tot;	build(t[x].lc,l,mid);
	t[x].rc=++tot;	build(t[x].rc,mid+1,r);
	t[x].sum=t[t[x].lc].sum+t[t[x].rc].sum;
}
long long query(int x,int l,int r)
{
	if(l<=t[x].l&&t[x].r<=r) return t[x].sum;
	int mid=(t[x].l+t[x].r)/2;
	long long ans=0;
	if(l<=mid) ans+=query(t[x].lc,l,r);
	if(mid<r)  ans+=query(t[x].rc,l,r);
	return ans;
}
void change(int x,int v,int d)
{
	if(t[x].l==t[x].r)
	{
		t[x].sum=d;return;
	}
	int mid=(t[x].l+t[x].r)/2;
	if(v<=mid) change(t[x].lc,v,d);
	if(mid<v)  change(t[x].rc,v,d);
	t[x].sum=t[t[x].lc].sum+t[t[x].rc].sum;
}
int main()
{
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
	int n,m;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=n;i++) 
	{
		scanf("%lld",&a[i]);
		if(a[i]<=1) fa[i]=father(i-1);
	}
	build(1,1,n);
	scanf("%d",&m);
	for(int i=1,k,x,y,z;i<=m;i++)
	{
		scanf("%d%d%d",&k,&x,&y);
		if(x>y) z=x,x=y,y=z;
		if(k) printf("%lld\n",query(1,x,y));
		if(!k)
		{
			for(int j=father(y);j>=x;j=father(j-1))
			{
				if(a[j]>1) a[j]=sqrt(a[j]),change(1,j,a[j]);
			    else fa[j]=father(j-1);
			}
		}
	} 
}

3.仓鼠

【问题描述】 Daniel最近养了一群仓鼠，每个仓鼠都有一仅由小写英文字母组成的名字。现在Daniel想用一个字母序列来表示它们的名字，对于任意一个仓鼠，只要它的名字出现在序列中就算，且可以重复计算次数。两只仓鼠的名字在序列中可以重叠。现在给你所有仓鼠的名字，请你求出 Daniel可以使用的最短字母序列的长度。

• 对于所有仓鼠两两之间可以暴力求出，一个名字接到另一个名字后面，最短要加多少个字母。 • 建出有向图。 • 问题转化成了：在图中走M步的最短路是多长。 • 经典问题：倍增+Floyd 然而我并不会写，写了个dp

标程： 

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <climits>
#include <cstdlib>
#include <queue>
#include <vector>
#include <cmath>
#include <utility>
#include <functional>
using namespace std;
typedef long long LL;
const int MAXN = 205, MAXL = 1e5 + 50;
const LL inf = 1e18, seed = 131;
int N, M; LL Hash_b[MAXL], sed[MAXL];
string s[MAXN];
vector<LL> Hash[MAXN];
struct mat
{
    LL a[MAXN][MAXN];
    void init()
    {
        for (int i = 0; i <= N; ++i)
            for (int j = 0; j <= N; ++j)
                a[i][j] = -1;
    }
    void clear()
    {
        memset(a, 0, sizeof a);
    }
    mat operator *(const mat &B)
    {
        mat res; res.init();
        for (int k = 0; k <= N; ++k) {
            for (int i = 0; i <= N; ++i)
                if (a[i][k] != -1) {
                    for (int j = 0; j <= N; ++j)
                        if (B.a[k][j] != -1) {
                            res.a[i][j] = (res.a[i][j] < 0 ? a[i][k] + B.a[k][j] : min(res.a[i][j], a[i][k] + B.a[k][j]));
                        }
                }
        }
        return res;
    }
};
void solve()
{
    mat x; x.init();
    for (int i = 1; i <= N; ++i) x.a[0][i] = s[i].length();
    for (int i = 1; i <= N; ++i) {
        int t1 = s[i].length(), mx(0); LL cur(0);
        for (--t1; t1 >= 0; --t1) {
            cur += (LL)s[i][t1] * sed[mx];
            Hash_b[mx++] = cur;
        }
        
        for (int j = 1; j <= N; ++j) {
            int len = min(s[i].length(), s[j].length()), res(0);
            if (i == j) --len;
            for (int k = 0; k < len; ++k) {
                if (Hash_b[k] == Hash[j][k]) res = k + 1;
            }
            x.a[i][j] = s[j].length() - res;
        }
    }
    
    mat res; res = x;
    for (--M; M; M >>= 1, x = x * x) if (M & 1) res = res * x;
    LL ans = inf;
    for (int i = 1; i <= N; ++i) ans = min(ans, res.a[0][i]);
    printf("%lld\n", ans);
}
int main()
{
	freopen("hamster.in", "r", stdin); freopen("hamster.out", "w", stdout);
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; ++i) {
        cin >> s[i];
        LL cur(0); int len = s[i].length();
        for (int j = 0; j < len; ++j) {
            cur = cur * seed + (LL)s[i][j];
            Hash[i].push_back(cur);
        }
    }
    sed[0] = 1;
    for (int i = 1; i < MAXL; ++i) sed[i] = sed[i - 1] * seed;
    solve();
    return 0;
}