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

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

A.旋律的总数

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

所以答案为 $m^{n-1}m^\{n-1\}$，用快速幂计算，时间复杂度 $\mathcal{O}(T\log n)\backslash mathcal\{O\}(T\backslash 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\le 40n\backslash le40$ 如果直接搜复杂度是 ${\prod }_{i=1}^n{a}_i\backslash prod\backslash limits\_\{i=1\}^na\_i$ 的，但题目有个限制：${\sum }_{i=1}^n{a}_i\le 40\backslash sum\backslash limits\_\{i=1\}^na\_i\; \backslash 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$ 开成 $10^{9}10^9$，$100->45100->45$.

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

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

2. 当前有一个位置有人：选 $1\mathrm{/}n1/n$；

3. 选 $1\mathrm{/}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）

然后在最小生成树上求解，答案即为 ${\sum }_{i=2}^k[di{s}_{a_{i-1}}+di{s}_{a_i}-di{s}_{lca(a_{i-1},a_i)}\times 2+(de{p}_{a_{i-1}}+de{p}_{a_i}-de{p}_{lca(a_{i-1},a_i)}\times 2)\times t_0]-t_0\backslash sum\backslash limits\_\{i=2\}^k[dis\_\{a\_\{i-1\}\}+dis\_\{a\_i\}-dis\_\{lca(a\_\{i-1\},a\_i)\}\backslash times2+(dep\_\{a\_\{i-1\}\}+dep\_\{a\_i\}-dep\_\{lca(a\_\{i-1\},a\_i)\}\backslash times2)\backslash 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了，然而还是因为一些细节问题而失分，所以不到最后一刻绝不轻言胜利

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