首页 > 其他分享 >复健复健!

复健复健!

时间:2022-11-16 17:37:01浏览次数:59  
标签:复健 ch ok int maxn now define

目录

复健复健! 终于来到了我的回合!

1 dp(打牌

1.1 斜率优化

P3195 [HNOI2008]玩具装箱

\[f_n=f_m+(n-m+s_n-s_m-L)^2\\ f_n=f_m+(T_n-T_m-L)^2\\ f_n-T_n^2-L^2+2LT_n+2T_nT_m=f_m+T_m^2+2LT_m\\ \]

点为\((T_m,f_m+T_m^2+2LT_m)\),

#include<bits/stdc++.h>
#define For(i, a, b) for(int i = (a), en = (b); i <= en; ++i)
#define Rof(i, a, b) for(int i = (a), en = (b); i >= en; --i)
#define Tra(u, i) for(int i = hd[u]; ~i; i = e[i].net)
#define cst const
#define LL long long
#define DD double
#define LD long double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
#define eps 1e-12
#define maxn 50000
using namespace std;

int n, L, a[maxn + 5]; 
LL sum[maxn + 5], f[maxn + 5], t[maxn + 5];

template <class T>
void read(T &x){
	char ch;
	bool ok;
	for(ok = 0, ch = getchar(); !isdigit(ch); ch = getchar()) if(ch == '-') ok = 1;
	for(x = 0; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
	if(ok) x = -x;
}

LL get_y(int x){
	return f[x] + t[x] * t[x] + 2ll * L * t[x];
}

double get_k(int x, int y){
	return (double)(get_y(x) - get_y(y)) / (t[x] - t[y]);
}


int st[maxn + 5], l = 1, r = 1;
int main(){
	//freopen("in", "r", stdin);
	read(n); read(L); L++;
	For(i, 1, n) read(a[i]), sum[i] = sum[i - 1] + a[i], t[i] = sum[i] + i;
	For(i, 1, n){
		while(l < r && get_k(st[l], st[l + 1]) < 2ll * t[i]) l++;
		f[i] = f[st[l]] + (t[i] - t[st[l]] - L) * (t[i] - t[st[l]] - L);
		while(l < r && get_k(st[r - 1], st[r]) > get_k(st[r], i)) r--;
		st[++r] = i;
	}
	printf("%lld\n", f[n]);
	return 0;
}


2 字符串

2.1 kmp(看猫片)

P3375 【模板】KMP字符串匹配

#include<bits/stdc++.h>
#define For(i, a, b) for(int i = (a), en = (b); i <= en; ++i)
#define Rof(i, a, b) for(int i = (a), en = (b); i >= en; --i)
#define Tra(u, i) for(int i = hd[u]; ~i; i = e[i].net)
#define cst const
#define LL long long
#define DD double
#define LD long double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
#define eps 1e-12
#define maxn 1000000
using namespace std;

int n, m, to[maxn + 5];
char s1[maxn + 5], s2[maxn + 5];

template <class T>
void read(T &x){
	char ch;
	bool ok;
	for(ok = 0, ch = getchar(); !isdigit(ch); ch = getchar()) if(ch == '-') ok = 1;
	for(x = 0; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
	if(ok) x = -x;
}

int main(){
	//freopen("in", "r", stdin);
	scanf("%s %s", s1 + 1, s2 + 1);
	n = strlen(s1 + 1); m = strlen(s2 + 1);
	int now = 0;
	For(i, 2, m){
		while(now && s2[now + 1] != s2[i]) now = to[now];
		if(s2[now + 1] == s2[i]) to[i] = ++now;
	}
	now = 0;
	For(i, 1, n){
		while(now && s2[now + 1] != s1[i]) now = to[now];
		if(s2[now + 1] == s1[i]) now++;
		if(now == m) printf("%d\n", i - m + 1);
	}
	For(i, 1, m) printf("%d ", to[i]);
	return 0;
}


2.2 ac自动机(树上看猫片

P3808 【模板】AC 自动机(简单版)

#include<bits/stdc++.h>
#define For(i, a, b) for(int i = (a), en = (b); i <= en; ++i)
#define Rof(i, a, b) for(int i = (a), en = (b); i >= en; --i)
#define Tra(u, i) for(int i = hd[u]; ~i; i = e[i].net)
#define cst const
#define LL long long
#define DD double
#define LD long double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
#define eps 1e-12
#define maxn 1000000
using namespace std;

int n, tot = 0, pos[maxn + 5], as = 0;
char s[maxn + 5];
struct Node{
	int ch[30], to, ok;
} tr[maxn + 5];

template <class T>
void read(T &x){
	char ch;
	bool ok;
	for(ok = 0, ch = getchar(); !isdigit(ch); ch = getchar()) if(ch == '-') ok = 1;
	for(x = 0; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
	if(ok) x = -x;
}

int q[maxn + 5], l = 1, r = 0;
void sol(){
	For(i, 0, 25) if(tr[0].ch[i]) q[++r] = tr[0].ch[i];
	while(l <= r){
		int now = q[l++];
		For(i, 0, 25){
			int to = tr[now].ch[i];
			if(to) tr[to].to = tr[tr[now].to].ch[i], q[++r] = to;
			else tr[now].ch[i] = tr[tr[now].to].ch[i];
		}
	}
}

int main(){
//	freopen("in", "r", stdin);
	read(n);
	For(i, 1, n){
		scanf("%s", s + 1);
		int len = strlen(s + 1), now = 0;
		For(j, 1, len){
			int x = s[j] - 'a';
			if(!tr[now].ch[x]) tr[now].ch[x] = ++tot;
			now = tr[now].ch[x];
		}
		pos[i] = now;
	}
	sol();
	scanf("%s", s + 1);
	int len = strlen(s + 1), now = 0;
	For(i, 1, len){
		now = tr[now].ch[s[i] - 'a'];
		tr[now].ok = 1;
	}
	Rof(i, r, 1) tr[tr[q[i]].to].ok |= tr[q[i]].ok;
	For(i, 1, n) as += tr[pos[i]].ok;
	printf("%d\n", as);
	return 0;
}


标签:复健,ch,ok,int,maxn,now,define
From: https://www.cnblogs.com/lprdsb/p/16896664.html

相关文章

  • 【Java复健指南13】OOP高级04【告一段落】-四大内部类
    四大内部类一个类的内部又完整的嵌套了另一个类结构。classOuter{//外部类classlnner{//内部类}}classOther{//外部其他类}被嵌套的类称为内......
  • 【Java复健指南12】OOP高级03-抽象类与接口
    抽象类引出问题:​ 父类方法有时候具有不确定性小结:当父类的某些方法,需要声明,但是又不确定如何实现时,可以将其声明为抽象方法,那么这个类就是抽象类例子:publicclas......
  • 【Java复健指南10】OOP高级01-类变量、类方法和main
    类变量什么是类变量类变量也叫静态变量/静态属性,是该类的所有对象共享的变量,任何一个该类的对象去访问它时,取到的都是相同的值,同样任何一个该类的对象去修改它时,修改......
  • 【Java复健指南09】项目练习全解--房屋出租系统
    一个基于文本界面的综合练习,主要用于串联和回忆知识点,比较简单各个界面的设计样式主菜单=============房屋出租系统菜单============ 1新增房源 2查找房......
  • 【Java复健指南08】OOP中级03【完结】-Object类和一些练习
    前情回顾:https://www.cnblogs.com/DAYceng/category/2227185.htmlObject类equals方法"=="与equals的区别"=="是一个比较运算符双等号既可以判断基本类型,又可以判断引......
  • 【Java复健指南07】OOP中级02-重写与多态思想
    前情提要:https://www.cnblogs.com/DAYceng/category/2227185.html重写注意事项和使用细节方法重写也叫方法覆法,需要满足下面的条件1.子类的方法的参数,方法名称,要和父......
  • 【Java复健指南06】OOP中级01-封装、继承、super
    注:从OOP中级部分开始使用IDEA构建代码封装封装的实现步骤1)将属性进行私有化private【不能直接修改属性】2)提供一个公共的set方法,用于对属性判断并赋值publicvoids......
  • 【Java复健指南03】递归思想
    【递归】递归重要规则1.执行一个方法时,就创建一个新的受保护的独立空间(栈空间)方法的局部变量是独立的,不会相互影响,比如n变量如果方法中使用的是引用类型变量(比......
  • 【Java复健指南01】简介与数组
    写在最前学习Java已经是很久之前的事情了,因为技术栈的转变,很久没有使用Java正经地开发过项目。对于该语言的理解也是停留在表面,因此萌生了重新学习的念头。一方面是为刷......
  • 复健笔记
    重学指针双向异或链表利用异或的特点,在双向链表的基础上进行改进,每个节点不再存储左节点和右节点的地址,改为存储左节点和右节点的地址的异或值。这样可以减少一半的空间......