LHRG 李的博客

LHRG's blog

发表于 更新于 分类于 ， 本文字数： 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;
}
阅读全文 »

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

\(\qquad\!\!\)在解决 dp 问题时，主要要从两点思考：

  • 1、状态：

\(\qquad\!\!\)通常来讲，状态的设立因题而异，大多数与答案的意义相同（dp数组 中的某个值即为答案）或者与答案具有直接联系（比如再经过某种统计即可得到答案）。

\(\qquad\!\!\)对于很难一眼看出状态（比如答案无法转移）的题，我们就要利用 dp的本质：“把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解。”和 dp 最重要的一个性质：“无后效性”去推理。

\(\qquad\!\!\)根据无后效性，我们可以假设在这个阶段之前的阶段（注意，这个“之前”表示的是 dp转移 上的之前，可能是空间上的之前、数位上的之前、拓扑序上的之前……）都已经进行了最优化的决策。根据 dp的本质，如果之前的阶段的最优决策映射出的一种“结果”能以 某种方式 转移到此阶段的这种“结果”，且此时的这种“结果”也恰好为此时的最优化决策的这种映射，那么这种“结果”即为 dp的状态。

  • 2、转移方程：

\(\qquad\!\!\)通常来讲，转移方程的确立也是因题而异的，不过在得出了正确的状态之后，转移方程的确立方式一般比较显然。

\(\qquad\!\!\)前文中加粗的的“某种方式”，即可理解为一种状态到状态的转移方式。我们在将其具体化以后，即可得到对于相邻状态的转移方程。同时，对于很多题目的转移方程可以利用数学的计算或者数据结构的辅助得以在复杂度上得以化简，即为 dp的优化。

  • 3、实现方法：

\(\qquad\!\!\)一般来说，动态规划可以通过递推和记忆化搜索两种方式实现。

阅读全文 »

发表于 更新于 分类于 ， 本文字数： 3.2k 阅读时长 ≈ 12 分钟
  • 1、递推：

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

\(\qquad\!\!\)共有 \(n\) 级台阶，每次可以上 \(1-k\) 级，上完的方案数：

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
#include<bits/stdc++.h>
#define in inline
#define re register
const int N=N;
using namespace std;
int n,k;
int f[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 ;
}
int main()
{
	n=qread();
	k=qread();
	f[0]=1;
	for(re int i=1;i<=n;i++)
	{
		for(re int j=max(0,i-k);j<i;j++)
		{
			f[i]+=f[j];
		}
	}
	qwrite(f[n]);
	putchar('\n');
    return 0;
}
阅读全文 »

发表于 更新于 分类于 ， 本文字数： 597 阅读时长 ≈ 2 分钟
  • 1、起手式：
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
#include<bits/stdc++.h>
#define in inline
#define re register
using namespace std; 
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()
{
	
	return 0;
}
阅读全文 »
0%