@TryMyEdge 2017-01-30T16:01:17.000000Z 字数 3866 阅读 1032

第二次作业

题解

A Game with Pearls

题目大意：

    M（M<=500）组数据。有N（1<=N<=100）个管子，给出每个管子内的珍珠数目a，你可以让其中任意一个管子增加K（1<=K<=N）个，该操作可进行任意次，问是否能让珍珠数目为1到N的管子各存在一个。

解题思路：

    用一个从小到大的优先队列维护所有的管子，当队首的管子的珍珠数大于当前要求的珍珠数时，说明不可行；当正好相等，说明这个管子是当前要求的，把珍珠数加一，直到珍珠数超过N；如果小于，就把管子内加K个珍珠重新加入队列。
    时间复杂度o（M*N^2/K*logn），空间复杂度o（N）。

AC代码：

#include<iostream>
#include<bits/stdc++.h>
#define pq priority_queue
using namespace std;
int main()
{
    int t,n,k,now;
    bool flag;
    scanf("%d",&t);
    while(t--)
    {
        pq <int,vector<int>,greater<int> > q;
        scanf("%d%d",&n,&k);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&now);
            q.push(now);
        }
        flag=0;
        for(int i=1;i<=n;i++)
        {
            do
            {
                now=q.top();
                q.pop();
                if(now<i)
                    q.push(now+k);
            }while(now<i);
            if(now>i)
            {
                flag=1;
                break;
            }
        }
        if(flag)
            printf("Tom\n");
        else
            printf("Jerry\n");
    }
    return 0;
}

C Seam Carving

题目大意：

    T（0<T<=30）组数据。给出个m*n（0<m,n<=100）的矩阵G，每个点可以往左下、右下或者正下方走，求和最小的路径。如果有多条路径，输出最右（字典序最大）的路径。

解题思路：

    让人联想起很经典的金字塔最优路径的dp题。记录到每个位置位置，最小的路径和，不断更新即可。
    因为要求输出最右（字典序最大）路径，所以从最后一行倒着dp。
    状态转移方程：dp[i][j]表示到第i行的第j列为止的最小路径和。
    dp[i][j]=min（dp[i=1][j-1]，dp[i=1][j]，dp[i=1][j+1]）+G[i][j]。
    用一个nex数组记录每个点的前一步，在第一行中找最优答案然后通过nex数组一行一行输出即可。
    注意边界的处理。
    时间复杂度o（T*n*m），空间复杂度o（n*m）。

AC代码：

#include<iostream>
#include<bits/stdc++.h>
#define pq priority_queue
using namespace std;
long long num[105][105];
long long dp[105][105];
int pre[105][105];
int main()
{
    long long minn;
    int T,n,m,ans;
    scanf("%d",&T);
    for(int t=1;t<=T;t++)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%lld",&num[i][j]);
        printf("Case %d\n",t);
        if(m==1)
        {
            for(int i=1;i<=n;i++)
            {
                if(i>1)
                    printf(" ");
                printf("1");
            }
            printf("\n");
        }
        else
        {
            for(int i=1;i<=m;i++)
                dp[n][i]=num[n][i];
            for(int i=n-1;i;i--)
                for(int j=1;j<=m;j++)
                {
                    if(j==1)
                    {
                        dp[i][j]=num[i][j]+dp[i+1][j];
                        pre[i][j]=j;
                        if(num[i][j]+dp[i+1][j+1]<=dp[i][j])
                        {
                            dp[i][j]=num[i][j]+dp[i+1][j+1];
                            pre[i][j]=j+1;
                        }
                    }
                    else
                    {
                        if(j==m)
                        {
                            dp[i][j]=num[i][j]+dp[i+1][j-1];
                            pre[i][j]=j-1;
                            if(num[i][j]+dp[i+1][j]<=dp[i][j])
                            {
                                dp[i][j]=num[i][j]+dp[i+1][j];
                                pre[i][j]=j;
                            }
                        }
                        else
                        {
                            dp[i][j]=num[i][j]+dp[i+1][j-1];
                            pre[i][j]=j-1;
                            if(num[i][j]+dp[i+1][j]<=dp[i][j])
                            {
                                dp[i][j]=num[i][j]+dp[i+1][j];
                                pre[i][j]=j;
                            }
                            if(num[i][j]+dp[i+1][j+1]<=dp[i][j])
                            {
                                dp[i][j]=num[i][j]+dp[i+1][j+1];
                                pre[i][j]=j+1;
                            }
                        }
                    }
                }
            minn=2000000000000;
            for(int i=1;i<=m;i++)
            {
                if(dp[1][i]<=minn)
                {
                    minn=dp[1][i];
                    ans=i;
                }
            }
            for(int i=1;i<n;i++)
            {
                printf("%d ",ans);
                ans=pre[i][ans];
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

F Linearization of the kernel functions in SVM

题目大意：

    T（T<120）组数据。给定10个系数描述了一个多项式，输出这个多项式。

解题思路：

    题目太长而且都是符号，所以我是对着样例写的，然后就WA了一发。。。
    按要求模拟，注意系数是0的情况，第一个输出的系数如果是正数不需要'+'，系数是1和-1的时候隐藏数字只保留符号，还有最后一个常数项是0等情况。
    时间复杂度o（T），空间复杂度o（1）。

AC代码：

#include<iostream>
#include<bits/stdc++.h>
#define pq priority_queue
using namespace std;
char s[]={'p','q','r','u','v','w','x','y','z'};
int main()
{
    int t,now;
    bool flag;
    cin>>t;
    while(t--)
    {
        flag=0;
        for(int i=0;i<9;i++)
        {
            scanf("%d",&now);
            if(now!=0)
            {
                if(now>0 && flag)
                    printf("+");
                if(abs(now)!=1)
                    printf("%d",now);
                else
                {
                    if(now<0)
                        printf("-");
                }
                printf("%c",s[i]);
                flag=1;
            }
        }
        scanf("%d",&now);
        if(now!=0)
        {
            if(now>0 && flag)
                printf("+");
            printf("%d",now);
        }
        printf("\n");
    }
    return 0;
}

H Page Rank

题目大意：

    多组数据，处理到文件结尾。给出一个N*N（N<=3000）的0/1矩阵S，根据题目的公式转化为一个N*N的实数矩阵G。然后求|qGq|<10^-10的时候的q。

解题思路：

    按题目给出的方法求出G，然后q初始值为全1的N阶向量，然后模拟向量乘法直到满足要求就行了。
    = =然而并不知道复杂度如何证明。。。查到的题解也没给出复杂度。
    时间复杂度o（?*N^2），空间复杂度o（N^2）。

AC代码：

#include<iostream>
#include<bits/stdc++.h>
#define pq priority_queue
using namespace std;
double G[3005][3005];
double q[2][3005];
bool flag;
int num[3005];
char s[3005][3005];
int n;
bool ok()
{
    double ans=0;
    for(int i=1;i<=n;i++)
        ans+=(q[flag][i]-q[!flag][i])*(q[flag][i]-q[!flag][i]);
    return ans>0.0000000001;
}
void getq()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            q[flag][i]+=G[i][j]*q[!flag][j];
}
int main()
{
    while(~scanf("%d",&n))
    {
        memset(num,0,sizeof(num));
        for(int i=1;i<=n;i++)
        {
            scanf("%s",s[i]+1);
            for(int j=1;j<=n;j++)
            {
                num[i]+=s[i][j]-'0';
            }
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                G[i][j]=0.15/n;
                if(s[j][i]-'0')
                    G[i][j]+=0.85/num[j];
            }
        memset(q[1],0,sizeof(q[1]));
        for(int i=1;i<=n;i++)
            q[0][i]=1;
        flag=0;
        while(ok())
        {
            flag=!flag;
            memset(q[flag],0,sizeof(q[flag]));
            getq();
        }
        for(int i=1;i<=n;i++)
        {
            if(i>1)
                printf(" ");
            printf("%.2f",q[flag][i]);
        }
        printf("\n");
    }
    return 0;
}

第二次作业

内容目录