长郡暑期集训 DAY - 1
太阳🔆未起床，我去上集训~
坐着车🚗，到门口🚪，迷迷糊糊坐在电脑💻前~
看一看题目，全都不会😭做！
摸电线⚡，开电闸，滋滋滋滋到阎王👼面前~
闲聊一阵
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}\) 芝士，加油💪，奥力给！