[比赛题解]CWOI2019-1

比赛日期：2019.10.12

T1

一道神仙DP题。

我们考虑\(dp[i][j][k]\)表示最后\(i\)位数,\(i-1\)位都是9，最后一位为\(j\)，最后\(i\)位数以前的部分最大数为\(k\)时，把最后\(i\)位数减到负数最小需要多少次。\(re[i][j][k]\)代表这个状态下，把这个数减到负数时，负数+10的值。

那么每次操作就会减去\(min(最后i位数中最小值,k)\)。

我们先预处理出\(dp\)和\(re\)数组（从低位向高位递推）。

然后读入给的数，考虑把除1之外所有位数变成9。那么从第二位向高位枚举，每次把当前位减掉1，直到减到9（最后一次注意退位），同时记录在这个过程中走了多少步。因为对于一个前缀全为9，最后一位无论是什么，减去一个小于10的数得到的数的前缀还是全为9。

全部变成9之后即可从高位到低位统计答案即可。

貌似状态设置成“全是9”也可以，但是没试过。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

long long dp[20][10][10],res[20][10][10];

long long ans=0;

char s[20];

int num[20];

void init() {

    for(int i=0;i<=9;i++) {

        for(int j=0;j<=9;j++) {

            if(i<j) {//当前位较小

                dp[1][i][j]=1;

                res[1][i][j]=i-j+10;

            }

            else {//当前位较大

                dp[1][i][j]=2;

                res[1][i][j]=10-j;

            }

        }

    }

    for(int i=2;i<=18;i++) {

        for(int j=0;j<=9;j++) {

            for(int k=0;k<=9;k++) {

                res[i][j][k]=j;

                for(int n=9;n>=0;n--) {

                    dp[i][j][k]+=dp[i-1][res[i][j][k]][max(n,k)];

                    res[i][j][k]=res[i-1][res[i][j][k]][max(n,k)];

                }

            }

        }

    }

}

void just_do_it() {

    scanf("%s",s+1);int len=strlen(s+1);

    for(int i=1;i<=len;i++)num[i]=s[i]-'0';

    reverse(num+1,num+1+len);

    int now=num[1];

    for(int i=2;i<=len;i++) {

        while(num[i]!=9) {

            int ma=0;

            for(int j=i;j<=len;j++)ma=max(ma,num[j]);

            if(!ma)break;//无法退位

            num[i]--;

            for(int j=i;num[j]<0;j++) {//退位

                num[j]=9;num[j+1]--;

            }

            ans+=dp[i-1][now][ma];

            now=res[i-1][now][ma];

        }

    }

    for(int i=len;i>=2;i--) {

        while(num[i]) {

            ans+=dp[i-1][now][num[i]];

            now=res[i-1][now][num[i]];

            num[i]--;

        }

    }

    if(now)ans++;

    printf("%lld",ans);

}

int main() {

    init();

    just_do_it();

}

T2

我们考虑三种情况

被覆盖点为祖先-后代关系
被覆盖点没有祖先-后代关系
被覆盖点相等

这三类都可以转换为统计某些点的子树内点的个数。（比如说第二种情况就是统计路径两端分别在\(u,v\)子树内的路径条数）。对于一个端点，我们可以把他转换为\(dfs\)序在一定范围内的点，而对于一条路径，我们可以把它转换成矩阵坐标在一定范围内的点。然后扫描线二维数点就好了。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<vector>

#define int long long

#define ll long long

using namespace std;

const int maxn=1e5+1000;

int root[maxn],ls[maxn*80],rs[maxn*80],head[maxn],cnt,idx,n,m,dep[maxn],po[maxn],f[maxn][23],size[maxn],dfn[maxn],dfn_cnt;

ll ans1=0,ans2,ans3,sum[maxn*80];

vector<int>list[maxn];

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

struct gg {

    int u,v,next;

}side[maxn*2];

//pair<int,int>ori[maxn];

struct data {

    int first,second;

}ori[maxn];

void insert(int u,int v){

    struct gg add={u,v,head[u]};side[++cnt]=add;head[u]=cnt;

}

void dfs(int now,int fa) {

    dep[now]=dep[fa]+1;size[now]=1;dfn[now]=++dfn_cnt;

    f[now][0]=fa;for(int i=1;i<=22;i++)f[now][i]=f[f[now][i-1]][i-1];

    for(int i=head[now];i;i=side[i].next) {

        int v=side[i].v;if(v==fa)continue;

        dfs(v,now);size[now]+=size[v];

    }

}

int lca(int u,int v) {

    if(dep[u]<dep[v])swap(u,v);

    for(int i=22;i>=0;i--)if(dep[f[u][i]]>=dep[v])u=f[u][i];

    if(u==v)return u;

    for(int i=22;i>=0;i--)if(f[u][i]!=f[v][i]){u=f[u][i],v=f[v][i];}

    return f[u][0];

}

int build(int l,int r) {//主席数，版本表示u的范围，线段树表示v的范围

    int now=++idx;

    if(l==r)return now;

    int mid=(l+r)>>1;

    ls[now]=build(l,mid);

    rs[now]=build(mid+1,r);

    return now;

}

bool cop(data x,data y) {

    return x.first<y.first;

}

int insert(int sync,int l,int r,int tar) {

    int now=++idx;

    ls[now]=ls[sync],rs[now]=rs[sync],sum[now]=sum[sync]+1;

    if(l==r)return now;

    int mid=(l+r)>>1;

    if(tar<=mid) {

        ls[now]=insert(ls[sync],l,mid,tar);

    }

    else {

        rs[now]=insert(rs[sync],mid+1,r,tar);

    }

    return now;

}

ll query(int sy1,int sy2,int l,int r,int tl,int tr) {

    ll tot=sum[sy2]-sum[sy1];

    if(tl<=l&&r<=tr)return tot;

    tot=0;int mid=(l+r)>>1;

    if(tl<=mid) {

        tot+=query(ls[sy1],ls[sy2],l,mid,tl,tr);

    }

    if(tr>=mid+1) {

        tot+=query(rs[sy1],rs[sy2],mid+1,r,tl,tr);

    }

    return tot;

}

int jump(int l,int h) {

    for(int i=22;i>=0;i--)if(dep[f[l][i]]>dep[h])l=f[l][i];

    return l;

}

signed main() {

    scanf("%lld%lld",&n,&m);

    for(int i=1;i<n;i++){int u,v;scanf("%lld%lld",&u,&v);insert(u,v);insert(v,u);}

    dfs(1,0);

    for(int i=1;i<=m;i++) {

        scanf("%lld%lld",&ori[i].first,&ori[i].second);

        if(dep[ori[i].first]>dep[ori[i].second])swap(ori[i].first,ori[i].second);

        if(ori[i].first==ori[i].second)po[ori[i].first]++;

        list[dfn[ori[i].first]].push_back(dfn[ori[i].second]);

        list[dfn[ori[i].second]].push_back(dfn[ori[i].first]);

    }

    root[0]=build(1,m);sort(ori+1,ori+1+m,cop);

    for(int i=1;i<=n;i++) {

        root[i]=root[i-1];

        for(int j=0;j<list[i].size();j++)root[i]=insert(root[i],1,n,list[i][j]);

    }

    //for(int i=1;i<=n;i++)

    for(int i=1;i<=m;i++) {

        int u=ori[i].first,v=ori[i].second;//查询u，v被多少路径包含

        //int lu,lv,ru,rv;

        if(lca(u,v)==u) {//祖先-儿子关系

            int p=jump(v,u);

            ans1+=query(root[0],root[dfn[p]-1],1,n,dfn[v],dfn[v]+size[v]-1);

            ans1+=query(root[dfn[p]+size[p]-1],root[n],1,n,dfn[v],dfn[v]+size[v]-1);

        }

        else {

            ans1+=query(root[dfn[u]-1],root[dfn[u]+size[u]-1],1,n,dfn[v],dfn[v]+size[v]-1);

           // ans1+=query(root[dfn[v]-1],root[dfn[v]+size[v]-1],1,n,dfn[u],dfn[u]+size[u]-1);

        }

        ans1--;

    }

    ans2=m*(m-1)/2;ans3=gcd(ans1,ans2);

    cout<<ans1/ans3<<'/'<<ans2/ans3;

    return 0;

}

巴特西

[比赛题解]CWOI2019-1

[比赛题解]CWOI2019-1

T1

T2

最新文章

热门文章