河南农业大学ACM训练第二场-A.K.W ,Y四题题解

A-HDU1096-A+B for Input-Output Practice (VIII)

你的任务是求许多数的和。
Input
第一行需要输入一个整数N，接下来会有N行。 每一行开始输入一个整数M，然后会有M个数在同一行。
Output
对于每组输入，要求在一行输出它们的和。并且你要保证每组输出之间有一空行。
Sample Input
3
4 1 2 3 4
5 1 2 3 4 5
3 1 2 3
Sample Output
10
15
6

解题思路：定义一个数组，将数存在数组里，然后遍历一遍用sum将所有的值加起来；也可以在输入时就sum+=a；
题目坑点：输出格式两行之间有换行，最后一行后面没换行，需要注意。
代码如下：

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
int num[maxn];
int main(){
/* #ifdef LOCAL freopen("C:/Users/Administrator/Desktop/input.txt", "r", stdin); #endif*/
    int t;
    scanf("%d",&t);
    while(t--){

        int n,sum=0;
        scanf("%d",&n);
        //第一种解法 
        for(int i=0;i<n;i++)scanf("%d",&num[i]);
        for(int i=0;i<n;i++)sum+=num[i];
        //第二种解法 
    /* int a; for(int i=0;i<n;i++){ scanf("%d",&a); sum+=a; } */
        if(t==0)printf("%d\n",sum); //如果是最后一行则不输出空行 
        else printf("%d\n\n",sum);

    }
} 

K-POJ-1321 棋盘问题

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
Input
输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
Output
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
Sample Input
2 1
#.
.#
4 4
…#
..#.
.#..
#…
-1 -1
Sample Output
2
1

解题思路：按行递增的顺序来搜索的, 因此不可能出现同行的情况, 对于同列的情况，设置了一个变量col[], 来保存列的访问状态, 对于之前访问过的列, 棋子是不能再放在这一列上的
dfs(begin, num) 代表将第k-num棵棋子放在begin行上, 然后就剩下num-1棵棋子需要放在begin行下面. 当然, 可能存在第num棵棋子根本无法放在begin行上的情况, 对于这种情况, dfs就回溯到上一个dfs调用的地方, 重新开始, 而如果遇到num=1, 且第begin行的一些列可以放的话, 就将方案数相应增加.
本题考的就是一个DFS深搜，理解了DFS这题就相较而言还是简单的
代码如下：

#include<stdio.h>
/*#include <bits/stdc++.h> #include<cstring>*/   //POJ不让用万能头 
using namespace std;
const int maxn=20; 
char pic[maxn][maxn];  
int col[maxn];//标记列的访问状态 
int c;  
int n,k;    
void dfs(int begin,int num){  
    for(int j=0;j<n;j++){  
        if(pic[begin][j]=='#' && col[j]==0){  
            if(num==1)c++;  
            else  {  
                col[j]=1;  
                for(int h=begin+1;h<n-num+2;h++)  dfs(h,num-1);  
                col[j]=0;  
            }  
        }  
    }  
}   
int main(){     
/* #ifdef LOCAL freopen("C:/Users/Administrator/Desktop/input.txt", "r", stdin); #endif*/
    while(scanf("%d%d",&n,&k) && !(n==-1 && k==-1)){  
        c=0;  
        for(int i=0;i<n;i++)scanf("%s",pic[i]); 
        for(int i=0;i<n;i++)col[i]=0;  
        for(int i=0;i<=n-k;i++){  //一共要放k个棋子,每行至多一个,所以需要k行 
            dfs(i,k);           //从第i行开始,放k个棋子.按照按行递增的顺序访问,一定不会出现同行 
        }  
        printf("%d\n",c);
    }  
}  

W-POJ-3461 Oulipo

PJ的女朋友是一个书法家，喜欢写一些好看的英文书法。有一天PJ拿到了她写的纸条，暗示要送给他生日礼物。PJ想知道自己想要的礼物是不是就是她送的，于是想看看自己想要的在纸条中出现了多少次。

Input
第一行输入一个整数代表数据的组数
每组数据第一行一个字符串 W代表PJ想要的礼物, 包含英语字符 {‘A’, ‘B’, ‘C’, …, ‘Z’}, 并且字符串长度满足 1 ≤|W| ≤ 10,000 (|W| 代表 W字符串的长度). 接下来一行一个字符串 T代表女朋友的纸条, 也包含英语字符 {‘A’, ‘B’, ‘C’, …, ‘Z’}, 满足 |W| ≤ |T| ≤ 1,000,000.
Output 输出一行一个整数代表 W 在T中出现的次数.

Sample Input :
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

Sample Output:
1
3
0

解题思路：题目要求求出模式串P在母串S中出现次数，注意点：模式串AZA在母串AZAZA中算出现两次 ；因为这题数据范围比较大，很明显用暴力算法是过不去的，所以这题是一道KMP字符串匹配模版题，所以详解请见KMP字符串匹配算法及KMP优化代码
代码如下：

#include<stdio.h>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1e6+5; 
char s[maxn],t[maxn];
int slen,tlen;
int nex[maxn];//nex数组大小和短串一致
int ans,a,b,c,d,n,m;
inline void get_nex(){
    int j=-1;//影响next[0] 
    for (int i=0;i<tlen;i++){
        while(t[i]!=t[j+1] && j!=-1)j=nex[j];
        if (t[i]==t[j+1] && i!=0) j++;
        nex[i]=j;
    }
}
inline void kmp(){
    int j=-1;
    for (int i=0;i<slen;i++){
        while(s[i]!=t[j+1] && j!=-1) j=nex[j];
        if (s[i]==t[j+1]) j++;
        if (j==tlen-1)ans++,j=nex[j];
    }
}
int main(){
    scanf("%d",&n);
    while(n--){
        ans=0;
        scanf("%s",t);
        scanf("%s",s);
        slen=strlen(s);
        tlen=strlen(t);//这两个长度应该设为全局变量最开始时求出，不能用一次求一次
        get_nex();
        //for(int i=0;i<tlen;i++)printf("%d ",nex[i]);
        //printf("\n"); 
        kmp();      //kmp函数 
        printf("%d\n",ans);
    }
}

Y–51nod-1089 最长回文子串 V2（Manacher算法）

回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。 输入一个字符串Str，输出Str里最长回文子串的长度。
Input
输入Str（Str的长度 <= 100000)
Output
输出最长回文子串的长度L。
Sample Input
daabaac
Sample Output
5

解题思路：本题题意很明确，给一串字符串，求出最长回文串长度。和W题一样，不得不和爱暴力解题的同学说声不好意思，这题范围也比较大，暴力不可能过，这题也是考一种高效算法–Manacher算法（俗称马拉车），这题也是一道马拉车经典模版题。因为要做出这道题你就需要学会马拉车（当然还有其他算法也可以做，但马拉车实现相对简单），所以请看Manacher最长回文串算法
代码如下：

#include<stdio.h> 
#include<bits/stdc++.h>
using namespace std;
const int maxn=111111;
char s[maxn];
char s_new[maxn*2];
int p[maxn*2];
int Init(){
    int len = strlen(s);
    s_new[0] = '$';
    s_new[1] = '#';
    int j = 2;
    for (int i = 0; i < len; i++){
        s_new[j++] = s[i];
        s_new[j++] = '#';
    }
    s_new[j] = '\0';  //别忘了哦  
    //printf("%s\n",s_new);
    return j;  //返回s_new的长度  
}
int Manacher(){
    int len = Init();  //取得新字符串长度并完成向s_new的转换  
    int maxLen = -1;   //最长回文长度  
    int id;
    int mx = 0;
    for (int i = 1; i < len; i++){
        if (i < mx)
            p[i] = min(p[2 * id - i], mx - i);  //需搞清楚上面那张图含义, mx和2*id-i的含义
        else
            p[i] = 1;
        while (s_new[i - p[i]] == s_new[i + p[i]])  //不需边界判断，因为左有'$',右有'\0'  
            p[i]++;
        //我们每走一步i，都要和mx比较，我们希望mx尽可能的远，这样才能更有机会执行if (i < mx)这句代码，从而提高效率 
        if (mx < i + p[i])  {
            id = i;
            mx = i + p[i];
        }
        maxLen = max(maxLen, p[i] - 1);
       // printf("%d %d %d\n",mx,id,maxLen);
    }
    /*for(int i=1;i<=len;i++)printf("%d ",p[i]);
    printf("\n");*/
    return maxLen;
}
int main(){
    scanf("%s", s);
    printf("%d\n", Manacher());
    return 0;
}

感觉题解不错的小伙伴麻烦点个赞哦QAQ