贪心: Problem - C - Codeforces

思维: Problem - D - Codeforces

这两个题不错, 第一个需要考虑后面,就先标记完, 从前遍历挨个除去标记

第二个需要考虑前面, 就开始初始化为0, 从前遍历挨个标记

C. Meximum Array

题意: 给出n个数, 把n个数分成任意份, 使得每一段mex结果尽量的大, 其次连起来数尽量的长

mex = 一组数最小且不存在于序列中的数, 包括0

题解:  既然要每段的mex尽量大, 那么后面加再多数  mex都不会变, 那么后面都是小于或大于mex, 即这一段序列后面没有mex

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+10;
int a[N], cnt[N];
bool st[N];
int main()
{
int t;
cin >> t;
while(t --)
{
vector<int> res;
int n;
cin >> n;
for(int i = 0; i < n; i ++)cnt[i]=0;
for(int i = 0; i < n; i ++)cin >> a[i], cnt[a[i]]++, st[i]=0;

/*
cnt //后面的所有数的次数, 用于判断后面还有没有更大的数
st //当前一小段序列谁出现过
*/

int mex = 0;//当前一小段序列的mex
for(int i = 0; i < n; i ++)
{
st[a[i]]=1;
while(st[mex])mex++;//找到从前到后第一个没有的数, 求mex
cnt[a[i]]--;//后面还有几个这个数
if(cnt[mex]<=0)//后面也没有这个数,那么再往后也没用了
{
res.push_back(mex);
for(int j = mex-1; j >= 0; j --)//为下一段序列初始化
{
st[j]=0;
}
mex=0;
}
}
cout << res.size() << endl;
for(int i = 0; i < res.size(); i ++)cout << res[i] << ' ';
cout << endl;
}
return 0;
}

D. Peculiar Movie Preferences

题意: 米海计划看一部电影。他只喜欢回文电影,所以他想跳过一些(可能零)场景,使电影的其余部分回文, 每个场景长度不超过三。

题解: 无非两种情况1.本身是回文2.遍历时前面有一串可以和他构成回文(从前往后遍历)

所以从前往后遍历的话, 只看它是否能够成为后缀


/*
做后缀:
倒过来加一个数
倒过来去一个数
倒过来 */
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int tx[4] = {-1,0,1,0}, ty[4] = {0,1,0,-1}; typedef pair<int,int> PII; const int N = 1e5+10;
string a[N];
map<string,bool> mp; bool solve()
{
mp.clear();//map用法
int n;
cin >> n;
bool f = 0;
for(int i = 0; i <n ; i ++)
{ cin >>a[i];
mp[a[i]]=1;
string s = a[i];
reverse(s.begin(), s.end());
if(s.size()==1 || s.size()==2&&s[0]==s[1] || mp[s])f=1;//本身是回文 if(mp[s.substr(0,s.size()-1)])f=1;//倒过来去一个数 for(char i = 'a'; i <= 'z'; i ++)//倒过来加一个数
if(mp[s+i])
f= 1;
}
return f;
}
int main()
{
int t;
cin >> t;
while(t --)
{
if(solve())puts("YES");
else puts("NO");
}
}

最新文章

  1. 微博feed系统的推(push)模式和拉(pull)模式和时间分区拉模式架构探讨
  2. 零基础学习云计算及大数据DBA集群架构师【Linux系统\网络服务及安全配置2015年1月8日周五】
  3. 【Linux探索之旅】第一部分第六课:Linux如何安装在虚拟机中
  4. uva 10831 - Gerg&amp;#39;s Cake(勒让德符号)
  5. centos6.5 x86_64安装oracle 11.2.0.3grid
  6. WindowsAzure上把WebApp和WebService同时部署在一个WebRole中
  7. FPGA时序约束——理论篇
  8. Java二分法
  9. 【highlight.js】页面代码高亮插件
  10. Intel格式与Motorola格式的区别
  11. Data Source与数据库连接池简介 JDBC简介(八)
  12. Uva10562——Undraw the Trees
  13. 循环队列搜索 Search in Rotated Sorted Array
  14. 机器学习实战1-1 KNN电影分类遇到的问题
  15. 【AGC005F】Many Easy Problems
  16. Codeforces 1102F Elongated Matrix 状压dp
  17. MVC请求管道
  18. Java SpringMVC框架学习(三)springMVC的执行流程
  19. Day22-Django之信号
  20. eclipse使用小技巧

热门文章

  1. vs 2019 社区版 .net core 5.0 之 .net core ef 迁移问题方案
  2. 如何做一个网站 (C# + MVC Web+ easyUI )
  3. 实习项目1-串口IP升级调试
  4. LinuxCNC中RS-274/NGC解析器的编译和使用
  5. Mapper 编写有哪几种方式?
  6. 阐述 final、finally、finalize 的区别?
  7. mac 修改环境变量bash_profile除了cd用不了其他命令,又关闭了终端
  8. 说说do...while和while的区别
  9. java-面向对象相关
  10. Saltstack自动化扩容