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

「SCOI2015」小凸解密码题解

一个数据结构题。

首先断环成链,发现对一个值修改只是修改了 4 个点,直接单点修改即可。

这里其实所有非零的值都是一样的,只用 0/1 来表示即可。

考虑查询,可以考虑二分最小长度,只要所有距离大于这个长度的这个区间内有符合条件的零串即可。

即我们需要去求一个区间内是否有被 1 包裹的 0 串,使用一个线段树即可。

#include<bits/stdc++.h>
using namespace std;
const int N=2E5+5;
int n,m,a[N],op[N],opt;struct node{int l,r,c,s;node(bool x=0){l=r=c=x,s=0;}node friend operator + ( node a, node b){node res(0);res.l = a.l ;res.r = b.r ;res.c = a.c + b.c ;res.s = a.s + b.s + (a.c && b.c && (!a.r || !b.l ));return res; } 
};struct SEGT{#define ls p<<1#define rs p<<1|1#define mid (l+r>>1) node c[N<<2];void pushup(int p){c[p]=c[ls]+c[rs];}void change(int p,int l,int r,int x,int w){if(l==r)return c[p]=node(w),void();if(x<=mid)change(ls,l,mid,x,w);else change(rs,mid+1,r,x,w);pushup(p);}node query(int p,int l,int r,int L,int R){if(R<L)return node(0);if(L<=l &&r<=R) return c[p];if(L<=mid && R>mid)return query(ls,l,mid,L,R) + query(rs,mid+1,r,L,R);if(L<=mid )return query(ls,l,mid,L,R);return query(rs,mid+1,r,L,R); }#undef mid 
}seg;
char s[2];
inline int calc(int x,int y,bool op){return op?(x*y%10):(x+y)%10; 
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d%s",a+i,s+1);op[i]=(s[1]=='*');a[i+n] = a[i],op[i+n]=op[i];}for(int i=2;i<=2*n;i++)seg.change(1,1,n*2,i,calc(a[i-1],a[i],op[i]));  while(m--){scanf("%d",&opt);if(opt==1){int x,pos,y;scanf("%d%d%s",&pos,&x,s+1);pos++;y=(s[1]=='*'); a[pos]=x;a[pos+n]=x;op[pos]=y,op[pos+n]=y;if(pos>1)seg.change(1,1,n*2,pos,calc(a[pos-1],a[pos],op[pos]));seg.change(1,1,n*2,pos+1,calc(a[pos],a[pos+1],op[pos+1]));seg.change(1,1,n*2,pos+n,calc(a[pos-1+n],a[pos+n],op[pos+n]));if(pos < n)seg.change(1,1,n*2,pos+1+n,calc(a[pos+n],a[pos+1+n],op[pos+1+n]));}else {int pos;scanf("%d",&pos);pos++;if(!a[pos] && !seg.query(1,1,n*2,pos+1,n+pos-1).s){puts("0");continue;} if(!seg.query(1,1,2*n,2,pos-1).s && !seg.query(1,1,2*n,pos+1,2*n).s) {puts("-1");continue; }int l=1,r=n/2,res=1;while(l<=r){int mid=l+r>>1; if(seg.query(1,1,2*n,pos+mid-1,pos-mid+n+1).s)res=mid,l=mid+1;else r=mid-1;}printf("%d\n",res);}}return 0;}
http://www.hskmm.com/?act=detail&tid=26929

相关文章:

  • 2025免费好用的度数符号的神器
  • 折腾笔记[31]-在线转换吉卜力风格图片
  • 2025 风淋室厂家 TOP 品牌推荐排行榜,不锈钢风淋室,防爆风淋室,自动门风淋室,风淋门公司推荐
  • 计算机视觉的现状与未来挑战
  • #20232408 2025-2026-1《网络与系统攻防技术》实验一实验报告
  • reLeetCode 热题 100- 239. 滑动窗口最大值 队列 - MKT
  • 深入解析:三维坐标转换
  • ToDo-List EveryDay
  • 英语_阅读_Water and digital life_待读
  • Wails + Go + React跨平台RTSP播放器分享
  • 网络与系统攻防实验报告一 20232408李易骋1
  • [KaibaMath]1003 关于[x+y]≥[x]+[y]的证明
  • 【A】Strategy above the depths
  • 完整教程:Python 训练营打卡 Day 43
  • 快读快写
  • [KaibaMath]1002 关于[x+n]=[x]+n的证明
  • SpringBoot进阶教程(八十七)数据压缩
  • 塑料回收技术创新与可持续发展
  • 共享掩码:TFHE在打包消息上的自举技术
  • 详细介绍:[论文阅读] (38)基于大模型的威胁情报分析与知识图谱构建论文总结(读书笔记)
  • MATLAB安装 - -一叶知秋
  • 2025球墨铸铁管厂家 TOP 企业品牌推荐排行榜,市政球墨铸铁管、球墨铸铁管件、防腐球墨铸铁管、给水球墨铸铁管推荐这十家公司!
  • Say 题选记(10.5 - 10.11)
  • E. Rasta Thamaye Dilo
  • 微信机器人开发最新协议API
  • JDK的安装与使用 - XYX
  • Rust 的英文数字验证码识别系统实现
  • 微信机器人制作教程+源码
  • 基于 Rust 的英文数字验证码识别系统实现
  • 使用 Fortran 实现英文数字验证码识别系统