LHRG 李的博客

题解 U534156 【赛艇表演】

发表于 2020-11-28 更新于 2025-02-11 分类于 OI ，题解本文字数： 1.2k 阅读时长 ≈ 4 分钟

题目链接：赛艇表演。

关于题目：作为 T3，小小的思维题。

应用算法：图论，割点，图的建立，最短路。

阅读全文 »

组合数学

发表于 2020-10-29 更新于 2025-02-20 分类于 OI ，模板本文字数： 982 阅读时长 ≈ 4 分钟

\(\qquad\!\!\)一些在求组合数的时候会很有用的东西：

1、乘法逆元:

①、费马小定理：

\(\qquad\!\!\)当 \(p\) 为素数，\(a\) 为一个正整数且 \(a\) 与 \(p\) 互质，则 \(a^{-1}\equiv a^{p-2} \pmod{p}\)

\(\qquad\!\!\)例题：

\(\qquad\!\!\)给定 \(a\)、\(p\)，保证 \(p\) 为素数并且 \(a\) 与 \(p\) 互质，求出在模 \(p\) 意义下的 \(a\) 的逆元。

#include<bits/stdc++.h>
#define in inline
#define re register
using namespace std;
int a,p;
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            y=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
    if(x<0)
    {
        putchar('-');
        qwrite(-x);
    }
    else
    {
        if(x>9)
        {
            qwrite(x/10);
        }
        putchar(x%10+'0');
    }
    return ;
}
in int qpow(re int x,re int y)
{
    int res=1;
    while(y)
    {
        if(y&1)
        {
            res=(res*x)%p;
        }
        x=(x*x)%p;
        y>>=1;
    }
    return res%p;
}
int main()
{
    a=qread();
    p=qread();
    qwrite(qpow(a,p-2));
    putchar('\n');
    return 0;
}

阅读全文 »

博弈论

发表于 2020-10-27 更新于 2025-02-20 本文字数： 826 阅读时长 ≈ 3 分钟

\(\qquad\!\!\)博弈论主要研究公式化了的激励结构间的相互作用，是研究具有斗争或竞争性质现象的数学理论和方法。博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。生物学家使用博弈理论来理解和预测进化论的某些结果。

\(\qquad\!\!\)在此总结四种常见的博弈结论：

阅读全文 »

筛法

发表于 2020-10-24 更新于 2025-02-20 分类于 OI ，模板本文字数： 1.1k 阅读时长 ≈ 4 分钟

\(\qquad\!\!\)整理一些 OI 中常用的筛法：

1、埃拉托斯特尼筛法：

\(\qquad\!\!\)例题：

\(\qquad\!\!\)给定一个数 \(n\) 判断这个数是不是质数：

#include<bits/stdc++.h>
#define in inline
#define re register
const int N=100;
const double eps=1e-6;
using namespace std;
int n;
bool prime[N]; 
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
		{
			y=-1;
		}
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
	if(x<0)
	{
		putchar('-');
		qwrite(-x);
	}
	else
	{
		if(x>9)
		{
			qwrite(x/10);
		}
		putchar(x%10+'0');
	}
	return ;
}
in void ass(re int x)
{
	memset(prime,1,sizeof(prime));
	prime[0]=0;
	prime[1]=0;
	int t=sqrt(x)+eps;
	for(re int i=2;i<=t;i++)
	{
		if(prime[i])
		{
			for(re int j=(i<<1);j<=x;j+=i)
			{
				prime[j]=0;
			}
		}
	}
}
int main()
{
	n=qread();
	ass(n);
	qwrite(prime[n]);
	putchar('\n');
	return 0;
}

阅读全文 »

线性代数

发表于 2020-10-19 更新于 2025-02-19 分类于 OI ，模板本文字数： 166 阅读时长 ≈ 1 分钟

\(\qquad\!\!\)线性代数是数学的一个分支，它的研究对象是向量，向量空间（或称线性空间），线性变换和有限维的线性方程组。向量空间是现代数学的一个重要课题；因而，线性代数被广泛地应用于抽象代数和泛函分析中；通过解析几何，线性代数得以被具体表示。线性代数的理论已被泛化为算子理论。由于科学研究中的非线性模型通常可以被近似为线性模型，使得线性代数被广泛地应用于自然科学和社会科学中。

题解 U534159 【降价处理】

发表于 2020-10-19 更新于 2025-02-11 分类于 OI ，题解本文字数： 500 阅读时长 ≈ 2 分钟

题目链接：降价处理

关于题目：作为 T2，一道数学题。

应用算法：最基础的数论。

阅读全文 »

数论

发表于 2020-09-22 更新于 2025-02-20 分类于 OI ，模板本文字数： 551 阅读时长 ≈ 2 分钟

\(\qquad\!\!\)数论是纯粹数学的分支之一，主要研究整数的性质。

1、欧几里得（GCD）：

\(\qquad\!\!\)例题：

\(\qquad\!\!\)给出两个正整数，求出两个数的 \(\gcd\)：

#include<bits/stdc++.h>
#define in inline
#define re register
using namespace std;
int a,b; 
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
		{
			y=-1;
		}
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
	if(x<0)
	{
		putchar('-');
		qwrite(-x);
	}
	else
	{
		if(x>9)
		{
			qwrite(x/10);
		}
		putchar(x%10+'0');
	}
	return ;
}
in gcd(re int x,re int y)
{
	return y?gcd(y,x%y):x;
}
int main()
{
	a=qread();
	b=qread();
	qwrite(gcd(a,b));
	putchar('\n');
	return 0;
}

阅读全文 »

数学

发表于 2020-09-22 更新于 2025-02-20 分类于 OI ，模板本文字数： 361 阅读时长 ≈ 1 分钟

\(\qquad\!\!\)大概是最近需要的 OI 中有关纯数学的部分算法，估计会鸽很多。

1、快速幂：

\(\qquad\!\!\)例题：

\(\qquad\!\!\)快速幂||取余运算：

#include<bits/stdc++.h>
#define in inline
#define re register
#define int long long
using namespace std;
int a,b,p;
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
		{
			y=-1;
		}
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
	if(x<0)
	{
		putchar('-');
		qwrite(-x);
	}
	else
	{
		if(x>9)
		{
			qwrite(x/10);
		}
		putchar(x%10+'0');
	}
	return ;
}
in int qpow(re int x,re int y)
{
	int res=1;
	while(y)
	{
		if(y&1)
		{
			res=(res*x)%p;
		}
		x=(x*x)%p;
		y>>=1;
	}
	return res%p;
}
signed main()
{
	a=qread();
	b=qread();
	p=qread();
	qwrite(a);
	printf("^");
	qwrite(b);
	printf(" mod ");
	qwrite(p);
	printf("=");
	qwrite(qpow(a,b));
	putchar('\n');
	return 0;
}

阅读全文 »

字符串

发表于 2020-09-15 更新于 2025-02-20 分类于 OI ，模板本文字数： 1.1k 阅读时长 ≈ 4 分钟

\(\qquad\!\!\)字符串算法……暂时就先这五种吧……

1、字符串哈希：

\(\qquad\!\!\)例题：

\(\qquad\!\!\)P3370 【模板】字符串哈希

#include<bits/stdc++.h>
#define in inline
#define re register
#define int long long
using namespace std;
const int N=10010;
const int M=1510;
int ba=4215,n,l,ans;
char a[N][M];
struct e
{
	int m1,m2;
};
e z[N];
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
		{
			y=-1;
		}
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
	if(x<0)
	{
		putchar('-');
		qwrite(-x);
	}
	else
	{
		if(x>9)
		{
			qwrite(x/10);
		}
		putchar(x%10+'0');
	}
	return ;
}
in int hash(char b[],int m)
{
	int x=0;
	for(re int j=1;j<=l;j++)
	{
		x+=(ba*x+b[j])%m;
	}
	return x;
}
in bool comp(e x,e y)
{
	if(x.m1>y.m1)
	{
		return 1;
	}
	return 0;
}
signed main()
{
	n=qread();
	for(re int i=1;i<=n;i++)
	{
		scanf("%s",a[i]+1);
		l=strlen(a[i]+1);
		z[i].m1=hash(a[i]+1,1e9+7);
		z[i].m2=hash(a[i]+1,1e9+9);
	}
	sort(z+1,z+n+1,comp);
	ans=n;
	for(re int i=1;i<=n;i++)
	{
		if(z[i].m1==z[i+1].m1&&z[i].m2==z[i].m2)
		{
			ans--;
		}
	}
	qwrite(ans);
	putchar('\n');
	return 0;
}

阅读全文 »

题解 P1453 【城市环路】

发表于 2020-08-12 更新于 2025-02-18 分类于 OI ，题解本文字数： 1.9k 阅读时长 ≈ 7 分钟

题目链接：城市环路。

关于题目：一道比较显然的 基环树 上的 dp 题。

应用算法：树形 dp \(+\) 环形 dp。

阅读全文 »