当前位置: 首页 > news >正文

day 5

昨天打比赛又遇到了子序列的题目,没写出来。
题目:https://ac.nowcoder.com/acm/contest/120061/E
题目大意:连续子数组是左右两边拼起来的数组的子序列,求这样的子数组数量。
最初想二分长度,发现不单调,题解是枚举每个左边界l,二分最大的右边界,此时对于每个左边界是单调的,因为大的可以小的一定可以。
代码:

include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2010;

int a[N],n;

bool check(int l,int mid)
{
int idx = l;
for(int i = 1;i<=n;i++)
{
if(i == l)
{
i = mid;
continue;
}
if(idx <= mid && a[idx] == a[i])
{
idx ++;
}
}
if(idx == mid + 1) return 1;
else return 0;
}
void solve()
{
cin >> n;
for(int i = 1;i<=n;i++) cin >> a[i];
ll ans = 0;
for(int i = 2;i<n;i++)
{
int l = i - 1,r = n - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(check(i,mid)) l = mid;
else r = mid - 1;
}
ans += l - i + 1;
}
cout << ans << endl;
}

int main()
{
int t = 1;
//cin >> t;
while(t--)
solve();
return 0;
}

http://www.hskmm.com/?act=detail&tid=34294

相关文章:

  • 2025年钢材厂家推荐排行榜,方钢/扁钢/圆钢/光轴/六角钢/异型钢/冷拉冷拔钢材/热轧钢材,Q355B/Q345B/16Mn/45#/40Cr/A3/Q235B钢公司精选
  • 2025定型机厂家推荐:鑫源恒进节能高效,智能排风引领行业新趋势!
  • LLM分词器
  • CF1859F Teleportation in Byteland
  • 密钥自己生成的方法
  • 2025机床维修厂家推荐:永华鑫数控设备,专业服务保障生产!
  • ubuntu 24.04虚拟机安装vgpu显卡驱动
  • 2025棋牌室加盟推荐麻友社,自主自助模式引领行业新风尚!
  • 计算机硬件-网络
  • 2025TYPE-C母座优质厂家推荐,创粤科技TID认证高速传输首选!
  • 2025年医药冷链运输厂家推荐排行榜,药品/临床样本/CAR-T/蛋白/诊断试剂/生物/血液/细胞/芯片运输,冷藏车/冷藏箱/保温箱/干冰/液氮/温控/国际冷链公司推荐!
  • Ubuntu 桌面美化
  • 题解:CF1336E2 Chiori and Doll Picking (hard version)
  • Apollo自动驾驶平台:开源、高性能的自动驾驶解决方案
  • 三八皇后、8线程、MMX
  • MantisBT vs Kanass,开源项目管理工具一文全面对比分析 - 详解
  • 2025工作服厂家推荐:深圳市贵格服饰,专业定制各类高品质工作服!
  • 2025年陶瓷过滤机厂家推荐排行榜,陶瓷真空过滤机/盘式陶瓷过滤机/矿用陶瓷过滤机/全自动陶瓷过滤机/固液分离设备公司精选
  • 2019年机器学习研究奖项获奖名单公布
  • 2025不锈钢清洗钝化液推荐:隆彦商贸环保高效,品质卓越!
  • 2025年棋牌室加盟推荐排行榜,自主棋牌室加盟,自助棋牌室加盟,优选品牌与服务指南
  • 2025年轻钢龙骨厂家,铝方通厂家,铝单板厂家,石膏板厂家推荐排行榜:专业品质与服务口碑之选!
  • 013的加密世界权威指南_第一部分
  • 卸载安装JDK
  • 2025年给汤机厂家最新权威推荐榜:诚信价格与卓越性能的完美结合,优质给汤机公司精选
  • 2025年给汤机厂家最新权威推荐榜:靠谱给汤机源头厂家精选,高效稳定与售后服务深度解析
  • DOS命令
  • windows防火墙开放某个端口的配置方法
  • 2025铝单板厂家推荐杰兰斯装饰,专业定制异形双曲等多款铝单板!
  • 条件运算符的中间表达式省略扩展