Codeforces Round #767 (Div. 2)C ,D
C
这一道题大意是给你一个数组，你可以选取任意长度的数组（连续）,求出这个数组的mex，然后问我们你得到最大的字典序的mex是多少（我这里犯了一个错误，就是我以为5 4 0和5 4 0 0的长度是一样的，其实是后者更大一点，是这个数字0误导了我）
这题就是模拟吧，不过我自己写的时候为了更好的求mex用了排序，结果答案超时了，其实也有其他方法可以求出mex而不需要用到排序，这里用到了记录下每一个数在数组里的数量（a[i]<n，可以记录，如果不是这样可能需要用到map)
然后一遍遍求当前位置可以得到的最大mex,一个一个往后遍历
具体实现看代码
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int t,n;
void solve()
{
cin>>n;
vector<int>a(n),cnt(n+1);
for (int i=0;i<n;i++)
{
cin>>a[i];
cnt[a[i]]++;
}
vector<bool>f(n+1);
queue<int>q;
int p=0;
while (p<n)
{
int now=0;
while (cnt[now]>0)//求p到最后一个mex(此时的mex是当前最大的)
{
now+=1;
}
int num=0;
while (num<now)//找到从当前p到下一位置刚好mex==上面求的最大的mex，而不浪费一个数
{
cnt[a[p]]--;//只要用过了cnt[a[p]]--，数量就会减一
if (!f[a[p]]&&a[p]<now)//我们真正需要从0到now-1的数，这样就会每一个数只会记录一次，num++一次
{
f[a[p]]=true;
num++;
}
p++;//找下一个
}
if (now==0) p++;//如果是0的话
for (int i=0;i<now;i++)
{
f[i]=false;
}
q.push(now);
/*if(now==0)
{
break;
//此时最大的mex是0,那么后面也全是0，直接break，这个就是我在前面说的错误认识，一定要有多少个0就加多少个0
}*/
}
cout<<q.size()<<'\n';
while (!q.empty())
{
cout<<q.front()<<" ";
q.pop();
}
cout<<'\n';
return ;
}
int main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
D
大意是给你n个字符串，问我们可不可以删除一些字符，实现剩下的字符串拼接出来是一个回文。
这一道题也是模拟题（这道题好就好在它每次输入的字符串长度小于等于3）
而我们只要找到一对符合回文的就可以了（输出YES）bool ok=false(代表找到了可以出现回文的没)
如果长度是1，那么本身就是一个回文，ok=true;
长度是2，有3种情况ok=true
1.本身是回文
2.前面出现过一个长度为2的可以和它形成回文
3.前面出现过一个长度为3的可以和它形成回文，比如如果这次字符串是ab,那么前面出现的必须是bax（x是任意字母）,形成baxab也是一个回文
如果长度是3，也有3种情况可以使ok=true
1.本身是回文
2.前面出现过一个长度为3的可以和它形成回文
3.前面出现过一个长度为2的可以和它形成回文，比如如果这次字符串是abc,那么前面出现的必须是cb（,形成cbabc也是一个回文
而我在做这一道题的时候忘记了是删除某些字符串，以为是可以随便排的，那么就多了很多情况，导致错了，ε=(´ο｀*)))唉
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;
int t,n;
string s;
void solve()
{
cin>>n;
set<string>two,three;
bool ok=false;
while (n--)
{
cin>>s;
if (ok) continue;
int len=s.size();
if (len==1)
{
ok=true;
continue;
}
if (len==2)
{
string ss=s;
reverse(ss.begin(),ss.end());
if (ss==s||two.count(ss))
{
ok=true;
continue;
}
for (int i=1;i<=26;i++)
{
char ch=i+'a'-1;
string tmp=ss;
// tmp=" "+tmp;//这个是我没有考虑到顺序问题，把s当成前面那一个了
// tmp[0]=ch;
// if (three.count(tmp))
// {
// ok=true;
// break;
// }
// tmp=ss;
tmp.push_back(ch);
if (three.count(tmp))
{
ok=true;
break;
}
}
two.insert(s);
}
else if (len==3)
{
string ss=s;
reverse(ss.begin(),ss.end());
if (ss==s||three.count(ss))
{
ok=true;
continue;
}
string tmp=ss;
tmp.pop_back();
if (two.count(tmp))
{
ok=true;
continue;
}
// tmp[0]=ss[1],tmp[1]=ss[2];//这个也是
// if (two.count(tmp))
// {
// ok=true;
// continue;
// }
three.insert(s);
}
}
if (ok)
{
cout<<"YES\n";
}
else cout<<"NO\n";
return ;
}
int main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}