Simulation3题解与标程

2018-01-23 18:30:40 By youyl

追逐

50分:

考虑一条路径上的连续的三个点,假设路径从V走到X走到T。定义N(X)为X所有邻居的铁球数总和,那么在X处丢下磁铁的收益就是N(X)-F(V),无论别的磁铁丢在哪里。

证明:

考虑X的邻居,如果他们不是V也不是T,那么必然对答案有贡献,因为逃亡者一定碰不到而追杀者一定碰得到。T处的铁球会被追杀者碰到,但是因为X处放了磁铁,所以逃亡者不会碰到。V处的铁球的收益只会被前面的磁铁影响而不会被X处磁铁影响。

这样可以枚举起点,然后用堆存储路径上的每个点的收益,最终的复杂度是O(n n v * log(n))

100分:

考虑使用动态规划,每个点保存两个数组,分别表示向下面走的和从下面来的两条路径放了若干个磁铁的收益。计算答案的时候合并路径即可。 需要注意的边界情况较多,如:两条路径来自同一子树,答案路径只由一条路径构成等。

回文串

35分:

考虑动态规划。

将问题考虑为每次截取字符串一对相等的前缀和后缀,问最多截取次数。

Dp[i]为原字符串正好截取了前i个和后i个字符。转移枚举截取长度。复杂度是立方级的。

60分:

考虑贪心。

可以发现最优策略一定是每次截下尽可能短的相同的前后缀。

证明:

假设有两个分解CADBC和EDE。现在需要证明如果存在CADBC,EDE一定不是最优解。

分两种情况讨论:

B的长度大于等于C的长度。

这个时候E=CXC,X可能为空串。把E分为CXC一定是更优解。

B的长度小于C的长度。

因为CA=BC且B的长度小于C的长度,所以C=BC[1],C[1]是C的某个前缀。

可以依此类推C=BC[1]=BBC[2]=BBBC[3]……直到BB…BC[k],使得B的长度大于等于C[k]的长度。

这时C[k]既是C的前缀也是C的后缀,因此也是E的前缀和后缀。

所以存在E=C[k]XC[k]可以构成更优解。

一个直观的想法就是从原字符串两端枚举,每次判断前后缀是否相同。

判断的时间复杂度是线性的,总复杂度是平方级的。

100分:

60分做法的瓶颈在于判断前后缀是否相等,这可以使用字符串哈希处理,每次判断是常数时间的,总复杂度就是线性的。

陷阱

Subtask1:

考虑到因为可以不操作,所以所有的堵路操作一定在所有的清理操作之前,因为如果有一个堵路操作在清洁操作之后,那么他可以交换这两个操作的顺序。

进一步观察可以发现,老鼠最后一定会被堵住。在堵住老鼠之前管理者只会进行堵路操作,堵住老鼠之后管理者可以先把老鼠到陷阱的路径上的向外的路全堵住,然后开始清理。老鼠一定会走向陷阱。

可以暴力枚举堵住哪些路。

Subtask2:

将陷阱房提根。可以发现老鼠出发点一定深度为1(根的深度为0),而且他一定会往深处走。

可以发现在老鼠未被堵住之前,管理者堵住的走廊一定和老鼠所在位置相邻,而且一定会堵住老鼠的最优解。在老鼠被堵住之后,管理者可以很容易构造出通向陷阱的路径。定义一个点的权值为老鼠向下走到这个点的情况下答案是多少,接下来就可以很容易的计算出每个点的权值,老鼠起始位置的权值就是答案。

100分:

考虑一般情况,还是将陷阱房提根。

考虑老鼠的起始位置通向根的路径,管理者不会去堵这些路。考虑这条路径,上挂的子树,可以发现最后老鼠必然是选择一个子树进去,然后卡住,最后被放到陷阱。

考虑二分答案,二分操作者需要多少步进行步,然后自下而上扫描,判断每个子树能否满足条件。复杂度为O(n log n)

标程

追逐:

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int ed,st[120000];
struct node
{
    int to,next;
}g[220000];
inline void addedge(int x,int y)
{
    ed++;
    g[ed].next=st[x];
    g[ed].to=y;
    st[x]=ed;
}
int n,v,x,y;
long long best,p[120000],tot[120000];
long long up[120000][120],down[120000][120];
inline void solve2(int x,int ch)
{
    for (int i=0;i<=v;i++)
    {
        best=max(best,up[x][i]+down[ch][v-i]);
        best=max(best,down[x][i]+up[ch][v-i]);
        if(i!=v)
        {
            best=max(best,up[x][i]+down[ch][v-i-1]+tot[ch]-p[x]);
            best=max(best,down[x][i]+up[ch][v-i-1]+tot[x]-p[ch]);
        }
    }
}
inline void update(int x,int ch)
{
    for (int i=0;i<=v;i++)
    {
        up[x][i]=max(up[x][i],up[ch][i]);
        down[x][i]=max(down[x][i],down[ch][i]);
    }
    for (int i=1;i<=v;i++)
    {
        up[x][i]=max(max(up[x][i-1],up[x][i]),up[ch][i-1]+tot[x]-p[ch]);
        down[x][i]=max(max(down[x][i-1],down[x][i]),down[ch][i-1]+tot[ch]-p[x]);
    }
}
inline void solve(int x,int fa)
{
    vector<int>adj;
    for (int i=st[x];i!=0;i=g[i].next)
    {
        if(g[i].to!=fa)
        {
            adj.push_back(g[i].to);
            solve(g[i].to,x);
        }
    }
    up[x][0]=0;
    for (int i=1;i<=v;i++)
    {
        up[x][i]=tot[x];
    }
    if(adj.size()==0)
    {
        return;
    }
    update(x,adj[0]);
    for (int i=1;i<adj.size();i++)
    {
        solve2(x,adj[i]);
        update(x,adj[i]);
    }
    best=max(best,up[x][v]);
    best=max(best,down[x][v]);
    if(v>0)best=max(best,down[x][v-1]+tot[x]);
    //printf("v:%d\n",x);
}
int main()
{
    scanf("%d %d",&n,&v);
    for (int i=1;i<=n;i++)
    {
        scanf("%lld",&p[i]);
    }
    for (int i=1;i<n;i++)
    {
        scanf("%d %d",&x,&y);
        addedge(x,y);
        addedge(y,x);
        tot[x]+=p[y];
        tot[y]+=p[x];
    }
    solve(1,0);
    printf("%lld\n",best);
    return 0;
}

回文串:

#include<cstdio>
#include<cstring>
using namespace std;
const long long mod=1000000007;
const long long mul=131;
char str[1200000];
inline int solve()
{
    int l=strlen(str+1);
    int lb=1,rb=l,cnt=0;
    long long hashl=0,hashr=0,mult=1;
    while (lb<rb)
    {
        hashr+=mult*(str[rb]-'a'+1)%mod;
        hashr%=mod;
        hashl*=mul;hashl%=mod;
        hashl+=(str[lb]-'a'+1);
        hashl%=mod;
        if(hashl==hashr)
        {
            hashl=0;
            hashr=0;
            mult=1;
            cnt+=2;
        }
        else
        {
            mult*=mul;
            mult%=mod;
        }
        lb++;
        rb--;
    }
    if(lb==rb)cnt++;
    if(lb!=rb&&hashl!=0)cnt++;
    return cnt;
}
int T;
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%s",str+1);
        printf("%d\n",solve());
    }
    return 0;
}

陷阱:

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>adj[1200000];
int parent[1200000];
int weight[1200000];
vector<pair<int,int> >subtrees;
int ispath[1200000];
int root,m,n;
int dfs1(int x,int fa)
{
    int fati=-1;
    for (int i=0;i<adj[x].size();i++)
    {
        if(adj[x][i]==fa)fati=i;
    }
    if(fati!=-1)
    {
        adj[x].erase(adj[x].begin()+fati);
    }
    parent[x]=fa;
    int step=-1;
    if(x==m)
    {
        step=0;
    }
    for (int i=0;i<adj[x].size();i++)
    {
        step=max(step,dfs1(adj[x][i],x));
    }
    ispath[x]=step;
    if(step==-1)
    {
        return step;
    }
    else
    {
        return step+1;
    }
}
void dfs2(int x,int c)
{
    if(adj[x].size()==0)
    {
        weight[x]=c;
        return;
    }
    if(ispath[x]==-1)
    {
        int cur=c+adj[x].size();
        for (int i=0;i<adj[x].size();i++)
        {
            dfs2(adj[x][i],cur);
        }
        if(adj[x].size()==1)
        {
            weight[x]=c+1;
            return;
        }
        int best=-1;
        int sbest=-1;
        for (int i=0;i<adj[x].size();i++)
        {
            if(weight[adj[x][i]]>best)
            {
                sbest=best;
                best=weight[adj[x][i]];
                continue;
            }
            if(weight[adj[x][i]]>sbest)
            {
                sbest=weight[adj[x][i]];
            }
        }
        weight[x]=sbest;
        return;
    }
    int cur=c+adj[x].size()-1;
    if(x==root)
    {
        cur=0;
    } 
    if(x==m)
    {
        cur++;
    }
    for (int i=0;i<adj[x].size();i++)
    {
        dfs2(adj[x][i],cur);
    }
    if(x==root)return;
    for (int i=0;i<adj[x].size();i++)
    {
        if(ispath[adj[x][i]]==-1)
        {
            subtrees.push_back(make_pair(ispath[x],weight[adj[x][i]]));
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&root,&m);
    for (int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int pathl=dfs1(root,-1);
    dfs2(root,0);
    sort(subtrees.begin(),subtrees.end());
    int lef=0,rig=n;
    while(lef<rig)
    {
        int mid=(lef+rig)/2;
        int x=0,y=0,pt=0;
        for (int i=0;i<pathl;i++)
        {
            if(pt>=subtrees.size())
            {
                rig=mid;
                break;
            }
            x++;
            int ydelta=0;
            while(pt<subtrees.size()&&subtrees[pt].first<=i)
            {
                if(subtrees[pt].second+y>mid)
                {
                    ydelta++;
                    x--;
                }
                pt++;
            }
            y+=ydelta;
            if(x<0||y>mid)
            {
                lef=mid+1;
                break;
            }
        }
    }
    printf("%d\n",lef);
    return 0;
}

评论

回复

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。