LHRG 李的博客

LHRG's blog

发表于 更新于 本文字数： 826 阅读时长 ≈ 3 分钟

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

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

阅读全文 »

发表于 更新于 分类于 ， 本文字数： 1.1k 阅读时长 ≈ 4 分钟

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

  • 1、埃拉托斯特尼筛法：

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#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;
}
阅读全文 »

发表于 更新于 分类于 ， 本文字数： 166 阅读时长 ≈ 1 分钟

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

发表于 更新于 分类于 ， 本文字数： 551 阅读时长 ≈ 2 分钟

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

  • 1、欧几里得（GCD）：

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#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;
}
阅读全文 »

发表于 更新于 分类于 ， 本文字数： 361 阅读时长 ≈ 1 分钟

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

  • 1、快速幂：

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#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;
}
阅读全文 »

发表于 更新于 分类于 ， 本文字数： 1.1k 阅读时长 ≈ 4 分钟

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

  • 1、字符串哈希：

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#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;
}
阅读全文 »

发表于 更新于 分类于 ， 本文字数： 2.6k 阅读时长 ≈ 9 分钟
  • 1、基础树形dp：

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

\(\qquad\!\!\)给一棵树以及根的编号，求出每个点的深度和子树大小：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<bits/stdc++.h>
#define in inline
#define re register
const int N=N;
using namespace std;
int n,r;
int cnt,head[N];
struct edge
{
	int to,nxt;
}; 
edge e[N<<1];
int d[N],s[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 mr(re int u,re int v)
{
	e[++cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
	return ;
}
in void dfs(re int u,re int fa)
{
	s[u]=1;
	for(re int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa)
		{
			continue;
		}
		d[v]=d[u]+1;
		dfs(v,u);
		s[u]+=s[v];
	}
	return ;
}
int main()
{
	n=qread();
	r=qread();
	for(re int i=1;i<n;i++)
	{
		int u=qread();
		int v=qread();
		mr(u,v);
		mr(v,u);
	}
	d[r]=1;
	dfs(r,0);
	for(re int i=1;i<=n;i++)
	{
		qwrite(d[i]);
		putchar(' ');
	}
	putchar('\n');
	for(re int i=1;i<=n;i++)
	{
		qwrite(s[i]);
		putchar(' ');
	}
	putchar('\n');
	return 0;
}
阅读全文 »

发表于 更新于 分类于 ， 本文字数： 4.3k 阅读时长 ≈ 16 分钟

战略威慑(智旭生加强版)伪题解

\(\qquad\!\!\)一句话题意：在 \(O(N)\) 的时间复杂度内求出一棵树删去一条边以后分裂成的两颗新树的直径的乘积的最大值。

\(\qquad\!\!\)相信暴力大家都会，下面就直接说一种比较麻烦的正解吧：

应用算法：换根\(dp\)

阅读全文 »
0%