首页 > 其他分享 >2024-4-4 分块补题

2024-4-4 分块补题

时间:2024-04-04 23:33:28浏览次数:25  
标签:maxx ch 分块 int 2024 maxn 补题 && getchar

P3203 [HNOI2010] 弹飞绵羊

记录每个位置跳出当前块所需要的步数和跳出的位置。
从后往前统计

#include<bits/stdc++.h> 
#define maxn 200100

using namespace std;

int n,m,len;
int pos[maxn],k[maxn];
int nxt[maxn],stp[maxn];
struct fk{int l,r;}a[maxn]; 

int read(){
	int s=0,w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
	return s*w;
}

void init(){
	len=sqrt(n);
	for(int i=0;i<n;i++) pos[i]=i/len;
	for(int i=0;i<=pos[n-1];i++){
		a[i].l=i*len;
		a[i].r=(i+1)*len-1;
	}
	a[pos[n-1]].r=n-1;
}

void work(int l,int r){
	for(int i=r;i>=l;i--){
        if(i+k[i]>a[pos[i]].r){
            nxt[i]=i+k[i];
            stp[i]=1;
        } 
		else{
            nxt[i]=nxt[i+k[i]];
            stp[i]=stp[i+k[i]]+1;
        }
    }
}

int main(){
	n=read();
	for(int i=0;i<n;i++) k[i]=read();
	init();work(0,n-1);m=read();
	for(int i=1,opt,x,y,ans,p;i<=m;i++){
		opt=read();x=read();
		if(opt==1){
			p=x,ans=0;
			while(p<n) ans+=stp[p],p=nxt[p];
			cout<<ans<<endl;
		}
		else{
			y=read();k[x]=y;
			work(a[pos[x]].l,a[pos[x]].r);
		}
	}
	return 0;
}

P4168 [Violet] 蒲公英

存下每种颜色出现的位置,处理块与块中的众数。
注意离散化。
计数时,中间的块直接记录,两边零散位置暴力扫。

#include<bits/stdc++.h>
#define maxn 100010
using namespace std;

int n,id,l,r,sum,res,m,las,o;
int a[maxn],num[maxn],pos[maxn];
int cnt[maxn],f[3010][3010],b[maxn];
vector<int>l1[maxn];
map<int,int>mp;

int read(){
	int s=0,w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
	return s*w;
}

int getans(int ll,int rr,int x){
	return upper_bound(l1[x].begin(),l1[x].end(),rr)-lower_bound(l1[x].begin(),l1[x].end(),ll);
}

void init(int x){
	memset(cnt,0,sizeof(cnt));
	int maxx=0,num1=0;
	for(int i=(x-1)*m+1;i<=n;i++){
		cnt[a[i]]++;
		if(cnt[a[i]]>maxx||(cnt[a[i]]==maxx&&a[i]<num1))
			maxx=cnt[a[i]],num1=a[i]; 
		f[x][pos[i]]=num1;
	}
}

int ask(int l1,int r1){
	int maxx=0,num1=0;
	if(pos[l1]+1<pos[r1])
		maxx=getans(l1,r1,f[pos[l1]+1][pos[r1]-1]),num1=f[pos[l1]+1][pos[r1]-1]; 
	for(int i=l1;i<=min(r1,pos[l1]*m);i++) {
		res=getans(l1,r1,a[i]);
		if(res>maxx||(res==maxx&&a[i]<num1))
			maxx=res,num1=a[i];
	}
	if(pos[l1]!=pos[r1]){
		for(int i=(pos[r1]-1)*m+1;i<=r1;i++){
			res=getans(l1,r1,a[i]);
			if(res>maxx||(res==maxx&&a[i]<num1))
				maxx=res,num1=a[i];
		}
	}
	return num[num1];
}
int main(){
	n=read();o=read();
	for(int i=1;i<=n;i++) a[i]=read(),b[i]=a[i];
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++) if(!mp[b[i]])
		id++,mp[b[i]]=id,num[id]=b[i];
	for(int i=1;i<=n;i++)
		a[i]=mp[a[i]],l1[a[i]].push_back(i); 
	for(int i=1;i<=id;i++) l1[i].push_back(n+1);
	m=sqrt(n);
	for(int i=1;i<=n;i++) pos[i]=(i-1)/m+1;
	sum=pos[n];
	for(int i=1;i<=sum;i++) init(i);
	for(int i=1;i<=o;i++){
		l=read();r=read();
		l=(l+las-1)%n+1,r=(r+las-1)%n+1;
		if(l>r) swap(l,r);las=ask(l,r);
		cout<<las<<endl;
	}
	return 0;
}

标签:maxx,ch,分块,int,2024,maxn,补题,&&,getchar
From: https://www.cnblogs.com/KnightL/p/18115332

相关文章

  • 2024年4月4号java学习
    继承减少编写重复的代码,提高代码的复用性,使用extends关键字用来表示继承一个类如果类和类有相同的特性,并且一个类是另一个类的一种那么就可以使用继承java中只支持单继承,但有多层继承所有的类都间接或者直接继承Object类子类能够继承父类的东西虚方法表中包含:非私有方法,非f......
  • 20240404
    T1洛谷P3436PRO-ProfessorSzu首先缩点。然后从所有没有入度的强连通分量开始dfs,进行dp,数一下每个点到终点有多少路径。要注意的是当且仅当一个点能够到达终点时才能够用来更新其他点的dp值。代码#include<iostream>#defineintlonglongusingnamespacestd;in......
  • 2024.4 做题记录
    299.CF1534ELostArray难崩。题意转化为每次翻转\(m\)个\(01\)序列的元素,要把全\(0\)翻成全\(1\)。不想分讨。考虑直接最短路求最小步数,转移就枚举选多少个原本已经有的数。交互就记录方案就行了。300.P9537[YsOI2023]CF1764B很棒的题。考察终态,可以发现最后输......
  • 小美的蛋糕切割(美团2024届秋招笔试第一场编程真题)
    题面核心思想前缀和(不过是以一整行或一整列的维度)(滑动窗口应该也可以)需要注意的是可以横着切也可以竖着切代码importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){finallongMOD=(long)(1e9+7);Scannerscanne......
  • 2024/4/4 分块补题
    2024/4/4分块补题P3203[HNOI2010]弹飞绵羊分块跳跳跳,核心是每次跳出当前块,用\(to[i]\)表示跳到的位置。#include<bits/stdc++.h>usingnamespacestd;#defineldlongdoubletemplate<typenameT>inlineTread(){Tx=0;charch=getchar();boolfl=false;......
  • 2024-04-04
    2024-04-04gcd上午模拟赛T1考场上写了\(O(n^2)\)的暴力,但是有的时候跑不满,\(10^5\)的大数据跑的飞快(100ms)考完没多久就想出来正解了观察到值域\(V\)只有\(100\),考虑把他放到时间复杂度里面枚举最大公约数\(g\)只有一段区间内所有的数都是\(g\)的倍数的时候才......
  • 2024年华为OD机试题-火星文计算
    题目描述:已知火星人使用的运算符为#、$,其与地球人的等价公式如下:x#y=2x+3y+4x$y=3*x+y+2其中x、y是无符号整数地球人公式按C语言规则计算火星人公式中,$的优先级高于#,相同的运算符,按从左到右的顺序计算现有一段火星人的字符串报文,请你来翻译并计算结果。输入描述:火......
  • 2024年华为OD机试题-提取字符串中的最长数学表达式并计算
    提取字符串中的最长数学表达式并计算题目描述提取字符串中的最长合法简单数学表达式,字符串长度最长的,并计算表达式的值。如果没有,则返回0。简单数学表达式只能包含以下内容0-9数字,符号+-*说明1、所有数字,计算结果都不超过long2、如果有多个长度一样的,请返回第一个表达式......
  • 红明谷初赛2024-web-wp
    这次队里我们仨发挥中规中矩,排14名。只能说最后unauth那道会错了意,然后卡住了,后面才发现是原题秒出的那种.....确实是我傻逼了....ezphp可以用endoafr报错拿到文件内容,然后就是一个匿名类的读取。<?phphighlight_file(__FILE__);//flag.phpif(isset($_POST['f'])......
  • 人是否应该以貌取人 英语作文 四级备考 20240404
    题目:Doyouagreeordisagreewiththefollowingstatement?Oneshouldneverjudgeapersonbyexternalappearances.Usespecificreasonsanddetailstosupportyouropinion.(150words)作文:Ifirmlybelievethatoneshouldneverjudgeapersonsolelybyt......