首页 > 其他分享 >[ABC362C]Sum = 0

[ABC362C]Sum = 0

时间:2024-07-14 23:07:28浏览次数:17  
标签:输出 No Sum 偏移 端点 lsum ABC362C Yes

题目大意

给定\(N\)个区间,每个区间有左端点和右端点,问从每个区间选择一个数字,使得这些数字加起来为0,如果能,输出“Yes”,并且输出这些数字,否则输出“No”,

题解

这个题如果只是输出Yes或者No,我们将所有的左端点加起来,所有的右端点加起来,这就是所有数的范围,如果这个范围内有0,则是Yes,否则就是No

输出方案呢?

假设答案的范围是\([lsum,rsum]\),可以肯定的是\(lsum \leq 0,rsum \geq 0\),如果我们想要结果取0,那么答案需要偏移\(|lsum|\)那么多,我们贪心的想,从第一个区间开始,我们尽可能多的偏移,偏移量为\(r[i]-l[i]\),如果不够的话,则偏移\(|lsum|-l[i]\),后面所有的数都不发生偏移即可,所以这个题考查贪心

标签:输出,No,Sum,偏移,端点,lsum,ABC362C,Yes
From: https://www.cnblogs.com/sdfzls/p/18302175

相关文章

  • SMU Summer 2024 第一周周报 (zhaosang)
    学到了很多,不仅仅是学习方面的,在学校学跟在家寒假对比,天差地别吧。补题的过程中收获满满,最近练习二分三分,栈队列单调栈等习题,题目不简单,努力学习中。。打比赛也是,也有打的很惨的时候,我自己需要多总结找出原因,把短板补齐。总的来说,这个星期很累,但很爽!星期一:https://www.cnblogs......
  • SMU Summer 2024 Contest Round 2 (7.9)zhaosang
    A-Ahttp://162.14.124.219/contest/1006/problem/A考查用vector画图我枚举到n==5才开始用,浪费40分钟,还是找规律太慢,得多学做题代码如下:一坨#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;constllN=1e6+8;charv[1000001];intw[10000001];ll......
  • SMU Summer 2024 Contest Round 3(7.10)zhaosang
    打的最菜一次,最惨一次,题读假了A-Ahttp://162.14.124.219/contest/1007/problem/A签到题要解决这道题,素数对,数据量不是很大,所以我们可以先预处理素数,这个偶数肯定是等于小于它的两个素数,所以只需要遍历到小于它即可,把素数存起来,然后这两个素数的和等于这个偶数,并且要求相差最小......
  • 题解:AT_abc362_c [ABC362C] Sum = 0
    很好写(15min解决)但不好讲(跟别人讲了20min)的写法QwQ……首先,咱先算出原式的范围。最小值(暂且记为\(k\))的公式就是:\[k=\sum_{i=1}^{N}L_i\]就是每一个最小可能值的和。同理,最大值(我记为\(w\))的公式就是:\[w=\sum_{i=1}^{N}R_i\]即最大可能值的和。算这玩意儿......
  • 南京大学计算理论之美 (Summer 2024)暑期学校游记
    day-nzero4338和我说有这么个暑校,报名了day0到了钟山风雨地,石头城下水南京到了南京大学(仙林校区),被硬件震撼了一波和zero4338两人互相贩卖焦虑:为啥还没预习这个,也没预习那个到了南京大学(鼓楼校区),和同学转鼓楼校区,和同学和zero4338和同学吃饭回酒店之后说预习预习,但是......
  • D2. Sum over all Substrings (Hard Version)
    原题链接题解code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;lldp[1000005]={0};voidsolve(){lln,ans=0;cin>>n;strings;cin>>s;s=""+s;//使字符串1索引化for(lli=1......
  • SMU Summer 2024 Contest Round 3
    1.To3原题链接:http://162.14.124.219/contest/1007/problem/I记录数组中除3余数的种类和个数,以及数组元素总和除3的余数,最后判断(考虑总余数为1,两个元素余数为2和总余数为2,两个元素余数为1的特殊情况)查看代码#include<bits/stdc++.h>#defineintlonglongusingnamespa......
  • SMU Summer 2024 Contest Round 2
    1.MinimumWidth原题链接:http://162.14.124.219/contest/1006/problem/C二分一行最大容量,如果check小于等于总行数就扩大,反之则缩小查看代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intn,m;inta[1000000],b[1000000];boolcheck(intx){......
  • B. Missing Subsequence Sum
    原题链接题解1.如果没有不能表示出\(k\)的限制,那么数组由一众二次方构成2.对于小于\(k\)的数,考虑\(k\)的最高位\(i\)由于\([0,i-1]\)最多为\(2^i-1\)所以可以考虑添加一个\(k-2^i\)来表示完\([1,k-1]\)内所有的数(尽管有重复)同时删掉\(2^i\)3.对于大于\(k\)......
  • P2398 GCD SUM
    原题链接题解\(ans=\sum_{i=1}^{n}i*sum[i]\)其中\(sum[i]\)为最大公约数为\(i\)的对数令\(f[i]\)为最大公约数为\(i\)的倍数的对数则有\(sum[i]=f[i]-sum[2i]-sum[3i]-...-sum[ki]\)而\(f[i]={\lfloor\frac{n}{i}\rfloor}^2\)(如果没懂请仔细阅读题目所给符号......