2020牛客暑期多校训练营(第九场)
in 牛客多校多校训练 with 0 comment

2020牛客暑期多校训练营(第九场)

in 牛客多校多校训练 with 0 comment

摘要

/ABCDEFGHIJKL
场上
zyj
wrf
lmj

题目

A.Groundhog and 2-Power Representation

题意

定义 $2(a)=2^a$,给出仅由 2、加号和括号组成的式子,求它的值

题解

做法

python 下使用 eval() 即可

时间复杂度

$O(Accepted)$

代码

print(eval(input().replace('(','**(')))

B.Groundhog and Apple Tree

题意

给出一棵树,每条边与每个点都有权值。
每次经过一条边需要消耗边权点体力,第一次经过一个点恢复点权点体力。
要求每条边最多经过两次,从点 1 经过每个点回到点 1,求最小的初始体力。

题解

做法

显然所求顺序为某种 dfs 序。

设恢复体力为正收益方向,即边权均取负值,点权均取正值。
设点(子树) $i$ 权值为 $a_i$,到父节点的边权为 $f_i$(特殊的,$f_1=0$),进入所属子树的总收益为 $t_i$,进入所属子树后最坏情况下的收益为 $s_i$。
答案即是 $-s_1$。

首先,每一个点的 $t_i$ 都不会随行走策略而变化。因为不论行走策略如何,在子树中的每一条边都会被经过两次,每个点都会被经过一次。
所以有:

$$ t_i=2f_i+a_i+\sum_{j \in son(i)}t_i $$

一遍 dfs 即可求出全部的 $t_i$。

求 $s_i$ 时就要考虑策略问题。
在某棵子树内,每一时刻的贡献将由两者决定:当前已经走完的子树,以及目前正在走的子树。
当前已经走完的每棵子树 $j$ 均给出 $t_j$ 的贡献,而目前正在走的子树 $k$ 给出的最大贡献即是 $s_k$。
也就是说,需要给出一种策略,以最大化如下式子:

$$ s'_i=\min_{k \in son(i)}\left\{{s_k+\sum_{j \in son(i) \ \wedge \ p_j<p_k} t_j}\right\} $$

(此处 $p_i$ 表示遍历子树的顺序)
考虑对子树进行排序。如果有 $p_l+1=p_r$,那么这两者无需交换的条件为:

$$ \min(s_l,t_l+s_r)>\min(s_r,t_r+s_l) $$

详细证明考虑下表:

$pos$$k_1$${s'_i}_1$$k_2$${s'_i}_2$
$p$$l$$\Sigma_{pre}+s_l$$r$$\Sigma_{pre}+s_r$
$p+1$$r$$\Sigma_{pre}+t_l+s_r$$l$$\Sigma_{pre}+t_r+s_l$

但这个条件是必要的而非充分的。考虑 $t_lt_r=0$ 的情况,就发现它可能将不相等的两个点判为相等。
所以考虑将其变成一个充分的结论:

时间复杂度

$O(n\log n)$

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=100020;

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

typedef vector<vector<pair<int,ll> > > graph;

// graph &g;

graph g;
vector<ll> a,h;
vector<ll> t,s;

bool cmp(const pair<int,ll> &a,const pair<int,ll> &b)
{
    bool f;
    if(h[a.first]<h[b.first]) return true;
    else if(h[a.first]>h[b.first]) return false;
    else
    {
        if(t[a.first]>=0 && t[b.first]<0) f=true;
        else if(t[a.first]<0 && t[b.first]>=0) f=false;
        else if(t[a.first]>=0 && t[b.first]>=0) f=s[a.first]>s[b.first];
        else f=t[a.first]-s[a.first]>t[b.first]-s[b.first];
    }
    return f;
}

ll dfs1(int n,int nh)
{
    h[n]=nh;
    for(auto i:g[n])
    {
        if(h[i.first]==0)
        {
            t[n]+=dfs1(i.first,nh+1);
        }
        else t[n]-=i.second*2;
    }
    return t[n];
}
void dfs2(int n,ll fa)
{
    if(g[n].size()==1 && h[n]>1) 
    {
        s[n]=min(fa,t[n]);
        return ;
    }
    for(auto i:g[n])
    {
        if(h[i.first]>h[n])
        {
            dfs2(i.first,-i.second);
        }
    }
    sort(g[n].begin(),g[n].end(),cmp);
    s[n]=0;
    ll now=0;
    for(int i=(h[n]>1?1:0);i<g[n].size();i++)
    {
        s[n]=min(now+s[g[n][i].first],s[n]);
        now+=t[g[n][i].first];
    }
    s[n]+=fa+a[n];
    s[n]=min(s[n],t[n]);
    s[n]=min(s[n],fa);
}

void solve()
{
    g.clear(),a.clear(),t.clear(),s.clear(),h.clear();

    int n=read();
    g.resize(n+1);
    a.resize(n+1),h.resize(n+1);
    s.resize(n+1);
    t.resize(n+1);

    for(int i=1;i<=n;i++) t[i]=a[i]=read();
    for(int i=1;i<n;i++)
    {
        int l=read(),r=read();
        ll w=read();
        g[l].push_back({r,w});
        g[r].push_back({l,w});
    }


    dfs1(1,1);
    dfs2(1,0);

    ll ans=s[1];
    printf("%lld\n",max(0LL,-ans));
}

int main(void)
{
    for(int _=read();_>0;_--)
    {
        solve();
    }
    
    return 0;
}

C.Groundhog and Gaming Time

题意

题解

代码


D.Groundhog and Golden Apple

题意

题解

代码


E.Groundhog Chasing Death

lmj 2:02:25 +2

题意

给定$a,b,c,d,x,y$,求$\prod_{i=a}^b\prod_{j=c}^d gcd(x^i,y^j)$模998244353

题解

考虑答案只和x,y的共同质因数有关,所以将共同质因数全部取出(最多10个),然后枚举i,可以发现j从c到d这个区间内,答案是一个一次函数加上一个常函数,可以快速求解。但是如果直接在循环内求答案的话 复杂度是O(10nlogn) 显然会T掉,考虑将幂次存储下来 利用欧拉降幂 去掉log 在最后总体求答案 即可通过。

代码

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=998244353;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int q[105];
int cnt[105];
int q1[105];
int cnt1[105];
int q2[105];
paii cnt2[105];
ll tmp1[105];
ll tmp2[105];
ll sum1[105];
ll sum2[105];
void work()
{
    int a,b,c,d,x,y;
    scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&x,&y);
    double time=clock();
    int tot=0;
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            q[++tot]=i;
            while(x%i==0){
                x/=i;
                cnt[tot]++;
            }
        }
    }
    if(x!=1){
        q[++tot]=x;
        cnt[tot]=1;
    }
    int tot1=0;
    for(int i=2;i*i<=y;i++){
        if(y%i==0){
            q1[++tot1]=i;
            while(y%i==0){
                y/=i;
                cnt1[tot1]++;
            }
        }
    }
    if(y!=1){
        q1[++tot1]=y;
        cnt1[tot1]=1;
    }
    int tot2=0;
    for(int i=1;i<=tot;i++){
        for(int j=1;j<=tot1;j++){
            if(q[i]==q1[j]){
                q2[++tot2]=q[i];
                cnt2[tot2]={cnt[i],cnt1[j]};
            }
        }
    }
    for(int i=1;i<=tot2;i++){
        tmp1[i]=qpow(q2[i],cnt2[i].fr);
        tmp2[i]=qpow(q2[i],cnt2[i].sc);
    }
    ll ans=1;
    for(int i=a;i<=b;i++){
        for(int j=1;j<=tot2;j++){
            int limit=i*cnt2[j].fr/cnt2[j].sc;
            if(limit<c){
                sum1[j]=(sum1[j]+1ll*i*(d-c+1))%(p-1);
                //ans=ans*qpow(tmp1[j],1ll*i*(d-c+1))%p;
            }else if(limit>=d){
                sum2[j]=(sum2[j]+1ll*(c+d)*(d-c+1)/2)%(p-1);
                //ans=ans*qpow(tmp2[j],1ll*(c+d)*(d-c+1)/2)%p;
            }else{
                sum2[j]=(sum2[j]+1ll*(c+limit)*(limit-c+1)/2)%(p-1);
                sum1[j]=(sum1[j]+1ll*i*(d-limit))%(p-1);
                //ans=ans*qpow(tmp2[j],1ll*(c+limit)*(limit-c+1)/2)%p;
                //ans=ans*qpow(tmp1[j],1ll*i*(d-limit))%p;
            }
            //printf("%d %d %d %d %lld\n",i,q2[j],cnt2[j].fr,cnt2[j].sc,ans);
        }
    }
    for(int i=1;i<=tot2;i++){
        ans=ans*qpow(tmp1[i],sum1[i])%p;
        ans=ans*qpow(tmp2[i],sum2[i])%p;
    }
    printf("%lld\n",ans);
    //printf("%f\n",clock()-time);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

F.Groundhog Looking Dowdy

lmj 1:17:21 +1

题意

给定n天,每天有$k_i$种权值选择,要求选出m天,使得选出的权值的最大值和最小值差最小。

题解

将所有点按照权值进行排序,然后不断将当前权值最小的加入,如果已经有该天的权值,那么把另一个权值删去,如果天数超过m,将当前权值最小的删除,然后就可以得到一个区间,不断双指针滑动求解即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e6+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
paii q[N];
int pos[N];
int vis[N];
void work()
{
    int tot=0;
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int k;
        scanf("%d",&k);
        for(int j=1;j<=k;j++){
            int x;
            scanf("%d",&x);
            q[++tot]={x,i};
        }
    }
    sort(q+1,q+tot+1);
    int sum=0;
    int ans=1e9;
    int l=1;
    int r=1;
       for(int r=1;r<=tot;r++){
           if(pos[q[r].sc]){
               vis[pos[q[r].sc]]=1;
               pos[q[r].sc]=r;
           }else{
               sum++;
               pos[q[r].sc]=r;
           }
           if(sum>m){
               while(l<=r&&sum>m){
                   if(vis[l]){
                       l++;
                   }else{
                       pos[q[l].sc]=0;
                       sum--;
                       l++;
                   }
               }
           }
           while(vis[l])l++;
           if(sum==m){
               //printf("%d %d\n",q[r].fr,q[l].fr);
               ans=min(ans,q[r].fr-q[l].fr);
           }
       }
       printf("%d\n",ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

G.Groundhog Playing Scissors

题意

题解

代码


H.Groundhog Speaking Groundhogish

题意

题解

代码


I.The Crime-solving Plan of Groundhog

zyj+wrf (01:28:15) +3

题意

给出$n$个$[0,9]$的数,要求你用他们组成两个没有前导零的正整数,并且要求乘积最小,输出乘积

题解

把当前的数字拆成4个数$a, b, c, d(a \leq b \leq c \leq d)$,那么我们有两种决策:两位数×两位数,或者三位数×一位数。

以此类推可以证明,留一个最小的正整数作为第一个数,剩下的所有数字排成最小的数作为第二个数时,答案取到最小值。

代码

高精度都是板子,就贴个solve吧

void solve(){
    scanf("%d",&n);
    rep(i,1,n) scanf("%d",&a[i]);
    sort(a+1,a+1+n);int pos=0;
    rep(i,1,n) if(a[i]>0){pos=i;break;}
    bign x=bign(a[pos]);
    int top=0;char c[maxn];
    c[top++]=a[pos+1]+'0';
    rep(i,1,pos-1) c[top++]='0';
    rep(i,pos+2,n) c[top++]=a[i]+'0';
    c[top]='\0';
    bign y=bign(c);bign ans=x*y;
    ans.print();puts("");
}

J.The Escape Plan of Groundhog

zyj (赛后)

题意

给出一个$500 \times 500$的01矩阵,问有多少子矩阵满足:

  1. 矩阵的四条边全为1
  2. 矩阵除去边界以外的部分,0和1的数量差不超过1
  3. 矩阵长宽均大于1

题解

显然此题要求我们做到$O(n^3)$的复杂度,那么一个通俗的套路就是$n^2$枚举上下边界,然后对于列扫一遍,用某些前缀和来维护。
我们将原矩阵中的$0$看成$-1$,在枚举完上下边界后去扫列,很显然在扫列的过程中我们可以知道在当前位置之前上下边界都是连续$1$的最左列,并且通过行这一维的前缀和我们可以知道某一列上两行之间的和。换句话说,我们可以很轻松地得到矩阵的上下和右边界,那么不妨设当前在列$r$为一个合法的右边界,保证上下边界都是连续$1$的最左列是$l$,那么此时问题变为:询问列$l$到列$r$中有多少全$1$列满足其和列$r$构成的矩阵内部的和为$[-1,0,1]$中的一个。
于是我们可以维护一个$pre[i]$表示截止当前列,其向左的前缀和为多少。然后再维护一个$num[i]$表示截止当前列,满足列$l$到列$j$的前缀和为$i$的$j$有多少个,那么答案就可以很轻松的得到了。

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)5e5+100;
const int mod=(int)1e9+7;
int mp[550][550],sub[550][550],pre[550],num[maxn<<1];
int main(){
    int n,m;scanf("%d%d",&n,&m);
    rep(i,1,n)rep(j,1,m){
        scanf("%d",&mp[i][j]);
        if(!mp[i][j]) mp[i][j]=-1;
        sub[i][j]=sub[i-1][j]+mp[i][j];
    }pre[0]=maxn;ll ans=0;
    rep(i,1,n)rep(j,i+1,n){int pos=1;
        rep(k,1,m){
            if(mp[i][k]!=1||mp[j][k]!=1){
                rep(l,pos,k)if(sub[j][l]-sub[i-1][l]==j-i+1)num[pre[l]]--;
                pos=k+1;pre[k]=maxn;continue;
            }
            if(sub[j][k]-sub[i-1][k]==j-i+1)
                ans+=num[pre[k-1]]+num[pre[k-1]+1]+num[pre[k-1]-1];
            pre[k]=pre[k-1]+sub[j-1][k]-sub[i][k];
            if(sub[j][k]-sub[i-1][k]==j-i+1)num[pre[k]]++;
        }
        rep(k,pos,m)if(sub[j][k]-sub[i-1][k]==j-i+1)num[pre[k]]--;
    }printf("%lld\n",ans);
}

K.The Flee Plan of Groundhog

lmj 00:29:09 +0

题意

给定一棵树,边权为1,第一个人开始处于1位置,第二个人开始处于2位置。第一个人的速度为1m/s,第二个人的速度为2m/s,一开始第一个人往n点走去,T秒后,第二个人要来追他,第一个人要逃跑,求最晚什么时候被抓住,每一秒先第一个人动,后第二个人动。

题解

显然可以快速求出T秒时第一个人的位置,那么就是第一个人在x位置,第二个人在n位置,第一个人1m/s,第二个人2m/s,求最迟什么时候被追上。
考虑二分答案,如果第一个人能在当前答案时间内走到该位置并且第二个人走不到,说明这个时间是可以的,继续延长,否则缩短。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int vis[N];
int dis[N];
int dis1[N];
vector<int>v[N];
void bfs(int x)
{
    memset(vis,0,sizeof(vis));
    vis[x]=1;
    dis[x]=0;
    queue<int>q;
    q.push(x);
    while(!q.empty()){
        int y=q.front();
        q.pop();
        for(int i=0;i<v[y].size();i++){
            int u=v[y][i];
            if(vis[u])continue;
            dis[u]=dis[y]+1;
            vis[u]=1;
            q.push(u);
        }
    }
}
void bfs1(int x)
{
    memset(vis,0,sizeof(vis));
    vis[x]=1;
    dis1[x]=0;
    queue<int>q;
    q.push(x);
    while(!q.empty()){
        int y=q.front();
        q.pop();
        for(int i=0;i<v[y].size();i++){
            int u=v[y][i];
            if(vis[u])continue;
            dis1[u]=dis1[y]+1;
            vis[u]=1;
            q.push(u);
        }
    }
}
void work()
{
    int n,t;
    scanf("%d%d",&n,&t);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    bfs(1);
    bfs1(n);
    if(dis[n]<=t){
        printf("0\n");return;
    }
    int tmp=0;
    for(int i=1;i<=n;i++){
        if(dis[i]==t&&dis[i]+dis1[i]==dis[n]){
            tmp=i;break;
        }
    }
    bfs(tmp);
    int l=1,r=n;
    while(l<=r){
        int m=(l+r)>>1;
        bool f=0;
        for(int i=1;i<=n;i++){
            if(dis[i]<=m&&dis1[i]>2*m){
                f=1;break;
            }
        }
        if(f){
            l=m+1;
        }else{
            r=m-1;
        }
    }
    printf("%d\n",l);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

L.The Shopping Plan of Groundhog

题意

题解

代码


Responses