海亮 DAY2 -- 解题报告

发表于 | 阅读次数:
字数统计: 1,897 字

今天按照安排应该是进行一次有关搜索的测试，主要是针对昨天所学的内容

T1

这一道t1其实正解是用二分做的，二分结果即可。
出现的错误：
在比赛时首先没有看清题目，以为每一个瓶盖之间的距离相等，即都是等距的。这直接导致GG，而且在做题的过程中心态并不平和，出现错误查不出来就很烦躁，然后恶性循环下去，这并不是一个好的事情。之后要调整。

二分的正确性：

因为这个答案显然是单调的，单调是满足二分的一个比较明显的标准，我们可以先把这一组数据进行排序，使满足单调的特性。当我们二分一个中间值作为一个答案的话，如果从第一个开始往后向后找，开始计数。如果计数大于等于 m 的话。 那么答案会在[mid,right]之间，如果计数小于 m 的话，答案就在[left,mid)之间，然后重复二分的过程，答案就在l-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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<stack>
#include<map>
using namespace std;

int a[1000005];
int l, r;
int n,m;
int main()
{
	scanf("%d %d", &n,&m);
	for (int i=1;i<=n;++i)
		scanf("%d", &a[i]);
	sort(a+1,a+n+1);
	l = 1; r = a[n] - a[1];
	while (l <= r)
	{
		int now(1);
		int times(1);
		int mid=(l + r)/2;
		for (int i = 2; i <= n; ++i)
			if (a[i] - a[now] >= mid)
			{
				++times;
				now = i;
			}
		if (times >= m)
		{
			l = mid + 1;
		}
		else 
			r = mid - 1;
	}
	printf("%d\n", l-1);
	return 0;
}

需要注意二分的端点问题，开区间与闭区间的区别。

T2

正解的算法是BFS,而我却当成一道图论题去做了（虽然在图论里BFS也是一种算法）这道题写的显然就是没有思考的结果，直接打最暴力的方法，根本不去思考了。

关于BFS算法的正确性：

因为BFS遍历到的点都是第一次走到，所以只要每遍历到一次就把计数加一即可，当
该点在此次遍历的过程中被记录的话，我们需要考虑的就是次数的转移。

挺经典的一个算法，之后又gdb跟踪了一下，搞懂标程了，贴下代码，带注释：

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<stack>
#include<map>
#include<utility>
using namespace std;

int n,m;

int d[100010],sum[100010];
bool v[100010];
vector<int> a[10010];
const int mod=100003;

inline int Read()
{
	int Num=0,F=1;  char ch=getchar();
	while (!isdigit(ch))	{if (ch == '-')	F=-1; ch=getchar();}
	while ( isdigit(ch))	{Num=(Num<<1)+(Num<<3)+ch-'0';	ch=getchar();}
	return Num*F;
}

void init()// 用vector数组来存无向图
{
	n=Read();m=Read();
	int xx,yy;
	for (int i=1;i<=m;++i)
	{
		xx=Read();yy=Read();
		a[xx].push_back(yy);//  即在xx 与 yy之间存在一条边，即yy为xx的子节点
		a[yy].push_back(xx);
	}
}
void bfs()
{	
	queue<int> q; q.push(1);d[1]=0;sum[1]=1;v[1]=1;// 1为根节点所以深度为0，
	while (!q.empty())
	{
		int x=q.front(); q.pop();
		for (int i=0;i<a[x].size();++i)
		{
			int t = a[x][i];
			if (!v[t])
			{
				v[t]=1;//  将该点标记，防止再次遍历。
				d[t]=d[x]+1;// 维护BFS的层数，当探到新的点以后说明这一层已经结束，将当前点的层数加上1即为新的子节点的层数。
				q.push(t);//  将本节点的子节点入队
			}
			if(d[t] == d[x] + 1)// 当当前点的子节点的层数比当前点的层数多一的话，将子节点的路径数更新，由上一层的根节点加上当前的子节点原来就有的路径数即可。
			sum[t]=(sum[x]+sum[t]) % mod;
		}
	}
}
int main()
{
	init();
	bfs();
	for (int i=1;i<=n;++i)
		printf("%d\n", sum[i]);
	return 0;
}

在这其中有一些很巧妙的东西，可以学习。

T3

这是一道很不容易拿满分的题吧，普通纯算法好像得不了全分。

正解是用重新构图然后跑一边SPFA得到的答案。
而我，又打出了最暴力的算法….，Dijastra加上dfs判断路径，复杂度直接爆掉。于是很惨的拿了10分。

正解思路：

重新构图，把每个点拆成 k + 1 个点，共连 2 * k 条边，如果消耗一次免费乘车的机会就把n与n相连的下一个点的边权设置成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
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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define inf 1000000007
#define M 100003
using namespace std;
int n,m,k,S,T,cnt,ans,head[10005],q[100005][2],dis[10005][11];
int next[100005],list[100005],key[100005];
bool v[10005][11];
inline int read()
{
    int a=0,f=1; char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();}
    while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();}
    return a*f;
}
inline void insert(int x,int y,int z)
{
    next[++cnt]=head[x];
    head[x]=cnt;
    list[cnt]=y;
    key[cnt]=z;
}
inline void spfa()
{
    int t=0,w=1,x,j;
    for (int i=0;i<n;i++) 
        for (int j=0;j<=k;j++)
            dis[i][j]=inf;
    memset(v,0,sizeof(v));
    dis[S][0]=0; v[S][0]=1; q[1][0]=S; q[1][1]=0;
    while (t!=w)
    {
        t=(t+1)%M;
        x=q[t][0];
        j=q[t][1];
        for (int i=head[x];i;i=next[i])
        {
            if (dis[x][j]+key[i]<dis[list[i]][j]) 
            {
                dis[list[i]][j]=dis[x][j]+key[i];
                if (!v[list[i]][j])
                {
                    v[list[i]][j]=1;
                    w=(w+1)%M;
                    q[w][0]=list[i];
                    q[w][1]=j;
                }
            }
            if (j<k&&dis[x][j]<dis[list[i]][j+1])
            {
                dis[list[i]][j+1]=dis[x][j];
                if (!v[list[i]][j+1])
                {
                    v[list[i]][j+1]=1;
                    w=(w+1)%M;
                    q[w][0]=list[i];
                    q[w][1]=j+1;
                }
            }
        }
        v[x][j]=0;
    }
}
int main()
{
    freopen("move.in","r",stdin);
    freopen("move.out","w",stdout);
    
    n=read(); m=read(); k=read(); S=read(); T=read();
    for (int i=1;i<=m;i++)
    {
        int u=read(),v=read(),w=read();
        insert(u,v,w); insert(v,u,w);
    }
    spfa();
    ans=inf;
    for (int i=0;i<=k;i++) ans=min(ans,dis[T][i]);
    printf("%d",ans);
    return 0;
}
//老师的代码，正在理解中...

总结

整体来说还好，打题状态不错，神经紧绷起来了，但是这种题最怕不进行思考，只打暴力，只套板子，其实有一些题想一想结论也不是很难，注意写题要思考，而不是无目的的刷题。

感觉自己正在不断进步吧，不论是知识水平，还是心里状态。毕竟用贪心的角度想一下，在当前阶段，最优决策就是不断学习与进步，提高自己，别忘了！不要太在乎之前和之后的状态，因为只要保证当前决策是最优的，那么这个照这样进行下去，得到的一定是一个全局最优解！

//别忘了你来这里是干什么的！！

成绩会反应一些问题，但是只要保证自己在不断提高自己，这些暂时的东西都影响不大！调整好状态，继续出发！