left_right_2022

题解

/ 注册

全部文章 / 题解（共5篇）

Codeforces 1527C.Sequence Pair Weight

题意：给定长度n的数组a[]，问所有的连续子数组中有多少对相同的数。这不就是整个a[]有多少对相同的数的变种题吗是不是叫一维数点来着？~~ 一对相同的数ai,aj，它们一共在i*(n-j+1)个子数组内出现过。根据这个直接算贡献。用mp[a[i]]维护a[i]在1-(i-1)的出现过的坐标和。这样每...

前缀和

2021-05-29

0 667

Codeforces 1520E.Arranging The Sheep

题目描述：有一块长度为n的一维地，每格地可能为空('.')也可能有一只羊('*')每次可以令一只羊左移或右移一格，当且仅当目的地是空。问最少几步能让这些羊相邻。我的做法：记所有羊的坐标为ai,维护两个值f(x)=Σ|x-ai|，sum1[x]为x及之前的羊数，sum2[x]为x及之后的羊数，定义g...

曼哈顿距离贪心数学前缀和

2021-05-29

0 625

Codeforces 1520D.Same Differences

题意描述：给定长度n的数组a[],问有多少对(i,j)满足1<=i<j<=n使得aj-ai=j-i. 对式子整理得到aj-j=ai-i. 这……根本不带掩饰的？这太经典了给b[]=a[i]-i，问有多少对相同的数？这都见过吧？用map维护1到i-1中，b[i]出现了mp[b[...

数学前缀和

2021-05-29

0 939

Codeforces 1519C.Berland Regional

题目描述：有n个人，给出所属学校和实力值，k个人才能组成一队，每个学校都按照实力值和尽可能大的方法派出队伍，问k从1~n，分别求所有学校所有队伍的实力值和。把人按照学校分开，实力值从小到大排序做前缀和，对某个学校有m个人，派出的实力值和sum[m]-sum[m%k]。累加进ans[k]即可。复杂度...

数学前缀和

2021-05-29

0 651

Codeforces 1519D.Maximum Sum of Products

题意：你可以反转a数组的至多一段区间，求最大的Σaibi 先求一个不反转的前缀和,ans=sum[n]，枚举反转区间的中心和反转区间的长度，统计反转部分的和.ans=max(ans,反转部分的和-该区间原和+sum[n]);复杂度O(n^2) ```#include<bits stdc++.h...

前缀和动态规划区间

2021-04-30

0 654