竞赛讨论区 > 牛客练习赛 94 Editorial

牛客练习赛 94 Editorial

头像
boringhacker
发布于 2021-12-30 22:07:19 APP内打开
赞 1 | 收藏 3 | 回复2 | 浏览1666

前言

这场比赛的锅貌似有点多…在准备的时候就已经推迟过三次,在这里为对各位比赛时造成的困扰抱歉。这是出题组第一次放比赛,欢迎批评指正。

主要问题在于 C 的数据造水了,hack 数据造反了于是没有 hack 到。D 的数据也不强。再次感到抱歉,并且努力做出改正。

最后重拾一下出比赛的初心以及发表一些 mozheng & Chuni 言论:罚金一百万元(不是),以及为自己的 Welcome to NHK 做一个 Sunny Side 式的收尾,或者称之为小结。总之都没差啦……虽然只是举个例子,但我们要告诉你的,就是这样的故事。

A

给出两种构造方式:

  • 考虑 的每一位,如果当前位为 ,则不对答案产生影响;如果当前位为 ,又因为 ,所以把 其中两个按位或上 即可。

当然这两种方式并无什么不同。无解的情况是

#include<bits/stdc++.h>
int ans[3],d;
signed main() {
    scanf("%d",&d);
    if((d&-d)==d)    return puts("-1"),0;
    for(int now=0; d; d^=d&-d)    ans[now]|=d&-d,ans[(now+=1)%=3]|=d&-d;
    printf("%d %d %d\n",ans[0],ans[1],ans[2]);
    return 0;
}
#include<bits/stdc++.h>
int d;
signed main() {
    scanf("%d",&d);
    if((d&-d)==d)    return puts("-1"),0;
    printf("%d %d %d\n",d,(d&-d),d-(d&-d));
    return 0;
}

B

首先 ,考虑第二位,因为保证有解,所以 ,同理可得 ,可以预见数据中最多有 个非 数,于是不断往上推即可。

#include<bits/stdc++.h>
int n,x,pre,now,vis[2000100];
signed main() {
    scanf("%d\n%d",&n,&x);
    vis[pre=now=x]=1;
    printf("%d ",x);
    for(int i=1; i<n; ++i) {
        scanf("%d",&x);
        if(pre!=x)    pre=now=x;
        else    while(vis[now])    now+=pre;
        vis[now]=1;
        printf("%d ",now);
    }
    return 0;
}

C

首先我们有个 的暴力遍历做法,读者很容易想到这样遍历了太多冗余的点。

于是很自然地想到将一个块缩成一个点。具体的,对于每一列,我们将障碍物隔开的一列点看成一个点,这样的店最多有 个。

然后 dp 即可,

然后要注意一个块能否转移到另一个块的判断条件有细节:并不是看两个块是联通,而是定义 为能到达第 个块的最低点(贪心),看从 起是否能到达 ,再更新

当然好像有更简便的做法,余不会。

同时存在更优的做法,为了代码的简便起见并没有作为 std,欢迎分享。

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
#define LL long long
#define Min(x,y) ((x)<(y)?(x):(y))
#define Max(x,y) ((x)>(y)?(x):(y))
using namespace std;
const int MAXN = 5005, MAXM = 1e7 + 5;
vector <int> v[MAXM], cx;
map <int, bool> vis;
map <int, int> lst;
struct Point {
    int X, Y, Y_;
}arr[MAXN];
int n, m, k, tot, mx, mn[MAXN];
int pre[MAXM];
bool dp[MAXN];
bool check(int x, int y) {
    if(arr[x].X == arr[y].X - 1) {
        if(arr[x].Y_ < arr[y].Y) return 0;
        if(arr[x].Y > arr[y].Y_) return 0;
        if(max(arr[y].Y, mn[x]) >= arr[y].Y && max(arr[y].Y, mn[x]) <= arr[y].Y_) {
            mn[y] = min(mn[y], max(arr[y].Y, mn[x])); return 1;
        }
        return 0;
    }
    if(arr[x].Y > arr[y].Y_) return 0;
    if(max(arr[y].Y, mn[x]) >= arr[y].Y && max(arr[y].Y, mn[x]) <= arr[y].Y_) {
        mn[y] = min(mn[y], max(arr[y].Y, mn[x])); return 1;
    }
    return  0;
}
int main() {
    int x, y;
    scanf("%d%d%d", &n, &m, &k); memset(mn, 0x3f, sizeof(mn));
    for(int i = 1; i <= k; i ++) {
        scanf("%d%d", &x, &y); v[x].push_back(y); cx.push_back(x); mx = max(mx, x);
    }
    sort(cx.begin(), cx.end());
    int Lst = 0;
    for(auto i : cx) {
        if(vis[i]) continue;
        pre[i] = 1;
        lst[i] = Lst; Lst = i; sort(v[i].begin(), v[i].end()); vis[i] = 1;
        int las = 0;
        for(auto j : v[i]) {
            if(j == las) { las ++; continue; }
            tot ++; arr[tot].X = i; arr[tot].Y = las; arr[tot].Y_ = j - 1; las = j + 1;
        }
        if(las <= m) tot ++, arr[tot].X = i, arr[tot].Y = las, arr[tot].Y_ = m;
    }
    for(int i = 1; i <= 10000000; i ++) pre[i] += pre[i - 1];
//    for(int i = 1; i <= tot; i ++) {
//        printf("%d %d %d\n", arr[i].X, arr[i].Y, arr[i].Y_);
//    }
    if(!tot) { printf("Yes"); return 0; }
    if(vis[0]) {
        if(arr[1].Y != 0) { printf("No"); return 0; }
        dp[1] = 1; mn[1] = 0;
    }
    else {
        for(int i = 1; i <= tot; i ++) if(arr[i].X == arr[1].X) dp[i] = 1, mn[i] = arr[i].Y, dp[i] = 1;
    }
    for(int i = 1; i <= tot; i ++) {
        for(int j = 1; j < i; j ++) {
            if(arr[j].X == arr[i].X) continue;
            if(((arr[j].X + 1 < arr[i].X && pre[arr[i].X - 1] - pre[arr[j].X] == 0) || arr[j].X + 1 == arr[i].X) && arr[j].X == lst[arr[i].X] && check(j, i)) {
                dp[i] |= dp[j];
            }
        }
    }
    if(vis[n]) {
        if(arr[tot].Y_ != m) { printf("No"); return 0; }
        if(dp[tot]) printf("Yes");
        else printf("No");
    }
    else {
        bool ans = 0;
        for(int i = 1; i <= tot; i ++) if(arr[i].X == mx) ans |= dp[i];
        if(ans) printf("Yes");
        else printf("No");
    }
    return 0;
}

D

你考虑维护 个单调队列。第 个单调队列的数满足:,其中 一定为正数。

每次我们取 个单调队列的队头最小值 ,设其在第 个队列,那么我们将 放入第 个队列中。(

可以证明,由于 数组为正数,这样队列一定是单调的。

一直这样做 次,取 即可。时间复杂度:。数据可以(?)把带 做法卡掉。

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <ctime>
#include <queue>
#define LL long long
using namespace std;
const int MAXN = 85;
queue <LL> que[MAXN];
int n, k, a[MAXN], num;
LL minn;
int main() {
    scanf("%d%d", &n, &k); k --;
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    que[0].push(0);
    for(int i = 1; i <= k + 1; i ++) {
        minn = 9e18;
        for(int j = 0; j <= n; j ++) if(!que[j].empty() && que[j].front() < minn) minn = que[j].front(), num = j;
        while(que[0].size()) que[0].pop();
        que[num].pop();
        for(int j = num; j <= n; j ++) que[j].push(minn + a[j]);
    }
    printf("%lld", minn);
    return 0;
}

E

表示第 这个点在坐标加 时距离自己最近的 点的距离。那么这个画出来就是一条折线,由若干条斜率为 的直线拼接而成。再设 ,**也就是取 时,题面中要求的距离之和**。

在折线的拐点上研究,设 图像上所有拐点的集合,再设 。w.l.o.g,提出两个数 ,且不存在 ,即 是紧相邻的。**换而言之,就是把所有 点的图像拼在一起,取两个相邻的 拐点来研究。**

现在我们可以求出 ,以及拐点后的直线斜率,从而可以求出 。以此,扫一遍就行了。

我们举个例子来画图:

图片说明

这个就是 的图像(我把多个 的拼在一起的)。现在假设我们取的 两点就是图中的蓝点(当然, 之间没有其他拐点,因为 是紧相邻的),这意味着我确定了 点处的 ,那么就可以算出 了,如此往后面扫,每次取最大值就行了。

/*
每个点处在每个区间的值是不相同的,但是是一个折线。
当它在[vi,vi+1]中间时,如果靠vi更近,则为与vi的距离,否则为与vi+1的距离。
那我们现在知道了每个点移动多少之后的答案。
这条折线有的地方是斜率-1,有的地方是斜率为+1.
那么我们把所有的折线加在一起。一共有ab个点,我们维护一下每一段的斜率,然后求下最大值就好…… 

1 1 1
0
0

4
10
3
0 0 1 1 3 3 3 3 4 4
0 1 4

13 2 9
2 9
0 1 2 3 5 6 7 11 12
*/ 
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector<long long> pri;
const long long INF=1e18;
long long l,n,m,a[1010],b[1010],delup,deldown,sols[4000010],cur,ans,s,mxs;
double mxp;
struct line
{
    long long l,r,num;
}lin[2000010];
long long nothingtimes;
void donothing()
{
    ++nothingtimes;
}
long long ABS(long long x)
{
    return x>=0?x:-x;
}
long long lint;
int main()
{
    scanf("%lld %lld %lld",&l,&n,&m);
    for(long long i=1;i<=n;++i)    scanf("%lld",&a[i]);
    for(long long i=1;i<=m;++i)    scanf("%lld",&b[i]);
    deldown=0;
    delup=l-b[m];
    deldown<<=1;
    delup<<=1;
    for(long long i=1;i<=n;++i)//第i个目标点 
    {
        for(long long j=1;j<m;++j)//位于第j个与第j+1个点之间 距离都*2了,因为中点可能不在格点上。 
        {
            //靠左
            long long l=a[i]*2-(b[j]+b[j+1]),r=(a[i]-b[j])*2;
            if(l>delup||r<deldown||l>=r)    donothing();
            else
            {
                if(l<deldown)    l=deldown;
                if(r>delup)    r=delup;
                if(l>=r)    donothing();
                else
                {
                    lin[++lint].l=l;
                    lin[lint].r=r;
                    lin[lint].num=-1;
                }
            }
            //靠右 
            l=a[i]*2-b[j+1]*2,r=a[i]*2-(b[j]+b[j+1]);
            if(l>delup||r<deldown||l>=r)    donothing();
            else
            {
                if(l<deldown)    l=deldown;
                if(r>delup)    r=delup;
                if(l>=r)    donothing();
                else
                {
                    lin[++lint].l=l;
                    lin[lint].r=r;
                    lin[lint].num=1;
                }
            }
        }
        //在第1个前面
        long long l=a[i]*2-b[1]*2,r=delup;
        if(l>delup||r<deldown||l>=r)    donothing();
        else
        {
            if(l<deldown)    l=deldown;
            if(r>delup)    r=delup;
            if(l>=r)    donothing();
            else
            {
                lin[++lint].l=l;
                lin[lint].r=r;
                lin[lint].num=1;
            }
        }
        //在第n个后面
        l=deldown,r=a[i]*2-b[m]*2;
        if(l>delup||r<deldown||l>=r)    donothing();
        else
        {
            if(l<deldown)    l=deldown;
            if(r>delup)    r=delup;
            if(l>=r)    donothing();
            else
            {
                lin[++lint].l=l;
                lin[lint].r=r;
                lin[lint].num=-1;
            }
        }
    }
    for(long long i=1;i<=lint;++i)
    {
        pri.push_back(lin[i].l);
        pri.push_back(lin[i].r);
    }
    sort(pri.begin(),pri.end());
    pri.erase(unique(pri.begin(),pri.end()),pri.end());
    s=pri.size();
    for(long long i=1;i<=lint;++i)
    {
        lin[i].l=lower_bound(pri.begin(),pri.end(),lin[i].l)-pri.begin()+1;
        lin[i].r=lower_bound(pri.begin(),pri.end(),lin[i].r)-pri.begin()+1;
    }
    for(long long i=1;i<=lint;++i)
    {
        sols[lin[i].l]+=lin[i].num;
        sols[lin[i].r]-=lin[i].num;
    }
    mxp=-1;
    mxs=-1;
    for(long long i=1;i<=n;++i)
    {
        long long nowpos=a[i]*2+deldown,minn=INF;
        for(long long j=1;j<=m;++j)    minn=min(minn,ABS(nowpos-b[j]*2));
        cur+=minn;
    }
    if(cur<=l*2)
    {
        mxp=deldown;
        mxs=cur;
    }
    for(long long i=1;i<=s;++i)    sols[i]+=sols[i-1];
    for(long long i=1;i<s;++i)
    {
        if(cur>l*2)
        {
            long long tmp=cur+sols[i]*(pri[i]-pri[i-1]);
            if(tmp<=l*2)
            {
                mxs=l*2;
                mxp=(l*2-cur)*1.0/sols[i]+pri[i-1];
            }
            cur=tmp;
        }
        else
        {
            long long tmp=cur+sols[i]*(pri[i]-pri[i-1]);
            if(tmp<=l*2)
            {
                if(tmp>=mxs)
                {
                    mxp=pri[i];
                    mxs=tmp;
                }
            }
            else
            {
                mxp=(l*2-cur)*1.0/sols[i]+pri[i-1];
                mxs=l*2;
            }
            cur=tmp;
        }
    }
    if(mxp==-1)    printf("NO\n");
    else    printf("%.6lf\n",mxp/2);
    return 0;
}

F

首先我们定义 表示包含 的最小区间。因为添加新的元素不会使区间变小, 所以 ,因此对于每个包含 的区间, 它肯定是包含 。若这个区间并不包含 , 则也可以得到这个区间不包含 所以, 这个区间的贡献应该是

将这 的贡献分别分到 中, 我们的问题就变成了, 每一次添加元素后, 包含 的区间个数。考虑一次插入后答案的变化,同时规定

一次插入的数 一定满足 。而这个 是唯一的(这个应该很好想吧)。

所以, 我们可以预处理出每一个 对应的 。当插入 的时候, 相当于在所有 的左(或右)边增加了 个点。

此时增加的区间数量即是 右(或左)边的点个数之和(注意, 对于一个点是可以重复计算的), 这里只需要用两个线段树分别记录 左右当前各有多少点了。

Bonus:Solve it in

#include <cstdio>
#include <algorithm>
using namespace std;

#define MAXN 1000000
#define L(p) (p << 1)
#define R(p) ((p << 1) | 1) 
#define make_mid(l,r) int mid = (l + r) >> 1

int s[MAXN + 5];
pair <int, int> si[MAXN + 5];
int sl[MAXN + 5], sr[MAXN + 5];
struct node {
    long long v;
    long long sign;
    int h, t;
}s1[(MAXN << 4) + 5], s2[(MAXN << 4) + 5];

void build (int p, int l, int r) {
    s1[p].h = l;
    s1[p].t = r;
    s1[p].sign = 0;
    s1[p].v = 0;
    s2[p].h = l;
    s2[p].t = r;
    s2[p].sign = 0;
    s2[p].v = 0;
    if (l == r) {
        return ;
    }
    make_mid (l, r);
    build (L(p), l, mid);
    build (R(p), mid + 1, r);
}
void downloadl (int p) {
    if (s1[p].sign && s1[p].h < s1[p].t) {
        s1[L(p)].sign += s1[p].sign;
        s1[R(p)].sign += s1[p].sign;
        s1[L(p)].v += (s1[L(p)].t - s1[L(p)].h + 1) * s1[p].sign;
        s1[R(p)].v += (s1[R(p)].t - s1[R(p)].h + 1) * s1[p].sign;
        s1[p].sign = 0;
    }
}
void downloadr (int p) {
    if (s2[p].sign && s2[p].h < s2[p].t) {
        s2[L(p)].sign += s2[p].sign;
        s2[R(p)].sign += s2[p].sign;
        s2[L(p)].v += (s2[L(p)].t - s2[L(p)].h + 1) * s2[p].sign;
        s2[R(p)].v += (s2[R(p)].t - s2[R(p)].h + 1) * s2[p].sign;
        s2[p].sign = 0;
    }
}
void changel (int p, int l, int r, long long x) {
    downloadl (p);
    if (s1[p].h >= l && s1[p].t <= r) {
        s1[p].v += x * (s1[p].t - s1[p].h + 1);
        s1[p].sign += x;

        return ;
    }
    make_mid (s1[p].h, s1[p].t);
    if (l <= mid) {
        changel (L(p), l, r, x);
    }
    if (r > mid) {
        changel (R(p), l, r, x);
    }
    s1[p].v = s1[L(p)].v + s1[R(p)].v;
}
void changer (int p, int l, int r, long long x) {
    downloadr (p);
    if (s2[p].h >= l && s2[p].t <= r) {
        s2[p].v += x * (s2[p].t - s2[p].h + 1);
        s2[p].sign += x;

        return ;
    }
    make_mid (s2[p].h, s2[p].t);
    if (l <= mid) {
        changer (L(p), l, r, x);
    }
    if (r > mid) {
        changer (R(p), l, r, x);
    }
    s2[p].v = s2[L(p)].v + s2[R(p)].v;
}
long long Suml (int p, int l, int r) {
    downloadl (p);
    if (s1[p].h >= l && s1[p].t <= r) {
        return s1[p].v;
    }

    long long sum = 0;

    make_mid (s1[p].h, s1[p].t);
    if (l <= mid) {
        sum += Suml (L(p), l, r);
    }
    if (r > mid) {
        sum += Suml (R(p), l, r);
    }

    return sum;
}
long long Sumr (int p, int l, int r) {
    downloadr (p);
    if (s2[p].h >= l && s2[p].t <= r) {
        return s2[p].v;
    }

    long long sum = 0;

    make_mid (s2[p].h, s2[p].t);
    if (l <= mid) {
        sum += Sumr (L(p), l, r);
    }
    if (r > mid) {
        sum += Sumr (R(p), l, r);
    }

    return sum;
}

int main () {
    int n;

    scanf ("%d", &n);
    for (int i = 1; i <= n; i ++) {
        int x;

        scanf ("%d", &x);
        s[x + 1] = i;//处理出i插入到的是哪个位置
    }
    build (1, 1, n);//初始两棵线段树
    //初始 sec(i)
    //----------------------------------------------
    si[1].first = s[1];
    si[1].second = s[1];
    for (int i = 2; i <= n; i ++) {
        si[i].first = min (si[i - 1].first, s[i]);
        si[i].second = max (si[i - 1].second, s[i]);
    }
    //----------------------------------------------
    //处理出 i 所对应的 y 且处理出到底是在 sec(y) 的左还是右
    for (int i = n - 1; i >= 1; i --) {
        for (int j = si[i + 1].first; j < si[i].first; j ++) {
            sr[j] = i;
        }
        for (int j = si[i + 1].second; j > si[i].second; j --) {
            sl[j] = i;
        }
    }

    long long ans = 0;//保存每次插入的答案
    long long Ans = 0;//保存最终答案

    for (int i = 1; i <= n; i ++) {
        if (sl[s[i]]) {
            ans += Suml (1, 1, sl[s[i]]);
            changer (1, 1, sl[s[i]], 1);
        }
        if (sr[s[i]]) {
            ans += Sumr (1, 1, sr[s[i]]);
            changel (1, 1, sr[s[i]], 1);
        }
        ans ++;//添加了 i 以后会多出 sec() , 此处将其加入答案中
        changel (1, i, i, 1);
        changer (1, i, i, 1);
        Ans += ans;
    }
    printf ("%lld", Ans);
}

1条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐