首页 > 其他分享 >倍增st表

倍增st表

时间:2024-10-22 20:59:07浏览次数:4  
标签:容器 倍增 int 输入输出 st 优点 端点 include


首先,因为士兵是环形的,所以先将其拆分为链,并且每个士兵的移动位子不会被包含,所以只需要对左端点进行排序就能得到一个递增的区间

点击查看代码
void init()
{
    cin >> n >> m;
    int i;
    for (i = 1; i <= n; ++i)
    {
        w[i].i1 = i;
        cin >> w[i].l >> w[i].r;
        if (w[i].r < w[i].l)//如果右端点小于左端点,加上m,让成为链的时候右端点在左端点的右边
            w[i].r += m;
    }

    sort(w + 1, w + n + 1);//根据左端点进行排序

    n2 = n * 2;
    i = n + 1;
    for (i; i <= n2; i++)//复制一份
    {
        w[i].i1 = w[i - n].i1;
        w[i].l = w[i - n].l + m;
        w[i].r = w[i - n].r + m;
    }
}

之后如此图,

如果a是一点要选的话,那么根据贪心,下一个选择最好的方案就是c,也就是在左端点小于当前右端点的情况下,右端点最远的点,此时我们假设a(f,j)为战士在f点跑2的j次方到达的边防站,那就可以转化为a(a(f,j-1),j-1)到达的边防站,(2的n次方=2的(n-1)次方*2)因为 2的20次方为1000000,够用了,所以我们以此预处理每组数据

点击查看代码
void st()
{

    int o = 1;

    for (int i = 1; i <= n2; ++i)
    {
        while (o <= n2 && w[o].l <= w[i].r)
            o++;
        a[i][0] = o - 1; // 找到左端点小于当前i的右端点且右端点最远的点
    }

    for (int i = 1; (1 << i) <= n; ++i)//i相当于从s点走了2的i次
    {

        for (int s = 1; s <= n2; ++s)
        {

            a[s][i] = a[a[s][i - 1]][i - 1];//公式
        }
    }
}
最后,要知道最少要多少战士,我们先根据当前战士的左端下标来确定最右端下标//之后从最大值开始遍历,如果x走2的i次方步存在最优点(就是预处理代码每个点选择的下一个最优点),那答案就可以加上当前点,并且之后now更新为当前的最优点,再由不断更新的最优点到达计划点。最后ans还要+1,因为for里到达的最远点是小于计划到达的最远点的,必须要再加一个点才能大于计划点(为什么只加1呢,因为如果还能加,那for循环就没有结束) 完整代码
点击查看代码
/* 台州第一深情 */
#include <iostream>      // 输入输出流
#include <iomanip>       // 输入输出格式控制
#include <fstream>       // 文件输入输出流
#include <sstream>       // 字符串输入输出流
#include <cmath>         // 数学函数
#include <string>        // 字符串操作
#include <vector>        // 动态数组容器
#include <queue>         // 队列容器
#include <stack>         // 栈容器
#include <set>           // 集合容器
#include <map>           // 映射容器
#include <unordered_set> // 无序集合容器
#include <unordered_map> // 无序映射容器
#include <algorithm>     // 算法
#include <bitset>        // 位集容器
#include <stdio.h>       // 标准输入输出
using namespace std;
using i64 = long;
// using int = long long;
typedef pair<int, int> PII;
const int N = 4e5 + 10;
int n1;
struct vv
{
    int i1, l, r;
    bool operator<(const vv &b) const { return l < b.l; }
} w[2 * N]; // 将环形记录成链
int a[N][25];
int res[N];
int n, m, n2;

void init()
{
    cin >> n >> m;
    int i;
    for (i = 1; i <= n; ++i)
    {
        w[i].i1 = i;
        cin >> w[i].l >> w[i].r;
        if (w[i].r < w[i].l) // 如果右端点小于左端点,加上m,让成为链的时候右端点在左端点的右边
            w[i].r += m;
    }
    sort(w + 1, w + n + 1); // 根据左端点进行排序

    n2 = n * 2;
    i = n + 1;
    for (i; i <= n2; i++)//复制一份
    {
        w[i].i1 = w[i - n].i1;
        w[i].l = w[i - n].l + m;
        w[i].r = w[i - n].r + m;
    }
}

void st()
{

    int o = 1;

    for (int i = 1; i <= n2; ++i)
    {
        while (o <= n2 && w[o].l <= w[i].r)
            o++;
        a[i][0] = o - 1; // 找到左端点小于当前i的右端点且右端点最远的点
    }

    for (int i = 1; (1 << i) <= n; ++i) // i相当于从s点走了2的i次
    {

        for (int s = 1; s <= n2; ++s)
        {

            a[s][i] = a[a[s][i - 1]][i - 1]; // 公式
        }
    }
}
void solve(int x)
{
    int len = w[x].l + m, now = x, ans = 1;//len就是计划点
    for (int i = 20; i >= 0; --i)
    {
        int to = a[now][i];//如果当前点走2的i次方步存在最优点,那下一个i判断的就是从当前最优点开始走2的i次方步能否到达下一个最优点,一直到计划点
        if (to && w[to].r < len)
        {
            ans = ans + (1 << i);
            now = to;
        }
    }
    res[w[x].i1] = ans + 1;//只能加上最后一个点,如果加其他数那都证明for循环每盘玩,因为if的判断条件是小于计划点
}
int main()
{
    init();
    st();
    for (int i = 1; i <= n; ++i)
    {
        solve(i);
    }
    for (int i = 1; i <= n; ++i)
    {
        cout << res[i] << " \n"[i == n];
    }
    return 0;
}
}

标签:容器,倍增,int,输入输出,st,优点,端点,include
From: https://www.cnblogs.com/tzstlove/p/18493634

相关文章

  • ReactOS寻找病返回最小StartingAddress所在结点。
    ReactOS寻找病返回最小StartingAddress所在结点。MmIterateFirstNode()函数文章目录ReactOS寻找病返回最小StartingAddress所在结点。MmIterateFirstNodeMmIterateFirstNode/*INCLUDES*****************************************************************/#incl......
  • vscode+phpstudy+xdebug无法断点(踩坑记)
    参考文档:https://zhuanlan.zhihu.com/p/113171737安装vscode、下载phpstudy最新版这2步都不说了,网上大把教程。本文主要把phpstudy的一个坑点记录一下配置网站配置伪静态location/{if(!-e$request_filename){rewrite^(.*)$/index.php?s=$1las......
  • NewStar2024-week3-Crypto
    古典密码不想看而且最近很忙,wp就贴exp了Crypto不用谢喵fromCrypto.CipherimportAESfromCrypto.Util.numberimport*importosKEY=b"fake_key_fake_ke"FLAG="flag{fake_flag_fake_flag}"defdecrypt(c):AES_ECB=AES.new(KEY,AES.MODE_ECB)......
  • platform_device_register 和platform_driver_register;有些驱动里没有platform_device
    platform_device_register和platform_driver_register是Linux内核中用于注册平台设备和平台驱动程序的函数。为什么很多驱动里没有platform_device_register在Linux内核中,不是所有的驱动程序都需要显式调用platform_device_register函数来注册平台设备。这是因为设备驱动程序可以......
  • 【Azure Developer】System.Net.WebException: The request was aborted: Could not c
    问题描述在Azure中,使用操作系统为WinServer2019和WinServer2012的虚拟机,同样代码可以链接同一个AzureServiceBus。Win2019成功运行,但是在Win2012上报错:CouldnotcreateSSL/TLSsecurechannel. 问题解答WinServer2012默认不支持TLS1.2,可以通过安装 Update3140245 ......
  • 【Azure Developer】System.Net.WebException: The request was aborted: Could not c
    问题描述在Azure中,使用操作系统为WinServer2019和WinServer2012的虚拟机,同样代码可以链接同一个AzureServiceBus。Win2019成功运行,但是在Win2012上报错:CouldnotcreateSSL/TLSsecurechannel. 问题解答WinServer2012默认不支持TLS1.2,可以通过安装 Update314......
  • 电能表预付费系统-标准传输规范(STS)(17)
    6.4TCDUGenerationfunctions TCDU生成函数6.4.1DefinitionoftheTCDU TCDU的定义TheTCDUmaybedifferentforeachTokenCarrierTypeandisthereforedefinedseparatelyforeachphysicallayerprotocolstandardrelevanttoeachpartoftheIEC62055-5x......
  • SUST-Sustainability
    文章目录一、征稿简介二、重要信息三、服务简述四、投稿须知五、联系咨询一、征稿简介二、重要信息期刊官网:https://ais.cn/u/3eEJNv三、服务简述Sustainability是一本关于人类环境、文化、经济和社会可持续性的国际跨学科学术开放获取期刊,为可持续性和可持续发......
  • 【Elasticsearch】分布式搜索引擎技术学习[上]
    目录一.认识与了解搜索引擎1.介绍2.安装二.初步了解Elasticsearch1.倒排索引2.IK分词器3.基础概念三.Elasticsearch基础操作1.索引库操作1.1.常见映射属性1.2.索引库的·CRUD操作2.文档操作1.1.文档的CRUD操作1.2.批量处理四.ES的Java客户端1.客户端的......
  • Control Statements and Jumps
    Lab04:ControlStatementsandJumps-2024.10.15Writeaprogramthatrequeststhehoursworkedinaweekandthenprintsthegrosspay,thetaxes,andthenetpay.Assumethefollowing:Basicpayrate=$10.00/hrOvertime(inexcessof40hours)=time......