2017武汉大学校赛 网络预选赛 简单题题解

补题目补了好几天，越发觉得自己是个菜鸡。。所以写个简单题的题解吧。。反正难的题目也不会做

除了A题题目贴过来都有格式问题。。所以不贴题目了。。。

A. One car comes and one car goes

Output

output one number, the answer. Your answer will be considered as correct if the relative or absolute error is less than 10^-​4

题意：

两个人从位于一条直线上的东西两个火车站相互向对方出发，全程保持速度不变；第一次他们在距离东火车站60里的地方见面了；接着他们保持原来的速度，原来的方向，继续前进，在到达火车站后立刻转向原速返回，接着他们在距离西站30里的位置第二次相遇了。请问东西站的距离是多少。

做法：

简单的小学奥数题，图上画一下就可以出结果。
答案是150

B.Color

题意：

给了一颗有n个节点的生成树，需要将这n个节点染成最多m种颜色，要求直接相连的2个节点颜色不同，问一共有多少种染色方案。注意有一些节点不能染成某种颜色。

做法：

树型dp（记忆化搜索）。记 $dp[i][j]$ 为如果第i个节点取颜色j的方案数。那么，最后的答案只要对任何一个节点枚举它可能的颜色并把结果相加：

状态转移方程：

对每个节点，它所有可能的颜色方案数，等于它所有孩子所有可能方案数的乘积；
对它的每个孩子，其可能方案数为在满足题意条件下（不取父亲颜色；可以取该颜色），所有可能情况之和。

初始化：

初始化为0.

注意点：

多组数据 用vector存下树，双向边存储；使用father数组表示父子关系；因为是生成树所以随便指定了1号节点为根；因为对树从底而上的递推比较难实现，使用了记忆化搜索。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+10;
const int Mod=1e7+9;
int n,m,xx,yy,ans;
vector <int> G[maxn];
int father[maxn];
bool reachable[maxn][25];//whether the i-th node could be classified into the j-th group
int dp[maxn][25];//memorization search
void init(void)
{
    ans=0;
    memset(father,-1,sizeof(father));//compared with visit,father is more efficient
    memset(dp,-1,sizeof(dp));//important!
    for(int i=1;i<=n;i++)
        G[i].clear();
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d%d",&xx,&yy);
        G[xx].push_back(yy);
        G[yy].push_back(xx);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&xx);
            if(xx==1)
                reachable[i][j]=true;
            else
                reachable[i][j]=false;
        }
    }
}
int  dfs(int i,int k)//The number of solutions in which you paint color j on Node i
{
    long long product=1LL;
    if(dp[i][k]!=-1)//to avoid duplicate search
        return dp[i][k];
    if(reachable[i][k]==0)//can not choose this color for Node i
        return 0;
    for(auto j:G[i])//traverse the son of i
    {
        int cnt=0;
        if(j==father[i])//ensure we don't go back to i's father
            continue;
        father[j]=i;
        for(int kk=1;kk<=m;kk++)//for every color
        {
            if((kk==k))
                continue;
            if(dp[j][kk]==-1)
                dp[j][kk]=dfs(j,kk);
            cnt=(cnt+dp[j][kk])%Mod;
        }
        product=(product*(long long)cnt)%Mod;

    }
    return (int)product;
}
int main(void)//dp on tree
{
    while(cin>>n>>m)
    {
        init();
        if(m==1)
        {
            cout<<0<<endl;
            continue;
        }
        for(int j=1;j<=m;j++)//enumerate the color of Node 1;consider Node 1 to be the root
        {
            if(reachable[1][j]==0)//can not choose this color
                continue;
            dp[1][j]=dfs(1,j);
            ans=(ans+dp[1][j])%Mod;
        }
        cout<<ans<<endl;
    }
    return 0;
}

C.Divide by six

题意：

给了一个长度很长的数（可能有前置0），要求从中删除最少的数位，得到这样的一个数：

方法：

数位dp。定义 $dp[i][j]$ 为以原数第i位为结尾，最后形成的数mod 3答案为j 的能够达到的最长的答案的长度。
那么很显然，如果第i位数 mod 3正好为j，那么$dp[i][j]$ 至少为1；
另外，我们可以从前面的数位中，选出$dp[m][k]$ 中最大的。其中,$m<i$ ,(k+a[i]%3==j

因为题目不允许前导0，所以对0特殊处理，遇到0时，$dp[i][j]$ 只能从前面推过来，而不能是因为自身是0直接取自身 $dp[i][0]$ 为1.

答案是枚举每一位作为最后一位，如果这一位是偶数并且$dp[i][0]$ 最大，就是答案
最后如果答案是0而且在原数中出现了0，把答案改成1.

注意点：

贪心也可以做，if else注意一下就好
对于0的处理是难点
对于k，一定要是正数，也不能大于3

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
char a[maxn];
int n;
int dp[maxn][6];//dp[i][j] means the ans for an substring ended with a[i] and mod 6 equals to j
int b[maxn][6];//b[i][j] means the max value for all dp[k][j] having k<i
int main(void)
{

    int x,k,ans=0,cnt=0;
    scanf("%s",a);
    n=strlen(a);
    memset(dp,0,sizeof(dp));
    memset(b,0,sizeof(b));
    for(int i=0;i<n;i++)
    {
        x=a[i]-'0';
        for(int j=0;j<3;j++)
        {
            if(x%3==j)
                dp[i][j]=1;//if x itself mod 6 equals to j,then itself could possibly be ans
            if(x==0)//single 0 should not be resolved as ans(to avoid leading 0)
            {
                dp[i][j]=0;
                cnt++;
            }
            k=((j-x)%3+3)%3;
            if(b[i][k]!=0)
                dp[i][j]=max(dp[i][j],b[i][k]+1);
            b[i+1][j]=max(b[i][j],dp[i][j]);
            //printf("dp[%d][%d]=%d\n",i,j,dp[i][j]);
        }
    }
    for(int i=0;i<n;i++)
    {
        x=a[i]-'0';
        if(x%2==0)
            ans=max(ans,dp[i][0]);
    }
    if((ans==0)&&(cnt!=0))
        ans=1;
    if(ans!=0)
        cout<<ans;
    else
        cout<<"-1s";
    return 0;
}

E.Lost in WHU

题意：

给了一张无向图，问在T步内可以从1走到n的总方案数。
注意如果走到n就停了，不会继续走。

做法：

根据矩阵的性质，直接矩阵快速幂。

注意点：

1. 因为题目要求走到n之后就停止，所以读入图的时候把从节点n出去的边都删掉。
2. 最后求答案需要二分等比矩阵或者再次构造一个矩阵递推式。我用了第二种做法。

代码：

#include<bits/stdc++.h>
using namespace std;
const long long Mod=1e9+7;
int n,m,T;
struct Mat
{
    int row,column;
    long long a[101][101];
    Mat(int xx,int yy):row(xx),column(yy)//构造函数
    {
        for(int i=1;i<=row;i++)
            for(int j=1;j<=column;j++)
                a[i][j]=0LL;
    }
    Mat operator *(const Mat& X)//重载矩阵乘法,必须确保合法
    {
        Mat Y(this->row,X.column);
        for(int i=1;i<=this->row;i++)
            for(int j=1;j<=X.column;j++)
        {
            for(int k=1;k<=this->column;k++)
                Y.a[i][j]=(Y.a[i][j]+this->a[i][k]*X.a[k][j])%Mod;
        }
        return Y;
    }
    Mat operator +(const Mat& X)
    {
        Mat Y(row,column);
        for(int i=1;i<=row;i++)
            for(int j=1;j<=column;j++)
        {
            Y.a[i][j]=(this->a[i][j]+X.a[i][j])%Mod;
        }
        return Y;
    }
    Mat& operator =(const Mat& X)
    {
        for(int i=1;i<=row;i++)
            for(int j=1;j<=column;j++)
            a[i][j]=X.a[i][j];
        return *this;
    }
};
Mat FastMod(Mat X,int i)//计算矩阵快速幂;i>0
{
    if(i==1)
        return X;
    Mat ANS=Mat(X.row,X.column);
    for(int i=1;i<=X.row;i++)
        ANS.a[i][i]=1LL;
    while(i)
    {
        if(i&1)
            ANS=ANS*X;
        i>>=1;
        X=X*X;
    }
    return ANS;
}

int main(void)
{
    int xx,yy;
    long long ans=0;
    cin>>n>>m;
    Mat A(n,n);
    Mat SUM(n,n);
    Mat TEMP(n,n);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&xx,&yy);
        A.a[xx][yy]=1LL;
        A.a[yy][xx]=1LL;
        if(xx==n)
            A.a[xx][yy]=0LL;
        if(yy==n)
            A.a[yy][xx]=0LL;
        //cout<<xx<<"with"<<yy<<endl;
    }
    scanf("%d",&T);
    Mat B(2*n,2*n);
    //为B赋值
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            B.a[i][j]=A.a[i][j];
        for(int j=n+1;j<=2*n;j++)
            B.a[i][j]=A.a[i][j-n];
    }
    for(int i=n+1;i<=2*n;i++)
    {
        for(int j=1;j<=n;j++)
            B.a[i][j]=0LL;
        for(int j=n+1;j<=2*n;j++)
        {
            if(i==j)
                B.a[i][j]=1LL;
            else
                B.a[i][j]=0LL;
        }
    }
    Mat C(2*n,n);
    //为C赋值
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            C.a[i][j]=A.a[i][j];
    for(int i=n+1;i<=2*n;i++)
        for(int j=1;j<=n;j++)
        {
            if(i-n==j)
                C.a[i][j]=1LL;
            else
                C.a[i][j]=0LL;
        }


    Mat ANS(2*n,n);
    Mat D(2*n,2*n);
    //printf("mark1\n");
    //printf("T=%d\n",T);
    if(T!=1)
    {
        D=FastMod(B,T-1);
        ANS=D*C;
    }
    else
        ANS=C;

    ans=ANS.a[1][n];
    cout<<ans;
    return 0;
}

G.Time Limit Exceeded

题意：求逆序对

做法：这里尝试了归并的做法

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int n;
int a[maxn];
long long cnt;
int A[maxn],B[maxn];
void merge(int i,int x,int j)
{
    int length_a=x-i,length_b=j-x;
    for(int k=0;k<length_a;k++)
        A[k]=a[i+k];
    for(int k=0;k<length_b;k++)
        B[k]=a[x+k];
    A[length_a]=B[length_b]=INT_MAX;
    int ii=0,jj=0;
    while((ii<length_a)||(jj<length_b))
    {
        if(A[ii]<=B[jj])
        {
             a[i+ii+jj]=A[ii];
             ii++;
        }
        else
        {
            a[ii+jj+i]=B[jj];
            //printf("We are now merging(%d,%d,%d),A[%d]=%d,B[%d]=%d\n",i,x,j,ii,A[ii],jj,B[jj]);
            jj++;
            if(A[ii]!=INT_MAX)
            cnt+=length_a-ii;
        }
    }

}
void mergeSort(int i,int j)
{
    int mid=(i+j)/2;
    if(j-i==1)//平凡情况，只有一个数
        return ;
    mergeSort(i,mid);
    mergeSort(mid,j);
    merge(i,mid,j);
}

int main(void)
{
    cin>>n;
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    cnt=0;
    mergeSort(0,n);
    cout<<cnt;
    return 0;
}

​​