第二次作业

题解

A - Game with Pearls

题目大意：

有N and K (1 <= N <= 100, 1 <= K <= N), n表示n根水管，每根水管里有一定数量的珍珠（大于0小于等于n）。先每次能放k的正整数倍珍珠进去，或者不放，问能否实现放珍珠后再升序排序实现低i根水管有i棵珍珠，

解题思路：

这是二分图求最大匹配数，如果最大匹配数为n的话，则说明可以实现，反之，则不能。先求得第i根水管放珍珠后能够得到的所有珍珠数。让后再用百bfs进行匹配。求最大匹配数。

AC代码：

    #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int T,n,k,ans,t,vis[105],a[105][105],march[105];
bool dfs(int x){
    for(int i=1;i<=n;i++){
        if(!vis[i]&&a[x][i]){
            vis[i]=1;
            if(!march[i]||dfs(march[i])){//如果第i位置的珍珠数没有被匹配，或者匹配了但是能匹配到其他的水管
                march[i]=x;
                return true;
            }
        }
    }
    return false ;
}
void solve(){
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));//ps :每次都得重置为0，因为上一匹配访问跟下次无关
        if(dfs(i)) ans++;//匹配一次匹配数加1
    }

}
int main(){
    cin>>T;
    while(T--){
        cin>>n>>k;
        memset(a,0,sizeof(a));
        memset(march,0,sizeof(march));
        ans=0;
        for(int i=1;i<=n;i++){
            cin>>t;
            while(t<=n){
                a[i][t]=1;//先求得第i根水管能到达的所有珍珠数
                t+=k;
            }
        }
        solve();
        if(ans==n)
            cout<<"Jerry"<<endl;
        else cout<<"Tom"<<endl;
    }
    return 0;
}

**C - Seam Carving **

题目大意：

一个m*n的矩阵（都小于100），让你从顶端走到底端，每次只能走到下一行的同一列，j-1列，j+1列（即a[i+1][j],a[i+1][j-1],a[i+1][j-1]）,找到期最短路径并依次输出他们的列下标，如果有多解，则输出最右

边的那条路径

解题思路：

这是一道dp题，状态转移方程dp[i][j]=min(min(dp[i+1][j],dp[i+1][j+1]),dp[i+1][j-1])+a[i][j].但要用一个bk数组来保存上一选取节点的纵坐标。

AC代码：

    #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
int a[105][105],dp[105][105],bk[105][105],T,ncase,n,m;
int main(){
    cin>>T;
    while(T--){
        cin>>n>>m;
        memset(a,0,sizeof(a));
        memset(dp,0,sizeof(dp));
        memset(bk,0,sizeof(bk));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)
                cin>>a[i][j];
        }
        for(int i=1;i<=m;i++)
            dp[1][i]=a[1][i];
        for(int i=2;i<=n;i++){
            for(int j=1;j<=m;j++){
                dp[i][j]=dp[i-1][j];
                bk[i][j]=j;
                if(j-1>=1&&dp[i-1][j-1]<=dp[i][j]){
                    dp[i][j]=dp[i-1][j-1];
                    bk[i][j]=j-1;
                }
               if(j+1<=m&&dp[i-1][j+1]<=dp[i][j]){
                    dp[i][j]=dp[i-1][j+1];
                    bk[i][j]=j+1;
                }
                dp[i][j]+=a[i][j];
            }
        }
        int ans=0x3f3f3f3f,t;
        for(int i=1;i<=m;i++){
            if(ans>=dp[n][i]){
                ans=dp[n][i];
                t=i;
            }
        }
        stack<int > p;
        p.push(t);
        cout<<"Case "<<++ncase<<endl;
        for(int i=n;i>1;i--){
            p.push(bk[i][t]);//将所有下标从最后一行到第一行依次推入栈当中
            t=bk[i][t];
        }
        cout<<p.top();
        p.pop();
        while(!p.empty()){
            cout<<" "<<p.top();
            p.pop();
        }
        cout<<endl;

    }
    return 0;
}

**F - Linearization of the kernel functions in SVM **

题目大意：

10个数分别表示p,q,r,u,v,w,x,y,z,的系数还有一个常数项系数，现在要求你还原原公式,例如：0，1,0,0,0,0,0,0,0,2表示q+1.

解题思路：

还原简单，但要注意细节，1，-1这两个数是只带符号的（除了常数项），还有除了第一项（前提是前面没现负数）的正数不带符号，其他的都得带符号。

AC代码：

>

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[15],T,n;
int main(){
    cin>>T;
    char s[10]="pqruvwxyz";
    while(T--){
        int flag=0;
        for(int i=0;i<9;i++){
            cin>>n;
            if(n>0){
                if(flag==0){
                    if(n==1)
                       cout<<s[i];
                    else cout<<n<<s[i];
                    flag=1;
                }
                else {
                    if(n==1) cout<<"+"<<s[i];
                    else cout<<"+"<<n<<s[i];
                }
            }
            if(n<0){
                if(n==-1)
                   cout<<"-"<<s[i];
                else cout<<n<<s[i];
                flag=1;
            }
        }
        cin>>n;
        if(n>0){
            if(flag) cout<<"+"<<n;
            else cout<<n;
        }
        if(n<0)
            cout<<n;
        cout<<endl;
    }
    return 0;
}

**P - Friendship of Frog **

题目大意：

一个字符串，求其相同字符之间的字符个数的最小值，例如：abcecba为1.没有相同字符的输出-1。

解题思路：

只有26个字母，可以用一个数组来保存这个字母上一次出现的位置，再更新，求其最小值。

AC代码：

   #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char s[1005];
int T,ncase,a[26];
int main(){
    cin>>T;
    while(T--){
        cin>>s;
        int Min=0x3f3f3f3f;
        memset(a,-1,sizeof(a));
        int len=strlen(s);
        for(int i=0;i<len;i++){
            int tp=s[i]-'a';

            if(a[tp]==-1)
                a[tp]=i;
            else {
                Min=min(i-a[tp],Min);
                a[tp]=i;
            }
        }
        printf("Case #%d: ",++ncase);
        if(Min==0x3f3f3f3f)
            cout<<-1<<endl;
        else cout<<Min<<endl;
    }
    return 0;
}