书海扬帆的博客

MO/OI双国家集训队大佬dmy出的模拟赛,文字中透露出神犇的霸气。%%%

K大和(kth.*)

题目描述

给出两个长为n的数组A,B
请你求出所有Ai+Bj (1<=i,j<=n)中第k大的值
注意:同一和出现多次时,算作多个。

格式

第一行两个正整数n,k
第二行n个数,表示 a1~an
第三行n个数,表示 b1~bn
输出一行整数,表示答案

范围与约定

对于百分之40的数据,n<=3000
对于百分之60的数据,n<=5000
对于百分之80的数据,n<=100000
对于百分之100的数据,n<=500000
$1<=K<=min(500000,n^2)$
$1<=Ai,bi<=100000000$

解题思路

由题意,同一个和出现多次时,算作多个。因此我们将A,B两数组从小到大排序。由于排序过后的数列满足单调性,所以考虑二分答案,时间复杂度$O(n \log^2 n)$.
std用的是优先队列实现,大同小异。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=500050;
int a[maxn],b[maxn];
ll n,k,ans;
inline ll check(register int x) {
ll ret=0;
for(register ll i=1;i<=n;i++) {
register ll res=upper_bound(a+1,a+n+1,x-b[i])-a-1;
ret+=res;
}
return ret;
}
int main() {
//freopen("kth.in","r",stdin);
//freopen("kth.out","w",stdout);
scanf("%lld%lld",&n,&k);
for(register ll i=1;i<=n;i++) scanf("%d",&a[i]);
for(register ll i=1;i<=n;i++) scanf("%d",&b[i]);
sort(a+1,a+n+1);
sort(b+1,b+n+1);
register int l=a[1]+b[1],r=a[n]+b[n];
register int mid;
while(l<=r) {
mid=(l+r)/2;
if(check(mid)>=k) {
r=mid-1;ans=mid;
}
else {
l=mid+1;ans=mid+1;
}
}
printf("%lld\n",ans);
return 0;
}

波动计数(wave.*)

题目描述

给定1~n到1~n的一一映射f。
定义一个有序数对(a1,a2,a3,…,ak)为一组长度为k的波动,当且仅当满足以下四点:

  1. k>=2 1<=ai<=n
  2. ai<a(i+1) 对1<=i<=k-1成立
  3. f(ai)<f(a(i+1)) 对于<=k-1的偶数i成立
  4. f(ai)>f(a(i+1)) 对于<=k-1的奇数i成立

对于所有的波动,你要求出它们的长度之和。
答案对998244353取模。

格式

第一行一个正整数n
第二行n个整数,表示f(1)~f(n)
输出一行一个整数,表示答案。

范围与约定

对于百分之40的数据,n<=15
对于百分之70的数据,n<=5000
对于百分之100的数据,n<=300000
数据保证f(1)到f(n)是1~n的排列。

解题思路

棋盘染色(color.*)

题目描述

给定n行m列的白色棋盘。
对于任意两行两列交出的四个方格,如果有三个是黑格,则可以将第四个格子免费染黑。
同时,每个格子有一个权值c。任意时刻,可以花费c的代价将这一格子染黑。
求染黑棋盘的最小代价。
由于格子数很多,我们采取这样一种方法生成权值:
$A0 = a,$
$A(i+1) = (Ai Ai b + Ai c + d) \mod p. $
其中$A(m
(i-1)+j)$为第i行j列格子的权值。

格式

输入7个正整数n,m,a,b,c,d,p
输出一行表示答案。

范围与约定

对于百分之30的数据,n,m<=5
对于百分之50的数据,n,m<=50
对于百分之80的数据,n,m<=1000
对于百分之百的数据,a,b,c,d<p<=100000 n,m<=5000

解题思路

最小生成树。

白天英语课讲到“Sharing a problem is like cutting it in half”, 不由自主想到递归实现的二分法。想到线段树里面也有这个查找函数,感觉还是挺重要的嘛,于是晚上闲来无事敲了个代码。

函数名有些长,就是二分查找的英文,不用理会;

另外要特别注意数组作为函数参数的时候是以指针形式传进去的。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdlib>
#include <cstdio>

using namespace std;
int a[1000010];
int binarysearch(int *a,int n,int left,int right){
if(left>right) return -1;
int mid=(left+right)/2;
if(a[mid]==n) return mid;
else if(a[mid]<n) return binarysearch(a,n,mid+1, right);
else return binarysearch(a,n,left,mid-1);
}
int main() {
for(int i=1;i<=1000005;i++) a[i]=i;
int n;
cin>>n;
cout<<binarysearch(a,n,1,1000000);
return 0;
}



本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:730.1k