2023.11.21初一周赛总结

2023.11.21初一欢乐周赛

总叙:思路差不多懂，但就是不会写

P1165 日志分析

题目链接：P1165

考点：模拟，线性数据结构，栈

难点：我们设a[i]为栈中从下到上的i个元素中的最大值，当我们加入一个新元素x时，t++，a[t]=max(a[t-1],x)。那么在出栈时只要输出a[t-1]，在查找时只要输出a[t]

比赛时自己的思路：插入、删除、查询栈

结果：$ {\color{red} Unaccept}$

正确代码：

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
#include<bits/stdc++.h>
using namespace std;
int s[20000000],a[20000000],top,k;
int n,t,x;
void cx()
{
	if(top==0)
	{
		cout<<0<<'\n';
		return;
	}
	cout<<a[k]<<'\n';
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>t;
		if(t==0)//入栈
		{
			cin>>x;
			s[++top]=x;
			if(x>a[k])//a是辅助站，保存最大值 
				a[k+1]=x;
			else
				a[k+1]=a[k];//当前最大值入栈 
			k++; 
	 	} 
	 	if(t==1)//出栈 
	 	{
			if(top!=0 && k!=0)
			{
				top--,k--;
			}
	 	}
		if(t==2) cx();
		
	}
	return 0;
}

P4387 【深基15.习9】验证栈序列

题目链接：P4387

考点：栈

难点：入栈（push（））、是否栈空（empty（））、访问栈顶（top（））、出栈（pop（））

比赛时自己的思路：想不明白

结果：$ {\color{red} Unaccept}$

正确代码：
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
#include<bits/stdc++.h>
using namespace std;
int q,n,a[100010],b[100010];
stack<int> s;
int main()
{
	cin>>q;
	while(q--)
	{
		memset(a,0,sizeof a);
		memset(b,0,sizeof b);
		int t=1;
		cin>>n;
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=1;i<=n;i++) cin>>b[i];
		for(int i=1;i<=n;i++)
		{
			s.push(a[i]);
			while(s.top()==b[t])
			{
				s.pop();
				t++;
				if(s.empty()) break;
			}
		}
		if(!s.empty()) cout<<"No"<<endl;
		else cout<<"Yes"<<endl;
		while(!s.empty()) s.pop();
	}
	return 0;
}

P9748 [CSP-J 2023] 小苹果

题目链接：P9748

考点：栈，O2

难点：每次拿去 $n/3$ 个苹果，而如果此时 $n % 3$ 刚好为一，则这一天也可以拿走第 $n$ 个苹果

比赛时自己的思路：栈逐一判断苹果树，记录

结果：$ {\color{red} Unaccept}$

正确代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
int n,t=0,s=1,ans=0;
int main()
{
	cin>>n;
	while(n>0)
	{
		if(n<0) break;
		if(!ans&&n%3==1) ans=s;
		t=ceil(1.0*n/3);
		n=n-t;
		s++;
	}
	cout<<s-1<<" "<<ans<<endl;
	return 0;
}

总结：

对于我来说挺难的，还要加倍努力