程序员经验分享-hwhale

Codeforces Round #367 (Div. 2)【贪心、差分、DP、字典树、二维链表】

2023-11-10

Codeforces Round #367 (Div. 2)

A. Beru-taxi

  就是问，我们知道一个点，从其他点到它的最少花费的时间是多少？

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 1e3 + 7;
double sx, sy;
double ans = 1000000000.;
double x, y, v;
double dis(double x1, double y1, double x2, double y2)
{
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
int main()
{
    scanf("%lf%lf", &sx, &sy);
    int N; scanf("%d", &N);
    for(int i=1; i<=N; i++)
    {
        scanf("%lf%lf%lf", &x, &y, &v);
        ans = min(ans, dis(sx, sy, x, y) / v);
    }
    printf("%lf\n", ans);
    return 0;
}

 

B. Interesting drink

  问小于等于某个数的数有多少个，我的做法是O(N)的差分，树状数组等等都是可以搞的，差分显得快一点（因为值的大小小的缘故吧）。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 1e5 + 7;
int N, a[maxN], q, mi, num[maxN];
int main()
{
    scanf("%d", &N);
    for(int i=1; i<=N; i++)
    {
        scanf("%d", &a[i]);
        num[a[i]]++;
    }
    for(int i=1; i<maxN; i++) num[i] += num[i - 1];
    scanf("%d", &q);
    while(q--)
    {
        scanf("%d", &mi);
        if(mi >= maxN) printf("%d\n", N);
        else printf("%d\n", num[mi]);
    }
    return 0;
}

 

C. Hard problem

  简单的DP，但是别忘了条件是等于也算是合法的。

也就是"a == a"也是认为是可行的。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 1e5 + 7;
int N;
ll c[maxN];
string s[maxN], t[maxN];
struct DO_it
{
    ll dp[maxN][2];
    inline void init()
    {
        for(int i=1; i<=N; i++) dp[i][0] = dp[i][1] = INF;
        dp[1][0] = 0;
        dp[1][1] = c[1];
    }
    void solve()
    {
        init();
        for(int i=2; i<=N; i++)
        {
            if(s[i] >= s[i-1]) dp[i][0] = dp[i-1][0];
            if(s[i] >= t[i-1]) dp[i][0] = min(dp[i][0], dp[i-1][1]);
            if(t[i] >= s[i-1]) dp[i][1] = dp[i-1][0] + c[i];
            if(t[i] >= t[i-1]) dp[i][1] = min(dp[i][1], dp[i-1][1] + c[i]);
        }
        if(dp[N][0] >= INF && dp[N][1] >= INF) printf("-1\n");
        else printf("%lld\n", min(dp[N][0], dp[N][1]));
    }
}kk;
int main()
{
    scanf("%d", &N);
    for(int i=1; i<=N; i++) scanf("%lld", &c[i]);
    for(int i=1; i<=N; i++)
    {
        cin >> s[i];
        t[i] = s[i];
        reverse(t[i].begin(), t[i].end());
    }
    kk.solve();
    return 0;
}

 

D. Vasiliy's Multiset

  简单的字典树了。

题意：

有如下三种操作：

  1. "+ x"向堆中加入值为x的值；
  2. "- x"从堆中减去一个值为x的元素，保证x在堆中；
  3. "? x"询问堆A中与x异或值最大的数的值是多少，输出最大值。

然后就是字典树的一般操作了，可惜卡C卡了点时间，赛后十分钟才写完。

  记住一种特殊情况，如果你没往堆中放0，堆中也是有0的。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 8e6 + 7;
int Q;
int x;
char op[3];
int tot = 0, waste[maxN], inwast = 0;
struct node
{
    int nex[2], num;
    node(int a=0, int b=0, int c=0):nex{a, b}, num(c) {}
    void init() { nex[0] = nex[1] = 0; num = 0; }
}trie[maxN];
void Insert(int x)
{
    int root = 0;
    for(int i=31, id; i>=0; i--)
    {
        id = (x >> i) & 1;
        if(!trie[root].nex[id])
        {
            if(inwast) trie[root].nex[id] = waste[inwast--];
            else trie[root].nex[id] = ++tot;
            trie[trie[root].nex[id]].init();
        }
        root = trie[root].nex[id];
        trie[root].num++;
    }
}
void del(int x)
{
    int root = 0, nex;
    for(int i=31, id; i>=0; i--)
    {
        id = (x >> i) & 1;
        nex = trie[root].nex[id];
        if(--trie[nex].num == 0)
        {
            trie[root].nex[id] = 0;
            waste[++inwast] = nex;
        }
        root = nex;
    }
}
int fid(int x)
{
    int root = 0, ans = 0;
    for(int i=31, id; i>=0; i--)
    {
        id = (x >> i) & 1;
        if(trie[root].nex[!id])
        {
            ans |= (1 << i);
            root = trie[root].nex[!id];
        }
        else root = trie[root].nex[id];
    }
    return ans;
}
int main()
{
    scanf("%d", &Q);
    Insert(0);
    while(Q--)
    {
        scanf("%s%d", op, &x);
        if(op[0] == '+')
        {
            Insert(x);
        }
        else if(op[0] == '-')
        {
            del(x);
        }
        else
        {
            printf("%d\n", fid(x));
        }
    }
    return 0;
}

 

E. Working routine

  可以说是一道模拟题了，写了有些时候，可能是太菜了吧…… 

  题意：给出一个原始矩阵，之后有Q次操作，我们将两个矩阵交换位置，题目中保证两个矩阵不相交，给出的是两个矩阵的左上方的端点，以及它们对应的高和宽。

  思路：很明显，题目中只有最多1e4次操作，矩阵的边最大也才不过是1e3，所以很明显的，我们可以O(1e4 * 1e3 * 常数)的“暴力”来解决问题了。

  首先，初始化二维链表，我们定义用新的一圈来包围这个子矩阵，相当于是防止溢出了，并且还保护了链首。

  然后的话，我们就是要去避免冲突了，我们的更新过程一定是需要有目的的，不然会造成冲突，譬如说这样的一个样例：

3 3 4
1 2 3
4 5 6
7 8 9
3 1 3 3 1 1
3 2 1 3 1 1
2 1 3 2 1 1
3 2 1 1 1 1

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 1e3 + 7;
int N, M, Q, v[maxN][maxN];
struct List_Table
{
    int down, right, val;
    List_Table(int b=0, int d=0, int f=0):down(b), right(d), val(f) {}
}t[maxN * maxN];
inline int _id(int x, int y) { return x * (M + 2) + y; }
inline void init()
{
    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=M; j++)
        {
            t[_id(i, j)] = List_Table(_id(i + 1, j), _id(i, j + 1), v[i][j]);
        }
    }
    for(int i=1; i<=M; i++)
    {
        t[_id(0, i)] = List_Table(_id(1, i), _id(0, i + 1));
    }
    t[_id(0, 0)] = List_Table(_id(1, 0), _id(0, 1));
    t[_id(0, M + 1)] = List_Table(_id(1, M + 1), 0);
    for(int i=1; i<=N; i++)
    {
        t[_id(i, 0)] = List_Table(_id(i + 1, 0), _id(i, 1));
    }
    t[_id(N + 1, 0)] = List_Table(0, _id(N + 1, 1));
    for(int i=1; i<=N; i++)
    {
        t[_id(i, M + 1)] = List_Table(_id(i + 1, M + 1), 0);
    }
    t[_id(N + 1, M + 1)] = List_Table(0, 0);
    for(int i=1; i<=M; i++)
    {
        t[_id(N + 1, i)] = List_Table(0, _id(N + 1, i + 1));
    }
}
inline void ex_change(int sx, int sy, int ex, int ey, int h, int w)
{
    int id_1 = _id(sx - 1, 0), id_2 = _id(ex - 1, 0), tims = sy - 1, tmp_1, tmp_2;
    while(tims --) id_1 = t[id_1].right;
    tims = ey - 1;
    while(tims --) id_2 = t[id_2].right;
    tmp_1 = id_1; tmp_2 = id_2;
    for(int i=1; i<=h; i++)
    {
        id_1 = t[id_1].down; id_2 = t[id_2].down;
        swap(t[id_1].right, t[id_2].right);
    }
    for(int i=1; i<=w; i++)
    {
        id_1 = t[id_1].right; id_2 = t[id_2].right;
        swap(t[id_1].down, t[id_2].down);
    }
    for(int i=1; i<=w; i++)
    {
        tmp_1 = t[tmp_1].right; tmp_2 = t[tmp_2].right;
        swap(t[tmp_1].down, t[tmp_2].down);
    }
    for(int i=1; i<=h; i++)
    {
        tmp_1 = t[tmp_1].down; tmp_2 = t[tmp_2].down;
        swap(t[tmp_1].right, t[tmp_2].right);
    }
}
inline void Prit()
{
    for(int i=1, now, cnt; i<=N; i++)
    {
        now = t[_id(i, 0)].right;
        cnt = M;
        while(cnt--)
        {
            printf("%d ", t[now].val);
            now = t[now].right;
        }
        printf("\n");
    }
}
int main()
{
    scanf("%d%d%d", &N, &M, &Q);
    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=M; j++)
        {
            scanf("%d", &v[i][j]);
        }
    }
    init();
    int sx, sy, ex, ey, h, w;
    while(Q--)
    {
        scanf("%d%d%d%d%d%d", &sx, &sy, &ex, &ey, &h, &w);
        ex_change(sx, sy, ex, ey, h, w);
//        Prit();
    }
    Prit();
    return 0;
}

 

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Codeforces

Codeforces Round #367 (Div. 2)【贪心、差分、DP、字典树、二维链表】 的相关文章

随机推荐

  • 深度学习总结——用自己的数据集微调CLIP

    CLIP概述 CLIP Contrastive Language Image Pretraining 是由OpenAI开发的一种深度学习模型 用于将图像和自然语言文本进行联合编码 它采用了多模态学习的方法 使得模型能够理解图像和文本之间的语

  • lbs、agps流程

    AT指令流程 CTZV 19 1 8 8 59 6 23 CIEV service 1 CIEV roam 0 CREG 1 AT CGDCONT 1 IP cmnet AT CGDCONT 1 IP cmnet OK AT CGACT 1

  • RTC和RTMP

    RTC 直播发布流程 offer answer 模型 直播订阅流程 1 使用UDP私有协议来进行媒体拉流 2 适用高互动性的直播场景 如在线教育 电商直播 远程医疗 3 低延时 lt 300ms 和无卡顿 4 快速切换分辨率 无需写上 服务

  • 在多线程中使用tensorRT

    仅记录 转自https www coder work article 4985246 import pycuda autoinit Create CUDA context import pycuda driver as cuda Main

  • Ubuntu ssh连接access deny

    一 尝试了修改配置的方法 不能解决问题 1 修改ssh配置文件vim etc ssh sshd config 设置为允许root远程登录 2 找到PermitRootLogin prohibie password 修改为 PermitRoo

  • windows11 使用 wsl2 安装 archLinux

    windows11 使用 wsl2 安装 archLinux 下载 archLinux 下载 tar gz 文件 下载地址 https mirrors tuna tsinghua edu cn archlinux iso latest 启用

  • 编译ROCKSDB总结

    Rocksdb是挺好的一个东西 就是取得一个可用的库太麻烦 之前我是用的rocksdbsharp里面他有编译好windows 和 linux的库 兼 容性还挺好 ubuntu win10 直接跑没毛病 可惜他是去年build的了 我要用的c

  • C++ - 强引用和弱引用

    原来 我认为 为什么会有引用计数这样的技术 是为了内存自动回收和节省内存 但是读完下面的几节后 内存自动回收是一个原因 但是节省内存并不是真正的原因 真正的原因是有些对象如果被复制在现实中是不合事实的 为什么有引用计数 C 中存在两种语义

  • vite vue3 规范化与Git Hooks

    优质资源分享 学习路线指引 点击解锁 知识定位 人群定位 Python实战微信订餐小程序 进阶级 本课程是python flask 微信小程序的完美结合 从项目搭建到腾讯云部署上线 打造一个全栈订餐系统 Python量化交易实战 入门级 手

  • 在Windows Server2016中安装SQL Server2016

    SQL Server2016安装硬 软件条件 点击打开链接 WinServer2016的安装参见 在虚拟机中安装Windows Server2016 1 SQL Server2016下载地址 1 SQL Server2016安装包 2016

  • SuperPunch - unity3D拳击小游戏项目源码

    SuperPunch是一个完整的项目 准备发布并且适合移动设备 它包含构建顶头拳击游戏的所有必要内容 特征 移动友好的纹理 分层的 包括 SVG 文件 包括 PNG文件 包括 C 脚本 包括文档 包括6架战斗机 包括战士动画 闲置 拳击 受

  • QChart入门教程-绘制正弦曲线

    1 创建界面 将widget作为容器进行绘图 并将widget提升为QChartView类 1 1 单击widget 右键中选择 提升 提升的类名称中填写 QChartView 会自动生成头文件名 选择 添加 将类和头文件添加进要提升的类中

  • ElasticSearch第十八讲 ES-Master节点职责和ES是如何做到数据实时性的

    Elasticsearch Master 节点的职责 由主节点负责ping 所有其他节点 判断是否有节点已经挂掉 创建或删除索引 决定分片在节点之间的分配 稳定的主节点对集群的健康是非常重要的 虽然主节点也可以协调节点 路由搜索和从客户端新

  • 6.84 C++ 遍历数组的几种方式

    1 计算出数组长度进行遍历 数组类型确定 数组中每个元素本身的字节大小就已经确定 利用 sizeof 函数可以计算出数组长度 而后利用 for 循序进行数组的遍历 2 使用类似 foreach 的方式进行遍历 C 中也可使用类似 forea

  • AVI文件与WAV文件格式

    AVI 与WAV文件都属于RIFF文件 因此都遵循RIFF文件的格式要求 先看看RIFF文件的格式 第一 RIFF 大小 AVI WAV 数据 第二 RIFF 文件中实际的数据通常采用列表 list 和块 Chunk 的形式表示 列表结构为

  • 智能门锁电路图_蓝牙门锁原理图一览 蓝牙智能门锁工作原理介绍

    蓝牙智能门锁工作原理是什么 蓝牙门锁原理图步骤详解 蓝牙智能门锁主要是通过手机开锁的方式来解锁 相比传统门锁 蓝牙门锁更加便捷 此外 还可以通过手机APP来实现门锁实时管理 访客管理 是符合智能家居时代对门锁要求的电子产品 那么蓝牙智能门锁

  • tesseract api C++使用例子

    转自 https code google com p tesseract ocr wiki APIExample APIExample API examples Updated Aug 12 2014 by theraysm gmail c

  • unsigned int 和 signed int 的区别

    unsigned int 和 signed int 的区别 对于 int 类型 默认是带有正负号的 也就是说 int 等同于 signed int signed int 等同于int 都能表示正负数 1 signed int 可以表示正整数

  • SQL优化之LIMIT语法, limit n,m 和 limit n有什么区别？

    在某些面试题中会遇到这样的问答或笔试题 limit 0 1 和 limit 1有什么区别 要准确回答这个问题就等深入明白limit一个参数和两个参数的本质区别 limit n m 中的第一次参数n表示的游标的偏移量 初始值为0 第二个参数m

  • Codeforces Round #367 (Div. 2)【贪心、差分、DP、字典树、二维链表】

    Codeforces Round 367 Div 2 A Beru taxi 就是问 我们知道一个点 从其他点到它的最少花费的时间是多少 include

热门标签