首页 > 其他分享 >12.15信息学笔记——尺取法

12.15信息学笔记——尺取法

时间:2023-12-25 20:34:34浏览次数:38  
标签:信息学 扫描 笔记 12.15 取法 指针

怎么说呢,这应该可以算作是一个算法吧,有另一个名字叫做“双指针”。通常,使用尺取法的序列应该是有序的,要先排序。同时,问题和序列的区间有关,且要操作两个变量。

对于这种问题,我们可以考虑在一个循环内同时处理两个下标,从而优化时间复杂度。

一般有两种方法:

1.反向扫描(在中间汇合)

  找指定和的整数对

  判断回文串

2.同向扫描(追及,其实产生了一个不固定大小的滑动窗口)

  寻找区间和

  数组去重

  快慢指针,判断链表是否含有环

3.多指针

  看具体题目分析,比如luoguP1102.

标签:信息学,扫描,笔记,12.15,取法,指针
From: https://www.cnblogs.com/czy-lemon/p/17926930.html

相关文章

  • 尺取法
    一.概念设:现在有一个有序的区间,要两个变量i和j扫描区间。对于上方应用,一般做法是用i和j分别扫描区间,有二重循环,复杂度为O(n^2)。以反向搜索(即i和j的方向相反,后文有解释)为例,代码如下:for(inti=0;i<n;i++)//i从头到尾for(intj=n-1;j>=0;j--)//j从尾到头......
  • 2023南海区信息学区赛(初中组)T2棋盘(原始)
    第2题   棋盘(原始) 查看测评数据信息有一个R行C列的棋盘,共有R×C个单元格子,每个单元格子都要放一个棋子,棋子只有黑色或者白色。如果两个单元格子有公共边,那么称为相邻的格子。如果一个棋盘满足所有相邻格子的棋子都是不同颜色,那么就称为“优美”棋盘;否则称为“普通”......
  • 2023南海区信息学区赛(初中组) T3 步数(原始)
    第3题   步数(原始) 查看测评数据信息有一个二维网格,从上往下,行的编号从1至n,从左往右,列的编号是1至m。第i行第j列的格子编号为(i,j),如果 a[i][j]为'@',表示格子(i,j)有障碍物,如果a[i][j]为'.'则表示格子(i,j)可通行。奶牛bessie当前在 格子(r1,c1),它每一步可以选择......
  • 2023南海区信息学区赛(初中组) T1二进制整除
    第1题   二进制整除 查看测评数据信息交换二进制数相邻两个位置的数字,需要花费1元的代价。读入整数n以及n位二进制数(也许有前导0),你需要依次回答n个独立的问题,第i个问题(1<=i<=n)是这样的:假如要使得读入的二进制数是2^i的倍数,至少需要花费多少元的代价?如果不可能,则输出......
  • 360沃通亮相2023年深圳市卫生健康信息学术会议,展示医疗行业商密应用方案
    2023年12月15日-16日,深圳市卫生健康信息协会举办主题为“智慧健康引领网络安全护航”的2023年深圳市卫生健康信息学术会议暨“京沪宁深连线”深圳专场,360沃通作为深圳密码领域代表性企业受邀参会,与现场知名专家学者、卫生健康信息化业内同仁、卫生健康信息产品厂商展开深入交流,并......
  • 河南科技大学 生物信息学
    生物信息学是生物科学类、农林类及医学类等本科专业的一门专业课程,主要培养学习者具备初步的生物信息学综合分析技能和创新创业能力。河南科技大学《生物信息学》课程于2018年度被遴选为河南省省级精品在线开放课程。——课程团队 课程概述生物信息学是生物学、计算机科学......
  • 青少年信息学奥赛学习规划指南!
    一、什么是信息学奥赛二、信息学奥赛赛制流程三、信息学奥赛系列赛事CSP-JCSP入门级(CSP-J),前身是NOIP普及组,是NOI系列赛事中难度最低,面向年龄最低的赛事,它是很多学生参与的第一个信息学的大型比赛。比赛时间:第一轮(初赛)为9月,第二轮(复赛)为10月。比赛形式:第一轮为2......
  • 12.15
    在Java中,缓冲类通常用于提高I/O操作的性能,例如 BufferedReader 用于读取文本文件,BufferedWriter 用于写入文本文件。下面分别给出这两个类的使用示例:使用 BufferedReader 读取文本文件的示例:importjava.io.BufferedReader;importjava.io.FileReader;importjava......
  • 信息学竞赛各赛制
    OI赛制每道题提交之后没有任何反馈,提交错误也没有任何惩罚。不限制提交次数。赛时看不到分数和排名。比赛结束之后以最后一次提交为准,按照总得分排名。CCFCSP-J/S,CCFNOIP,CCFNOI,牛客OI赛,洛谷普及组月赛,蓝桥杯都是OI赛制。ICPC赛制又称ACM赛制,ACM-ICPC赛制。每题提......
  • 12.15
    <!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><title>房产经纪人页面</title><style>.form{width:600px;margin:0auto;/*bor......