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

  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;
}