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

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

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

摘要

/ABCDEFGHIJ
场上
zyj
wrf
lmj

题目

A.Permutation

题意

求一个 1~p-1 的排列,要求在模 p 意义下,后一项总是前一项的两倍或三倍。

题解

做法

每次尽量乘 2,如果重复就乘一次 3。

证明

由欧拉定理,某个数乘以 2 的幂构成循环,并且整个循环乘 3 必然正好跳到另一个循环。
所以每次跳跃,遍历整个循环,再跳跃即可。

时间复杂度

$O(n)$

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int inf=0x3f3f3f3f;
const ll mint=0x7fffffff;
const ll linf=1000000000000000000LL;
const ll mod=998244353LL;
const double eps=1e-3;

const int N=1000200;

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;
}

int main(void)
{
    //ios::sync_with_stdio(false);
    
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    
    for(int _=read();_>0;_--)
    {
        ll p=read();
        bitset<N> b;
        vector<ll> v;
        bool f=true;

        ll pos=1;
        while(v.size()<p-1)
        {
            v.push_back(pos);
            b[pos]=true;
            if(!b[pos*2%p]) pos=pos*2%p;
            else if(!b[pos*3%p]) pos=pos*3%p;
            else
            {
                if(v.size()<p-1)
                {
                    f=false;
                    break;
                }
            }
        }
        if(!f) printf("-1\n");
        else
        {
            for(int i=0;i<v.size();i++) printf("%lld ",v[i]);
            printf("\n");
        }
        
    }
    
    return 0;
}

B.KMP Algorithm

题意

题解

代码


C.Decrement on the Tree

lmj 2:49:09 +1

题意

给定一棵树和边权,每次操作可以使某一条路径上的边全部减一,求最少需要几次操作,有q次修改,每次修改一条边的边权,求修改完之后最少需要几次操作

题解

首先考虑无修改的情况。将一个点和他父亲的连边的值记为$val_{fa}$,将其子边的权值和记为$val_{sum}$,将子边中的最大值记为$val_{max}$。
对于某一个点,可以发现经过这个点的路径数与该点所连的所有边有关,考虑将这个路径分为只在该点的子树内和连到该点的子树外。连到该点子树外的路径,显然只和该点与其父亲的这条边有关,然后我们可以将其扩展,将一部分子树内的边也消耗掉。(这里的贡献可以在往上回溯的时候计算)那么我们还需要删掉的边就是$val_{sum}-val_{fa}$,当前这个值小于0就不需要了。然后对于这还需要删掉的边权,考虑两个两个减,此时需要注意最大值过大时其他边用完会导致接下来的操作只能减1,对答案有负影响。如果$val_{max}>val_{sum}-val_{max}-val_{fa}$,那么所需要的额外次数就是$val_{max}-val_{fa}$,这个是化简出来的,没化简的可以看代码,否则的话就是$(val_{sum}-val_{fa}+1)/2$
对于修改情况,我们可以发现只对这条边所连的2个点的贡献有影响,由于对点重新遍历一遍边较为麻烦,在第一次求答案时维护好当前子边和,还要动态求最大值,所以将子边存入multiset,这样就只需要一次删除一次添加就可以获得当前的情况,然后重新计算当前点的贡献即可

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
#define inf 0x3f3f3f
const int N=1e5+5;
int head[N*2],nxt[N*2],to[N*2],w[N*2];
int fa[N];
int vis[N];
ll ans[N];    
ll sum[N];
multiset<int>s[N];
int cnt;
ll ans1=0;
struct node
{
    int x,y,z;
}edge[N];
void add(int u,int v,int z)
{
    to[++cnt]=v;
    w[cnt]=z;
    nxt[cnt]=head[u];
    head[u]=cnt;
}
void dfs(int x,ll tmp)
{
    vis[x]=1;
    for(int i=head[x];i;i=nxt[i]){
        int v=to[i];
        if(vis[v])continue;
        fa[v]=x;
        dfs(v,w[i]);
        sum[x]+=w[i];
        s[x].insert(w[i]);
    }
    if(tmp<sum[x]){
        if(s[x].size()==1){
            ans[x]=sum[x]-tmp;
        }else{
            ll tmp1=sum[x]-*(--s[x].end());
            if(tmp1>=(sum[x]-tmp+1)/2){
                ans[x]=(sum[x]-tmp+1)/2;
            }else{
                ans[x]=tmp1+(sum[x]-tmp-2*tmp1);
            }
        }
    }
}
void cal(int x,ll tmp)
{
    ans1-=ans[x];
    if(tmp<sum[x]){
        if(s[x].size()==1){
            ans[x]=sum[x]-tmp;
        }else{
            ll tmp1=sum[x]-*(--s[x].end());
            if(tmp1>=(sum[x]-tmp+1)/2){
                ans[x]=(sum[x]-tmp+1)/2;
            }else{
                ans[x]=tmp1+(sum[x]-tmp-2*tmp1);
            }
        }
    }else{
        ans[x]=0;
    }
    ans1+=ans[x];
}
void cal1(int x,ll past,ll now,ll tmp)
{
    s[x].erase(s[x].lower_bound(past));
    s[x].insert(now);
    sum[x]-=past;
    sum[x]+=now;
    ans1-=ans[x];
    if(tmp<sum[x]){
        if(s[x].size()==1){
            ans[x]=sum[x]-tmp;
        }else{
            ll tmp1=sum[x]-*(--s[x].end());
            if(tmp1>=(sum[x]-tmp+1)/2){
                ans[x]=(sum[x]-tmp+1)/2;
            }else{
                ans[x]=tmp1+(sum[x]-tmp-2*tmp1);
            }
        }
    }else{
        ans[x]=0;
    }
    ans1+=ans[x];
}
map<paii,ll>mp;
void work()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        mp[{x,y}]=mp[{y,x}]=z;
        edge[i]={x,y,z};
        add(x,y,z);
        add(y,x,z);
    }
    dfs(1,0);
    // for(int i=1;i<=n;i++){
    //     printf("%d ",fa[i]);
    // }
    for(int i=1;i<=n;i++){
        ans1+=ans[i];
    }
    printf("%lld\n",ans1);
    for(int i=1;i<=m;i++){
        int op,v;
        scanf("%d%d",&op,&v);
        if(fa[edge[op].x]==edge[op].y){
            swap(edge[op].x,edge[op].y);
        }
        cal(edge[op].y,v);
        cal1(edge[op].x,edge[op].z,v,(edge[op].x==1)?0:mp[{edge[op].x,fa[edge[op].x]}]);
        edge[op].z=v;
        mp[{edge[op].x,edge[op].y}]=mp[{edge[op].y,edge[op].x}]=edge[op].z;
        printf("%lld\n",ans1);
    }
}
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();
    }
}

D.Hearthstone Battlegrounds

lmj 赛后

题意

给定4种鱼人,均带有剧毒,身材为1/1e9,1攻,1e9血,4种鱼人分别为圣盾亡语,圣盾,亡语,无特效,亡语为招一个1/1,圣盾为格挡一次攻击,剧毒为受到伤害秒杀(对圣盾无效),可以任意选择攻击方式,求是否能获胜。

题解

如果要尽可能的获胜,那么尽量要让1/1去破圣盾,然后对面的亡语可以被我们的无盾鱼人无伤吃掉,那么我们肯定是选择带有亡语的鱼人优先攻击,对于我们的选择就是优先亡语,再是圣盾亡语,再是圣盾,再是无特效,原因,我们要尽可能的快速出1/1将对面的圣盾破完,这样就不需要用鱼人去撞对面的圣盾;
对于攻击目标,优先亡语,再是无特效,再是圣盾亡语,再是圣盾。首先圣盾显然是会放到偏后的,因为在前面的过程中有可能还能出亡语将对面的圣盾破掉,然后为什么是优先打亡语怪呢,优先打亡语怪可以尽量保证在出亡语的时候,我们还有更多的鱼人可以去吃掉他,显然是更优的。

代码

#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 a[5];//0 shengdunwangyu 1shengdun 2wangyu 3wu  4 1/1
int b[5];
void solve()
{
    while(b[0]||b[1]||b[2]||b[3]){
        // for(int i=0;i<=4;i++){
        //     printf("%d ",a[i]);
        // }
        // printf("\n");
        // for(int i=0;i<=4;i++){
        //     printf("%d ",b[i]);
        // }
        // printf("\n");
        if(a[2]){
            if(b[2]){
                b[2]--,a[2]--,b[4]++;
                if(b[0]){
                    b[0]--,b[2]++;
                }else if(b[1]){
                    b[1]--,b[3]++;
                }else{
                    a[4]++;
                }
            }else if(b[3]){
                b[3]--,a[2]--;
                if(b[0]){
                    b[0]--,b[2]++;
                }else if(b[1]){
                    b[1]--,b[3]++;
                }else{
                    a[4]++;
                }
            }else if(b[0]){
                b[0]--,b[2]++,a[2]--;
                if(b[0]){
                    b[0]--,b[2]++;
                }else if(b[1]){
                    b[1]--,b[3]++;
                }else{
                    a[4]++;
                }
            }else if(b[1]){
                b[1]--,b[3]++,a[2]--;
                if(b[0]){
                    b[0]--,b[2]++;
                }else if(b[1]){
                    b[1]--,b[3]++;
                }else{
                    a[4]++;
                }
            }
        }else if(a[0]){
            if(b[2]){
                b[2]--,a[0]--,a[2]++,b[4]++;
            }else if(b[3]){
                b[3]--,a[0]--,a[2]++;
            }else if(b[0]){
                b[0]--,b[2]++,a[0]--,a[2]++;
            }else if(b[1]){
                b[1]--,b[3]++,a[0]--,a[2]++;
            }
        }else if(a[1]){
            if(b[2]){
                b[2]--,a[1]--,a[3]++,b[4]++;
            }else if(b[3]){
                b[3]--,a[3]++,a[1]--;
            }else if(b[0]){
                b[0]--,b[2]++,a[3]++,a[1]--;
            }else if(b[1]){
                b[1]--,b[3]++,a[3]++,a[1]--;
            }
        }
        else if(a[3]){
            if(b[2]){
                b[2]--,a[3]--,b[4]++;
            }else if(b[3]){
                b[3]--,a[3]--;
            }else if(b[0]){
                b[0]--,b[2]++,a[3]--;
            }else if(b[1]){
                b[1]--,b[3]++,a[3]--;
            }
        }
        if(a[2]||a[3]){
            b[4]=0;
        }
        if(a[0]==0&&a[1]==0&&a[2]==0&&a[3]==0)return;
    }
    
}
void work()
{
    for(int i=0;i<=3;i++){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<=3;i++){
        scanf("%d",&b[i]);
    }
    a[4]=0;
    b[4]=0;
    solve();
    // for(int i=0;i<=4;i++){
    //     printf("%d ",a[i]);
    // }
    if(a[1]||a[2]||a[3]||a[0]){
        printf("Yes\n");
    }else if(b[1]||b[2]||b[3]||b[0]){
        printf("No\n");
    }else{
        if(a[4]>b[4]){
            printf("Yes\n");
        }else{
            printf("No\n");
        }
    }
}
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();
    }
}

E.Game

lmj 0:40:14 +1

题意

给定一个方块图,可以将任意行往左推,推的同时会将其上面的方块一起推动,如果方块的下面没有方块,那么会掉下去,求该图的最小高度。

题解

猜了一下,直接求前缀的平均值。
证明待补

代码

#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 a[N];
void work()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    ll ans=0;
    ll now=0;
    for(int i=1;i<=n;i++){
        now+=a[i];
        ans=max(ans,(now+i-1)/i);
    }
    printf("%lld\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();
    }
}

F.Parenthesis sequence

题意

题解

代码


G.Math Test

题意

题解

代码


H.Heyawake

题意

题解

代码


I.Tournament

zyj (赛后)

题意

对$n*(n-1)/2$个$pair$排序,使得每个数出现时间和结束时间之差的和最小。

题解

考虑$n=5$时,容易想到初始情况显然为:

1,2
1,3
1,4
1,5
2,3
2,4
2,5
3,4
3,5
4,5

于是我们考虑改变一个$pair$的位置会带来的影响。

1,2
1,3
2,3
1,4
1,5
2,4
2,5
3,4
3,5
4,5

当我们把$(2,3)$移动到这个位置时,$1$的结束时间推迟了$1$,但是$4$和$5$的开始时间都推迟了$1$,相当于对答案带来了$1-2=-1$的贡献,那么我们就按着这个策略不断判断哪些$pair$是可以插到前面的就可以了。

代码

#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)1e6+100;
const int mod=(int)1e9+7;
void solve(){
    int n;scanf("%d",&n);
    rep(i,2,n-1) rep(j,1,min(i-1,n-i)) printf("%d %d\n",j,i);
    rep(i,1,n-1) rep(j,n-min(i,n-i)+1,n) printf("%d %d\n",i,j);
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}

J.Identical Trees

题意

给出两棵带标号的有根树,每次操作可以修改其中某棵树上某节点的标号。
求通过尽量少的操作使得两棵树全等。

题解

做法

令可以修改的那棵树为 $T_1$,另一棵为 $T_2$。
定义 $G(i,j)$ 表示 $T_1$ 中根为 $i$ 的子树变成 $T_2$ 中根为 $j$ 的子树所需的代价;
定义 $D(i,j)$ 表示 $T_1$ 中根为 $i$ 的子树是否与 $T_2$ 中根为 $j$ 的子树同构。

对于某一对 $i,j$,他们同构的充要条件为,存在各个子树之间的一一对应关系,使得这些子树之间分别同构。代价则是各个子树对之间变化的代价。
这样就可以转化为一个二分图最小权完美匹配的问题,网络流即可。

时间复杂度

$O(n^3)$

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int inf=0x3f3f3f3f;
const ll mint=0x7fffffff;
const ll linf=1000000000000000000LL;
const ll mod=998244353LL;
const double eps=1e-3;

const int N=520;

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;
}


struct ZKW_SPFA{
    #define maxn 5005
    #define maxe 53050
    const int INF=(int)1e9;
    int dis[maxn],vis[maxn],head[maxn],tot;
    int n,Cost=0,Flow=0;
    struct Edge{int v,cap,cost,nxt;}g[maxe<<1];
    void init(int _n){Cost=0,Flow=0,tot=0;memset(head,-1,sizeof(head));n=_n;}
    void add(int u,int v,int cap,int cost){
        g[tot]={v,cap,cost,head[u]};head[u]=tot++;
    }
    void addedge(int u,int v,int cap,int cost){
        add(u,v,cap,cost);add(v,u,0,-cost);
    }
    bool spfa(int S,int T){
        for(int i=0;i<=n;i++) vis[i]=0,dis[i]=INF;
        deque<int>Q;Q.push_back(T);dis[T]=0;vis[T]=1;
        while(!Q.empty()){
            int u=Q.front();Q.pop_front();
            for(int i=head[u],v;~i;i=g[i].nxt)
                if(g[i^1].cap&&dis[v=g[i].v]>dis[u]+g[i^1].cost){
                    dis[v]=dis[u]+g[i^1].cost;
                    if(!vis[v]){
                        vis[v]=1;
                        if(!Q.empty()&&dis[v]<dis[Q.front()]) Q.push_front(v);
                        else Q.push_back(v);
                        //SLF优化
                    }
                } vis[u]=0;
        } return dis[S]<INF;
    }
    int dfs(int S,int T,int flow){
        if(S==T){vis[T]=1;return flow;}
        int used=0,res;vis[S]=1;
        for(int i=head[S],v;~i;i=g[i].nxt)
            if(!vis[v=g[i].v]&&g[i].cap&&dis[S]-g[i].cost==dis[v]){
                res=dfs(v,T,min(g[i].cap,flow-used));
                if(res) Cost+=res*g[i].cost,g[i].cap-=res,g[i^1].cap+=res,used+=res;
                if(used==flow)break;
            }
        return used;
    }
    void solve(int S,int T){
        while(spfa(S,T)){
            vis[T]=1;
            while(vis[T]) memset(vis,0,sizeof vis),Flow+=dfs(S,T,INF);
        }
    }
    //先zkw.init(n),再zkw.addedge(),再zkw.solve(S,T)
    //可以输出zkw.Flow和zkw.Cost
}zkw;

int n;
vector<vector<int> > t1,t2;
ll G[N][N],D[N][N];

void F(int s1,int s2)
{
    if(t1[s1].size()!=t2[s2].size()) 
    {
        D[s1][s2]=-1;
        return ;
    }
    if(t1[s1].size()==0 && t2[s2].size()==0)
    {
        D[s1][s2]=1;
        G[s1][s2]=(s1!=s2?1:0);
        return ;
    }

    for(int i:t1[s1]) for(int j:t2[s2]) F(i,j);

    zkw.init(1020);
    for(int i:t1[s1])
    {
        for(int j:t2[s2])
        {
            if(D[i][j]==1)
            {
                zkw.addedge(i,n+j,1,G[i][j]);
            }
        }
    }
    int S=2*n+3,T=2*n+4;
    for(int i:t1[s1]) zkw.addedge(S,i,1,0);
    for(int j:t2[s2]) zkw.addedge(j+n,T,1,0);

    zkw.solve(S,T);
    // printf("%lld ### \n",zkw.Cost);
    if(zkw.Flow!=t1[s1].size())
    {
        D[s1][s2]=-1;
    }
    else
    {
        D[s1][s2]=1;
        G[s1][s2]=zkw.Cost;
        if(s1!=s2) G[s1][s2]++;
    }
    
    return ;
}

int main(void)
{
    //ios::sync_with_stdio(false);
    
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);

    n=read();
    t1.resize(n+1),t2.resize(n+1);
    int s1,s2;

    for(int i=1;i<=n;i++) t1[read()].push_back(i);
    for(int i=1;i<=n;i++) t2[read()].push_back(i);
    s1=t1[0][0],s2=t2[0][0];

    F(s1,s2);
    printf("%lld",G[s1][s2]);


    //     printf("\n");
    // for(int i=1;i<=n;i++)
    // {
    //     for(int j=1;j<=n;j++)
    //     {
    //         printf("%lld ",G[i][j]);
    //     }
    //     printf("\n");
    // }
    //     printf("\n");
    // for(int i=1;i<=n;i++)
    // {
    //     for(int j=1;j<=n;j++)
    //     {
    //         printf("%lld ",D[i][j]);
    //     }
    //     printf("\n");
    // }
    
    return 0;
}
Responses