做题笔记 2023/11/8

A.依赖背包 [NOIP2006 金明的预算方案]

Q:有\(n\)元钱，想买\(m\)个物品，第\(i\)个物品的价格为\(v_{i}\)，重要度为\(p_{i}\)，有些物品是从属于某个主件物品的附件，要买这个物品，必须购买它的主件。目标是让所有购买的物品的\(v_{i}p_{i}\)之和最大。

考虑将每个物品与其子类的各种组合看成另一些物品，先不将子类存在应遍历的数据里，在 dp 到父类时遍历一遍物品的子类与其的组合。

例如：3 物品有两个子类 7 、8 ，先不将 7 8 放入要查的数组里，查到 3 时再查 7 8，总共有 3 、3 7 、3 8 、3 7 8 四种取法，遍历子类组合时将组合里所有的 \(v\) 和 \(vp\) 加起来看作一个新物品。

代码：

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N = 0X7FFF;
int n,m;
int dp[N];
pair<int,int> p1[N];
vector<pair<int,int> > s[N]; /*（其实写之前不知道 vector 有这个用法，想用两个数组来着）*/
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int v,p,q;cin>>v>>p>>q;
        p *=v;
        if(!q)p1[i]={v,p};
        else s[q].push_back({v,p});
    }
    for(int i=1;i<=m;i++){
        for(int j=n;j>=0;j--){
            for(int t=0;t<1<<s[i].size();t++){
                int v=p1[i].first;
                int w=p1[i].second;
                for(int z=0;z<s[i].size();z++){
                    if(t>>z & 1){
                        v+=s[i][z].first;
                        w+=s[i][z].second;
                    }
                }
                if(j>=v) dp[j]=max(dp[j],dp[j-v] + w);
            }
        }
    }
    cout<<dp[n];
}

B.分治+计算几何 [平面最近点对 Luogu P1429]

Q:给出\(R^{2}\)上的一些点，搜出这些点中最小的距离。

爆搜即可 乍一看无从下手 确实无从下手，但是仔细想想，有点像区间dp（能量项链）：先将这些点按横坐标排序，再将其不断二分成两个或一个点的集合：\((x_{1},x_{2})\)、\((x_{3},x_{4})\) ……如果集合只有一个点将其值设置为无穷，有两个则设置为两点距离。接着进行合并，合并时除了先求出原先两个区间的最小值中的更小值之外，只需要再考虑跨越右区间左端 \(mid\)或左区间右端 \(mid+1\) 的相互“比较近”的点，与上面求出的更小值进行比较即可。（如果全部点都遍历一遍复杂度就变成\(O(nlogn)\)了，必t）

那么问题就落到怎么定义“比较近”了。注意到在平面中：

\[ A:(x_{A}-x_{B}>m) \vee B:(y_{A}-y_{B}>m) \Rightarrow d(A,B)>m \\ \]

由于是横向分割，关于 \((mid)\) 不满足 \(A\) 的的点互相不满足 \(A\) ，且落在一个横向距离为 \(2m\) ，纵向无线延长的条带上，而遍历条带中的点对组合时，先考察一遍 \(B\) 性质代替 \(sqrt\)() 的运算即可。（注意，遍历“近”点时，必须保证纵坐标有序）

代码：

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<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 0X7FFFF;
int n;
int flag = 0;
struct pont{
    double first,second;
}point[N];

bool cmp(pont a,pont b){
    if(a.first==b.first) return a.second<b.second;
    else if(a.first==b.first &&a.second==b.second) flag=1;
    return a.first<b.first;
}
bool cmps(int a,int b){
    return point[a].second<point[b].second;
}
double cal(pont a,pont b){
    return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}
int temp[N];
double merge(int l,int r){
    if(r-l==1){
        return cal(point[l],point[r]);   
    }
    else if(l==r) return N;
    int mid = (l+r)/2;
    double d1 = merge(l,mid);
    double d2 = merge(mid + 1,r);
    int k = 0;
    double d3 = N;
    for(int i = l; i <= r;i ++)
    if(fabs(point[mid].first-point[i].first) < min(d1,d2))
        temp[k++] = i;
    sort(temp, temp + k, cmps);
    for(int i=0;i<k;i++){
        for(int j=1+i;j<k && fabs(point[temp[j]].second-point[temp[i]].second) < min(d1,d2);j++){
            d3 = min(d3,cal(point[temp[j]],point[temp[i]]));
        }
    }
    return min(min(d1,d2),d3);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>point[i].first>>point[i].second;
    }
    sort(point+1,point+n+1,cmp);
    printf("%.4lf",merge(1,n));
}

C.前缀和+逆序对[COCI2015-2016#2 VUDU]

Q：给定一个长度为 n 的序列以及一个数 p ，求出该序列的平均数大于 p 的连续子列的个数。

看到平均数，先想到前缀和。下面对前缀和做一些数学推导。设序列为 \(a_{n}\) ，前缀和为 \(s_{n}\) ，假设某连续子列满足题意，不妨设 \(k>j\) ，则有

\[ {\frac{\sum_{i=j}^{k}a_{i}}{k-j}\geq p} \tag{C.1} \]

即

\[ {\frac{s_{k}-s_{j}}{k-j}}\geq p \Leftrightarrow s_{k}-kp\geq s_{j} -jp \tag{C.2}\quad(j,k\in[0,n]) \]

\((2)\)式右端极其对称，考虑构造新数列

\[ {b_{n}=\sum_{i=1}^{n}a_{i}-np\quad(n>0)\\}\tag{C.3} \]

特别地，令 \(b_{0}=0\) ，使\((C.2)\)和 \((C.3)\) 完全等价。（这是因为 \(j\) 在 \((C.3)\) 中不能取到0，而在 \((C.2)\) 中可以取到 \(0\) ）

考察 \(b_{n}\) 的递推式，易得

\[ {b_{n}=b_{n-1}+a_{n}-p\quad(n\geq0)\\}\tag{C.3'} \]

则题目变为求当 \(k>j\)时，\(b_{j}\leq b_{k}\) 的 \((j,k)\) 对数。

推完了，这不就求顺序对吗？两个办法：归并排序或树状数组。本人代码里用的是归并。（直接把板子弄过来的 我是fw，归并改了半天不对）

说一下树状数组的思路：简单来说就是大型哈希，先将数组初始化为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
#include<iostream>
#include<cstring>
#include<algorithm>
const int N = 1000005;
using namespace std;
long long n;
long long a[N];
long long s[N];
long long s2[N];
long long ans = 0;
long long d[N];
long long p;
void msort(int L, int R)//归并求逆序对
{
    if (L == R) {
        return;
    }
    int mid = (L + R) / 2;
    msort(L, mid); msort(mid + 1, R);
    for (int k = L; k <= R; k++)a[k] = s2[k];
    int i = L, j = mid + 1;
    for (int k = L; k <= R; k++) {
        if ((i <= mid) && (a[i]<a[j] || j>R))s2[k] = a[i++];
        else s2[k] = a[j++], ans += mid - i + 1;
    }
}
int main() {
    cin>>n;
    for (int i = 1; i <= n; i++) {
        cin>>a[i];
    }
    cin >> p;
    s2[0] = 0;
    for (int i = 1; i <= n; i++) {
        s2[i] = s2[i-1] + a[i] - p;
    }
    reverse(s2 + 1, s2 + n + 1);//翻转后求逆序对
    s2[n+1] = 0;
    msort(1, n+1);
    cout << ans;
}

(比较有思维难度的题)

D.分类讨论+实数二分[ICPC2020 Shanghai R Walker]

Q:给出一段区间[0,n],给定两个点的位置\(\boldsymbol {x_{A},x_{B}}\)它们分别能以\(\boldsymbol{v_{A},v_{B}}\)的速率在区间内移动，速度的方向变化认为是瞬时的，A、B的移动会留下轨迹，求出这个区间被轨迹完全覆盖的最短时间。

乍一看有点像物理题。这题的确有种高考板块模型的味道，即对A、B的运动状态详尽分类，搜索出每种状态的时间后取最小值。下面对状态进行分类：(不妨设 \(x_{A}>x_{B}\) )

A.二者相向而行，此时完全覆盖的时间为:

\[ min(\frac{x_{B}}{v_{B}},\frac{n-x_{A}}{v_{A}}) \tag{D.1} \]

B.二者之一单独完全覆盖了区间，此种情况的最小时间为

\[ min(\frac{min(n-x_A,x_{A})+n}{v_{A}},\frac{min(n-x_B,x_{B})+n}{v_{B}}) \tag{D.2} \]

C.二者各自负责自己的一边。设分界线为 \(mid\) ,则此种情况的最小值为

\[ max(\frac{min(x_{A}-mid,n-x_{A})+n-mid}{v_{A}},\frac{min(x_{B},mid-x_{B})+x_{B}}{v_{B}}) \tag{D.3} \]

这种情况不太好直接算出来，因此对 \((D.3)\) 式的 \(mid\) 在 \([x_{B},x_{A}]\) 上进行二分搜索。

最后，上三式取最小值即可。

代码：

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<iostream>
#include<cmath>
using namespace std;
int main() {
	int t; cin >> t;
	while (t--) {
		double n, x1, v1, x2, v2; cin >> n >> x1 >> v1 >> x2 >> v2;
		if (x1 < x2) {
			swap(x1, x2);
			swap(v1, v2);
		}
		double ans = 0;
		ans = min(min((2 * n - x1), n + x1) / v1, min((n + x2), 2 * n - x2) / v2);
		ans = min(ans, max(x1 / v1, (n - x2) / v2));
		double l = x2;
		double r = x1;
		while (r - l >= 1e-7) {
			double mid = (l + r) / 2;
			double m = (min(n - x1, x1 - mid) + n - mid) / v1; double q = (min(mid - x2, x2) + mid) / v2;
			ans = min(ans, max(m, q));
			if (m > q) l = mid;
			else r = mid;
		}
		printf("%.10lf\n", ans);
	}
}

E.函数stolz定理[华师数分]

Q：设函数\(\boldsymbol f\)定义在\(\boldsymbol{(a,+\infty)}\)上，\(\boldsymbol f\)在每一个有限区间\(\boldsymbol {(a,b)}\)上有界，并满足

\[ \lim_{x\rightarrow+\infty}{(f(x+1)-f(x))}=A. \]

证明

\[ \lim_{x\rightarrow+\infty}\frac{f(x)}{x}=A. \tag{E} \]

证明：由题

\[ \forall \varepsilon,\exists M>0,\forall x>M,\left| f(x+1)-f(x)-A \right|< \varepsilon \tag{E.1} \]

令

\[ g(x)=\frac{f(x)}{x} \]

设\(f(x)\)的界为\(k\)，并注意到

\[ \left| \frac{f(x)}{x}-A \right|=\frac{1}{x}\left|f(x)-Ax\right| \tag{E.2} \]

对\((E.2)\)式右端进行构造

\[ \frac{1}{x}\left|f(x)-Ax\right|=\frac{1}{x}\left|\sum_{i=x-[x-M]+1}^{x}(f(i)-f(i-1)-A)+f(x-[x-M])-A(x-[x-M])\right| \tag{E.2'} \]

结合

\[ x-M-1<[x-M]\le x-M\\ M\le x-[x-M]<M+1 \]

以及\((E.2')\)、\((E.1)\)和绝对值不等式易见

\[ \begin{aligned} |g(x)-A| &\leq \frac{1}{x}\{\sum_{i=x-[x-M]+1}^{x}|f(i)-f(i-1)-A|+|f(x-[x-M])|+|A(x-[x-M])| \}\\ &< \frac{1}{x}([x-M]\varepsilon+|A|(M+1)+k))\\ &=\frac{[x-M]\varepsilon}{x}+\frac{k+(M+1)|A|}{x}\tag{E.3} \end{aligned} \]

考察等式右端第二项，注意到分式上方皆为常数，即有\(\lim_{x\rightarrow+\infty}\frac{k+(M+1)|A|}{x}=0.\)从而存在正数\(M\),当\(x>M\)时，对于任给正数\(\varepsilon\) ，有 \(\frac{k+(M+1)|A|}{x}< \varepsilon\) .因此当\(x>M\)时，有

\[ |g(x)-A|<\frac{[x-M]\varepsilon}{x}+\frac{k+(M+1)|A|}{x}<2\varepsilon\tag{E.4} \]

这就证明了\((E)\).\(\ \ \ \square\)

评注：这题证明方法类似stolz定理的证明，即依照极限定义式进行放缩。但由于函数非离散，需要对末端进行一些处理才能达到目的。