2021牛客OI赛前集训营-提高组（第六场）-（重现赛）赛后总结

旋律的总数

https://ac.nowcoder.com/acm/contest/20111/A
时间 名称 赛制 组别 得分 排名
2022.11.14 2021牛客OI赛前集训营（第六场） OI 提高组 335/400 6

注：买的去年的题，本地OI赛制，排名按当年的计算。

A.旋律的总数

容易发现假设最高位填 11，其它位填什么互相之间都不会有影响，而最高位为 2,3,4,……,m2,3,4,……,m 的一定会被认为是重复的。

所以答案为 mn−1m^{n-1}，用快速幂计算，时间复杂度 O(Tlog⁡n)\mathcal{O}(T\log n)。

代码：

#include<bits/stdc++.h>
using namespace std;

const int MOD=1e9+7;
int quick_pow(int a,int b)
{
    int ret=1;
    while(b)
    {
        if(b&1) ret=(long long)ret*a%MOD;
        a=(long long)a*a%MOD,b>>=1;
    }
    return ret;
}
int main()
{
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
    int T;
    cin>>T;
    int n,m;
    while(T--)
    {
        scanf("%d %d",&n,&m);
        printf("%d\n",quick_pow(m,n-1));
    }
    return 0;
}

B.水果加工

背包 dp 我不懂，搜索大法好

观察 n≤40n\le40 如果直接搜复杂度是 ∏i=1nai\prod\limits_{i=1}^na_i 的，但题目有个限制：∑i=1nai≤40\sum\limits_{i=1}^na_i \le 40，所以搜索轻松能过。

然而为了保守起见还是写了 meet in middle。

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> pa;
const int MAXN=45;
int a[MAXN],b[2],c[2][MAXN],d[2][MAXN],u[2][MAXN];
vector<pa>cost1[MAXN][MAXN],cost2[MAXN][MAXN];
vector<pa>w1[MAXN][MAXN],w2[MAXN][MAXN];
int n,mid;
void dfs1(int x,ll sum1,ll sum2,int cnt1,int cnt2)
{
    if(x>mid)
    {
        cost1[cnt1][cnt2].push_back({sum1,sum2});
        return;
    }
    for(int i=0;i<=a[x];++i)
        if(c[0][x]*(i!=0)+cnt1<=b[0] && c[1][x]*(i!=a[x])+cnt2<=b[1])
        {
            dfs1(x+1,max(sum1,max((ll)d[0][x]*i,(ll)d[1][x]*(a[x]-i))),max(sum2,max((ll)u[0][x]*i,(ll)u[1][x]*(a[x]-i))),cnt1+c[0][x]*(i!=0),cnt2+c[1][x]*(i!=a[x]));
        }
}
void dfs2(int x,ll sum1,ll sum2,int cnt1,int cnt2)
{
    if(x>n)
    {
        cost2[cnt1][cnt2].push_back({sum1,sum2});
        return;
    }
    for(int i=0;i<=a[x];++i)
        if(c[0][x]*(i!=0)+cnt1<=b[0] && c[1][x]*(i!=a[x])+cnt2<=b[1])
            dfs2(x+1,max(sum1,max((ll)d[0][x]*i,(ll)d[1][x]*(a[x]-i))),max(sum2,max((ll)u[0][x]*i,(ll)u[1][x]*(a[x]-i))),cnt1+c[0][x]*(i!=0),cnt2+c[1][x]*(i!=a[x]));
}
int main()
{
    freopen("B.in","r",stdin);
    freopen("B.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int i=0;i<=1;++i) scanf("%d",&b[i]);
    for(int i=1;i<=n;++i) scanf("%d",&c[0][i]);
    for(int i=1;i<=n;++i) scanf("%d",&c[1][i]);
    for(int i=1;i<=n;++i) scanf("%d",&d[0][i]);
    for(int i=1;i<=n;++i) scanf("%d",&d[1][i]);
    for(int i=1;i<=n;++i) scanf("%d",&u[0][i]);
    for(int i=1;i<=n;++i) scanf("%d",&u[1][i]);
    mid=n/2;
    dfs1(1,0,0,0,0),dfs2(mid+1,0,0,0,0);
    for(int i=0;i<=b[0];++i)
    {
        for(int j=0;j<=b[1];++j)
        {
            sort(cost1[i][j].begin(),cost1[i][j].end());
            vector<pa>tmp;
            int si=cost1[i][j].size();
            for(int x=0;x<si;++x) if(!x || cost1[i][j][x].first!=cost1[i][j][x-1].first) tmp.push_back(cost1[i][j][x]);
            si=tmp.size();
            for(int x=0;x<si;++x) if(!x || tmp[x].second<tmp[x-1].second) w1[i][j].push_back(tmp[x]);
        }
    }
    for(int i=0;i<=b[0];++i)
    {
        for(int j=0;j<=b[1];++j)
        {
            sort(cost2[i][j].begin(),cost2[i][j].end());
            vector<pa>tmp;
            int si=cost2[i][j].size();
            for(int x=0;x<si;++x) if(!x || cost2[i][j][x].first!=cost2[i][j][x-1].first) tmp.push_back(cost2[i][j][x]);
            si=tmp.size();
            for(int x=0;x<si;++x) if(!x || tmp[x].second<tmp[x-1].second) w2[i][j].push_back(tmp[x]);
        }
    }
    ll ans=1e18;
    for(int i=0;i<=b[0];++i)
        for(int j=0;j<=b[1];++j)
            for(int k=0;k<=b[0]-i;++k)
                for(int l=0;l<=b[1]-j;++l)
                    for(auto x:w1[i][j])
                        for(auto y:w2[k][l])
                            ans=min(ans,max(x.first,y.first)+max(x.second,y.second));
    cout<<ans<<endl;
    return 0;
}

C.最佳位置

考场怒码 6k 代码然而发现 INFINF 开成 10910^9，100−>45100->45.

思路和题解一样，分类讨论一波：

  1. 当前全是空位：显然选 11；

  2. 当前有一个位置有人：选 1/n1/n；

  3. 选 1/n1/n 或最长的一段空段的中点。

考场采用的是 Treap+set+priority_queue 的写法，慢的要死……

代码：

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pa;
const int MAXN=3e5+5;
const int INF=2e9;
struct Treap
{
    struct NODE
    {
        int ls=0,rs=0;
        int val,sum,siz,rnd;
    }tree[MAXN<<1];
    int tot=0,root=0;
    void push_up(int k){tree[k].siz=tree[k].sum+tree[tree[k].ls].siz+tree[tree[k].rs].siz;}
    void turn_right(int &k)
    {
        int t=tree[k].ls;
        tree[k].ls=tree[t].rs,tree[t].rs=k;
        push_up(k),push_up(t),k=t;
    }
    void turn_left(int &k)
    {
        int t=tree[k].rs;
        tree[k].rs=tree[t].ls,tree[t].ls=k;
        push_up(k),push_up(t),k=t;
    }
    void insert(int &k,int val)
    {
        if(!k)
        {
            k=++tot;
            tree[k].val=val;
            tree[k].sum=tree[k].siz=1;
            tree[k].rnd=rand();
            return;
        }
        if(val<tree[k].val)
        {
            insert(tree[k].ls,val);
            if(tree[k].rnd<tree[tree[k].ls].rnd) turn_right(k);
        }
        else if(val>tree[k].val)
        {
            insert(tree[k].rs,val);
            if(tree[k].rnd<tree[tree[k].rs].rnd) turn_left(k);
        }
        else ++tree[k].sum;
        push_up(k);
    }
    void del(int &k,int val)
    {
        if(!k) return;
        if(tree[k].val==val)
        {
            if(tree[k].sum>1) --tree[k].sum,push_up(k);
            else if(!tree[k].ls && !tree[k].rs) k=0;
            else
            {
                if(!tree[k].rs || tree[tree[k].ls].rnd>tree[tree[k].rs].rnd) turn_right(k),del(tree[k].rs,val);
                else turn_left(k),del(tree[k].ls,val);
                push_up(k);
            }
            return;
        }
        if(val<tree[k].val) del(tree[k].ls,val);
        else del(tree[k].rs,val);
        push_up(k);
    }
    int ask_pre(int k,int val)
    {
        int ret=-INF;
        if(!k) return ret;
        if(tree[k].val<val) ret=max(ask_pre(tree[k].rs,val),tree[k].val);
        else ret=ask_pre(tree[k].ls,val);
        return ret;
    }
    int ask_nxt(int k,int val)
    {
        int ret=INF;
        if(!k) return ret;
        if(tree[k].val>val) ret=min(ask_nxt(tree[k].ls,val),tree[k].val);
        else ret=ask_nxt(tree[k].rs,val);
        return ret;
    }
}BST;
struct node
{
    pa now;
    int mid,dis;
    friend bool operator > (const node x,const node y){return x.dis==y.dis?x.mid<y.mid:x.dis>y.dis;}
    friend bool operator < (const node x,const node y){return x.dis==y.dis?x.mid>y.mid:x.dis<y.dis;}
};
map<pa,bool>tag;
unordered_set<int>pos;
priority_queue<node>q;
priority_queue<int>max_pos;
priority_queue< int,vector<int>,greater<int> >min_pos;
int seat[MAXN];
int n,m;
int dist(int l,int r)
{
    int mid=(l+r)>>1;
    return min(mid-l,r-mid);
}
int main()
{
    freopen("C.in","r",stdin);
    freopen("C.out","w",stdout);
    cin>>n>>m;
    int x,cnt=0;
    for(int i=1;i<=m*2;++i)
    {
        scanf("%d",&x);
        if(!seat[x])
        {
            if(pos.empty()) seat[x]=1,pos.insert(1),min_pos.push(1),max_pos.push(1),BST.insert(BST.root,1);
            else if(pos.size()==1)
            {
                for(auto y:pos)
                {
                    if(y-1>=n-y) seat[x]=1;
                    else seat[x]=n;
                    node tmp={{y,seat[x]},(y+seat[x])>>1,dist(min(y,seat[x]),max(y,seat[x]))};
                    if(tmp.now.first>tmp.now.second) swap(tmp.now.first,tmp.now.second);
                    q.push(tmp),tag[{tmp.now.first,tmp.now.second}]=0;
                }
                pos.insert(seat[x]),min_pos.push(seat[x]),max_pos.push(seat[x]),BST.insert(BST.root,seat[x]);
            }
            else
            {
                while(!pos.count(min_pos.top())) min_pos.pop();
                while(!pos.count(max_pos.top())) max_pos.pop();
                int L=min_pos.top(),R=max_pos.top();
                int maxdis=max(L-1,n-R);
                while(q.top().dis>=maxdis && tag[q.top().now]) q.pop();
                maxdis=max(maxdis,q.top().dis);
                if(L-1==maxdis)
                {
                    seat[x]=1;
                    node tmp={{seat[x],L},(seat[x]+L)>>1,dist(seat[x],L)};
                    q.push(tmp),tag[{seat[x],L}]=0;
                }
                else if(q.top().dis==maxdis)
                {
                    seat[x]=q.top().mid;
                    node tmp1={{q.top().now.first,seat[x]},(q.top().now.first+seat[x])>>1,dist(q.top().now.first,seat[x])};
                    node tmp2={{seat[x],q.top().now.second},(q.top().now.second+seat[x])>>1,dist(seat[x],q.top().now.second)};
                    q.push(tmp1),q.push(tmp2);
                    tag[q.top().now]=1;
                    tag[{q.top().now.first,seat[x]}]=0;
                    tag[{seat[x],q.top().now.second}]=0;
                }
                else
                {
                    seat[x]=n;
                    node tmp={{R,seat[x]},(seat[x]+R)>>1,dist(R,seat[x])};
                    q.push(tmp),tag[{R,seat[x]}]=0;
                }
                pos.insert(seat[x]),min_pos.push(seat[x]),max_pos.push(seat[x]),BST.insert(BST.root,seat[x]);
            }
            if(++cnt==m) break;
        }
        else
        {
            int pre=BST.ask_pre(BST.root,seat[x]),nxt=BST.ask_nxt(BST.root,seat[x]);
            if(pre!=-INF) tag[{pre,seat[x]}]=1;
            if(nxt!=INF) tag[{seat[x],nxt}]=1;
            if(pre!=-INF && nxt!=INF)
            {
                tag[{pre,nxt}]=0;
                node tmp={{pre,nxt},(pre+nxt)>>1,dist(pre,nxt)};
                q.push(tmp);
            }
            pos.erase(seat[x]),BST.del(BST.root,seat[x]);
        }
    }
    for(int i=1;i<=m;++i) printf("%d\n",seat[i]);
    return 0;
}

D.跑步路线

不难发现因为边权互不相同，最小生成树一定唯一（证明见OI WiKi）

然后在最小生成树上求解，答案即为 ∑i=2k[disai−1+disai−dislca(ai−1,ai)×2+(depai−1+depai−deplca(ai−1,ai)×2)×t0]−t0\sum\limits_{i=2}^k[dis_{a_{i-1}}+dis_{a_i}-dis_{lca(a_{i-1},a_i)}\times2+(dep_{a_{i-1}}+dep_{a_i}-dep_{lca(a_{i-1},a_i)}\times2)\times t_0] - t_0

然后就爆 long long 了……

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pa;
const int MAXN=2e5+5;
const int MAXK=1e6+5;
vector<pa>G[MAXN];
struct NODE
{
    int u,v,w;
}edge[MAXN];
int f[MAXN],a[MAXK];
int dep[MAXN],fa[MAXN][21];
__int128_t dis[MAXN];
int n,m;
int getfa(int x){return f[x]==x?x:f[x]=getfa(f[x]);}
bool cmp(NODE x,NODE y){return x.w<y.w;}
void kruskal()
{
    sort(edge+1,edge+m+1,cmp);
    for(int i=1;i<=n;++i) f[i]=i;
    for(int i=1;i<=m;++i)
    {
        int x=edge[i].u,y=edge[i].v,z=edge[i].w;
        if(getfa(x)==getfa(y)) continue;
        G[x].push_back({y,z}),G[y].push_back({x,z});
        f[getfa(x)]=getfa(y);
    }
}
void dfs(int x,int father)
{
    dep[x]=dep[father]+1,fa[x][0]=father;
    for(int i=1;i<=20;++i) fa[x][i]=fa[fa[x][i-1]][i-1];
    for(auto i:G[x])
    {
        int y=i.first,z=i.second;
        if(y==father) continue;
        dis[y]=dis[x]+z,dfs(y,x);
    }
}
int lca(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=20;i>=0;--i) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;--i) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
void print(__int128_t x)
{
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
int main()
{
    freopen("D.in","r",stdin);
    freopen("D.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=m;++i) scanf("%d %d %d",&edge[i].u,&edge[i].v,&edge[i].w);
    kruskal(),dfs(1,0);
    int k,t;
    cin>>k>>t;
    for(int i=1;i<=k;++i) scanf("%d",&a[i]);
    __int128_t ans=0;
    for(int i=2;i<=k;++i)
    {
        if(a[i-1]==a[i]) continue;
        int x=a[i-1],y=a[i],z=lca(x,y);
        ans+=dis[x]+dis[y]-dis[z]*2+(__int128_t)t*(dep[x]+dep[y]-dep[z]*2);
    }
    ans-=t;
    print(ans);
    return 0;
}

//后记&总结：考完感觉AK了，然而还是因为一些细节问题而失分，所以不到最后一刻绝不轻言胜利

笔者能力有限，有未述详尽或有误之处，欢迎指正。

全部评论

相关推荐

10-23 22:31
Université d’Auvergne-Clermont-Ferrand 1 C++
校招三方签约问题
前言最近很多同学拿到offer，都会遇到一个签三方的问题（可能是企业逼签，也可能是自己想签个保底）如果是比较满意，那签了直接结束招聘了，挺开心，挺满意的，那直接签就行，无所谓。焦虑的就是对目前拿的不满意，纠结怎么办针对这个问题，先看《拿到了XXoffer，要不要接，要不要去》通过上面文章了解到了，发offer接过来，变被动为主动，三方一直拖。讲解这个时候就会面临逼签的问题，比如公司hr知道我学校下来三方了，不签就把offer撤回了这个时候怎么办？第一步：试探性的询问就是委婉的问问，看看假如三方已经和其他公司签了，需要XX个时间才能违约愿不愿意等。（注意措辞，委婉的问是先要想人家强烈表达想加入的...
点赞 评论 收藏
分享
头像
10-13 18:10
已编辑
东南大学 C++
HW凉经
。收拾收拾心情下一家吧————————————————10.12更新上面不知道怎么的，每次在手机上编辑都会只有最后一行才会显示。原本不想写凉经的，太伤感情了，但过了一天想了想，凉经的拿起来好好整理，就像象棋一样，你进步最快的时候不是你赢棋的时候，而是在输棋的时候。那废话不多说，就做个复盘吧。一面：1，经典自我介绍2，项目盘问，没啥好说的，感觉问的不是很多3，八股问的比较奇怪，他会深挖性地问一些，比如，我知道MMU，那你知不知道QMMU（记得是这个，总之就是MMU前面加一个字母）4，知不知道slab内存分配器-&gt;这个我清楚5，知不知道排序算法，排序算法一般怎么用6，写一道力扣的，最长回文子串反问：1，工作内容2，工作强度3，关于友商的问题-&gt;后面这个问题问HR去了，和中兴有关，数通这个行业和友商相关的不要提，这个行业和别的行业不同，别的行业干同一行的都是竞争关系，数通这个行业的不同企业的关系比较微妙。特别细节的问题我确实不知道，但一面没挂我。接下来是我被挂的二面，先说说我挂在哪里，技术性问题我应该没啥问题，主要是一些解决问题思路上的回答，一方面是这方面我准备的不多，另一方面是这个面试写的是“专业面试二面”，但是感觉问的问题都是一些主管面/综合面才会问的问题，就是不问技术问方法论。我以前形成的思维定式就是专业面会就是会，不会就直说不会，但事实上如果问到方法论性质的问题的话得扯一下皮，不能按照上面这个模式。刚到位置上就看到面试官叹了一口气，有一些不详的预感。我是下午1点45左右面的。1，经典自我介绍2，你是怎么完成这个项目的，分成几个步骤。我大致说了一下。你有没有觉得你的步骤里面缺了一些什么，（这里已经在引导我往他想的那个方向走了），比如你一个人的能力永远是不够的,,,我们平时会有一些组内的会议来沟通我们的所思所想。。。。3，你在项目中遇到的最困难的地方在什么方面4，说一下你知道的TCP/IP协议网络模型中的网络层有关的协议......5，接着4问，你觉得现在的socket有什么样的缺点，有什么样的优化方向？6，中间手撕了一道很简单的快慢指针的问题。大概是在链表的倒数第N个位置插入一个节点。————————————————————————————————————10.13晚更新补充一下一面说的一些奇怪的概念：1，提到了RPC2，提到了fu（第四声）拷贝，我当时说我只知道零拷贝，知道mmap，然后他说mmap是其中的一种方式，然后他问我知不知道DPDK，我说不知道，他说这个是一个高性能的拷贝方式3，MMU这个前面加了一个什么字母我这里没记，别问我了4，后面还提到了LTU，VFIO，孩子真的不会。
走呀走：华子二面可能会有场景题的，是有些开放性的问题了
点赞 评论 收藏
分享
10-15 16:40
河南科技大学 Java
点赞 评论 收藏
分享
评论
2
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 牛客树洞，我想对你说 #
19393次浏览 137人参与
# 大学最后一个寒假，我想…… #
56047次浏览 613人参与
# 快手技术岗信息交流阵地 #
8472次浏览 60人参与
# 你最近一次加班是什么时候？ #
94660次浏览 515人参与
# 除了主业以外，你还有哪些其他收入？ #
32653次浏览 299人参与
# 你最满意的offer薪资是哪家公司？ #
43126次浏览 214人参与
# 求职中的尴尬瞬间 #
7887次浏览 66人参与
# 应届生被毁约被毁意向了怎么办 #
48450次浏览 282人参与
# 当下环境，你会继续卷互联网，还是看其他行业机会 #
138313次浏览 886人参与
# 机械人避雷的岗位/公司 #
30737次浏览 250人参与
# 研究所笔面经互助 #
98367次浏览 550人参与
# 牛客周边新品开箱 #
12237次浏览 91人参与
# 国央企薪资爆料 #
123781次浏览 580人参与
# 如何KTV领导 #
74691次浏览 505人参与
# 硬件人的春招flag #
53518次浏览 435人参与
# 牛友的志愿填报指南 #
37130次浏览 189人参与
# 打工人锐评公司红黑榜 #
176613次浏览 1023人参与
# 怎么给家人解释你的工作？ #
16175次浏览 96人参与
# 得物app工作体验 #
30676次浏览 69人参与
# 国企还是互联网，你怎么选？ #
173329次浏览 1315人参与
# 25届非技术实习投递记录 #
132782次浏览 993人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务