2020杭电多校联合训练（第九场）
in 杭电多校多校训练 with 0 comment
多校 杭电

2020杭电多校联合训练（第九场）

in 杭电多校多校训练 with 0 comment

多校 杭电

摘要

/ABCDEFGHIJ
场上✔ ✔
zyj ✔
wrf✔ ✔
lmj ✔

题目

A.Tree

题意

给出一棵树，规定边的方向都指向子树。
可以在树上加一条边，使得存在尽量多的点对(i,j)，使得点i能够到达点j。

题解

做法

两次 dfs。
第一次维护所有点子树的补集大小，第二次维护到根的路径上补集大小之和。
取最大的即可。

证明

首先，显然所加边必然是从叶节点连向根节点。
设从根到所求叶节点的路径上各点为 $a_1,a_2,...,a_m$，其子树大小分别为 $k_{a_1},k_{a_2},...,k_{a_m}$。
这里面的每一个点都能到达整棵树。

对于其中的节点 $a_i$ 而言，它原本能够到达 $k_{a_i}$ 个点，而现在可以到达所有的 $n$ 个点，贡献为 $n-k{a_i}$。
那么某一种连接方案的总贡献即为：

$$ n+\sum (n-k_{a_i}) $$

维护和式内的值即可。

时间复杂度

$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=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<int> > graph;

int dfs1(graph& g,vector<int>& v,int n)
{
    v[n]=1;
    for(auto a:g[n])
    {
        v[n]+=dfs1(g,v,a);
    }
    return v[n];
}
ll dfs2(graph &g,vector<int>& v,int n)
{
    ll ans=0;
    for(auto a:g[n])
    {
        ans=max(dfs2(g,v,a),ans);
    }
    ans+=v[n];

    return ans;
}

int main(void)
{
    //ios::sync_with_stdio(false);
    
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    
    for(int _=read();_>0;_--)
    {
        int n=read();
        graph g(n+1);
        vector<int> v(n+1);

        for(int i=2;i<=n;i++)
        {
            g[read()].push_back(i);
        }

        dfs1(g,v,1);
        ll s=0;
        for(int i=1;i<=n;i++) s+=v[i],v[i]=n-v[i];
        printf("%lld\n",dfs2(g,v,1)+s);
    }
    
    return 0;
}

B.Absolute Math

题意

题解

代码

C.Slime and Stones

题意

有两堆石子，博弈双方每次要么从一堆中取石子，要么在两堆中取相差不超过 k 的石子，求先手是否必胜。

题解

做法

检测所求石子堆是否满足如下形式即可：

$$ \{min(a,b),max(a,b)\}=\{\lfloor n\alpha \rfloor,\lfloor n\alpha \rfloor+k+1\} $$

其中

$$ \alpha= {2-(k+1)+\sqrt{(k+1)^2+4} \over 2} $$

证明

本题属于威佐夫博弈的一种推广。

首先，显然所有的必败点关于 $y=x$ 对称。

记 $x \leq y$ 的所有必败点按 $x$ 单调递增排序为 $(x_i,y_i)$，研究它们的性质：
显然有

$$ x_n=\mathop{\mathrm{mex}}\limits_{i<n}\{x_i,y_i\} \tag{1} $$

且 $x$ 与 $y$ 均单调递增。
值得注意的是，任何正整数要么属于 $x$，要么属于 $y$，且只能属于其中之一。原因在于坐标系上每行每列有且仅有一个必败态。
这就可以推得，必然有 $x_n \leq y_n$。反之，由 $(1)$，$y_n$必然会与某个 $x_i$ 或 $y_i$ 相等，矛盾。

接下来记 $y_n=x_n+f(n)$。分两种情况讨论：

首先分析第一种情况。
先分析相反情况：如果必败态转移到了必败态，必然是同时从两堆中拿，因为每行每列有且仅有一个必败态。设两个必败态标号分别为 $n$、$m$，保证 $n>m$。
那么就存在 $|(y_n-y_m)-(x_n-x_m)| =|f(n)-f(m)|\leq k$，返回原问题即得：

$$ \forall m<n , |f(n)-f(m)| > k \tag{2.1} $$

再分析第二种情况。
记该必胜态为 $(x',y')$，$x' \leq y'$。
如果 $x' \in y$，记该必胜态为 $(y_n,y')$，则 $x_n \leq y_n \leq y'$，构造转移 $(y_n,y') \rightarrow (y_n,x_n)$ 即可。
如果 $x' \in x$，记该必胜态为 $(x_n,y')$，情况比较复杂：

$$ \forall n>0,\forall y'<y_n,\exists m<n, |y'-x_n-f(m)| \leq k \tag{2.2} $$

令 $y'=y_n-1$，结合 $(2.1)$ 与 $(2.2)$ 两个约束可得：

$$ \forall n>0,\exists m<n, |y_n-1-x_n-f(m)|=|f(n)-f(m)-1| \leq k < |f(n)-f(m)| $$

分类讨论易得：

$$ \forall n>0,\exists m<n,f(n)=f(m)+k+1 \tag{3} $$

而每个 $f(n)$ 都可以最终转移到 $f(0)=0$，所以可以记 $f(n)=(k+1)f'(n)$，$f'(n)$ 为转移次数。
那么上面的式子可以改写为：

$$ \forall m<n , |f'(n)-f'(m)| \geq 1 \tag{1.1} $$

$$ \forall n>0,\exists m<n,f'(n)=f'(m)+1 \tag{3.1} $$

由归纳法可证 $f(n)=(k+1)n$，即

$$ y_n=x_n+n(k+1) \tag{4} $$

接下来考察它的通项。
之前已经注意到，任何正整数要么属于 $x$，要么属于 $y$，且只能属于其中之一。即 ${x_i}$、${x_i+(k+1)i}$ 构成一个对正整数的划分。

考虑贝蒂定理：

贝蒂定理

设 $a$、$b$ 是正无理数且 $\frac{1}{a}+\frac{1}{b}=1$，则 $\lfloor na \rfloor$、$\lfloor nb \rfloor$ 构成一个对正整数的划分。

证明：

  • 先证组内没有重复：由原式可得 $a>1,b>1$，所以显然。
  • 再证两集合没有交：如果有交，记为 $k=\lfloor na \rfloor=\lfloor mb \rfloor$，则 $\frac{k}{a} \leq m<\frac{k+1}{a},\frac{k}{b} \leq n<\frac{k+1}{b}$。由 $\frac{1}{a}+\frac{1}{b}=1$，两式相加得 $k \leq m+n <k+1$，与 $k$、$m$、$n$ 均为整数矛盾。
  • 最后证包含了全体正整数：如果存在正整数 $k$ 未被包含，那么 $\lfloor ma \rfloor< k <\lfloor (m+1)a \rfloor,\lfloor nb \rfloor< k <\lfloor (n+1)b \rfloor$，即 $ma< k < (m+1)a-1,nb< k < (n+1)b-1$。同样的，${m \over k}< {1 \over a} < {m+1 \over k+1} -{1\over ak} <{m+1 \over k+1},{n \over k}< {1 \over b}<{n+1 \over k+1}$。两式相加得 $m+n<k<k+1<m+n+2$，与 $k$、$m$、$n$ 均为整数矛盾。

我们即是要找到一对 $(\alpha,\beta)$，使得 $\lfloor n\alpha \rfloor+n(k+1)=\lfloor n\beta \rfloor$，且 $\frac{1}{\alpha}+\frac{1}{\beta}=1$。
显然，$\lfloor n(\alpha+k+1) \rfloor=\lfloor n\beta \rfloor$，即 $\alpha+k+1=\beta$。与贝蒂定理联立解得：

$$ \alpha= {2-(k+1)+\sqrt{(k+1)^2+4} \over 2} $$

这就是所要求的。

时间复杂度

$O(1)$

代码

#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=1020;

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

ll dp[N][N];

int main(void)
{
    //ios::sync_with_stdio(false);
    
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    
    for(int _=read();_>0;_--)
    {
        ll a=read(),b=read(),k=read();

        if(a>b) swap(a,b);
        double p=(sqrt((k+1)*(k+1)+4)+2-(k+1))/2.0,q=p+(k+1);
        bool f=false;
        ll n1=floor(a/p),n2=floor(b/q);
        for(int i=max(0LL,n1-10);i<n1+10;i++)
        {
            ll ta=ll(floor(p*i)),tb=ll(floor(q*i));
            // printf("%d %lld %lld\n",i,ta,tb);
            if(ta==a && tb==b) f=true;
        }
        for(int i=max(0LL,n2-10);i<n2+10;i++)
        {
            ll ta=ll(floor(p*i)),tb=ll(floor(q*i));
            // printf("%d %lld %lld\n",i,ta,tb);
            if(ta==a && tb==b) f=true;
        }

        printf("%d\n",int(!f));
    }
    
    return 0;
}

D.Product

题意

题解

代码

E.Resistance

题意

题解

代码

F.Skyscrapers

题意

题解

代码

G.Game

zyj (赛后)

题意

阿巴阿巴阿巴

题解

直接用$Treap$模拟即可

代码

#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;
template<class T>
struct fhq_Treap{
    static const int N=2e5+5;
    int rt,tot,lc[N],rc[N],sz[N];
    unsigned int rnd[N];
    T val[N],mn[N],mx[N];
    ll sum[N];
    void clear(){
        fill(lc,lc+tot+1,0);
        fill(rc,rc+tot+1,0);
        fill(sz,sz+tot+1,0);
        rt=tot=0;
    }
    fhq_Treap(){
        rt=tot=0;
        srand(clock()+time(0));
        mn[0]=1e9,sum[0]=val[0]=mx[0]=0;
    }
    inline void pushup(int u){
        sz[u]=sz[lc[u]]+sz[rc[u]]+1;
        mn[u]=min({val[u],mn[lc[u]],mn[rc[u]]});
        mx[u]=max({val[u],mx[lc[u]],mx[rc[u]]});
        sum[u]=sum[lc[u]]+sum[rc[u]]+val[u];
    }
    void split_by_sz(int u,const int left_size,int &x,int &y){//sz[x]==v
        if(!u)return x=y=0,void();
        if(sz[lc[u]]+1<=left_size)x=u,split_by_sz(rc[u],left_size-sz[lc[u]]-1,rc[u],y);
        else y=u,split_by_sz(lc[u],left_size,x,lc[u]);
        pushup(u);
    }
    void split_by_min(int u,const int right_mn,int &x,int &y){//mn[l]<v
        if(!u)return x=y=0,void();
        if(mn[rc[u]]<right_mn||val[u]<right_mn) x=u,split_by_min(rc[u],right_mn,rc[u],y);
        else y=u,split_by_min(lc[u],right_mn,x,lc[u]);
        pushup(u);
    }
    void split_lower(int u,const int left_val,int &x,int &y){//val[x]<v
        if(!u)return x=y=0,void();
        if(val[u]<left_val)x=u,split_lower(rc[u],left_val,rc[u],y);
        else y=u,split_lower(lc[u],left_val,x,lc[u]);
        pushup(u);
    }
    void split_upper(int u,const int left_val,int &x,int &y){//val[x]<=v
        if(!u)return x=y=0,void();
        if(val[u]<=left_val)x=u,split_upper(rc[u],left_val,rc[u],y);
        else y=u,split_upper(lc[u],left_val,x,lc[u]);
        pushup(u);
    }
    int merge(int x,int y){//x<y
        if(!x||!y)return x+y;
        if(rnd[x]<rnd[y])return rc[x]=merge(rc[x],y),pushup(x),x;
        else return lc[y]=merge(x,lc[y]),pushup(y),y;
    }
    void insert(const int pos,const T v){ // 插入 v
        assert(pos);
        int x,y,u=++tot;
        sum[u]=val[u]=mn[u]=v,sz[u]=1,rnd[u]=rand();
        split_by_sz(rt,pos-1,x,y);
        rt=merge(merge(x,u),y);
    }
    void remove(const T v){
        int x,y,z;
        split_lower(rt,v,x,y);
        split_upper(y,v,y,z);
        if(!y)assert(0); // 删除不存在的元素
        y=merge(lc[y],rc[y]);
        rt=merge(x,merge(y,z));
    }
    int dfs(int *a,int l,int r){
        if(l>r)return 0;
        int u=++tot,mid=(l+r)>>1;
        sum[u]=val[u]=mn[u]=a[mid],sz[u]=r-l+1,rnd[u]=rand();
        lc[u]=dfs(a,l,mid-1);rc[u]=dfs(a,mid+1,r);
        pushup(u);return u;
    }
    void build_from(int *a,int l,int r){rt=dfs(a,l,r);}
    int rk(T v){ // 相同的数中，第一个数的排名
        int x,y,res;
        split_lower(rt,v,x,y);
        assert(val[y]>=v);
        res=sz[x]+1,rt=merge(x,y);
        return res;
    }
    T kth(int k){ // 查询排名为 k 的数
        int u=rt;
        while(k!=sz[lc[u]]+1){
            if(k<=sz[lc[u]])u=lc[u];
            else k-=sz[lc[u]]+1,u=rc[u];
        }
        return val[u];
    }
    void dfs_seq(int u,T *p){
        if(u==0)return;
        dfs_seq(lc[u],p);
        *(p+sz[lc[u]]+1)=val[u];
        dfs_seq(rc[u],p+sz[lc[u]]+1);
    }
    void seq(T *p){dfs_seq(rt,p);}
    void solve(){
        int op,x,y;scanf("%d%d",&op,&x);
        if(op==1){
            scanf("%d",&y);
            if(kth(x)<y) return (void)puts("0");
            int L,R;split_by_sz(rt,x,L,R);
            if(mn[L]>=y){
                rt=merge(L,R);
                return (void)puts("0");
            }int l,r;
            split_by_min(L,y,l,r);
            ll ans=sum[r]-1ll*(y-1)*sz[r];
            int l1,l2,r1,r2;
            split_by_sz(l,sz[l]-1,l1,l2);
            split_by_sz(r,1,r1,r2);
            val[l2]+=val[r1]-(y-1);
            sum[l2]=mn[l2]=val[l2];
            val[r1]=sum[r1]=mn[r1]=y-1;
            rt=merge(merge(merge(l1,l2),merge(r2,r1)),R);
            printf("%lld\n",ans);
        }else printf("%d\n",kth(x));
    }
};
fhq_Treap<int> t;
int a[maxn];
void solve(){
    int n,q;scanf("%d%d",&n,&q);
    rep(i,1,n) scanf("%d",&a[i]);
    t.clear();
    rep(i,1,n) t.insert(i,a[i]);
    while(q--) t.solve();
    rep(i,1,n) printf(i==n?"%d\n":"%d ",t.kth(i));
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}

H.Distance

题意

题解

代码

I.Yajilin

lmj 赛后

题意

给定网格图，将一些点涂成黑色，涂黑的点不能相邻，且涂完之后，白点可以形成曼哈顿回路，求黑色块的和的最大值。

题解

插头$dp$即可，加一个额外状态黑色块，注意转移的时候除非变成黑色状态，否则要变成普通状态。
如果不会插头$dp$建议学习洛谷插头$dp$模板题题解

代码

#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=1e5+7;
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 dp[2][N];
int state[2][N];
int now;
int change(int k,int x) { return ((k)<<(2*(x))); }
int get(int k,int x) { return (((k)>>(2*(x)))&3); }
struct Hash
{
    int fst[N],nxt[N];
    int mark[N];
    int mt=0;
    int T;
    void init()
    {
        mt++;
        T=0;
    }
    void insert(int s,int v)
    {
        int S=s%N;
        if(mark[S]!=mt)mark[S]=mt,fst[S]=-1;
        for(int i=fst[S];i!=-1;i=nxt[i]){
            if(state[now][i]==s){
                dp[now][i]=max(dp[now][i],v);
                return;
            }
        }
        nxt[T]=fst[S];
        fst[S]=T;
        state[now][T]=s;
        dp[now][T]=v;
        T++;
    }
}H;
int a[20][20];
void work()
{
       int n,m;
       scanf("%d",&n);
       m=n;
       for(int i=1;i<=n;i++){
           for(int j=1;j<=n;j++){
               scanf("%d",&a[i][j]);
           }
       }
       int t;
       state[0][(t=1)-1]=0;dp[0][0]=0;now=0;
       int ans=0;
       for(int i=1;i<=n;i++){
           for(int j=1;j<=m;j++){
               now^=1;
               H.init();
               memset(dp[now],0,sizeof(dp[now]));
               memset(state[now],0,sizeof(state[now]));
               for(int k=0;k<t;k++){
                   int s=state[now^1][k];
                   int v=dp[now^1][k];
                   int k1=get(s,j-1),k2=get(s,j);
                   if(k1==0&&k2==0){
                       H.insert(s^change(3,j-1)^change(3,j),v+a[i][j]);
                   }
                   if(k1==3){
                       s^=change(3,j-1);k1=0;
                   }
                   if(k2==3){
                       s^=change(3,j);k2=0;
                   }
                   if(k1==0&&k2==0){
                       if(i<n&&j<m)H.insert(s^change(1,j-1)^change(2,j),v);
                   }else if(k1==0){
                       if(i<n)H.insert(s^change(k2,j-1)^change(k2,j),v);
                       if(j<m)H.insert(s,v);
                   }else if(k2==0){
                       if(i<n)H.insert(s,v);
                       if(j<m)H.insert(s^change(k1,j-1)^change(k1,j),v);
                   }else if(k1==2&&k2==1){
                       H.insert(s^change(k1,j-1)^change(k2,j),v);
                   }else if(k1==1&&k2==1){
                       int cnt=1;
                       for(int aaa=j+1;aaa<=m;aaa++){
                           if(get(s,aaa)==1)cnt++;
                           if(get(s,aaa)==2)cnt--;
                           if(!cnt){
                               H.insert(s^change(k1,j-1)^change(k2,j)^change(3,aaa),v);break;
                           }
                       }
                   }else if(k1==2&&k2==2){
                       int cnt=1;
                       for(int aaa=j-2;aaa>=1;aaa--){
                           if(get(s,aaa)==1)cnt--;
                           if(get(s,aaa)==2)cnt++;
                           if(!cnt){
                               H.insert(s^change(k1,j-1)^change(k2,j)^change(3,aaa),v);break;
                           }
                       }
                   }else{
                       if(i==n&&j==m){
                           ans=max(ans,v);
                       }else if(i==n&&j==m-1&&get(s,m)==0){
                           ans=max(ans,v+a[n][m]);
                       }
                   }
               }
               t=H.T;
           }
           for(int k=0;k<t;k++){
               state[now][k]<<=2,state[now][k]&=change(1,m+1)-1;
           }
       }
       printf("%d\n",ans);
}
int main()
{
    //freopen("1.in","r",stdin);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

J.Jump

题意

题解

代码

本文由 Edwiv 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 23, 2020 at 09:51 pm

← → ↓ ↑
2020杭电多校联合训练（第十场）
杭电多校多校训练
2020杭电多校联合训练（第八场）
杭电多校多校训练
2020杭电多校联合训练（第七场）
杭电多校多校训练
2020牛客暑期多校训练营（第十场）
牛客多校多校训练
2020牛客暑期多校训练营（第九场）
牛客多校多校训练
2020杭电多校联合训练（第六场）
杭电多校多校训练
Responses