牛客编程巅峰赛S2第4场
牛牛摆玩偶
题目描述
牛牛有
n
(
2
≤
n
≤
1
0
5
)
(
2
≤
n
≤
105
)
n(2 \leq n \leq 10^5)(2≤n≤105)
n(2≤n≤105)(2≤n≤105)个玩偶,牛牛打算把这n个玩偶摆在桌子上,桌子的形状的长条形的,可以看做一维数轴。 桌子上有
M
M
M 个互不相交的区间
(
1
≤
M
≤
1
0
5
)
(1≤M≤10^5)
(1≤M≤105),这些区间上面可以放玩偶。一个位置只能放一个玩偶,玩偶之间的距离越大越美观,牛牛想最大化 D 的值,其中 D 为最近的两个玩偶之间的距离。请帮牛牛求出 D 的最大可能值。
示例1
输入
5,3,[[0,2],[4,7],[9,9]]
返回值
2
备注:
区间长度
≤
2
31
−
1
\leq 2^{31} -1
≤231−1
思路:
最大最小值,最小最大值,一看就是二分。比赛中就是过不了(
90
%
90\%
90%的数据), 肯定思路没错,以为是数据错了(*^▽^*)。
思路数据没错,应该首先想到是不是时间复杂度太高,应该是judge
函数的时间复杂度高了。下次一定注意。
代码
#define ll long long
const int maxn = 2e5+10;
class Solution {
public:
bool judge(ll x, vector<pair<ll, ll> > inv, int n){
ll pos = -2e10;
for(auto in : inv){
ll l = max(pos+x, in.first);
if(l > in.second) continue;
ll t = (in.second - l) / x;
n -= (t+1);
if(n <= 0) return true;
pos = l + t*x;
}
return n <= 0;
}
int doll(int n, int m, vector<Interval>& intervals) {
vector<pair<ll, ll> > inv;
for(auto ine : intervals) {
inv.push_back({1ll * ine.start, 1ll * ine.end});
}
sort(inv.begin(), inv.end(), [](const pair<ll, ll> &a, const pair<ll, ll> &b)->bool{
return a.first < b.first;
});
ll l = 0, r = inv.back().second - inv[0].first;
ll ans = -1;
while(l <= r){
ll mid = l + (r - l) / 2;
if(judge(mid, inv, n)){
ans = mid;
l = mid + 1;
}else r = mid - 1;
}
return ans;
}
};
交叉乘
题目描述
上小学二年级的牛牛已经精通整数的加法和乘法。现在你要考考他。你先给出一个整数数组
a
1
,
a
2
,
.
.
.
,
a
n
a_1,a_2,...,a_n
a1,a2,...,an,然后每次你会给一对整数
l
,
r
(
l
≤
r
)
l,r(l≤r)
l,r(l≤r),牛牛需要算出
∑
i
=
l
r
∑
j
=
i
+
1
r
a
i
∗
a
j
\sum_{i=l}^{r} \sum_{j=i+1}^{r} a_i*a_j
∑i=lr∑j=i+1rai∗aj的值。但是牛牛算完之后你不能不确定他算得对不对,为了验证他的答案,你决定自己算一遍。
为了不输出过大的答案,假设答案为
a
n
s
ans
ans,请输出
a
n
s
%
1
,
000
,
000
,
007
ans \% 1,000,000,007
ans%1,000,000,007。
提示:
在
%
1
,
000
,
000
,
007
\%1,000,000,007
%1,000,000,007的意义下
/
2
/2
/2相当于
∗
500
,
000
,
004
*500,000,004
∗500,000,004
示例1
输入
[1,2,5,3,4],[1,4,2,5,2,2]
返回值
[41,71,0]
说明
第一个询问,l=1,r=4,ans=1*2+1*5+1*3+2*5+2*3+5*3=41;
第二个询问,l=2,r=5,ans=2*5+2*3+2*4+5*3+5*4+3*4=71;
第三个询问,l=2,r=2,ans=0。
备注:
参数
a
a
a为
v
e
c
t
o
r
<
i
n
t
>
vector<int>
vector<int>,依次为
a
1
,
a
2
,
.
.
.
,
a
n
a_1,a_2,...,a_n
a1,a2,...,an;
参数
q
u
e
r
y
query
query为
v
e
c
t
o
r
<
i
n
t
>
vector<int>
vector<int>,依次为
l
1
,
r
1
,
l
2
,
r
2
,
.
.
.
,
l
q
,
r
q
l_1,r_1,l_2,r_2,...,l_q,r_q
l1,r1,l2,r2,...,lq,rq;
n
n
n为数组
a
a
a长度,
q
q
q为询问次数。
30
%
30\%
30% 数据满足
1
<
=
n
,
q
<
=
1000
1<=n,q<=1000
1<=n,q<=1000
100
%
100\%
100% 数据满足
1
<
=
n
,
q
<
=
100000
,
1
<
=
a
i
<
=
100000
,
1
<
=
l
i
<
=
r
i
<
=
n
1<=n,q<=100000,1<=a_i<=100000,1<=l_i<=r_i<=n
1<=n,q<=100000,1<=ai<=100000,1<=li<=ri<=n
思路
没想出来,思路是听直播学的。
九九乘法表,划掉对角线,前缀和优化。
就是主对角线下面的等式之和,矩阵里对角线上面的元素和下面的元素和相同,故可以总体相加,如下图:
求和公式:
∑
i
=
l
r
∑
j
=
i
+
1
r
a
i
∗
a
j
=
(
∑
i
=
l
r
a
i
)
2
−
∑
i
=
l
r
a
i
2
2
\sum_{i=l}^{r} \sum_{j=i+1}^{r} a_{i} * a_{j}=\frac{\left(\sum_{i=l}^{r} a_{i}\right)^{2}-\sum_{i=l}^{r} a_{i}^{2}}{2}
∑i=lr∑j=i+1rai∗aj=2(∑i=lrai)2−∑i=lrai2
另外:题目中数较大。需要开long long。用到了逆元的知识。
代码
#define ll long long
const int mod = 1e9+7;
const int maxn = 2e5+10;
ll sum[maxn], mul[maxn];
class Solution {
public:
vector<int> getSum(vector<int>& a, vector<int>& query) {
sum[0] = mul[0] = 0;
for(int i = 1; i <= a.size(); i++){
sum[i] = (sum[i-1] + a[i-1]) % mod;
mul[i] = (mul[i-1] + 1ll * a[i-1]*a[i-1] % mod) % mod;
}
vector<int> ans;
for(int i = 0; i < query.size(); i+=2){
int l = query[i], r = query[i+1];
ll t = (sum[r] - sum[l-1]) % mod;
ll res = (t * t % mod - (mul[r]-mul[l-1])% mod + mod)% mod ;
res = (res * 500000004 % mod + mod) % mod;
ans.push_back(res);
}
return ans;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)