LCX的算法笔记Week-5
DP
建立一个有序容器map，键值为边的权值，值为该权值的所有边构成的vector
名为ans的map代表以某点为结尾的递增序列的所有方案
遍历map，即从小到大遍历所有边，每遍历一个vector，就会更新这个vector所存的边的端点的值
更新的时候，因为新加入一条边，方案数应先加1（区分该点是否在本次遍历中出现过）
再加上以另一点为结尾的方案数（即从x->y或y->x）
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
| #include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
map<int,ll> ans;
map<int, vector<pii>> road;
int n;
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cin>>n;
for (int i=1; i<n; i++) {
int a,b,c;
cin>>a>>b>>c;
road[c].push_back({a,b});
}
for(auto i:road)
{
map<int,ll> temp;
for(auto j:i.s)
{
if (temp.count(j.f)) {
temp[j.f]++;
}
else temp[j.f]=ans[j.f]+1;
temp[j.f]+=ans[j.s];
if (temp.count(j.s)) {
temp[j.s]++;
}
else temp[j.s]=ans[j.s]+1;
temp[j.s]+=ans[j.f];
}
for(auto j:temp)
{
ans[j.f]=j.s;
}
}
ll sum=0;
for(auto i:ans)
{
sum+=i.s;
}
cout<<sum;
}
|
欧拉回路
每一个城市的名字即代表首字母到尾字母的一条有向边，问题即转换为判断该有向图是否存在欧拉回路
- 无向图存在欧拉回路的充要条件
一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图。
- 有向图存在欧拉回路的充要条件
一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。
该图为有向图，所以先判断是否为连通图，采用并查集来判断，每加入一条边，就把两个顶点加入到一个集合，建一条由首字母到尾字母的有向边。最后判断是否所有点都在一个集合中，并且所有点的入度等于出度，所以对于每个点，当它为起始点就让degree++，否则–，最后判断是否为0即可
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
| #include <bits/stdc++.h>
using namespace std;
int deg[26],n;
int fa[26],f;
bool state[26];
int find(int x)
{
if (fa[x]!=x) {
fa[x]=find(fa[x]);
}
return fa[x];
}
void merge(int x,int y)
{
fa[find(x)]=find(y);
}
int main() {
cin>>n;
for (int i=0; i<=25; i++) {
fa[i]=i;
}
while (n--) {
string t;
cin>>t;
int len=(int)t.size();
int u=t[0]-'a',v=t[len-1]-'a';
deg[u]++;
deg[v]--;
state[u]=state[v]=true;
merge(u,v);
f=fa[u];
}
bool flag=true;
for (int i=0; i<=25; i++) {
if ((deg[i]||find(i)!=f)&&state[i]) {
flag=false;
}
}
if (flag) {
cout<<"YES";
}
else cout<<"NO";
return 0;
}
|
区间选点
给定 N 个闭区间 [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。
将区间按右端点排序，每次选出右端点，遍历区间，如果该区间左端点大于当前维护右端点最大值，则把当前右端点加入集合并更新最大值。
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int n;
struct range{
int l,r;
bool operator <(const range & t)const
{
return r<t.r;
}
} ran[N];
int main() {
cin>>n;
for (int i=0; i<n; i++) {
cin>>ran[i].l>>ran[i].r;
}
sort(ran,ran+n);
int rmax=-2e9;
int ans=0;
for (int i=0; i<n; i++) {
if (ran[i].l>rmax) {
ans++;
rmax=ran[i].r;
}
}
cout<<ans;
return 0;
}
|
最大不相交区间数量
给定 N 个闭区间 [ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。
输出可选取区间的最大数量。
同样地对右端点排序，做法和上题一致
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int n;
struct range{
int l,r;
bool operator <(const range & t)const
{
return r<t.r;
}
} ran[N];
int main() {
cin>>n;
for (int i=0; i<n; i++) {
cin>>ran[i].l>>ran[i].r;
}
sort(ran,ran+n);
int rmax=-2e9;
int ans=0;
for (int i=0; i<n; i++) {
if (ran[i].l>rmax) {
ans++;
rmax=ran[i].r;
}
}
cout<<ans;
return 0;
}
|
区间分组
给定 N 个闭区间 [ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。
输出最小组数。
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int n;
struct range{
int l,r;
bool operator <(const range & t)const
{
return l<t.l;
}
} ran[N];
int main() {
cin>>n;
for (int i=0; i<n; i++) {
cin>>ran[i].l>>ran[i].r;
}
sort(ran,ran+n);
priority_queue<int,vector<int>,greater<int>> heap;
for (int i=0; i<n; i++) {
auto t=ran[i];
heap.push(t.r);
if (heap.top()<t.l) {
heap.pop();
}
}
cout<<heap.size();
return 0;
}
|
另一个很巧妙的解法
转换为上课问题，有若干个活动，第i个活动开始时间和结束时间是[si,fi]，同一个教室安排的活动之间不能交叠，求要安排所有活动，少需要几个教室？
有时间冲突的活动不能安排在同一间教室，与该问题的限制条件相同，即最小需要的教室个数即为该题答案。
我们可以把所有开始时间和结束时间排序，遇到开始时间就把需要的教室加1，遇到结束时间就把需要的教室减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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int n;
int a[N],idx;
int main() {
cin>>n;
for (int i=0; i<n; i++) {
int l,r;
cin>>l>>r;
a[idx++]=2*l;
a[idx++]=2*r+1;
}
sort(a,a+idx);
int ans=0,cur=0;
for (int i=0; i<idx; i++) {
ans=max(ans,cur);
if (a[i]%2) {
cur--;
}
else cur++;
}
cout<<ans;
return 0;
}
|
区间覆盖
给定 N 个闭区间 [ai,bi] 以及一个线段区间 [s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。
输出最少区间数，如果无法完全覆盖则输出 −1。
对区间按左端点排序，每次选一个左端点小于线段区间st且右端点最大的，并用此右端点更新st，当最大右端点小于st则代表不能完全填满，当最终结果区间st<ed同样代表区间不能被填满
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>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int n;
int st,ed;
struct range{
int l,r;
bool operator <(const range & t)const
{
return l<t.l;
}
} ran[N];
int main() {
cin>>st>>ed;
cin>>n;
for (int i=0; i<n; i++) {
cin>>ran[i].l>>ran[i].r;
}
sort(ran,ran+n);
int res=0;
for (int i=0; i<n; i++) {
int j=i;
int rmax=-2e9;
while (j<n&&ran[j].l<=st) {
rmax=max(rmax,ran[j].r);
j++;
}
if (rmax<st) {
res=-1;
break;
}
res++;
st=rmax;
i=j-1;
if (rmax>=ed) {
break;
}
}
if (st<ed) {
res=-1;
}
cout<<res;
return 0;
}
|
合并果子（Huffman树）
在一个果园里，达达已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。
达达决定把所有的果子合成一堆。
每一次合并，达达可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。
可以看出，所有的果子经过 n−1 次合并之后，就只剩下一堆了。
达达在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以达达在合并果子时要尽可能地节省体力。
假定每个果子重量都为 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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int n,ans;
priority_queue<int,vector<int>,greater<int>> heap;
int main() {
cin>>n;
for (int i=0; i<n; i++) {
int t;
cin>>t;
heap.push(t);
}
while (heap.size()>1) {
int a1=heap.top();
heap.pop();
int a2=heap.top();
heap.pop();
ans+=a1+a2;
heap.push(a1+a2);
}
cout<<ans;
return 0;
}
|
排队打水（排序不等式）
有 n 个人排队到 1 个水龙头处打水，第 i 个人装满水桶所需的时间是 ti，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int n,a[N];
ll ans;
int main() {
cin>>n;
for (int i=0; i<n; i++) {
cin>>a[i];
}
sort(a,a+n);
for (int i=0; i<n; i++) {
ans+=a[i]*(n-i-1);
}
cout<<ans;
return 0;
}
|
货仓选址（绝对值不等式）
在一条数轴上有 N 家商店，它们的坐标分别为 A1∼AN。
现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。
- 每两个点一组，只要选的点在这两个点之间，就能使该点到两点之和最小（为两点距离）所以选中位数即可求到最优解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int n,a[N];
ll ans;
int main() {
cin>>n;
for (int i=0; i<n; i++) {
cin>>a[i];
}
sort(a,a+n);
for (int i=0; i<n; i++) {
ans+=abs(a[i]-a[n/2]);
}
cout<<ans;
return 0;
}
|
耍杂技的牛
农民约翰的 N 头奶牛（编号为 1..N）计划逃跑并加入马戏团，为此它们决定练习表演杂技。
奶牛们不是非常有创意，只提出了一个杂技表演：
叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。
奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。
这 N 头奶牛中的每一头都有着自己的重量 Wi 以及自己的强壮程度 Si。
一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。
您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。
- 将每头奶牛的wi+si排序，从小到大的顺序即为奶牛从上到下的顺序，易证若非递增则交换后，最大值会变小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N=1e5+10;
int n;
ll ans=-2e9,sum;
pii cow[N];
int main() {
cin>>n;
for (int i=0; i<n; i++) {
int w,s;
cin>>w>>s;
cow[i]={w+s,w};
}
sort(cow,cow+n);
for (int i=0; i<n; i++) {
int s=cow[i].first-cow[i].second,w=cow[i].second;
ans=max(ans,sum-s);
sum+=w;
}
cout<<ans;
return 0;
}
|
表达式求值(中缀表达式)
给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。
注意：
- 数据保证给定的表达式合法。
- 题目保证符号
- 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
- 题目保证表达式中所有数字均为正整数。
- 题目保证表达式在中间计算过程以及结果中，均不超过 231−1。
- 题目中的整除是指向 0 取整，也就是说对于大于 0 的结果向下取整，例如 5/3=1，对于小于 0 的结果向上取整，例如 5/(1−4)=−1。
- C++和Java中的整除默认是向零取整；Python中的整除
//默认向下取整，因此Python的eval()函数中的整除也是向下取整，在本题中不能直接使用。
存两个栈，一个操作符栈，一个数字栈，当要入栈的操作符优先级小于等于栈顶的操作符，则用栈顶的操作符进行一次计算，当遇到左括号时，直接入栈，当遇到右括号时将一直到左括号的运算符全部进行运算，最后对剩下的运算符进行运算操作即可得到最终结果
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
| #include <bits/stdc++.h>
using namespace std;
unordered_map<char, int> dic{{'+',1},{'-',1},{'*',2},{'/',2}};
stack<char> op;
stack<int> num;
void calculate()
{
int b=num.top();num.pop();
int a=num.top();num.pop();
char o=op.top();op.pop();
int res=0;
if (o=='+') {
res=a+b;
}
if (o=='-') {
res=a-b;
}
if (o=='*') {
res=a*b;
}
if (o=='/') {
res=a/b;
}
num.push(res);
}
int main() {
string s;
cin>>s;
for (int i=0; i<s.size(); i++) {
if (isdigit(s[i])) {
int x=0,j=i;
while (j<s.size()&&isdigit(s[j])) {
x=x*10+s[j]-'0';
j++;
}
i=j-1;
num.push(x);
}
else if (s[i]=='(')
op.push(s[i]);
else if (s[i]==')')
{
while (op.top()!='(') {
calculate();
}
op.pop();
}
else
{
while (op.size()&&dic[op.top()]>=dic[s[i]]) {
calculate();
}
op.push(s[i]);
}
}
while (op.size()) {
calculate();
}
cout<<num.top();
return 0;
}
|
KMP字符串
给定一个模式串 S，以及一个模板串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串 P 在模式串 S 中多次作为子串出现。
求出模板串 P 在模式串 S 中所有出现的位置的起始下标。
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int n,m,ne[N];
char p[N],s[N];
int main() {
cin>>n>>(p+1);
cin>>m>>(s+1);
for (int i=2,j=0; i<=n; i++) {
while (j&&p[i]!=p[j+1]) {
j=ne[j];
}
if (p[i]==p[j+1]) {
j++;
}
ne[i]=j;
}
for (int i=1,j=0; i<=m; i++) {
while (j&&s[i]!=p[j+1]) {
j=ne[j];
}
if (s[i]==p[j+1]) {
j++;
}
if (j==n) {
cout<<i-n<<' ';
j=ne[n];
}
}
return 0;
}
|
