HDU 4125 Moles 段树+KMP

HDU 4125 Moles 段树+KMP

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

意甲冠军:

特定n,

下面是一个1-n该装置。

下面的二进制字符串。

按给定的建立二叉树安排。

然后遍历树(根->左子树->根->右子树->根)

当遍历节点 如果右值为奇数入栈一个1,若为偶数入栈一个0

得到一个母串。

问母串中出现了几次子串。

思路:

先是建树得到母串。然后求子串个数就是裸的KMP。

建树就是找个规律,然后用线段树维护一下输入的排列

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
template <class T>
inline bool rd(T &ret) {
	char c; int sgn;
	if(c=getchar(),c==EOF) return 0;
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}
template <class T>
inline void pt(T x) {
    if (x <0) {
        putchar('-');
        x = -x;
    }
    if(x>9) pt(x/10);
    putchar(x%10+'0');
}
//
const int N = 600000+5;
const int M = 70000+5;
int mi[N<<2], pos[N];
inline void up(int& fa, int& ls, int& rs) {
	if (ls>rs)
		fa = rs;
	else
		fa = ls;
}
void build(int l, int r, int rt) {
	if (l == r) {
		mi[rt] = pos[l];
	} else {
		int mid = (l+r)>>1;
		build(lson);
		build(rson);
		up(mi[rt], mi[rt<<1], mi[rt<<1|1]);
	}
}
int query(int L, int R, int l, int r, int rt) {
	if (L<= l && r<=R) {
		return mi[rt];
	} else {
		int mid = (l+r)>>1;
		if (L>mid)
			return query(L, R, rson);
		else if (R<=mid)
			return query(L, R, lson);
		else
			return min(query(L, mid, lson), query(mid+1, R, rson));
	}
}
void update(int p, int v, int l, int r, int rt) {
	if (l == r) {
		mi[rt] = v;
	} else {
		int mid = (l+r)>>1;
		if (p <= mid)
			update(p, v, lson);
		else
			update(p, v, rson);
		up(mi[rt], mi[rt<<1], mi[rt<<1|1]);
	}
}


int T = 0, n, a[N], L[N], R[N];
char s[M], ch[N*3];
int nex[M], top;
void dfs(int u, int l, int r) {
	update(u, n+1, 1, n, 1);
	int v = query(l, u, 1, n, 1);
	if (v != n+1) {
		L[u] = a[v];
		dfs(a[v], l, u);
	}
	v = query(u, r, 1, n, 1);
	if (v != n+1) {
		R[u] = a[v];
		dfs(a[v], u, r);
	}
}
void f(int u) {
	char c;
	if (u&1)
		c = '1';
	else
		c = '0';
	ch[top++] = c;
	if (L[u] != -1) {
		f(L[u]);
		ch[top++] = c;
	}
	if (R[u] != -1) {
		f(R[u]);
		ch[top++] = c;
	}
}
void work() {
	int v, len, idx, ans = 0;
	rd(n);
	for (int i = 1; i <= n; ++i) {
		rd(a[i]);
		pos[a[i]] = i;
	}
	build(1, n, 1);
	memset(L, -1, sizeof L);
	memset(R, -1, sizeof R);
	dfs(a[1], 1, n);
	//
	scanf("%s", s);
	len = strlen(s);
	nex[0] = nex[1] = 0;
	for (int i = 1; i < len; ++i) {
		int j = nex[i];
		while (j && s[j] != s[i])
			j = nex[j];
		if (s[i] == s[j])
			nex[i+1] = j+1;
		else
			nex[i+1] = 0;
	}
	//
	top = 0;
	f(a[1]);
	idx = 0;
	for (int i = 0; i < top; ++i) {
		while (idx && s[idx] != ch[i])
			idx = nex[idx];
		if (s[idx] == ch[i])
			++ idx;
		if (idx == len) {
			++ ans;
			idx = nex[idx];
		}
	}
	printf("Case #%d: %d\n", ++T, ans);
}
int main() {
	int cas;
	scanf("%d", &cas);
	while (cas-->0)
		work();
	return 0;
}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117292.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 580显卡驱动_3分钟成为矿卡鉴别大师:通用AMD二手显卡检验、测试流程送上「建议收藏」

    580显卡驱动_3分钟成为矿卡鉴别大师:通用AMD二手显卡检验、测试流程送上「建议收藏」二手矿卡坑太深,手握秘籍不求人AMD自2016年中发布Polaris系列GPU至今,长达四年的时间里,一代又一代的RX470、480、570、580等显示卡进入暗无天日的区块链矿场,挥洒着血泪和青春。在经历一次次矿难之后,貌似廉价的二手矿卡不断涌现,花2~300块钱入手一张鲁大师16~7万分的游戏显卡似乎成为所有“穷游族”的首选。Polaris10发售伊始,挑翻GTX980的口号就喊到震天响那么…

  • H2数据库入门_H2数据库越来越大

    H2数据库入门_H2数据库越来越大一、H2简介  1、H2是一个用Java开发的嵌入式数据库,它本身只是一个类库,可以直接嵌入到应用项目中。  H2最大的用途在于可以同应用程序打包在一起发布,这样可以非常方便地存储少量结构化数据。  它的另一个用途是用于单元测试。启动速度快,而且可以关闭持久化功能,每一个用例执行完随即还原到初始状态。  H2的第三个用处是作为缓存,作为NoSQL的一个补充。当某些场景下数据模型必须为关系型…

    2022年10月12日
  • java 泛型深入之Set有用工具 各种集合泛型深入使用演示样例,匿名内部类、内部类应用于泛型探讨

    java 泛型深入之Set有用工具 各种集合泛型深入使用演示样例,匿名内部类、内部类应用于泛型探讨

  • 简述android触屏事件的处理_移动端touch事件有哪些

    简述android触屏事件的处理_移动端touch事件有哪些本文介绍了Android系统中触屏事件的相关知识,包括触屏事件的产生,分类,触屏事件序列,以及触屏事件在代码中的表示方式。了解这些内容,是理解Android触屏事件的分发,拦截和处理的基础。

  • 秒杀多线程第六篇 经典线程同步 事件Event

    秒杀多线程第六篇 经典线程同步 事件Event阅读本篇之前推荐阅读以下姊妹篇:《秒杀多线程第四篇一个经典的多线程同步问题》《秒杀多线程第五篇经典线程同步关键段CS》 上一篇中使用关键段来解决经典的多线程同步互斥问题,由于关键段的“线程所有权”特性所以关键段只能用于线程的互斥而不能用于同步。本篇介绍用事件Event来尝试解决这个线程同步问题。首先介绍下如何使用事件。事件Event实际上是个内核对象,它的使用非常方便。下面列出一些常用的函数。

  • MATLAB GUI设计之弹出式菜单的使用

    MATLAB GUI设计之弹出式菜单的使用弹出式菜单在MATLABGUI设计中常常出现。比如串口助手、绘制图形等经常见到弹出式菜单如下图所示:使用方法:一、准备工作1、从MATLABGUIDE中拖出一个弹出式菜单2、双击这个弹出式菜单,出现检查器:将注意力放在途中红线位置处,点击string处的图标将其中的内容修改为你想要显示的内容:tag处的内容修改为自己想管这个弹出式菜单的名字。这里就按照原来

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号