Void Space

发表于 更新于 分类于

分块

定义

  • 把一个序列从左往右切分成若干块，每块大小不超过size。
  • 一个区间可以看作是若干个完整的块加上两端零碎的不超过2size个数。
  • 对于每个完整的块维护信息方便修改/查询。
    阅读全文 »

发表于 更新于 分类于

高级二分查找

知识回顾

  • 给定一个单调不下降的序列a[1..n]，问x是否在其中。

  • 根据初始信息，答案显然位于[1,n]。

  • 假设我们已知答案位于[l,r]。

  • 若l>r，则说明x不在其中。

  • 否则取mid=(l+r)/2，比较x与a[mid]的大小关系。

  • 若x==a[mid]，则x在其中。

  • 若x<a[mid]，则答案位于[l,mid-1]。

  • 若x>a[mid]，则答案位于[mid+1,r]。 ### 二分的适用范围

  • 当x<a[mid]时，可以把可能区间缩小至[1,mid-1]是因为a[mid]<=a[mid..n]。

  • 二分的适用范围：单调不下降/不上升的序列或函数。

代码实现

bool find(int n, int a[], int x) {
    int l = 1, r = n;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (x == a[mid]) return true;
        if (x < a[mid]) r = mid - 1;
        else l = mid + 1;
    }
    return false;
}

例子：找平方根下取整

ll findsq(ll val){
    ll l = 0;
    ll ans=-1; 
    ll r = maxmid;
    while(l <= r ){
        ll mid = (l + r) >> 1;
        if((mid*mid)<=val){
            ans=mid;
            l = mid +1;
        }
        else{
            r = mid -1;
        }
    }
    return ans;
}

例题1-序列划分

  • 给定n个正整数a[1..n]，将这个序列从左到右划分成m段，使得每段至少有一个数。
  • 你需要让数字之和最大的那一段的数字和尽可能得小。
  • 1 <= m <= n <= 100000。
  • 1 <= a[i] <= 10^9。

代码

贪心

int f(long long x) {
    long long sum = 0;//当前段的数字之和
    int cnt = 1;//最少切出的段数
    for(int i = 1; i <= n; i++) {
        if (a[i] > x) return -1;//无解
        if (sum + a[i] <= x) sum += a[i];
        else sum = a[i], cnt ++;
    }
    return cnt;
}

二分解法（更快

  • 若f(x)有解，则若能划分成f(x)段，必然能划分成f(x)+1段。
  • 另一方面，若f(x)有解，则f(x)≥f(x+1)，因为x+1的限制变松了。
  • 显然我们要求的答案位于[max(a[1..n]), sum(a[1..n])]之中。
  • 我们需要在这个范围里，找到最小的x，使得f(x)≤m。
  • 因为f(x)≥f(x+1)，是单调函数，二分即可。

需要通过O（n）算法f处理数据，看是否满足 二分即可（可以使用ANS储存中间值，更方便）

long long solve(long long mx, long long sum) {
    long long l = mx, r = sum, ans = r;
    while (l <= r) {
        long long mid = (l + r) / 2;
        int tmp = f(mid);
        if (tmp <= m) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    return ans;
}

最大/最小 等问题可以用二分解决

例题2 - Tower

例2-Ice Cream Tower

  • 给定n个正整数a[1..n]和一个正整数k。
  • 一座高度为k的塔b[1..k]满足b[1]*2≤b[2]，b[2]*2≤b[3]，b[3]*2≤b[4]…
  • 你要从中选择一些数来叠很多座高度为k的塔，问最多能叠多少座塔。
  • 2 ≤ n ≤ 100000。
  • 2 ≤ k ≤ 30。
  • 1 ≤ a[i] ≤ 10⁹。

考虑的问题

  • 如何判断能否叠出x座塔？
  • 将序列从小到大排序，那么最优情况下前x小的数字将作为这x座塔的底层。
  • 从小到大依次考虑剩下的数，不断尝试铺出第二层、第三层…第k层。
  • 如果一个数铺不上去，那么舍弃就好。
  • 考虑完所有数字之后，判断每座塔的高度是否达到k即可。

代码：

using namespace std;
typedef long long ll;
const int N=300010;
int Case,cas,n,k,i,l,r,mid,ans,c[N]; ll a[N],b[N];
bool check(int x){
    int i,j;
    for(i=1;i<=x;i++)b[i]=a[i],c[i]=1;
    for(i=x+1,j=1;i<=n;i++)if(a[i]>=b[j]*2){
        b[j]=a[i];
        c[j]++;
        j++;
        if(j>x)j=1;
    }
    for(i=1;i<=x;i++)if(c[i]<k)return 0;
    return 1;
}
int main(){
    scanf("%d",&Case);
    for(cas=1;cas<=Case;cas++){
        scanf("%d%d",&n,&k);
        for(i=1;i<=n;i++)scanf("%lld",&a[i]);
        sort(a+1,a+n+1);
        l=1,r=n,ans=0;
        while(l<=r){
            mid=(l+r)>>1;
            if(check(mid))l=(ans=mid)+1;else r=mid-1;
        }
        printf("%d\n",ans);
    }
}

例题3 - K小

  • 给定n个正整数a[1..n]和m个正整数b[1..m]。
  • 在n*m个a[i] + b[j]中，找到第k小的数（不去重）。
  • 1 ≤ n,m ≤ 100000。
  • 1 ≤ k ≤ n * m。
  • 1 ≤ a[i], b[i] ≤ 10^8。

思路：

例3-第K小的数

  • 本题的单调函数是什么呢？
  • 设f(x)表示有多少对i,j满足a[i]+b[j]<=x。
  • 则f(x)<=f(x + 1)，是单调函数。
  • 我们需要找到最小的x，满足f(x)>=k。
  • 二分。
  • 给定x，如何统计有多少对i,j满足a[i]+b[j]<=x？
  • 将a和b都从小到大排序后双指针统计。

代码

long long f(int x) {
    long long cnt = 0;
    int j = m;
    for (int i = 1 ; i <= n ; i ++) {
        while (j && a[i] + b[j] > x) j --;
        cnt += j;
    }
    return cnt;
}

j 直接减小即可，因为a序列有序，j只能减小，O（n）

发表于 更新于 分类于

Box64 Arm64 平台运行 x86_64 应用

预构建容器

docker run -it -v yourvolumename:/minecraft -p 19132:19132/udp -p 19132:19132 -p 19133:19133/udp -p 19133:19133 --restart unless-stopped 05jchambers/legendary-bedrock-container:latest

指令

可以直接运行，无需环境

export BOX64_LD_LIBRARY_PATH=.
box64 ./bedrock_server

QEUM 虚拟机

使用 qemu-x86_64-static 需要提取环境依赖文件，然后

export LD_LIBRARY_PATH=.
qemu-x86_64-static ./bedrock_server

发表于 更新于 分类于

Netsh Windows 网络端口转发

https://zhuanlan.zhihu.com/p/584098323

创建转发

listen 是转发机的地址 connect 是被转发，也就是要访问的主机地址

netsh interface portproxy add v4tov4 listenaddress=0.0.0.0 listenport=5555 connectaddress=192.168.163.102 connectport=5555

查看已有的转发

netsh interface portproxy show all

发表于 更新于 分类于

Docker 启用 IPV6

修改文件

sudo vim /etc/docker/daemon.json

在大括号内添加如下内容，没有大括号则补上

"ipv6": true,
"fixed-cidr-v6": "fd00::/80",
"experimental": true,
"ip6tables": true

重启docker

systemctl restart docker

发表于 更新于 分类于

数位 DP

基础知识

可以对有上限的数字进行枚举（相当于考虑无限制情况下的预处理） 这样就允许了预处理

  • 三、前缀的用途（以1234为例，控制上界枚举）
  • 11**：满足的为1100-1199，所以下一位可以是0-9
  • 12**：满足的为1200-1234，所以下一位可以是0-3
  • 那么，1234要求的是——
  • 0000-0999
  • 1000-1199
  • 1200-1229
  • 1230-1233
  • 1234（本身）
    阅读全文 »

发表于 更新于 分类于

JDK 安装 Java 版本切换

进行JDK安装

apt-get install openjdk-17-jdk

选择JAVA版本

update-alternatives --config java

发表于 更新于 分类于

设置 git 与终端代理

Powershell 使用

$env:HTTP_PROXY="http://127.0.0.1:7890"; $env:HTTPS_PROXY="http://127.0.0.1:7890"

对于 git

git config --global http.proxy 'http://127.0.0.1:7890'
git config --global https.proxy 'https://127.0.0.1:7890'

Bash

export http_proxy=http://127.0.0.1:7890
export https_proxy=http://127.0.0.1:7890

发表于 更新于 分类于

线性基

异或的性质

预备知识-奇妙的异或运算

  • 异或的性质：

  • 如果\(c == a \land b\)

  • 则有：\(a \land c == b\) 和 \(b \land c == a\)

  • 执行以下3条操作的效果是？

  • \(a = a \land b\)；\(b = a \land b\)；\(a = a \land b\)；

  • 答案：整数a和b的交换

    阅读全文 »
0%