EasyRound2(冒险之旅)题解

发表于 | 评论数： | 阅读次数：

本场比赛，没那么难吧，一个AK的也没有吗?

A U57818

分析

本题本来还有一个名字，叫做【模板】秦九韶算法。

秦九韶算法就是在$O(n)$的时间内，计算一元$n$次多项式的值的算法。

具体过程请直接看代码。

Code A

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
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
/* consts */
const int MAXN = 1e4+10;
using namespace std;
namespace FastIO{
    const int BUFSIZE=1<<20;
    char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==it)
            it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==it)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res<0){
            putch('-');
            res=-res;
        } 
        int top=0;
        while(res){
            q[top++]=res%10+'0';
            res/=10;
        }
        while(top--)	putch(q[top]);
    }
} 
using namespace FastIO;
/* definitions */
int n,x,pointer;
int function[MAXN];
long long value;
/* functions */
inline void init(){
	scanf("%d%d",&n,&x);
	for(int i=0;i<=n;i++){
		scanf("%d",&function[i]);
	}
	pointer=n-1;
	value=function[n];
}
inline void QJS(){
	init();
	while(pointer>=0){
		value=value*x+function[pointer];
		pointer--;	
	}
	printf("%d",value);
}
int main(int argc,char *argv[]){
	//freopen("QJS4.in","r",stdin);
	//freopen("OJS4.out","w",stdout);
	QJS();
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

B U57822

分析

ZROI#518原题。

我们用一个vector对于搜索的过程进行维护，当当前格子的右方和下方的字符相同时，就把他们都计入vector中。

然后，分别对这两种情况进行扩展，再判断一下他们各自的右方和下方和它字典序之和，取最小值，如果还相同，那么继续把这3个节点计入vector中，以此类推，直到找到答案为止。

但是！

这样的话很可能会导致某些节点会被重复计入vector中，也意味着vector容量必须扩大很多，直接的后果就是TLE,

所以，我们要再处理中对于重复计算的节点进行处理，优化程序算法。

Code 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
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
/* Headers */
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cctype> 
#include<algorithm>
#include<climits>
#include<vector>
/* define */
typedef std::pair<int,int> point;
/* consts */
const int MAXN = 2010;
using namespace std;
namespace FastIO{
	const int BUFSIZE=1<<20;
	char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
	char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
	inline char getch(){
		if(is==it)
			it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
		return (is==it)?EOF:*is++;
	}
	inline int getint(){
		int res=0,neg=0,ch=getch();
		while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
			ch=getch();
		if(ch=='-'){
			neg=1;ch=getch();
		}
		while(isdigit(ch)){
			res=(res<<3)+(res<<1)+(ch-'0');
			ch=getch();
		}
		return neg?-res:res;
	}
	inline void flush(){
		fwrite(obuf,1,os-obuf,stdout);
		os=obuf;
	}
	inline void putch(char ch){
		*os++=ch;
		if(os==ot)	flush();
	}
	inline void putint(int res){
		static char q[10];
		if(res==0)	putch('0');
		else if(res<0){
			putch('-');
			res=-res;
		} 
		int top=0;
		while(res){
			q[top++]=res%10+'0';
			res/=10;
		}
		while(top--)	putch(q[top]);
	}
	inline void space(int x){
		if(!x)puts("");
		else putchar(' ');
	}
} 
using namespace FastIO;
/* defintions */
char word[MAXN][MAXN];
int n,m;
bool visited[MAXN][MAXN];

/* functions */
inline void init(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		cin>>word[i];
	}
}
inline void find_answer(){
	init();
	vector<point>v,nexts;
	for(v.push_back({0, 0}); !v.empty();v = nexts){
		point p=v.back();
		cout<<word[p.first][p.second];
		char another='z';
		for(point k : v){
			int x=1,y=0;
			for(int i=0;i<2;++i){
				swap(x,y);
				int dx=k.first+x;
				int dy=k.second+y;
				if(dx>=n||dy>=m)continue;
				another=min(another,word[dx][dy]);
			}
		}
		nexts.clear();
		for(point k : v){
			int x=1,y=0;
			for(int i=0;i<2;++i){
				swap(x,y);
				int dx=k.first+x;
				int dy=k.second+y;
				if(dx>=n||dy>=m)continue;
				if(visited[dx][dy])continue;
				if(word[dx][dy]==another){
					nexts.push_back({dx,dy});
					visited[dx][dy]=1;
				}
			}
		}
	}
}
int main(void){
	find_answer();
	space(0);
	return 0;
}

C U57857

分析

一道非常简单的大根堆模板题，只考察了堆的插入和出堆等基础操作，只要了解堆的概念就肯定会做。

Code C

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
/* define */
#define IOS ios::sync_with_stdio(false);
/* consts */
const int MAXN = 1e6+10;
using namespace std;
namespace FastIO{
    const int BUFSIZE=1<<20;
    char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==it)
            it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==it)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res<0){
            putch('-');
            res=-res;
        } 
        int top=0;
        while(res){
            q[top++]=res%10+'0';
            res/=10;
        }
        while(top--)	putch(q[top]);
    }
} 
using namespace FastIO;
/* definitons */
struct Node{
	string names;
	int degree;
};
Node Heap[MAXN];
int sizes,n;
string op;
/* functions */
inline void swaps(int &x,int &y){
	int z=x;
	x=y;
	y=z;
}
inline int TreeLeft(int k){
	return k<<1;
}
inline int TreeRight(int k){
	return (k<<1)+1;
}
inline void shiftUp(int point){
	while(point>1&&Heap[point/2].degree<Heap[point].degree){
		swap(Heap[point/2],Heap[point]);
		point/=2;
	}
}
inline void shiftDown(int point){
	int p;
	while(TreeLeft(point)<=sizes){
		if(TreeRight(point)<=sizes&&Heap[TreeRight(point)].degree>Heap[TreeLeft(point)].degree)
			p=TreeRight(point);
		else p=TreeLeft(point);
		if(Heap[p].degree>Heap[point].degree){
			swap(Heap[p],Heap[point]);
			point=p;
		}
		else break;
	}
}
inline void pushIn(Node x){
	Heap[++sizes]=x;
	shiftUp(sizes);
}
Node top(){
	return Heap[1];
}
inline void popOut(){
	Heap[1]=Heap[sizes--];
	shiftDown(1);
}
inline void work(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		cin>>op;
		if(op=="max"){
			if(!sizes){
				printf("All Healthy\n");
				continue;
			}
			Node Top=top();
			popOut();
			cout<<Top.names<<endl;
		}
		else{
			Node push;
			cin>>push.names>>push.degree;
			pushIn(push);
		}
	}
}
int main(int argc,char *argv[]){
	//freopen("healthy5.in","r",stdin);
	//freopen("healthy5.out","w",stdout);
	work();
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

D U58415

luoguP1339HeatWave原题。

题解链接。

模板：单源最短路径之SPFA。

Code D

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
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype> 
#include<queue>
#include<vector>
using namespace std;
namespace FastIO{
    const int BUFSIZE=1<<20;
    char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==it)
            it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==it)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res<0){
            putch('-');
            res=-res;
        } 
        int top=0;
        while(res){
            q[top++]=res%10+'0';
            res/=10;
        }
        while(top--)	putch(q[top]);
    }
} 
using namespace FastIO;
/* consts */
const int MAXN = 2e4+10;
const int INF = 1e9;
/* definitions */
vector<int>Map[MAXN],value[MAXN];
int n,m,start,end;
int dist[MAXN];
bool visited[MAXN];
queue<int>Q;
/* functions */
inline void init(){
	scanf("%d%d%d%d",&n,&m,&start,&end);
	int s,e,val;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&s,&e,&val);
		Map[s].push_back(e);
		Map[e].push_back(s);
		value[s].push_back(val);
		value[e].push_back(val);
	}
}
inline void SPFA(){
	init();
	for(int i=1;i<=n;i++){
		dist[i]=INF;visited[i]=0;
	}
	dist[start]=0;visited[start]=1;
	Q.push(start);
	int first,tmp;
	while(!Q.empty()){
		first=Q.front();
		Q.pop();
		visited[first]=0;
		for(unsigned int i=0;i<Map[first].size();i++){
			tmp=dist[first]+value[first][i];
			if(tmp<dist[Map[first][i]]){
				dist[Map[first][i]]=tmp;
				if(!visited[Map[first][i]]){
					Q.push(Map[first][i]);
					visited[Map[first][i]]=1;
				}
			}
		}
	}
	printf("%d\n",dist[end]);
	return;
}
int main(int argc,char *argv[]){
	//freopen("data4.in","r",stdin);
	//freopen("data4.out","w",stdout);
	SPFA();
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

花絮

奇怪ishq大佬为什么没有AK。

奇怪HandwerSTD王太阳为什么没有AK。

感谢@HandwerSTD提供的T3数据。

rk1:ishq(325pts,46ms)

rk2:HandwerSTD(300pts,53ms)

rk3:extmool(100pts,71ms)

THE END