记一次 Div3 AK

发表于 2021-02-18 分类于题解阅读次数： Valine：本文字数： 7.1k 阅读时长 ≈ 6 分钟

这是人生第一次 AK Div3。

比赛链接在这里

这是最后的榜：

可以发现：我对简单题的思考有很大的欠缺；而且罚时动不动爆炸，经常心急。

下面一道题一道题说。

A

题目中定义“密集的”序列是序列的任意相邻两数中，大的除以小的小于等于 $2$ 。

发现题目范围中 $a_i\le 50$ ，我们对于那些不满足题意的相邻两数暴力的在中间加数即可。具体来讲就是不停的加入 $\min\{a_i,a_{i+1}\}\times 2^k$ ，直到 $\frac{\max\{a_i,a_{i+1}\}}{\min\{a_i,a_{i+1}\}\times 2^k}\le 2$ 为止。

代码：

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
int _,n,a[55];
int main() {
    for(scanf("%d",&_);_;--_) {
        scanf("%d",&n);
        rep(i,1,n) scanf("%d",&a[i]);
        int ans=0;
        rep(i,1,n-1) {
            int mx=max(a[i],a[i+1]),mn=min(a[i],a[i+1]);
            while((mx+mn-1)/mn>2) {
                mn*=2,ans++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

B

我们循环按题意模拟两边即可。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
int _,n;
int main() {
    for(scanf("%d",&_);_;--_) {
        int c[3];
        rep(i,0,2) c[i]=0;
        scanf("%d",&n);
        rep(i,1,n) {
            int x;
            scanf("%d",&x);
            c[x%3]++;
        }
        int ans=0,anss=0x3f3f3f3f;
        int x=n/3;
        rep(i,0,2) if(c[i]!=x) {
            if(c[i]<x) ;
            else ans+=c[i]-x,c[(i+1)%3]+=c[i]-x,c[i]=x;
        }
        rep(i,0,2) if(c[i]!=x) {
            if(c[i]<x) ;
            else ans+=c[i]-x,c[(i+1)%3]+=c[i]-x,c[i]=x;
        }
        anss=min(anss,ans);ans=0;
        printf("%d\n",anss);
    }
    return 0;
}

C

因为 $1\le x\le 10^{12}$ ，因此 $a,b$ 不会超过 $\sqrt[3]{10^{12}}=10^4$ 。

所以我们枚举 $1\sim 10^4$ 这些数的三次方。把这些三次方数扔进一个 set 里。

然后对于每一个询问，我们遍历一遍 set，看看这个数减去遍历到的数是不是在那个 set 里面。如果是的话，这个数就可以表示成 $a^3+b^3$ 的形式。如果遍历了一遍都不是的话，就不行。

代码：

#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
int _,n;
set<int> s;
signed main() {
    rep(i,1,10000) s.insert(i*i*i);
    for(scanf("%lld",&_);_;--_) {
        scanf("%lld",&n);
        bool flg=0;
        for(set<int>::iterator ii=s.begin();ii!=s.end();++ii) {
            int qwq=(*ii);
            if(qwq>=n) break;
            int rem=n-qwq;
            if(s.count(rem)) {flg=1;break;}
        }
        if(flg) puts("YES");
        else puts("NO");
    }
    return 0;
}

D

题目给了一棵二叉树的中序遍历，让我们求出所有节点的深度。

这不大水题吗？？考虑分治，每次找到范围内最大的数拎成根，更新答案，然后从这里劈两半继续往下处理即可。

代码：

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
int _,n;
int a[105],ans[105];
void solve(int l,int r,int dep) {
    if(l==r) {ans[l]=dep;return;}
    if(l>r) return;
    int mx=0,id;
    rep(i,l,r) {
        if(a[i]>mx) mx=a[i],id=i;
    }
    ans[id]=dep;
    solve(l,id-1,dep+1);
    solve(id+1,r,dep+1);
}
int main() {
    for(scanf("%d",&_);_;--_) {
        scanf("%d",&n);
        rep(i,1,n) {
            scanf("%d",&a[i]);
        }
        solve(1,n,0);
        rep(i,1,n) printf("%d ",ans[i]);
        puts("");
    }
    return 0;
}

E

首先一个人肯定有机会打败 $a$ 值 $\le$ 他的人（因为 $a$ 值相同的话是随机打败，总之有机会）。

因此我们先将 $a$ 数组排个序。

打败完了这么多人之后，我们设这个人位置为 $x$ ，他现在的 $a$ 值变成了所有 $a$ 值 $\le a_x$ 的人的 $a$ 值之和。

然后他打败了这么多人后还有机会接着向后打败，也就是说，如果现在这个人的 $a$ 值比后头一个人的 $a$ 值大，那么就可以往下继续滚雪球。但如果遇到当前 $a$ 值比后一个人的 $a$ 值小了，这个人就打败不了，后头的人也打败不了了。

也就是说我们肯定要先做个前缀和。

一个人要赢，肯定就是要打败所有人，意思就是他滚的雪球要滚到底。

所以我们从后往前推，如果说哪里遇到当前的前缀和比后一个人的 $a$ 值小了，那么就 break 掉，因为再往前的人都打败不了这个人了，雪球滚不下去。否则就继续循环。

代码：

#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
int _,n;
pair<int,int> a[200005];
int sum[200005];
bool ans[200005];
int b[200005];
map<int,int> summ,nxt;
signed main() {
    for(scanf("%lld",&_);_;--_) {
        summ.clear();nxt.clear();
        scanf("%lld",&n);
        rep(i,1,n) ans[i]=0;
        rep(i,1,n) b[i]=0;
        rep(i,1,n) {
            scanf("%d",&a[i].first);
            a[i].second=i;
        }
        sort(a+1,a+n+1);
        rep(i,1,n) {
            sum[i]=sum[i-1]+a[i].first;
            summ[a[i].first]=sum[i];
            if(a[i].first!=a[i-1].first) nxt[a[i-1].first]=a[i].first;
        }
        ans[a[n].second]=1;
        nxt[a[n].first]=0;
        per(i,n-1,1) {
            if(summ[a[i].first]>=nxt[a[i].first]) ans[a[i].second]=1;
            else break;
        }
        int qwq=0;
        rep(i,1,n) {
            if(ans[i]) ++qwq;
        }
        printf("%lld\n",qwq);
        rep(i,1,n) {
            if(ans[i]) printf("%lld ",i);
        }
        puts("");
    }
    return 0;
}

F

一句话题意：给一个数组 $a$ ，我们要任意画一条线 $C$ ，使得出现次数比 $C$ 多的数的出现次数要删到 $C$ ，出现次数比 $C$ 少的数的出现次数要删到 $0$ ，问所有划线的方案中最少要删多少个数。

首先我们先离散化一下数组 $a$ ，这样 $a$ 数组中的数可以扔进一个桶 $bin$ 里。

然后我们对这个桶数组进行排序（也就是将所有数的出现次数排个序），然后跑个前缀和。

由于所有数最多出现 $n$ 次，因此我们画的线 $C$ 一定不超过 $n$ 。那么我们可以枚举 $C$ ，对于每个 $C$ ，在桶中二分找到第一个 $\ge C$ 的数。在这个数前面的就都删到 $0$ ，删除次数就是个前缀和；在这个数后面的就都删到 $C$ ，删除次数就是用前缀和相减再减去这些数的个数 $\times C$ 。

代码：

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
int _,n;
int a[200005],b[200005];
int bin[200005],sum[200005];
int main() {
    for(scanf("%d",&_);_;--_) {
        scanf("%d",&n);
        rep(i,1,n) scanf("%d",&a[i]),b[i]=a[i];
        sort(b+1,b+n+1);
        int nn=unique(b+1,b+n+1)-b-1;
        rep(i,1,n) a[i]=lower_bound(b+1,b+nn+1,a[i])-b;
        rep(i,1,nn) bin[i]=0;
        rep(i,1,n) bin[a[i]]++;
        sort(bin+1,bin+nn+1);
        rep(i,1,nn) sum[i]=sum[i-1]+bin[i];
        int anss=0x3f3f3f3f;
        rep(i,0,n) {
            int id=lower_bound(bin+1,bin+nn+1,i)-bin;
            int ans;
            if(id>nn) ans=sum[nn];
            else ans=sum[id-1]+(sum[nn]-sum[id-1]-(nn-id+1)*i);
            anss=min(anss,ans);
        }
        printf("%d\n",anss);
    }
    return 0;
}

G

题目用蜗牛爬井解释更好理解一点。

题目大意

有一只蜗牛在从一个井里往上爬。初始时它所在高度为 $0$ 。

他按照序列 $a$ 不停的爬着（序列 $a$ 长度为 $n$ ），每次爬的时候，他所在高度都 $+a_i$ （ $a_i$ 可能为负）。爬完 $n$ 次之后又从 $a_1$ 继续爬。

有 $m$ 次询问，每次问蜗牛爬到高度 $x$ 最少需要爬多少次，如果蜗牛会一直爬下去不停下，输出 -1。

题解

考虑把蜗牛在一次循环内能到达的正数所需的最短时间扔进一个 map 内。换句话说，我们想知道蜗牛在一次循环中到达 $x$ 最少需要爬多少次，只需在这个 map 上 lower_bound 一下 $x$ 就可以了。

然后显然还需要存一次循环总共蜗牛会移动多少，记为 $k$ 。

那么我们对于每个询问，先在 map 中找一下第一轮能不能到。

能就直接输出，不能的话分两种情况：

如果 $k\le0$ ，那么蜗牛一定会永无停息地爬，输出 -1。
如果 $k>0$ ，我们可以找到一个循环的次数 $w$ 使得 map 中最高的 key $+w\times k\ge x$ 。这个时候就是 $x$ 第一次被达到的时候。

代码：

#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
int _,n,m;
int a[200005];
map<int,int> tim;
signed main() {
    for(scanf("%lld",&_);_;--_) {
        tim.clear();
        scanf("%lld%lld",&n,&m);
        int row=0,mx=0,mxid=0;
        rep(i,1,n) {
            scanf("%lld",&a[i]);
            row+=a[i];
            if(row>mx) mx=row,mxid=i,tim[mx]=i;
        }
        rep(i,1,m) {
            int x;
            scanf("%lld",&x);
            map<int,int>::iterator ii=tim.lower_bound(x);
            if(ii==tim.end()&&row<=0) {printf("-1 ");continue;}
            else if(ii==tim.end()){
                map<int,int>::iterator lst=tim.end();--lst;
                int ned=(x-lst->first+row-1)/row;
                ii=tim.lower_bound(x-ned*row);
                printf("%lld ",ii->second+ned*n-1);
            } else {
                printf("%lld ",ii->second-1);
            }
        }
        puts("");
    }
    return 0;
}