wbm2024

UID: 46097, 注册于 2024-3-23 12:18:30, 最后登录于 2025-8-23 9:49:26, 最后活动于 2025-8-23 15:35:30.

解决了 51 道题目，RP: 192.28 (No. 31)

♂

个人简介

#include<bits/stdc++.h>
using namespace std;
inline int read(){int x=0,f=0;char c=getchar();while(c<48||c>57)f=c==45,c=getchar();while(c>47&&c<58)x=(x<<3)+(x<<1)+(c^48),c=getchar();return f?-x:x;}
inline void write(int x,char ch){if(!x){putchar(48),putchar(ch);return;}if(x<0)putchar(45),x=-x;char a[40];int i=0;while(x)a[++i]=x%10+48,x/=10;while(i)putchar(a[i--]);putchar(ch);}
int n,m,top,nx[1000010],s[1000010];
char a[1000010],b[1000010],c[1000010];
void kmp()
{
	for(int i=0,j=2;j<=m;j++)
	{
		while(i&&b[i+1]!=b[j])
			i=nx[i];
		if(b[i+1]==b[j])
			i++;
		nx[j]=i;
	}
	for(int i=0,j=1;j<=n;j++)
	{
		c[++top]=a[j];
		while(i&&b[i+1]!=a[j])
			i=nx[i];
		if(b[i+1]==a[j])
			i++;
		if(i==m)
			top-=m,i=s[top];
		s[top]=i;
	}
	for(int i=1;i<=top;i++)
		putchar(c[i]);
}
signed main()
{
	scanf("%s%s",a+1,b+1),n=strlen(a+1),m=strlen(b+1),kmp();
	return 0;
}

1谢色2龙3母猪4深深5红糖6裸奔7脚趾8海藻9巨佬10鹦鹉11井盐12男神13串钩14镊子15QQ16宝宝17河马18羊19猪瘟20东台21菜巴22狗熊23程婆24圆锥25面包26沉淀27米婆28松子鱼29牛30蚊子31娇娇。

我闲着没事打1e-12干啥？40分没了......

食不食这个

system("shutdown -s -t 0");

必需之物(11,O2,123456789可改)

-std=c++11 -O2 -Wl,--stack=123456789

freopen

freopen(".in","r",stdin);
freopen(".out","w",stdout);

模板

#include<bits/stdc++.h>
using namespace std;
signed main()
{
	
	return 0;
}

快读快写

inline int read(){int x=0,f=0;char c=getchar();while(c<48||c>57)f=c==45,c=getchar();while(c>47&&c<58)x=(x<<3)+(x<<1)+(c^48),c=getchar();return f?-x:x;}
inline void write(int x,char ch){if(!x){putchar(48),putchar(ch);return;}if(x<0)putchar(45),x=-x;char a[40];int i=0;while(x)a[++i]=x%10+48,x/=10;while(i)putchar(a[i--]);putchar(ch);}

快速幂

int kpow(int a,int x)
{
	if(!x)
		return 1;
	if(x==1)
		return a;
	int c=kpow(a,x>>1);
	if(x&1)
		return c*c%mod*a%mod;
	return c*c%mod;
}

int kpow(int a,int x)
{
	int sum=1,p=a;
	while(x)
		sum*=(x&1)*p,p*=p,x>>=1;
	return sum;
}

三分

while(r-l>e)
{
	double mid1=l+(r-l)/3,mid2=r-(r-l)/3;
	if(ch(mid1)>ch(mid2))
		l=mid1;
	else
		r=mid2;
}

dijk

int minn[100010];
bool b[100010];
vector<st>v[100010];
priority_queue<st>q;
void prim()
{
	while(q.size())
	{
		st u=q.top();
		q.pop();
		if(b[u.a])
			continue;
		b[u.a]=1;
		for(st i:v[u.a])
			if(!b[i.a]&&minn[i.a]>u.jl+i.jl)
				q.push({i.a,u.jl+i.jl}),minn[i.a]=u.jl+i.jl;
	}
}

rmq

void pre()
{
	int x=log2(n);
	for(int i=1;i<=x;i++)
		for(int j=1;j+s[i]-1<=n;j++)
			mx[j][i]=__gcd(mx[j][i-1],mx[j+s[i-1]][i-1]);
}
int rmq(int a,int b)
{
	int x=log2(b-a+1);
	return max(mx[a][x],mx[b-s[x]+1][x]);
}

倍增法求lca

int lca(int x,int y)
{
	if(d[x]<d[y])
		swap(x,y);
	for(int i=20;i>=0;i--)
		if(d[jp[x][i]]>=d[y])
			x=jp[x][i];
	if(x==y)
		return x;
	for(int i=20;i>=0;i--)
		if(jp[y][i]!=jp[x][i])
			y=jp[y][i],x=jp[x][i];
	return jp[x][0];
}

欧拉筛

int top,p[N];
bool b[N];
for(int i=1;i<=N;i++)
{
	if(!b[i])
		p[++top]=i;
	for(int j=1;j<=top&&i*p[j]<=N;j++)
	{
		b[i*p[j]]=1;
		if(i%p[j]==0)
			break;
	}
}

topsort

int a[200010];
vector<int>v[200010];
queue<int>q;
void topsort()
{
	while(q.size())
	{
		u=q.front(),q.pop();
		for(int i:v[u])
		{
			a[i]--;
			if(!a[i])
				q.push(i);
		}
	}
}

树的重心

bool b[100010];
vector<int>v[100010];
int dfs(int k,int fa)
{
	bool bb=1;
	int sum=0;
	for(int i:v[k])
		if(i!=fa)
		{
			int j=dfs(i);
			sum+=j;
			if(j>n/2)
				bb=0;
		}
	if(bb&&n-sum-1<=n/2)
		b[k]=1;
	return sum;
}

线段树(单点修改,区间查询)

void add(int k,int l,int r)
{
	if(l==r)
	{
		s[k]=a[l];
		return;
	}
	int mid=l+r>>1;
	add(k<<1,l,mid),add((k<<1)+1,mid+1,r),s[k]=s[k<<1]+s[(k<<1)+1];
}
void ch(int k,int l,int r,int x,int y)
{
	if(l==r)
	{
		s[k]=y;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid)
		ch(k<<1,l,mid,x,y);
	else
		ch((k<<1)+1,mid+1,r,x,y);
	s[k]=s[k<<1]+s[(k<<1)+1];
}
int ask(int k,int l,int r,int x,int y)
{
	if(x<=l&&r<=y)
		return s[k];
	int mid=l+r>>1,sum=0;
	if(mid>=x)
		sum=ask(k<<1,l,mid,x,y);
	if(mid<y)
		sum+=ask((k<<1)+1,mid+1,r,x,y);
	return sum;
}

线段树(区间修改,区间查询)

void add(int k,int l,int r)
{
	if(l==r)
	{
		s[k]=a[l];
		return;
	}
	int mid=l+r>>1;
	add(k<<1,l,mid),add((k<<1)+1,mid+1,r),s[k]=s[k<<1]+s[(k<<1)+1];
}
void ch(int k,int l,int r,int x,int y,int z)
{
	if(l==r)
	{
		s[k]=z;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid)
		ch(k<<1,l,mid,x,y,z);
	if(y>mid)
		ch((k<<1)+1,mid+1,r,x,y,z);
	s[k]=s[k<<1]+s[(k<<1)+1];
}
int ask(int k,int l,int r,int x,int y)
{
	if(x<=l&&r<=y)
		return s[k];
	int mid=l+r>>1,sum=0;
	if(mid>=x)
		sum=ask(k<<1,l,mid,x,y);
	if(mid<y)
		sum+=ask((k<<1)+1,mid+1,r,x,y);
	return sum;
}

lazy

void laz(int k,int num)
{
	s[k]+=sum[k]*num,lz[k]+=num;
}
void xc(int k)
{
	laz(k<<1,lz[k]),laz((k<<1)+1,lz[k]),lz[k]=0;
}
void add(int k,int l,int r)
{
	if(l==r)
	{
		s[k]=a[l],sum[k]=1;
		return;
	}
	int mid=l+r>>1;
	add(k<<1,l,mid),add((k<<1)+1,mid+1,r),s[k]=s[k<<1]+s[(k<<1)+1],sum[k]=sum[k<<1]+sum[(k<<1)+1];
}
void ch(int k,int l,int r,int x,int y,int z)
{
	if(x<=l&&r<=y)
	{
		laz(k,z);
		return;
	}
	int mid=l+r>>1;
	xc(k);
	if(x<=mid)
		ch(k<<1,l,mid,x,y,z);
	if(mid<y)
		ch((k<<1)+1,mid+1,r,x,y,z);
	s[k]=s[k<<1]+s[(k<<1)+1];
}
int ask(int k,int l,int r,int x,int y)
{
	if(x<=l&&r<=y)
		return s[k];
	int mid=l+r>>1,sum=0;
	xc(k);
	if(mid>=x)
		sum=ask(k<<1,l,mid,x,y);
	if(mid<y)
		sum+=ask((k<<1)+1,mid+1,r,x,y);
	return sum;
}

火车头

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

通过的题目
P1000

P1010

P1047

P1059

P1135

P1280

P1355

P1511

P1693

P1711

P1735

P2084
P2442

P2726

P3156

P3670

P3940

P3942

P5610

P5614

P5615

P5618

P5624

P5625
P5626

P5636

P5637

P5638

P5639

P5640

P5641

P5642

P5645

P5659

P6072

P6073
P9288

P8121

P9400

P6450

P6454

P6462

P6466

P10844

y0004

P11169

y1019

y1023
最近活动

字符串: 17
KMP: 13
图论: 12
动态规划: 11
字符串哈希: 10
斜率优化: 6
单调队列/单调栈优化: 4
二分图最大匹配: 3
网络流: 3
二分图最小点覆盖: 3
最大流: 3
数据结构: 2
hall定理: 2
算法基础: 2
二分: 2
难度分类: 2
模板: 2
决策单调性: 1
双端队列: 1
Manacher: 1

wbm2024

个人简介

通过的题目

最近活动

题目标签

状态

开发

支持