【作业向】程序设计思维与实践 Week8 作业

发表于 | 分类于 ，
字数统计: 2.1k | 阅读时长 ≈ 10

【作业向】程序设计思维与实践 Week8作业

♔A 区间选点 II

♔Problem

给定一个数轴上的 n 个区间，要求在数轴上选取最少的点使得第 i 个区间 [ai, bi] 里至少有 ci 个点

使用差分约束系统的解法解决这道题

♔Input

输入第一行一个整数 n 表示区间的个数，接下来的 n 行，每一行两个用空格隔开的整数 a，b 表示区间的左右端点。1 <= n <= 50000， 0 <= ai <= bi <= 50000 并且 1 <= ci <= bi - ai+1。

♔Output

输出一个整数表示最少选取的点的个数

♔Example

♔Input

1
2
3
4
5
6
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

♔Output

1
6

♔解题思路

这一题用差分约束的方法来做的话就需要构造不等式组，其中

  • 记sum[i]表示数轴上[0,i]之间选点的个数
  • 对于第i个区间[ai, bi]需要满足sum[bi] - sum[ai - 1] ≥ ci
  • 同时还要保证0 ≤ sum[i] - sum[i- 1] ≤ 1

（除此之外，由于点的编号从0开始，ai-1会小于0导致数组越界，故将各点整体加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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#define ll long long
using namespace std;
int adj[50005],nxt[150005],too[150005],w[150005],ecnt;
int n,s,t,dis[50005],visit[50005];

void spfa()
{
	queue<int> q;
	q.push(s);
	visit[s]=1;
	int u,v;
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		visit[u]=0;
		for(int i=adj[u];i;i=nxt[i])
		{
			v=too[i];
			if(dis[v]<dis[u]+w[i])
			{
				dis[v]=dis[u]+w[i];
				if(!visit[v])
				{
					visit[v]=1;
					q.push(v);
				}
			}
		}
	}
}

int main()
{
	int i,j,k;
	int a,b,c;
	scanf("%d",&n);
	s=0x7fffffff;
	for(i=1;i<=n;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		nxt[++ecnt]=adj[a],adj[a]=ecnt,too[ecnt]=b+1,w[ecnt]=c;
		s=min(s,a);
		t=max(t,b+1);
	}
	for(i=s;i<=t;i++)
	{
		nxt[++ecnt]=adj[i],adj[i]=ecnt,too[ecnt]=i+1,w[ecnt]=0;
		nxt[++ecnt]=adj[i+1],adj[i+1]=ecnt,too[ecnt]=i,w[ecnt]=-1;
	}
	spfa();
	printf("%d",dis[t]);
	return 0;
}

♔B 猫猫向前冲

♔Problem

众所周知， TT 是一位重度爱猫人士，他有一只神奇的魔法猫。
有一天，TT 在 B 站上观看猫猫的比赛。一共有 N 只猫猫，编号依次为1，2，3，…，N进行比赛。比赛结束后，Up 主会为所有的猫猫从前到后依次排名并发放爱吃的小鱼干。不幸的是，此时 TT 的电子设备遭到了宇宙射线的降智打击，一下子都连不上网了，自然也看不到最后的颁奖典礼。
不幸中的万幸，TT 的魔法猫将每场比赛的结果都记录了下来，现在他想编程序确定字典序最小的名次序列，请你帮帮他。

♔Input

输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示猫猫的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即编号为 P1 的猫猫赢了编号为 P2 的猫猫。

♔Output

给出一个符合要求的排名。输出时猫猫的编号之间有空格，最后一名后面没有空格!

其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。

♔Examples

♔Input

1
2
3
4
4 3
1 2
2 3
4 3

♔Output

1
1 2 4 3

♔解题思路

对于每一组a胜过b，构建一条从a指向b的有向边，然后进行拓扑排序。特别的，对于输出时要求编号小的队伍在前，因此存储入度为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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#define ll long long
using namespace std;
int n,m,t;
int tu[505][505],d[505];

int main()
{
	int i,j,k;
	priority_queue< int,vector<int>,greater<int> > q;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(tu,0,sizeof(tu));
		for(i=1; i<=m; i++)
		{
			scanf("%d%d",&j,&k);
			if(tu[j][k]) continue;
			tu[j][k]=1;
			d[k]++;
		}
		for(i=1; i<=n; i++)
			if(d[i]==0)
			{
				q.push(i);
			}
		t=0;
		while(!q.empty())
		{
			k=q.top();
			if(t!=n-1)
			{
				printf("%d ",k);
				t++;
			}
			else printf("%d\n",k);
			q.pop();
			for(i=1; i<=n; i++)
			{
				if(tu[k][i])
				{
					d[i]--;
					if(d[i]==0) q.push(i);
				}
			}
		}
	}
	return 0;
}

♔C 班长竞选

♔Problem

大学班级选班长，N 个同学均可以发表意见 若意见为 A B 则表示 A 认为 B 合适，意见具有传递性，即 A 认为 B 合适，B 认为 C 合适，则 A 也认为 C 合适 勤劳的 TT 收集了M条意见，想要知道最高票数，并给出一份候选人名单，即所有得票最多的同学，你能帮帮他吗？

♔Input

本题有多组数据。第一行 T 表示数据组数。每组数据开始有两个整数 N 和 M (2 <= n <= 5000, 0 <m <= 30000)，接下来有 M 行包含两个整数 A 和 B(A != B) 表示 A 认为 B 合适。

♔Output

对于每组数据，第一行输出 “Case x: ”，x 表示数据的编号，从1开始，紧跟着是最高的票数。 接下来一行输出得票最多的同学的编号，用空格隔开，不忽略行末空格！

♔Examples

♔Input

1
2
3
4
5
6
7
8
9
10
2
4 3
3 2
2 0
2 1

3 3
1 0
2 1
0 2

♔Output

1
2
3
4
Case 1: 2
0 1
Case 2: 2
0 1 2

♔解题思路

这一题首先要对建好的图求强连通分量，然后将各强连通分量缩成一个点并对缩号的点进行反向建图，从各入度为零的点开始跑dfs，记录他们所能到达的所有强连通分量的点数总和ppsum[i]，然后对各ppsum[i]求max，求得的max-1即为答案（因为要去掉自身），然后对各点进行判断，若该的所在的强连通分量的ppsum为取得的最大值，则将该点输出。

（又及：在跑dfs时因为建返图时会有重边，因此要注意对重边的处理

♔代码

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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#define ll long long
using namespace std;
int adj[5005],adj1[5005],nxt[600005],too[600005],ecnt;
int dfn[5005],low[5005],visit[5005],stck[5005],fa[5005],ppsum[5005],psum[5005],du[5005],ti[5005];
int M,n,m,top,times,ssum,maxp,pcnt,flag;

void tarjan(int u)
{
	visit[u]=1,stck[++top]=u;
	dfn[u]=low[u]=++times;
	for(int i=adj[u];i;i=nxt[i])
	{
		int v=too[i];
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(visit[v] && dfn[v]<low[u]) low[u]=dfn[v];
	}
	if(dfn[u]==low[u])
	{
		int v;
		visit[u]=0;
		fa[u]=++ssum;
		psum[ssum]=1;
		while(v=stck[top--],v!=u) fa[v]=ssum,psum[ssum]++,visit[v]=0;
	}
}

int dfs(int x)
{
	int cnt=psum[x];
	for(int i=adj1[x];i;i=nxt[i])
	{
		if(!visit[too[i]])
		{
			visit[too[i]]=1;
			cnt+=dfs(too[i]);
		}
	}
    return cnt;
} 

int main()
{
	int i,j,k,h;
	int x,y;
	scanf("%d",&M);
	for(h=1;h<=M;h++)
	{
		memset(adj,0,sizeof(adj));
		memset(adj1,0,sizeof(adj1));
		memset(nxt,0,sizeof(nxt));
		memset(du,0,sizeof(du));
		memset(dfn,0,sizeof(dfn));
		memset(low,0,sizeof(low));
		memset(visit,0,sizeof(visit));
		memset(ppsum,0,sizeof(ppsum));
		ecnt=top=times=ssum=maxp=pcnt=flag=0;
		scanf("%d%d",&n,&m);
		for(i=1;i<=m;i++)
		{
			scanf("%d%d",&x,&y);
			nxt[++ecnt]=adj[x],adj[x]=ecnt,too[ecnt]=y;
		}
		for(i=0;i<n;i++)
			if(!dfn[i]) tarjan(i);
		for(i=0;i<n;i++)
		{
			for(j=adj[i];j;j=nxt[j])
			{
				k=too[j];
				if(fa[i]!=fa[k])
				{
					nxt[++ecnt]=adj1[fa[k]],adj1[fa[k]]=ecnt,too[ecnt]=fa[i];
					du[fa[i]]++;
				}			
			}
		}
		for(i=1;i<=ssum;i++) 
			if(!du[i])
			{
				memset(visit,0,sizeof(visit));
				visit[i]=1;
				maxp=max(maxp,ppsum[i]=dfs(i));
			} 
//		for(i=1;i<=ssum;i++)
//			maxp=max(maxp,ppsum[i]);
		for(i=1;i<=ssum;i++)
			if(ppsum[i]==maxp) ti[++pcnt]=i;
		printf("Case %d: %d\n",h,maxp-1);
		for(i=0;i<n;i++)
		{
			for(j=1;j<=pcnt;j++)
				if(fa[i]==ti[j])
				{
					if(flag==0)
					{
						printf("%d",i);
						flag=1;
					}
					else printf(" %d",i);
					break;
				}
		}
		printf("\n");
	}
	return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！