7-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
#include<bits/stdc++.h>
using namespace std;
int fa[1010];
int find(int x)
{ 
    if(fa[x]==x)
        return fa[x];
    else {
        fa[x]=find(fa[x]);
        return fa[x];
    }
}
void merge(int a,int b)
{
    int a1=find(a);
    int b1=find(b);
    if(a1!=b1)
    {
        fa[a1]=b1;
    }
}
int main()
{
    int n,m;
    while(1)
    {
        cin>>n;
        if(n==0)
        {
            break;
        }
        cin>>m;
        for(int i=1;i<=n;i++)
        {
            fa[i]=i;
        }
        for(int i=1;i<=m;i++)
        {
            int a,b;
            cin>>a>>b;
            merge(a,b);
        }
        int cou=0;
        for(int i=1;i<=n;i++)
        {
            if(fa[i]==i)
            {
                cou++;
            }
        }
        cout<<cou-1<<endl;
    }
}

7-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
#include<bits/stdc++.h>
using namespace std;
int fa[10010];
int cou=0;
void init()
{
    for(int i=1;i<=10010;i++)
    {
        fa[i]=i;
    }
}
int find(int x)
{ 
    if(fa[x]==x)
        return fa[x];
    else {
        fa[x]=find(fa[x]);
        return fa[x];
    }
}
void merge(int a,int b)
{
    int a1=find(a);
    int b1=find(b);
    if(a1!=b1)
    {
        fa[a1]=b1;
        cou++;
    }
}
int main()
{
    init();
    int n;
    cin>>n;
    int num=0;
    for(int i=1;i<=n;i++)
    {
        int k,a;
        cin>>k;
        k--;
        cin>>a;
        num=max(num,a);
        while(k--)
        {
            int b;
            cin>>b;
            num=max(num,b);
            merge(a,b);
        }
    }
    cout<<num-cou<<" "<<num<<endl;
    int t;
    cin>>t;
    while(t--)
    {
        int a,b;
        cin>>a>>b;
        if(find(a)==find(b))
        {
            cout<<"Yes"<<endl;
        }
        else
        {
            cout<<"No"<<endl;
        }
    }
}

7-3 社交集群

用每个人的第一个兴趣编号代表自己，然后与自己的其他兴趣合并，就能将所有兴趣爱好相同的人合并到一起，之后查找父节点统计。

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
#include<bits/stdc++.h>
using namespace std;
int fa[1010];
int peo[1010];
int hob[1010];
void init()
{
    for(int i=1;i<1010;i++)
    {
        fa[i]=i;
    }
}
int find(int x)
{
    if(x==fa[x])
        return fa[x];
    else
    {
        fa[x]=find(fa[x]);
        return fa[x];
    }
}
void merge(int a,int b)
{
    int a1=find(a);
    int b1=find(b);
    if(a1!=b1)
    {
        fa[a1]=b1;
    }
}
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    init();
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int k,a;
        scanf("%d:",&k);
        cin>>a;
        peo[i]=a;
        k--;
        while(k--)
        {
            int b;
            cin>>b;
            merge(a,b);
        }
    }
    set<int> s;
    memset(hob,0,sizeof(hob));
    for(int i=1;i<=n;i++)
    {
        int tmp=find(peo[i]);
        s.insert(tmp);
        hob[tmp]++;
    }
    sort(hob,hob+1010,cmp);
    cout<<s.size()<<endl;
    for(int i=0;i<s.size();i++)
    {
        if(i!=0)
        {
            cout<<" ";
        }
        cout<<hob[i];
    }
    
}

7-4 Dijkstra堆优化算法求最短路

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
    ll d;//长度
    int u;//点的编号
    bool operator < (const node & rhs) const {
		return d > rhs.d;
	}
};
int n,m,s,t;
ll dis[100100];
int vis[100100];
vector<int> e[100100];
vector<int> w[100100];
void dijkstra(int s)
{
    priority_queue<node> q;
    for(int i=1;i<=n;i++)
    {
        dis[i]=0x3f3f3f;
    }
    dis[s]=0;
    memset(vis,0,sizeof(vis));
    node tmp;
    tmp.d=0;
    tmp.u=s;
    q.push(tmp);
    while(!q.empty())
    {
        node t;
        t=q.top();
        q.pop();
        int u=t.u;
        if(vis[u]==1)
        {
            continue;
        }
        vis[u]=1;
        for(int i=0;i<e[u].size();i++)
        {
            if(dis[e[u][i]]>dis[u]+w[u][i])
            {
                dis[e[u][i]]=dis[u]+w[u][i];
                node t1;
                t1.d=dis[e[u][i]];
                t1.u=e[u][i];
                q.push(t1);
            }
        }

    }
}
int main()
{
    cin>>n>>m>>s>>t;
    for(int i=1;i<=n;i++)
    {
        e[i].clear(), w[i].clear();
    }
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        e[a].push_back(b);
        w[a].push_back(c);
        e[b].push_back(a);
        w[b].push_back(c);
    }
    dijkstra(s);
    if(dis[t]!=0x3f3f3f)
    {
        cout<<dis[t]<<endl;
    }
    else
    {
        cout<<"-1"<<endl;
    }
}

7-5 夺宝大赛

从大本营开始进行一次bfs(),即可得到所有点到大本营的最小路程，然后找符合要求的就好

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
#include<bits/stdc++.h>
using namespace std;
#include<algorithm>
#include<iostream>
typedef struct n
{
	int a;
	int b;

}node;
int arr[110][110];
int brr[110][110];
int re[10010] = { 0 };
int n, m, tx, ty;
queue<node>q;
int xrr[4] = { -1,1,0,0 };
int yrr[4] = { 0,0,-1,1 };
void bfs(int x, int y)
{
	q.push({x,y});
	while (!q.empty())
	{
		node tem = q.front();
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			if (brr[tem.a + xrr[i]][tem.b + yrr[i]] || !arr[tem.a + xrr[i]][tem.b + yrr[i]])
			{
				continue;
			}
			else if (tem.a + xrr[i] > m || tem.a + xrr[i] < 1 || tem.b + yrr[i]<1 || tem.b + yrr[i]>n)
			{
				continue;
			}
			else
			{
				brr[tem.a + xrr[i]][tem.b + yrr[i]] = brr[tem.a][tem.b] + 1;
				q.push({ tem.a + xrr[i],tem.b + yrr[i] });
			}

		}
	}
}
int main()
{
	cin >> m >> n;
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> arr[i][j];
			if (arr[i][j] == 2)
			{
				tx = i;
				ty = j;
			}
		}
	}
	bfs(tx, ty);
	int k;
	cin >> k;
	for (int i = 1; i <= k; i++)
	{
		int a, b;
		cin >> a >> b;
		if (brr[b][a])
		{
			if (re[brr[b][a]] == 0)
			{
				re[brr[b][a]] = i;
			}
			else
			{
				re[brr[b][a]] = -1;
			} 
		}
	}
	int flag = 0;
	for (int i = 1; i <= n * m ; i++)
	{
		if (re[i] && re[i] != -1)
		{
			cout << re[i] << " " << i<<endl;
			flag = 1;
			break;
		}
	}
	if (!flag)
	{
		cout << "No winner."<<endl;
	}

}
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
#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;
int gra[101][101];
int dis[101][101];
int vis[101][101];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
struct node
{
    int d;
    int x,y;
    bool operator < (const node &a) const{
        return d>a.d;
    }
};
void dijkstra(int s,int t)
{
    priority_queue<node> q;
    memset(dis,0x3f3f3f,sizeof(dis));
    dis[s][t]=0;
    node tmp;
    tmp.x=s;
    tmp.y=t;
    tmp.d=0;
    q.push(tmp);
    while(!q.empty())
    {
        tmp=q.top();
        q.pop();
        int x=tmp.x;
        int y=tmp.y;
        if(vis[x][y]==1)
            continue;
        vis[x][y]=1;
        for(int i=0;i<4;i++)
        {
            int x1,y1;
            x1=x+dx[i];
            y1=y+dy[i];
            if(gra[x1][y1]==0||x1<1||x1>m||y1<1||y1>n)
            {
                continue;
            }
            if(dis[x1][y1]>dis[x][y]+1)
            {
                dis[x1][y1]=dis[x][y]+1;
                node t1;
                t1.x=x1;
                t1.y=y1;
                t1.d=dis[x1][y1];
                q.push(t1);
            }
        }
    }
}
int main()
{
    cin>>m>>n;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>gra[i][j];
            if(gra[i][j]==2)
            {
                s=i,t=j;
            }
        }
    }
    dijkstra(s,t);
    int k;
    cin>>k;
    vector<int> v[10010];
    for(int i=1;i<=k;i++)
    {
        int x,y;
        cin>>y>>x;
        if(dis[x][y]<0x3f3f3f)
        {
            //cout<<dis[x][y]<<endl;
            v[dis[x][y]].push_back(i);
        }
    }
    int flag=0;
    for(int i=1;i<=n*m;i++)
    {
        if(v[i].size()==1)
        {
            cout<<v[i][0]<<" "<<i<<endl;
            flag=1;
            break;
        }
    }
    if(!flag)
    {
        cout<<"No winner.";
    }
}

7-6 xt的考研路

最终的子图应该是一个“Y”字型，即两个起点到达中间结点，再从中间结点到终点。特殊情况就是中间结点是某个起点或者终点。通过Dijkstra预处理出来从两个起点出发的单源最短路径的dist1，dist2，还有从终点出发的单源最短路径的dist3数组（从终点出发的要反向走），随后枚举中间点取最小值即可。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
int id1,id2,id3;
ll dis1[100010],dis2[100010],dis3[100010];
int vis1[100010],vis2[100010],vis3[100010];
vector<ll> e1[100010],e2[100010];
vector<ll> w1[100010],w2[100010];
struct node
{
    ll d;//长度
    int u;//点的编号
    bool operator < (const node & rhs) const {
		return d > rhs.d;
	}
};
void dijkstra(int s,vector<ll> e[],vector<ll> w[],ll dis[],int vis[])
{
    priority_queue<node> q;
    for(int i=0;i<=n;i++)
    {
        dis[i]=0x3f3f3f3f/3;
    }
    dis[s]=0;
    memset(vis,0,sizeof(vis));
    node tmp;
    tmp.d=0;
    tmp.u=s;
    q.push(tmp);
    while(!q.empty())
    {
        node t;
        t=q.top();
        q.pop();
        int u=t.u;
        if(vis[u]==1)
        {
            continue;
        }
        vis[u]=1;
        for(int i=0;i<e[u].size();i++)
        {
            if(dis[e[u][i]]>dis[u]+w[u][i])
            {
                dis[e[u][i]]=dis[u]+w[u][i];
                node t1;
                t1.d=dis[e[u][i]];
                t1.u=e[u][i];
                q.push(t1);
            }
        }

    }
}
int main()
{
    cin>>n>>m;
    cin>>id1>>id2>>id3;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        e1[a].push_back(b);
        w1[a].push_back(c);
        e2[b].push_back(a);
        w2[b].push_back(c);
    }
    dijkstra(id1,e1,w1,dis1,vis1);
    dijkstra(id2,e1,w1,dis2,vis2);
    dijkstra(id3,e2,w2,dis3,vis3);
    ll res=0x3f3f3f3f;
	for(int i=0;i<n;i++){
        res = min(res,dis1[i]+dis2[i]+dis3[i]);
        //cout<<dis1[i]<<" "<<dis2[i]<<" "<<dis3[i]<<endl;
	}
	if(res<0x3f3f3f3f/3){
		cout<<res<<endl;
	}else{
		cout<<"xt,我好没本领！"<<endl;
	}
}

7-7 二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
const int N=1e6+10;
using namespace std;
int n,m,a[N],x;
int binary_search(int x){
	int l=1,r=n;
	while(l<r){
		int mid=(l+r)>>1;
		if(a[mid]<x) l=mid+1;
		else  r=mid;
	}
	return l;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++){
		cin>>x;
		int q=binary_search(x);
		if(a[q]!=x) cout<<"-1 ";
		else cout<<q<<" ";
	} 
	return 0;
}

7-8 h0008.卡片延伸长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
int main(){
    double n;
    while(cin>>n&&n!=0.00){
        int l=1,r=300;
        while(l<r){
            int mid=(l+r)/2;
            double len=0;
            for(int i=1;i<=mid;i++){
                len+=1.0/(i+1);
            }
            if(len>=n) r=mid;
            else l=mid+1;
        }
        cout<<l<<" card(s)\n";
    }
    return 0;
}

7-9 【USACO】进击的奶牛

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
#include <iostream>
#include <algorithm>
#define N 100010
using namespace std;

int n,c,x[N];
bool check(int d){
    int ct=1,pre=x[1];
    for(int i=2;i<=n;i++){
        if(x[i]-pre>=d){
            ct++;
            pre=x[i];
        }
    }
    return ct>=c;
}
int main(){
    cin>>n>>c;
    for(int i=1;i<=n;i++) cin>>x[i];
    sort(x+1,x+1+n);
    int l=1,r=(x[n]-x[1])/(c-1);
    while(l<r){
        int mid=(l+r+1)/2;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<r<<endl;
    return 0;
}

7-10 逆序对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
#include<iostream>
#define N 100010
using namespace std;
typedef long long ll;

int n,a[N];
int t[N];

void update(int x,int c){
    for(;x<=n;x+=x&-x) t[x]+=c;
}
ll sum(int x){
    ll ans=0;
    for(;x;x-=x&-x) ans+=t[x];
    return ans;
}

int main(){
    ll ans=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
         ans+=i-1-sum(a[i]);
         update(a[i],1);
    }
    cout<<ans<<endl;
    return 0;
}

7-11 逆序对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
#include <iostream>
#include <algorithm>
#include <vector>
#define N 100010
using namespace std;
typedef long long ll;

int n,a[N];
int t[N];

void pre(){
	vector<int> ve;
	for(int i=1;i<=n;i++) ve.push_back(a[i]);
	sort(ve.begin(),ve.end());
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(ve.begin(),ve.end(),a[i])-ve.begin()+1; 
	}
}
void update(int x,int c){
    for(;x<=n;x+=x&-x) t[x]+=c;
}
ll sum(int x){
    ll ans=0;
    for(;x;x-=x&-x) ans+=t[x];
    return ans;
}

int main(){
    ll ans=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    pre();
    for(int i=1;i<=n;i++){
         ans+=i-1-sum(a[i]);
         update(a[i],1);
    }
    cout<<ans<<endl;
    return 0;
}

7-12 树状数组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
#include <iostream>
#include <algorithm>
#include <vector>
#define N 100010
using namespace std;
typedef long long ll;

int n,q,a[N];
int t[N];

void update(int x,int c){
    for(;x<N;x+=x&-x) t[x]+=c;
}
ll sum(int x){
    ll ans=0;
    for(;x;x-=x&-x) ans+=t[x];
    return ans;
}

int main(){
    ll ans=0;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        update(i,a[i]);
    }
    for(int i=1;i<=q;i++){
        int op;
        cin>>op;
        if(op==1){
        	int x,c;
        	cin>>x>>c;
        	update(x,c);
		}
		else{
			int l,r;
			cin>>l>>r;
            ll ans=0;
			cout<<sum(r)-sum(l-1)<<endl; 
		}
    }
    return 0;
}

7-13 树状数组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
#include <iostream>
#define N 100010
using namespace std;
typedef long long ll;

int n,q;
ll a[N],d[N],t[N];

void update(int x,int c){
	for(;x<N;x+=x&-x) t[x]+=c;
}
ll sum(int x){
	ll ans=0;
	for(;x;x-=x&-x) ans+=t[x];
	return ans;
}
int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		d[i]=a[i]-a[i-1];
		update(i,d[i]);
	} 
	while(q--){
		int op;
		cin>>op;
		if(op==1){
			int l,r,c;
			cin>>l>>r>>c;
			update(l,c);
			update(r+1,-c);
		}
		else{
			int x;
			cin>>x;
			cout<<sum(x)<<endl;
		}
	}
	return 0;
}