不谈离散数学基本定理

AzureHair · 2023-12-03 21:24:13 · 个人记录

本文半娱乐向半学术向

先列出定理：

1.对于 \forall x,y \in \mathbb{Z},x<y，有 x+1\le y
2.\forall a,b\in\mathbb{Z},a<b,x>1，则有 x^a<x^b
3.\forall i\in\{1,2\cdots,n\},a_i\in\mathbb{N_+}，且 \sum_{i=1}^n a_i=S，则必定存在 k_1,k_2\in\{1,2\cdots n\},a_{k_1}\le\frac{S}{n},a_{k_2}\ge\frac{S}{n}
4.\forall x,y\in\mathbb{R},x=x+y\times 0,x=x+y-y
1.对于 \forall x,y \in \mathbb{Z},x<y，有 x+1\le y

推论：对于 \forall x_1,x_2 \cdots x_n \in \mathbb{Z},x_1<x_2< \cdots <x_n，有 x_1+n-1 \le x_2+n-2 \le \cdots \le x_n

典例分析：

Solution

首先观察到 d\in[0,1] 想到分情况讨论，对于 d=0 显然是单调队列优化DP的板子题，对于 d=1 我们发现对于一个 f_i 他最多就会加一，根据“离散数学基本定理”可以知道，一个不为最大值的 f_i 加一之后也无法影响最大值，所以可以忽略不为最大值的 f_i 所以需要做的就是写一个线段树找 f_i 最小的中的 h_i 最大的一个即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,d,h[300010],w[300010],f[300010];
struct node
{
    int l,r,pre,mmax;
}t[1200010];
struct node1
{
    node1(){}
    node1(int pre,int mmax):pre(pre),mmax(mmax) {}
    int pre,mmax;
};
void build(int x,int a,int b)
{
    t[x].l=a;t[x].r=b;
    if(a==b)
    {
        t[x].pre=0;t[x].mmax=h[a];
        return ;
    }
    int mid=a+b>>1;
    build(x*2,a,mid);
    build(x*2+1,mid+1,b);
    t[x].pre=min(t[x*2].pre,t[x*2+1].pre);
    if(t[x*2].pre==t[x*2+1].pre)t[x].mmax=max(t[x*2].mmax,t[x*2+1].mmax);
    else if(t[x*2].pre>t[x*2+1].pre)t[x].mmax=t[x*2+1].mmax;
    else t[x].mmax=t[x*2].mmax;
    return ;
}
void change(int x,int a,int b,int s)
{
    if(a<=t[x].l&&b>=t[x].r)
    {
        t[x].pre=s;
        return ;
    }
    int mid=t[x].l+t[x].r>>1;
    if(a<=mid)
    {
        change(x*2,a,b,s);
    }
    if(b>mid)
    {
        change(x*2+1,a,b,s);
    }
    t[x].pre=min(t[x*2].pre,t[x*2+1].pre);
    if(t[x*2].pre==t[x*2+1].pre)t[x].mmax=max(t[x*2].mmax,t[x*2+1].mmax);
    else if(t[x*2].pre>t[x*2+1].pre)t[x].mmax=t[x*2+1].mmax;
    else t[x].mmax=t[x*2].mmax;
}
node1 query(int x,int a,int b)
{
    if(a<=t[x].l&&b>=t[x].r)
    {
        return node1(t[x].pre,t[x].mmax);
    }
    int mid=t[x].l+t[x].r>>1;
    node1 ans1,ans2;
    if(a<=mid)
    {
        ans1=query(x*2,a,b);
    }
    if(b>mid)
    {
        ans2=query(x*2+1,a,b);
    }
    if(a<=mid&&b>mid)
    {
        int pre=min(ans1.pre,ans2.pre),mmax;
        if(ans1.pre==ans2.pre)mmax=max(ans1.mmax,ans2.mmax);
        else if(ans1.pre>ans2.pre)mmax=ans2.mmax;
        else mmax=ans1.mmax;
        return node1(pre,mmax);
    }
    else if(a<=mid)return ans1;
    else if(b>mid)return ans2;
    else return node1(0x3f,0x3f);
}
signed main()
{
    scanf("%lld%lld%lld",&n,&k,&d);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&h[i],&w[i]);
    }
    build(1,1,n);
    change(1,1,1,w[1]);
    for(int i=2;i<=n;i++)
    {
        node1 ans=query(1,max(i-k,1ll),i-1);
        f[i]=ans.pre+w[i]+(ans.mmax<=h[i])*d;
        change(1,i,i,f[i]);
    }
    cout<<f[n]<<endl;
    return 0;
}

赛时写的抽象代码。

2.对于 \forall x,有 x=x+y\times0。

看起来抽象实际非常具体，看例题：

A(z)=\sum a_nz^z$，$B(z)=\sum a_nz^n$，$C(z)=\sum c_nz^n

c_n=\sum_{i+2j\le n}a_ib_j

试用 A(z) 和 B(z) 表示 C(z)。

我们首先发现这个东西是一个卷积的形式但不完全是卷积的形式。

但是我们可以使用高贵的换元法：

c_n=\sum_{i+j\le n}a_ib_{\frac{j}{2}}

到这里，不知道这个重要的离散数学基本定理的人一定就不会做了，但是，我们会！发现只有 j 为偶数时才会计数，但是我们完全可以让奇数项的值为零即可，所以变成了没脑子题。

c_n=\sum_{i+j\le n}a_ib_j

所以他就是一个卷积再求和的形式，所以答案为：

C(z)=\frac{A(z)B(z^2)}{1-z}

要睡觉了以后再写。