首页 > 其他分享 >牛客练习赛108

牛客练习赛108

时间:2023-05-26 13:45:31浏览次数:50  
标签:练习赛 int res pos update 牛客 108 num query

风间

分析:

暴力

实现:

int a[N], b[N];
void solve()
{
    res = 0;
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &b[i]);
 
    for (int i = 1; i <= n; i++)
    {
        if (abs(a[i] - b[i]) & 1)
        {
            puts("-1");
            return;
        }
        res += abs(a[i] - b[i]) / 2;
        int t = a[i] - b[i];
        if (i == n && t != 0)
        {
            puts("-1");
            return;
        }
        if (t == 0)
            continue;
        else if (t > 0)
            a[i + 1] += t;
        else if (t < 0)
            a[i + 1] += t;
               }
    printf("%lld\n", res);
}

梦迹

分析:

快速求出数组中满足 x + num ≤ w 的num的个数,树状数组维护前缀和
(数组中有0,加偏移量处理)

实现:

int tr[N], a[N];
int lowbit(int x)
{
    return x & -x;
}
void update(int x, int c) // 位置x加c
{
    for (int i = x; i <= N; i += lowbit(i))
        tr[i] += c;
}
int query(int x) // 返回前x个数的和
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i))
        res += tr[i];
    return res;
}
void solve()
{
    cin >> n >> q >> w;
    w += 2;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i]++;
        update(a[i], 1);
        res += query(w - a[i]);
    }

    for (int i = 1, pos, x; i <= q; i++)
    {
        cin >> pos >> x;
        x++;
        int num = a[pos];
        res -= query(w - num);
        update(a[pos], -1);
        a[pos] = x;
        update(x, 1);
        res += query(w - x);
        cout << res << endl;
    }
}

标签:练习赛,int,res,pos,update,牛客,108,num,query
From: https://www.cnblogs.com/Aidan347/p/17255384.html

相关文章

  • error C1083: 无法打开包括文件:“dxsdkver.h”: No such file or directory
    参考1:https://www.cnblogs.com/AI-Algorithms/p/3778527.html参考2:https://learn.microsoft.com/zh-cn/windows/win32/directx-sdk--august-2009-?redirectedfrom=MSDN参考3:https://www.microsoft.com/en-us/download/details.aspx?id=6812......
  • maximum clique 1 (牛客多校) (转化为图论, 二分图的最大独立集)
    题面大意:给出N个数, 找出最大的子集size使得子集中,任意2个数的二进制下,每一位,至少有2位不同 思路:N只有5000,可以直接暴力建边,转化位图论2种建边方式:一种是能在一个集合的2个数,建一条边,(没有办法去处理这个问题)一种是不能在一个集合的就建一条......
  • 1080. 根到叶路径上的不足节点
    给你二叉树的根节点root和一个整数limit,请你同时删除树中所有不足节点,并返回最终二叉树的根节点。假如通过节点node的每种可能的“根-叶”路径上值的总和全都小于给定的limit,则该节点被称之为不足节点,需要被删除。叶子节点,就是没有子节点的节点。来源:力扣(LeetCode......
  • 力扣---1080. 根到叶路径上的不足节点
    给你二叉树的根节点root和一个整数limit,请你同时删除树中所有不足节点,并返回最终二叉树的根节点。假如通过节点node的每种可能的“根-叶”路径上值的总和全都小于给定的limit,则该节点被称之为不足节点,需要被删除。叶子节点,就是没有子节点的节点。 示例1:输入:r......
  • subsequence1 (牛客多校) (2个串比大小, DP, 组合数)
    题面大意:给定2个字符串,问有多少个子字符串S,是大于t的 思路数据范围很小,因此考虑n^2做法分2步,位数s>位数t的时候然后位数相等的时候利用DP,处理,分别就是枚举前k个数和s相同,然后k+1个数比t大就可以. 具体思路自己想想,和那个比较像   cons......
  • 1086 Tree Traversals Again
    题目:Aninorderbinarytreetraversalcanbeimplementedinanon-recursivewaywithastack.Forexample,supposethatwhena6-nodebinarytree(withthekeysnumberedfrom1to6)istraversed,thestackoperationsare:push(1);push(2);push(3);pop();......
  • 刷题笔记:Luogu P1083 借教室
    题目传送门让结果最接近\(s\)值,显然我们要二分\(w\),check的写法可以直接暴力模拟,如果check(mid)<s则将r右移(通过读公式可以知道\(w\)越小检验值\(y\)就越大)但是这样会TLE,再读一下柿子:\(y_i=\sum\limits_{j=l_i}^{r_i}[w_j\geW]\times\sum\limits_{j=l_i}^{r_i}[w_j\geW]......
  • apio 练习赛 t3
    题意有\(N\)个化学药品,其中有\([1,K]\)个药品内有杂质。你可以进行\(M\)次操作,第\(i\)次你可以放进去一些化学药品,然后机器会返回这里面是否有药品中有杂质。你的操作序列必须是固定的。并且你在固定策略后,有\(T\)组测试,每组测试会告诉每次操作的结果,你都要返回哪些......
  • 【牛客小白72】E 二分答案
    https://ac.nowcoder.com/acm/contest/56825/E题意给你\(10^{10}\)个数(数组an个数,数组bm个数,数是a*b的集合),有\(Q\)(Q为常数)个询问,每次问你第\(x\)小的数是多少思路最暴力的思路肯定是把所有数放在一起,然后排序。易知时间复杂度为\(nlogn(n=1e10)\),会超时。继续思......
  • MX5108n
    DellMX7000的交换机MX5108n有1个40G,两个100G和4个10G接口1-8为内部25G口940G10、11100G12-1510G命令和思科的差不多查看vlt:showvlt100showvlt100vlt-port-detail查看网口配置:showinterfaceethernet1/1/10貌似这个QSFP28模块由于兼容性问题被认为是40G…正常来说应......