2023.7.13 长郡模考复盘

太阳🔆未起床,我去上集训~

坐着车🚗,到门口🚪,迷迷糊糊坐在电脑💻前~

看一看题目,全都不会😭做!

摸电线🔋,开电闸,滋滋滋滋到阎王👼面前~

闲聊一阵

emm,今天我被各种东西惨😭了!

Why?

我妈让我早上 \(\texttt {6:00}\) 起床,\(\texttt {6:00}\) 啊!暑假不睡懒觉!对于我这种懒癌晚期患者比杀了我还痛苦😖!!!

但最要命的不是这个,而是上午的模拟考试😨!!!

四道题目,除了 \(\texttt {T1}\) 的艺术创作我看得懂,做了一点点,\(\texttt {T2 T3 T4}\) 明明知道每个词的意思,连起来就不知道意思了……(太弱了

比赛结果出来了,不出意外地全部爆零😪

嘤嘤嘤!

除此之外,长郡的上课节奏跟机构的完全不一样

如果说机构的上课速度是化学火箭🚀,那长郡的就是星环号🛸了!

我才学到链表,那里有人已经会二叉搜索树了😱!

回去我一定要疯狂卷题☹️!!!


进入正题

先放出今日模考题面 \(\texttt {PDF}\)地址

T1 艺术创作

这道题目是我做的题目中最简单的一道(也是唯一一道我做的),但是我没得一分……(弱死了),不过还好没人 \(\color {green} {\texttt {AC}}\)

当时我的思路是用递归的方式处理 \(L - R\) 区间的色块,每次固定一个左端点 \(L\),然后循环查找与 \(a_L\) 值相等的 \(a_i\),这时有三种情况:

  • 如果找到,递归 \(ans(L + 1,i - 1)\),将 \(L\) 更新为 \(i + 1\),继续查找。

  • 如果未找到,说明 \(a_L\) 是单个色块,直接将 \(L\) 更新为 \(L + 1\),继续查找。

  • 寻找的过程中发现了以前用过的色块,return -1,结束所有函数。

而返回结果则是用一个变量 \(day\) 记录一共递归了几层,递归的层数就是答案。

然后出现了什么结果呢?

\(\color {red} {\texttt {8 WA 2 TLE}}\)

看来是有一些递归死循环,还有一些说胡话……

QAQ!多么惨烈的战况​😭!

为了节省篇幅,错误代码就放一个链接了。


以下是正解🙂~

我们分析题目,会发现色块之间可以包含,但不能相交

根据这个特性,我们可以考虑使用来实现。

把涂色的开始视为入栈,涂色的结束视为出栈

若整个过程中出现操作非法(弹出时发现不合法),则表示涂色的区间出现了相交,无解。

否则答案为操作过程中栈内元素个数的最大值

但是,我知道思路我依旧没写对啊喂😭!!!

不过我还是拿了 \(\texttt {20}\) 分,先把代码放在这里吧。

#include<bits/stdc++.h>
using namespace std;
int jmap[100005],imap[100005],a[100005],n,maxn;
bool flag;
stack<int> s;
int main(){
	cin>>n;
	for(int i = 1;i <= n;i ++){
		cin>>a[i];
		imap[a[i]] ++;
	}
	for(int i = 1;i <= n;i ++){
		if(a[i] == 0 && flag == 0)continue;
		else flag = 1; 
		if(!jmap[a[i]]){
			if(imap[a[i]] != 1)s.push(a[i]);
			else maxn ++;
			jmap[a[i]] = 1;
		}
		else {
			if(s.top() == a[i])
				s.pop();
			else {
				cout<<-1;
				return 0;
			}
		}
		if(s.empty() == 0)
			if(maxn < s.size())maxn = s.size();
	}
	cout<<maxn;
	return 0;
}


集训虽然让我痛苦,但也让我学到了一堆 \(\texttt {OI}\) 芝士,加油💪,奥力给!

热门相关:洪荒二郎传   裙上之臣   裙上之臣   戏精老公今天作死没   闺范