NOIP-2015

D1T1 神奇的幻方

简单模拟

#include<bits/stdc++.h>
using namespace std;
int n;
int a[50][50];
int main()
{
    scanf("%d",&n);
    int x=1,y=(n+1)/2;
    a[x][y]=1;
    for(int i=2;i<=n*n;i++)
    {
        if(x==1 && y!=n) x=n,y++;
        else if(x!=1 && y==n) x--,y=1;
        else if(x==1 && y==n) x++;
        else if(!a[x-1][y+1]) x--,y++;
        else x++;
        a[x][y]=i;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            printf("%d%c",a[i][j],(j<n)?' ':'\n');
}

D1T2 信息传递

n个点，每个点出度为1，形成的图为基环(内向)树构成的森林。题目要求最小的环长。

可以用并查集维护，这样就能找出所有环上的某一条边了，沿环绕一圈求出环长。这样每个环只遍历一次，复杂度线性。

#include<bits/stdc++.h>
using namespace std;
#define N 200010
#define rep(i,l,r) for(int i=l;i<=r;++i)
int n;
int a[N];
int fa[N];
int getfa(int x)
{
    return x==fa[x]?x:fa[x]=getfa(fa[x]);
}
bool Union(int x,int y)
{
    x=getfa(x);
    y=getfa(y);
    if(x==y) return false;
    fa[x]=y;
    return true;
}
int walk(int x)
{
    int ans=0,y=x;
    while(true)
    {
        y=a[y];
        ++ans;
        if(y==x) break;
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    rep(i,1,n) scanf("%d",a+i),fa[i]=i;
    int ans=~0U>>1;
    rep(i,1,n)
        if(!Union(i,a[i]))
            ans=min(ans,walk(i));
    printf("%d\n",ans);
}

D1T3 斗地主

搜索剪枝结合贪心，贪心即考虑枚举的牌型顺序，肯定优先走出牌多的，比如顺子，四带二等等，这样就能使最优性剪枝发挥出作用了。

#include<bits/stdc++.h>
using namespace std;
int T,n,ans;
int a[16];
int calc()
{
    int now=0;
    for(int i=0;i<=14;++i)
        if(a[i])
            ++now;
    return now;
}
void dfs(int step,int x)
{
    if(step>=ans) return;
    ans=min(ans,step+calc());
    for(int i=3;i<=13;++i)//san shun
    {
        int j=i;
        while(j<=14 && a[j]>=3) ++j;
        if(j-i<2) continue;
        a[i]-=3;
        for(int k=i+1;k<j;++k)
        {
            a[k]-=3;
            dfs(step+1,x-(k-i+1)*3);
        }
        for(int k=i;k<j;++k)
            a[k]+=3;
    }

    for(int i=3;i<=12;++i)// shuang shun
    {
        int j=i;
        while(j<=14 && a[j]>=2) ++j;
        if(j-i<3) continue;
        a[i]-=2;a[i+1]-=2;
        for(int k=i+2;k<j;++k)
        {
            a[k]-=2;
            dfs(step+1,x-(k-i+1)*2);
        }
        for(int k=i;k<j;++k)
            a[k]+=2;
    }
    for(int i=3;i<=10;++i) //dan shun
    {
        int j=i;
        while(j<=14 && a[j]>=1) ++j;
        if(j-i<5) continue;
        a[i]--;a[i+1]--;a[i+2]--;a[i+3]--;
        for(int k=i+4;k<j;++k)
        {
            a[k]--;
            dfs(step+1,x-(k-i+1));
        }
        for(int k=i;k<j;++k)
            a[k]++;
    }
    for(int i=2;i<=14;++i)
    if(a[i]==4)
    {
        a[i]=0;
        dfs(step+1,x-4);
        for(int j=0;j<=14;++j)
        if(a[j]>0)
        {
            a[j]--;
            for(int k=j;k<=14;++k)
            if(a[k]>0)
            {
                a[k]--;
                dfs(step+1,x-6);
                a[k]++;
            }
            a[j]++;
        }
        for(int j=2;j<=14;++j)
        if(a[j]>1)
        {
            a[j]-=2;
            for(int k=j;k<=14;++k)
            if(a[k]>1)
            {
                a[k]-=2;
                dfs(step+1,x-8);
                a[k]+=2;
            }
            a[j]+=2;
        }
        a[i]=4;
    }

    for(int i=2;i<=14;++i)
    if(a[i]>=3)
    {
        a[i]-=3;
        dfs(step+1,x-3);
        for(int j=0;j<=14;++j)
        if(a[j]>=1)
        {
            a[j]--;
            dfs(step+1,x-4);
            a[j]++;
        }
        for(int j=2;j<=14;++j)
        if(a[j]>=2)
        {
            a[j]-=2;
            dfs(step+1,x-5);
            a[j]+=2;
        }
        a[i]+=3;
    }
}
int main()
{
    scanf("%d%d",&T,&n);
    while(T--)
    {
        memset(a,0,sizeof(a));
        for(int i=1;i<=n;++i)
        {
            int x;
            scanf("%d%*d",&x);
            if(x==1) x=14;
            a[x]++;
        }
        ans=n;
        dfs(0,n);
        printf("%d\n",ans);
    }
}

D2T1 跳石头

非常基本的二分答案+贪心。二分一个最短跳跃距离mid，判断是否可行，即需要移走的块数是否小于等于M。可行，说明答案大于等于mid；不可行，说明答案小于mid、

#include<bits/stdc++.h>
using namespace std;
#define N 50010
#define rep(i,l,r) for(int i=l;i<=r;++i)
int a[N];
int n,m,H;
bool ok(int len)
{
    int last=0,i=0,ans=0;
    while(true)
    {
        while(i<=n&& a[i]-last<len) ++i;
        if(i>n) break;
        ++ans;
        last=a[i];
    }
    if(ans>0 && H-last<len) --ans;
    return n-ans<=m;
}

int main()
{
    scanf("%d%d%d",&H,&n,&m);
    rep(i,1,n) scanf("%d",a+i);
    int l=1,r=H;
    while(l<r)
    {
        int mid=l+(r-l+1)/2;
        if(ok(mid)) l=mid;
        else r=mid-1;
    }
    printf("%d\n",l);
}

D2T2 子串

记$dp[k][i][j]$表示字符串A考虑前 $i$ 个字符，字符串B考虑前 $j$ 个字符，分 $k$ 段的方案数。

目前虽然AC了，但较为暴力，改天优化一下。

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,m,K;
int dp[2][1005][205];
char a[1005],b[205];
void add(int &x,int y)
{
    x+=y;
    if(x>=mod) x-=mod;
}
int main()
{
    scanf("%d%d%d",&n,&m,&K);
    scanf("%s",a+1);
    scanf("%s",b+1);
    for(int i=0; i<=n; ++i)
        dp[0][i][0]=1;

    for(int k=1; k<=K; ++k)
    {
        memset(dp[k&1],0,sizeof(dp[k&1]));
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=m; ++j)
            {
                add(dp[k&1][i][j],dp[k&1][i-1][j]);
                int l=0;
                while(l<j && l<i && a[i-l]==b[j-l])
                {
                    ++l;
                    add(dp[k&1][i][j],dp[(k&1)^1][i-l][j-l]);
                }
                //cout<<i<<" "<<j<<" "<<k<<" "<<dp[i][j][k]<<endl;
            }
    }
    printf("%d\n",dp[K&1][n][m]);
}

D2T3 运输计划

二分答案+树上差分

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 300010
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define dow(i,l,r) for(int i=l;i>=r;--i)
int e,head[N<<1],w[N<<1],last[N<<1],p[N];
int deep[N],fa[N],num[N],son[N];
int top[N];
int a[N],dis[N];
int u[N],v[N],lca[N],val[N];
int n,m;
void add(int x,int y,int c)
{
    head[++e]=y;w[e]=c;
    last[e]=p[x];
    p[x]=e;
}
void dfs(int x,int pre,int dep)
{
    deep[x]=dep;
    fa[x]=pre;
    num[x]=1;
    for(int j=p[x];j;j=last[j])
    {
        int y=head[j];
        if(y==pre) continue;
        dis[y]=dis[x]+w[j];
        dfs(y,x,dep+1);
        num[x]+=num[y];
        if(son[x]==-1||num[y]>num[son[x]])
            son[x]=y;
    }
}
void dfs_son(int x,int rt)
{
    top[x]=rt;
    if(son[x]==-1) return;
    else dfs_son(son[x],rt);
    for(int j=p[x];j;j=last[j])
        if(head[j]!=fa[x] && head[j]!=son[x])
            dfs_son(head[j],head[j]);
}
void dfs(int x)
{
    for(int j=p[x];j;j=last[j])
    {
        int y=head[j];
        if(y==fa[x]) continue;
        dfs(y);
        a[x]+=a[y];
    }
}
int calc(int x,int y)
{
    int f1=top[x],f2=top[y];
    while(f1!=f2)
    {
        if(deep[f1]<deep[f2])
        {
            swap(x,y);
            swap(f1,f2);
        }
        x=fa[f1];
        f1=top[x];
    }
    if(deep[x]>deep[y]) swap(x,y);
    return x;
}

bool ok(int mid)
{
    int tot=0,mx=0,ans=0;
    memset(a,0,sizeof(a));
    rep(i,1,m)
    if(val[i]>mid)
    {
        a[u[i]]++;
        a[v[i]]++;
        a[lca[i]]-=2;
        ++tot;
        ans=max(ans,val[i]);
    }
    dfs(1);
    rep(i,1,n)
        if(a[i]>=tot)
            mx=max(mx,dis[i]-dis[fa[i]]);
    return ans-mx<=mid;
}
int main()
{
    scanf("%d%d",&n,&m);
    rep(i,1,n-1)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        add(x,y,c);
        add(y,x,c);
    }
    memset(son,-1,sizeof(son));
    dfs(1,0,1);
    dfs_son(1,1);
    rep(i,1,m)
    {
        scanf("%d%d",u+i,v+i);
        lca[i]=calc(u[i],v[i]);
        val[i]=dis[u[i]]+dis[v[i]]-2*dis[lca[i]];
    }
    int l=0,r=4e8;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(ok(mid))  r=mid;
        else l=mid+1;
    }
    printf("%d\n",l);
    return 0;
}