首页 > 其他分享 >B - Christmas Trees

B - Christmas Trees

时间:2023-12-30 19:11:08浏览次数:42  
标签:diffr numr LL Trees abs numl Christmas diffl

B - Christmas Trees

https://atcoder.jp/contests/abc334/tasks/abc334_b

 

思路

对于起始种树点A 在 [L, R]区间的位置情况,三种

A < L

A> R

A>=L, A<=R

 

Code

https://atcoder.jp/contests/abc334/submissions/48822474

LL a, m, l, r;

int main()
{
    cin >> a >> m >> l >> r;
    
    
    if (a < l){
        LL diffl = abs(l - a);
        LL numl = diffl / m;
        if (diffl % m == 0){
            numl--;
        }
//        assert(1);

        LL diffr = abs(r - a);
        LL numr = diffr / m;

        LL total = numr - numl;
        cout << total << endl;

        return 0;
    }
    else if (a > r){
        LL diffl = abs(a - l);
        LL numl = diffl / m;

        LL diffr = abs(a - r);
        LL numr = diffr / m;
        if (diffr % m == 0){
            numr--;
        }

        LL total = numl - numr;
        cout << total << endl;

        return 0;
    }
    else
    {
        LL diffl = abs(a - l);
        LL numl = diffl / m;

        LL diffr = abs(r - a);
        LL numr = diffr / m;

        LL total = numr + numl + 1;
        cout << total << endl;
        
        return 0;
    }
    

    return 0;
}

 

标签:diffr,numr,LL,Trees,abs,numl,Christmas,diffl
From: https://www.cnblogs.com/lightsong/p/17936675.html

相关文章

  • [ABC334E] Christmas Color Grid 1 题解
    题目传送门一道dfs题。先统计出绿连通块数量,然后对于每个红色方块统计涂成绿色方块后会变成多少个连通块。正常涂成绿色后应该会增加一个大小为\(1\)的绿连通块,但若是有不同的绿连通块与其相邻,答案又会减少\(1\)。Code#include<bits/stdc++.h>constlonglongIMX=1......
  • AtCoder Beginner Contest 334 G Christmas Color Grid 2
    洛谷传送门AtCoder传送门考虑相当于把每个标记点的边全部断掉,然后求连通块个数。考虑一条边\((u,v)\)(设\(u<v\))的出现时间,不难发现是\([1,u-1]\cup[u+1,v-1]\cup[v+1,n]\)。于是考虑直接套线段树分治和可撤销并查集。时空复杂度均为\(O(n^2\logn)\)......
  • 题解 ABC334G【Christmas Color Grid 2】
    先求出初始时绿连通块数量。将一个绿色格子染成红色,会改变绿连通块数量,当且仅当这个绿色格子是孤点或割点。如果是孤点,会使得绿连通块数量减少一;如果是割点,会使得绿连通块数量增加它所在的点双数量减一。根据上述规则可以求出每个绿色格子染红后的绿连通块数量,求平均值即可。时......
  • 题解 ABC334F【Christmas Present 2】
    设\(f_i\)表示假设只有编号为\(1\simi\)的点,此时的答案。\(f_n\)即为所求。显然有:\[f_i=\min\limits_{i-k\lej<i}\{f_j+dis(s\toj+1\toj+2\to\cdots\toi)\}+dis(i\tos)\]当\(i\toi+1\)时,大括号内部全局增加\(dis(i\toi+1)\),可以全局打标记后单调队列维护。......
  • 题解 ABC334E【Christmas Color Grid 1】
    先求出初始时绿连通块数量。枚举每个红色格子,将其染成绿色本应增加一个绿连通块,但是它每与一个绿连通块相邻,就又会减少一个绿连通块。根据上述规则可以求出每个红色格子染绿后的绿连通块数量,求平均值即可。时间复杂度\(O(nm)\)。//Problem:E-ChristmasColorGrid1//Co......
  • CodeForces 1902F Trees and XOR Queries Again
    洛谷传送门CF传送门如果我们能把\(x\toy\)路径上的所有点权插入到线性基,那么可以\(O(\logV)\)查询。但是因为线性基合并只能\(O(\log^2V)\)(把一个线性基的所有元素插入到另一个),所以只能倍增做\(O((n+q)\logn\log^2V)\),过不了。考虑\(O(n\logV)\)预处理出......
  • 【JavaSE】集合Collection{List(ArrayList, LinkedList), Set(TreeSet, HashSet, Link
    集合单列集合:Collection接口单列集合:一次添加一个元素;如果集合中添加的是类,要重写equals方法,否则比较的是地址,无法正常删除内容相同的元素。单列集合通用遍历方式1.迭代器遍历2.增强for循环遍历增强for循环底层逻辑还是迭代器,字节码文件反编译为java会发现还是迭代......
  • 【题解】CodeForces 1902F Trees and XOR Queries Again
    传送门:https://codeforces.com/contest/1902/problem/F数据结构题,这里讲两种思路。$ST$表思路:判定“从若干个数中能否取出其中一些,使得异或和为$x$”的问题,第一时间想到线性基,本题要做的显然就是快速求出询问路径上所有数的线性基。两组数的线性基可以合并,方法为“暴力将......
  • F. Trees and XOR Queries Again
    首先容易想到lca+线性基,\(O(nlognB^2+qlognB^2)\),显然T飞了。#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<map>#include<vector>#include<set>#include<iostream>#include<queue>#i......
  • vue-treeselect使用案例
    https://vue-treeselect.js.org/父子节点没有关联<TreeSelectflatstyle="background-color:#0e3977"placeholder="请选择"v-model="org":multiple="true":options="state.orgData&qu......