[20180908]邓神模拟赛 题解

国家集训队大佬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用的是优先队列实现,大同小异。

#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的排列。

解题思路

dp。

\color{black}dp[i][j] = \sum\limits_{k < i,f\left( {{a_k}} \right) < f\left( {{a_i}} \right)} {dp[k][j – 1].}

棋盘染色(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

解题思路

最小生成树。

点赞

发表评论