DAY5共2题:
-
储物点的距离(前缀和)
-
糖糖别胡说,我真的不是签到题目(multiset,思维)
🎈 作者:Eriktse
🎈 简介:19岁,211计算机在读,现役ACM银牌选手🏆力争以通俗易懂的方式讲解算法!❤️欢迎关注我,一起交流C++/Python算法。(优质好文持续更新中……)🚀
🎈 原文链接(阅读原文获得更好阅读体验):https://www.eriktse.com/algorithm/1096.html
储物点的距离
题目链接:https://ac.nowcoder.com/acm/problem/14683
预处理出各点搬运到点1
和点n
的代价前缀和,以及区间重量和。
假如我们要将区间[5, 7]
的物品全部搬运到3
,代价应该是区间[5, 7]
的物品全部搬运到的1
,然后减去多搬的代价:[5, 7]
的重量和 * dist(1, 3)。
上面是x 的情况,
x > r
的情况类似。
当l 只需将区间
[l, r]
分为两部分求和即可。
记得取模,距离要取模,前缀和也要取模。
#include
#define int long long
using namespace std;
const int maxn = 2e5 + 9, p = 1e9 + 7;
//sum_l[i]表示区间[1, i]的物品都运到点1的代价之和
//prefix_a[i]表示区间[1, i]的物品重量之和
//pos[i]是第i个点的位置,通过a[]作前缀和得到
int a[maxn], pos[maxn], sum_l[maxn], sum_r[maxn], prefix_a[maxn];
int n, m;
//取模函数
int mo(int x){return (x % p + p) % p;}
int f(int x, int l, int r)
{
if(l > r)return 0;
int res = 0;
if(x = r)
{
res = mo(sum_r[r] - sum_r[l - 1]);
res = mo(res - mo(pos[n] - pos[x]) * mo(prefix_a[r] - prefix_a[l - 1]) % p);
}
return res;
}
signed main()
{
scanf("%lld %lld",&n, &m);
pos[1] = 1;
for(int i = 2, d;i
糖糖别胡说,我真的不是签到题目
题目链接:https://ac.nowcoder.com/acm/problem/14583
本题有两种解法,第一种容易理解,第二种效率更优。
第一种解法:正向,multiset。
发功次数可以用一个桶来记录,让[1, i]
的所有点的属性值都+1
,相当于把后面的都-1
,用一个fix
表示偏移量。
建立两个multiset
表示两组中的糖糖,好处是可以快速找出能力值最小的,从而去除掉。
扫一遍,把第i只糖糖加入到属于它的集合中,然后将另外一个集合中已有的能力值小的糖糖进行删除,再检查此时是否有发功。
最后集合中留下的糖糖个数即为答案。
#include
#define int long long
using namespace std;
const int maxn = 1e6 + 9, inf = 8e18;
struct Node
{
int a, b;
}p[maxn];
int add[maxn];
void solve()
{
int n, m;scanf("%lld %lld",&n, &m);
memset(add, 0, sizeof(int) * (n + 2));
for(int i = 1;i st[2];
for(int i = 1;i
第二种解法:反向,思维。
我们想这么一个问题,一个糖糖x
是否会被删除取决于在x
出现之后,在另外一个集合中,是否出现了能力值高于x
的能力值的糖糖y
。
那么我们逆向遍历,维护两个集合的最值,当前的新加入的糖糖x
的能力值如果低于另外一个集合中已经存在的(即右边的)糖糖能力值的最大值,说明他后面会被某个糖糖y
删除掉,直接打上标记,但是我们不用真的删除。
糖糖x
还可以用于删除左边的另一个集合的能力值较小的糖糖。注意此时的发功应该在循环开始时进行修改。
#include
#define int long long
using namespace std;
const int maxn = 1e6 + 9, inf = 8e18;
struct Node
{
int a, b;
}p[maxn];
int add[maxn];
void solve()
{
int n, m;scanf("%lld %lld",&n, &m);
memset(add, 0, sizeof(int) * (n + 2));
for(int i = 1;i = 1; -- i)
{
fix += add[i];
int a = p[i].a, b = p[i].b + fix;
mx[a] = max(mx[a], b);
if(mx[a ^ 1] > b)cnt ++;
}
printf("%lldn", n - cnt);
}
signed main()
{
int _;scanf("%lld", &_);
while(_ --)solve();
return 0;
}
🎈 本文由eriktse原创,创作不易,如果对您有帮助,欢迎小伙伴们点赞👍、收藏⭐、留言💬
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net