投稿
  1. 首页
  2. C

2022-04-01每日刷题打卡

code • 2022-4-2 • C • 阅读 86

2022-04-01每日刷题打卡,第1张

2022-04-01每日刷题打卡 代码源——每日一题 Lusir的游戏 - 题目 - Daimayuan Online Judge

Lusir 正在玩一个古老的基于 DOS 的游戏。


游戏中有 N+1 座建筑——从 0 到 N 编号，从左到右排列。


编号为 00 的建筑高度为 00 个单位，编号为 i 的建筑高度为 H(i) 个单位。


起初，Lusir 在编号为 0 的建筑处。


每一步，它跳到下一个（右边）建筑。


假设 Lusir 在第 k个建筑，且它现在的能量值是 E，下一步它将跳到第 k+1 个建筑。


如果 H(k+1)>E，那么 Lusir就失去 H(k+1)−E 的能量值，否则他将得到 E−H(k+1) 的能量值。


游戏目标是到达第 N 个建筑，在这个过程中能量值不能为负数个单位。


现在的问题是 Lusir 至少以多少能量值开始游戏，才可以保证成功完成游戏？

输入格式

第一行输入整数 N。


第二行是 N 个空格分隔的整数，H(1),H(2),…,H(N) 代表建筑物的高度。


输出格式

输出一个整数，表示所需的最少单位的初始能量值上取整后的结果。


数据范围

1≤N,H(i)≤10^5

输入样例1：

5
3 4 3 2 4

输出样例1：

4

贪心做法：

题目说要最初始能量最低，那么到达终点时所剩能量应该是0（能省则省）
然后每跳一格，能量变化为：（e是下一层所剩能量，E是当前能量，H是下一层的高）

下一层高度大于E时：e-=H-E
下一层高度小于E时：e+=E-H
其实这里就可以看出来，到达下一层的能量变化就是e=E+(E-H)，只是根据下一层高度的不同括号里的结果分正负罢了。



那么我们就可以根据：到达末尾能量为0和能量变化式e=E+(E-H)来进行反向 *** 作，根据当前层剩的能量反向求上一层的能量，此时能量变化式变为了：E=(e+H)/2,但为了向上取整，我们给分式加上1，即E=(e+H+1)/2。



此时问题就变成了：到达最后一层时能量为0，问最初开始时能量是多少。



然后我们就可以从末尾出发，根据E=(e+H+1)/2一步步求上一层时能量，最后得到的结果就是开始时所需的最少能量。


（但是当你用得到的能量正着求的时候会发现，到达终点并不是0，这是因为有前面的楼的高度做影响，我们要保证的是到达下一个楼高度后的能量最少，这个剩余的能量必须要足够我们跳到下下个楼去，同时到下下个楼的时候我们要保证剩余的能量要能跳到下下下个楼。


以此类推，而当我们跳到最后一个楼的时候，我们不用继续往下跳了，所以剩的能量可以是0。


）

#include
using namespace std;
#include
int main()
{
    //e是能量到达最后一层剩的能量
    int n,e=0;
    cin>>n;
    vectorv(n);
    for(int i=0;i>v[i];
    //e是下一层时剩的能量，E是当前层能量，h是下一层的高
    //e=E+(E-h) ——> e=2E-h ——> E=(e+h)/2 ——>(为了向上取整我们将分数式+1）E=(e+h+1)/2
    //此时逆推，E就是上一层能量，e是当前能量
    for(int i=n-1;i>=0;i--)
    {
        e=(e+v[i]+1)/2;
    }
    cout<

二分答案：

我们可以从1到1e6区间二分答案，每次去中间值看能否到达末尾，如果能到达说明这个能量还能少，我们去左区间继续找；如果到达不了说明能量不够，我们去右边继续找。


为什么是上限是1e6?因为当你能量能大于当前高度数组的最大值时，你的能量就会一直增加了，而这题数据范围高度最多是1e5,所以我们取个1e6就可以。


但有一点要注意的是，因为当你能量x大于当前高度时，你的能量会加上x-h。


这样如果你的初始能量过大，而且数组里的元素都远小于你时，相当于每跳一次你的能量就翻倍，数组最多有1e5项，那么你的能量就可能会过大而爆掉long long，这样会使得我们的结果有误差。


所以要加一个特判，就像我们上面说的，当你的能量大于当前高度数组的最大值时，你的能量就会一直增加了。


所以我们可以一开始先找到数组的最大值，然后当我们枚举的能量大于这个最大值时，就说明这个能量过大了，我们可以找更小的。


#include
using namespace std;
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define endl '\n';
typedef long long ll;
typedef pairPII;
int mx = 0;
bool check(ll x, vector& v, int n)
{
    for (int i = 0; i < n; i++)
    {
        x = x + (x - v[i]);
        if (x < 0)return false;

        if (x > mx)return true;
    }
    return true;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, e = 0;
    cin >> n;
    vectorv(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        mx = max(mx, v[i]);
    }
    int l = 0, r = 1e6;
    while (l < r)
    {
        ll mid = (l + r) / 2;
        if (check(mid,v,n))r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}
洛谷——线段树 P3368 【模板】树状数组 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述

如题，已知一个数列，你需要进行下面两种 *** 作：

  1. 将某区间每一个数数加上 x*；
  2. 求出某一个数的值。


输入格式

第一行包含两个整数 N*、*M，分别表示该数列数字的个数和 *** 作的总个数。


第二行包含 N 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值。


接下来 MM 行每行包含 2 或 4个整数，表示一个 *** 作，具体如下：

*** 作 11： 格式：1 x y k 含义：将区间 [x,y] 内每个数加上 k；

*** 作 22： 格式：2 x 含义：输出第 xx 个数的值。


输出格式

输出包含若干行整数，即为所有 *** 作 2 的结果。


输入输出样例

输入 #1

5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4

输出 #1

6
10

昨天的打卡笔记我们说了带懒惰标记的线段树，可以做到区间修改和区间求和。


但这次是区间修改和单点求值。


这里就要用到一个新的 *** 作：标记下传。


昨天的时候说了，我们可以通过给管理一段区间的父节点打上一个懒惰标记，来做到logn的复杂度内把区间的点都加上k。


但是此时那些点的值并没有被修改。


所以如果我们单点求值时就会暴露了。


此时我们就可以把父节点的懒惰标记下传给孩子。


区间修改的时候，我们仍然是给父节点打上标记。


此时还不下传给孩子，当我们单点查询时，再把标记下传给孩子，这样就方便了很多。


下传标记时，我们把当前父节点的标记赋给两个孩子的标记数组：lz[k+k+1]+=lz[k]、lz[k+k]+=lz[k]。


同时把当前父亲节点的标记清空。


就这样一层层往下传。


当到底的时候，我们把lz标记加到叶节点上，再把lz清空，这样就做到了修改+查询。


要注意的是，此过程还要更新父节点的值。


更新的方法就和建造树时一样。


#include
using namespace std;
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define endl '\n';
typedef long long ll;
typedef pairPII;
ll n, m, a[500050], f[2000050],lz[2000050];

void buildtree(int k, int l, int r)
{
    if (l == r)
    {
        //到达叶节点后把值赋给树状数组
        f[k] = a[l];
        return;
    }
    int m = (l + r) / 2;
    //以m为中点分成左右
    buildtree(k + k, l, m);//左
    buildtree(k + k + 1, m + 1, r);//右
    f[k] = f[k + k] + f[k + k + 1];//父节点值是两个子节点的和
}

void add(int k, int l, int r, int x, int y, ll c)
{
    if (l == x && y == r)
    {
        lz[k] += c;
        return;
    }
    f[k] += (y - x + 1) * c;
    int m = (l + r) / 2;
    if (y <= m)
        add(k + k, l, m, x, y, c);
    else
        if (x > m)add(k + k + 1, m+1, r, x, y, c);
        else
        {
            add(k + k, l, m, x, m, c);
            add(k + k + 1, m + 1, r, m + 1, y, c);
        }
}

ll calc(int k, int l, int r, int x)
{
    if (l == r)
    {
        f[k] += lz[k];
        lz[k] = 0;
        return f[k];
    }
    lz[k + k] += lz[k];
    lz[k + k + 1] += lz[k];
    lz[k] = 0;
    int m = (l + r) / 2;
    if (x <= m)
        return calc(k + k, l, m, x);
    else
        return calc(k + k + 1, m + 1, r, x);
    f[k] = f[k + k] + f[k + k + 1];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)cin >> a[i];
    buildtree(1, 1, n);
    while (m--)
    {
        int t;
        cin >> t;
        if (t == 1)
        {
            int x, y, c;
            cin >> x >> y >> c;
            add(1, 1, n, x, y, c);
        }
        else
        {
            int x;
            cin >> x;
            cout << calc(1, 1, n, x) << endl;
        }
    }
    

    return 0;
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/562764.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-02
下一篇 2022-04-02

发表评论

登录后才能评论

评论列表（0条）

保存