LHRG 李的博客

LHRG's blog

发表于 更新于 分类于 ， 本文字数： 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\)

阅读全文 »

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

\(\qquad\!\!\)除了基础动态规划中的三种动态规划以外，还有一些比较难的动态规划：

阅读全文 »

发表于 更新于 分类于 ， 本文字数： 2.3k 阅读时长 ≈ 8 分钟
  • 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
#include<bits/stdc++.h>
#define in inline
#define re register
const int N=N;
using namespace std;
int n;
int a[N],f[N];
int ans; 
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 ;
}
int main()
{
	n=qread();
	for(re int i=1;i<=n;i++)
	{
		a[i]=qread();
	}
	for(re int i=1;i<=n;i++)
	{
		for(re int j=0;j<i;j++)
		{
			if(a[i]>a[j])
			{
				f[i]=max(f[i],f[j]+1);
			}
		}
		ans=max(ans,f[i]);
	}
	qwrite(ans);
	putchar('\n');
	return 0;
}
阅读全文 »
0%