吃宵夜

U374729 hrmm 吃宵夜 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

非常粗糙的dp，一开始想用搜索，其实是大错特错，这个题实际上第二天有且仅有从第一天推导出来。

所以我们可以采用dp。

dp[i][j]表示第i天我们买第j种宵夜，这样我们的结果就是最后第n天买这三种宵夜的最大值，可能不太直观，但确实是我这个蒟蒻所能想到的了。

还是来想想转移方程吧，第i天选第j种，我们是不是第i-1天一定不能选第j种是不是这样。

然后我们是不是要加上a[i][j],这点不否认吧。

那我们多出来的循环K是干什么的，为什么要多出来，有什么用呢？

因为我们已经在第天选了第j种宵夜了，那我们在前面，也就是第i-1天我们可以选其他两种宵夜，这也是这个循环的由来，第二个原因是我们可以判断k==j嘛，这样就可以实现买的宵夜隔一天不同了对吧。

所以说我们的状态转移方程就是，应该不太难懂，就是第i天选了j种，然后前面一天我们有k种选择，所以说，要枚举一下，最后别忘了加上去就可以了。

真是有趣(×)难想（√）！

1
dp[i][j]=max(dp[i][j],dp[i-1][k]+a[i][j]);
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
#include<iostream>
using namespace std;
int a[1000000][4];
int dp[1000000][4];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=3;j++)
		{
			cin>>a[i][j];		
		}	
	}

for(int i=1;i<=n;i++)
{
	for(int j=1;j<=3;j++){
		for(int k=1;k<=3;k++)
		{
			if(j!=k)
			{
				dp[i][j]=max(dp[i][j],dp[i-1][k]+a[i][j]);
			}
			
		}
		
	}
	
}
	
	cout<<max(dp[n][3],max(dp[n][1],dp[n][2]));
	
	
}

学数学

U374726 hrmm 学数学 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
using namespace std;
string s="3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679";
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n+2;i++)
	
	{
		
		cout<<s[i];
	}
}

去种树

U374725 hrmm 去种树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

本题有个难点，但有且仅有一个

我们观察数据范围，二维数组肯定不行，字符串行不行我没试过，但可变数组vector应该行。于是就莫名其妙的过了。

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
#include<iostream>
#include<vector>

using namespace std;
vector<int>h[210000];
int main()
{
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
	{
		int a;
		cin >> a;
		for (int j = 1; j <= a; j++)
		{
			int s;
			cin >>s;
			h[i].push_back(s);

		}

	}
	while (q--)
	{
		int x, y;
		cin >> x >> y;
		cout << h[x][y- 1]<<'\n';
	
	}



}

期末考

U374720 hrmm 期末考 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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
#include<iostream>
using namespace std;
int a[4];
int main()
{
	int x, y;
	cin >> x >> y;
	

	if (x == 1)
	{
		a[1] = 1;
	}
	if (x == 2)
	{
		a[2] = 1;
	}
	if (x == 4)
	{
		a[3] = 1;
	}
	if (x == 3)
	{
		a[1] = 1;
		a[2] = 1;
	}
	if (x == 5)
	{
		a[1] = 1;
		a[3] = 1;
	}
	if (x == 6)
	{
		a[2] = 1;
		a[3] = 1;
	}
	if (x == 7)
	{
		a[1] = 1;
		a[2] = 1;
		a[3] == 1;
	}

	if (y == 1)
	{
		a[1] = 1;
	}
	if (y== 2)
	{
		a[2] = 1;
	}
	if (y == 4)
	{
		a[3] = 1;
	}
	if (y == 3)
	{
		a[1] = 1;
		a[2] = 1;
	}
	if (y == 5)
	{
		a[1] = 1;
		a[3] = 1;
	}
	if (y == 6)
	{
		a[2] = 1;
		a[3] = 1;
	}
	if (y == 7)
	{
		a[1] = 1;
		a[2] = 1;
		a[3] =1;
	}
	int sum = 0;
	
		if (a[1] == 1)
		{
			sum += 1;
		}
		if (a[2] == 1)
		{
			sum += 2;
		}
		if (a[3] == 1)
		{
			sum += 4;
		}
		cout << sum;





}

玩原神

U374722 hrmm 玩原神 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

好像讨论不太难，就讨论在不在一边，同时再讨论讨论位置，画画图就可以了。我说的很轻松对吧，但本蒟蒻写了半天。

据说有二进制优化，但不会......

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
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
	int x, y, z;
	cin >> x >> y >> z;
	if (x * y < 0)
	{
		cout << abs(x);
	}
	if (x * y > 0&&x>0&&y>0&&x<y)
	{
		cout << x;


	}
	if (x * y > 0 && x > 0 && y > 0 && x > y&&z>y)
	{
		cout << -1;


	}
	if (x * y > 0 && x > 0 && y > 0 && x > y && z < y&&z>0)
	{
		cout << x;


	}
	if (x * y > 0 && x > 0 && y > 0 && x > y && z < y&&z<0)
	{
		cout << 2*abs(z)+abs(x);


	}
	if (x * y > 0 && x < 0 && y < 0 && x > y)
	{
		cout << x;


	}
	if (x * y < 0 && x < 0 && y < 0 && x < y && z < y)
	{
		cout << -1;


	}
	if (x * y > 0 && x < 0 && y < 0 && x < y && z > y && z<0)
	{
		cout << x;


	}
	if (x * y > 0 && x < 0 && y < 0 && x < y && z > y && z > 0)
	{
		cout << 2 * abs(z) + abs(x);


	}

















}

走迷宫

U374723 hrmm 走迷宫 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

好难！！

虽然据说是模板，但我对这个存储想了大半年。

姑且来说一说吧，毕竟练多就菜。

首先，最短路，bfs合理吧。

我们存边，用最简便的邻接表合理吧。

我们是无向图，存两条边合理吧。

我们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
94
95
96
97
#include<iostream>
#include<queue>
using namespace std;
vector<int>g[200000];
vector<int>s[300000];
int n;
queue<int>q;
int vis[300000];
int r;
bool bfs(int x)
{
	q.push(x);
	vis[x] = 1;

	while (!q.empty())
	{
		int t = q.front();	
		q.pop();
		s[t].push_back(t);
		for (int i = 0; i < g[t].size(); i++)
		{
			
		
			if (!vis[g[t][i]])
			{
				vis[g[t][i]] = 1;
				q.push(g[t][i]);
			
					s[g[t][i]].push_back(t);
			


			}
			if (g[t][i] == r)
			{

				return 1;

			}



		}
	}
	


	return 0;



}
	int m;
	int flag=0;
	
void print(int r)
{
	if(flag)
	{
		return ;
	}
	if(r==m)
	{	
	flag=1;
		return ;
	}

print(s[r][0])	;
	cout<<s[r][0]<<' ';	
	
}


int main() {
	
	cin >> n;

	cin >> m;

	cin >> r;
	
	for (int i = 1; i <= n - 1; i++)
	{
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);

	}

	bfs(m);
print(r);
	cout << r;
	return 0;


}

开趴体

最后一题！

U374728 hrmm 开趴体 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

给大家开个Party

一道贪心题，就是说我们先把最大的排在偶数位，然后次大排在奇数位，然后比较就可以了。

群友真厉害啊，我是想不出来一点，被群友一说才会写！

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
#include<iostream>
#include<algorithm>
using namespace std;
int a[1000000];
int b[1000000];
bool cmp(int x,int y)
{
	return x>y;
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+1+n,cmp);
	int n2=1;
	for(int i=2;i<=n;i+=2)
	{
		b[i]=a[n2++];
	}
b[0]=999999999;
for(int i=1;i<=n;i+=2)
{
	b[i]=a[n2++];
}

for(int i=2;i<=n;i+=2)
{
	if(b[i]<=b[i-1]||b[i]<=b[i+1])
	{
		cout<<"No";
		return 0;
	}
	
}
cout<<"Yes";



	return 0;
}

世间温柔，不过是芳春柳摇染花香，槐序蝉鸣入深巷，白茂叶落醉故乡。

人生何处不相逢，各位再见。