题单一览
时间：20201028~20201101
✔hdu1050 活动安排变形
✔hdu4864 不错的题
✔poj1328 活动安排变形
✔poj1089 区间覆盖
✔hdu4911 逆序对
✔hdu1425 快速排序思想
部分总结
大部分都是比较典型的贪心题目，现在拿出来复习一下基本的算法思想。因为过于依赖STL，快排都忘了怎么写（是的我快排WA了几发）。
HDU1050
本来想的是多次的活动安排问题模型，但实际上并不是。活动安排要求尽可能多参加，而这个题目要求全部参加时间尽可能少。
因此，我们可以举出按活动安排模型排序（按结束时间排序）的反例：
主要就是这里需要注意一下，其他都是很常规的排序贪心。
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
| #include <bits/stdc++.h>
#define maxn 4005
using namespace std;
int t, n;
struct seg{
int lf;
int rt;
int val;
} s[maxn];
bool cmp(const seg &A, const seg &B){
return A.lf < B.lf;
}
int main(void)
{
scanf("%d", &t);
while(t--)
{
memset(s, 0, sizeof(s));
int num = 0, ans = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%d %d", &s[i].lf, &s[i].rt);
if(s[i].lf > s[i].rt)
swap(s[i].lf, s[i].rt);
}
sort(s+1, s+n+1, cmp);
while(num < n)
{
int nrt = 0;
for(int i = 1; i <= n; i++)
{
if(s[i].val) continue;
if(s[i].lf & 1 && s[i].lf > nrt)
{
s[i].val = 1;
nrt = s[i].rt;
num++;
}
if(s[i].lf % 2 == 0 && s[i].lf > nrt + 1)
{
s[i].val = 1;
nrt = s[i].rt;
num++;
}
}
ans += 10;
}
printf("%d\n", ans);
}
return 0;
}
|
HDU4864
的确是很妙的一道贪心题。
首先观察数据范围，确定$x_i$的影响远远大过$y_i$，由此确定排序方法。
（当然你也可以直接用计算的函数来排序）
然后，妙的地方来了。
排序好后，顺序枚举每一个任务，每次枚举开始时，将可使用的机器（最大使用时间达到要求）的等级用一个桶存起来。
完成这一步后，由当前任务的等级向最高等级枚举，若发现存在这样的机器还未被使用，则调用，统计完答案后跳出循环，保证了调用的是尽可能菜的机器。同时由于已经排了序，因此机器的最大使用时间也是符合要求的。
这样子可以大大压缩时间复杂度。
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 maxn 300005
using namespace std;
int n, m, c[maxn];
struct des{
int maxt;
int level;
} a[maxn], t[maxn];
bool cmp(const des &A, const des &B){
if(A.maxt != B.maxt) return A.maxt > B.maxt;
return A.level > B.level;
}
int main(void)
{
while(~scanf("%d %d", &n, &m))
{
memset(c, 0, sizeof(c));
for(int i = 1; i <= n; i++)
scanf("%d %d", &a[i].maxt, &a[i].level);
for(int i = 1; i <= m; i++)
scanf("%d %d", &t[i].maxt, &t[i].level);
sort(a+1, a+n+1, cmp);
sort(t+1, t+m+1, cmp);
long long ans = 0, num = 0;
for(int i = 1, j = 1; i <= m; i++)
{
while(a[j].maxt >= t[i].maxt && j <= n)
{
c[a[j].level]++;
j++;
}
for(int k = t[i].level; k <= 100; k++)
{
if(c[k])
{
c[k]--;
ans += 500 * t[i].maxt + 2 * t[i].level;
num++;
break;
}
}
}
printf("%lld %lld\n", num, ans);
}
return 0;
}
|
HDU1425
排序板子题。
主要踩了快速排序的一个坑。
具体看代码注释。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| void qsort(int lf, int rt){
if(lf >= rt) return;
int mid = a[(lf + rt) / 2];
int i = lf, j = rt;
while(i <= j)
{
while(a[i] < mid) i++;
while(a[j] > mid) j--;
if(i <= j)
{
swap(a[i], a[j]);
i++;
j--;
}
}
qsort(lf, j);
qsort(i, rt);
}
|
下阶段目标
本来想先看图论的，不过想了一下还是先看看简单数学。
主要包含，快速幂，GCD，LCM，exGCD，不定方程，同余方程，逆元，基础生成函数，入门博弈论等。
在数学复习完后，需要去复习一下图论的基本内容，然后去刷字符串的基本内容，再然后巩固好这些基础题后，去刷一下高级数据结构（Splay这种）和计算几何，希望人没事，大概。
下一阶段数学回顾题单：
hdu1061，求$n^n$的末尾数字
hdu3117，矩阵快速幂算Fib数列
hdu6030，递推数列转为矩阵，再进行快速幂取模
hdu1576，拓展欧几里得
hdu2588，欧拉函数复习
hdu5656，有关GCD的动态规划
poj2689，区间素数板子
hdu3792，素数打表可做
hdu2841，容斥原理
hdu4135，容斥原理
hdu1028，递归/DP/生成函数
hdu1521，指数型生成函数
hdu5673，卡特兰数+逆元
hdu4035，树+期望DP
hdu2999，SG函数
hdu4111，记忆化搜索+SG函数
hdu1527，威佐夫博弈