精华内容
下载资源
问答
  • 2015南大机试

    2018-03-02 17:48:01
    罗马数字转十进制数
  • 题目是这样的: 已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵,你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。 比如,如下4 * 4的矩阵 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 ...

    题目是这样的:

    已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵,你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。
    比如,如下4 * 4的矩阵

    0 -2 -7 0
    9 2 -6 2
    -4 1 -4 1
    -1 8 0 -2

    的最大子矩阵是

    9 2
    -4 1
    -1 8

    这个子矩阵的大小是15。

    输入

    输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。
    再后面的若干行中,依次(首先从左到右给出第一行的N个整数,再从左到右给出第二行的N个整数……)给出矩阵中的N2个整数,整数之间由空白字符分隔(空格或者空行)。
    已知矩阵中整数的范围都在[-127, 127]。

    输出

    测试数据可能有多组,对于每组测试数据,输出最大子矩阵的大小。

    样例输入

    1
    27 
    3
    -40 29 -16 
    38 18 22 
    24 -35 5 
    

    样例输出

    27
    78

    其实吧,这题不难,主要就是要能转过来一个弯:

    将二维数组转化为一维数组,然后通过该一维数组来找到最大连续子序列。

    比如最大的连续子矩阵的和为从第 i 行 到 第 j 行的元素在列的方向上相加,得到一个一维数组arrtemp[],然后计算出这个一维数组的最大子序列的和maxtemp,通过对 i 和 j 进行枚举(1<=i<=N, i<=j<=N),计算出N(N-1)/2 个 maxtemp,取其中最大的那个作为最终的最大子矩阵的值。

     

    /*
        实际上就是最大连续子序列和的问题,只不过要对从i行到j行的所有的可能都枚举
        然后要设置一个Max值来进行保存并更新当前的最大值
    */
    #include<iostream>
    #include<cstring>
    using namespace std;
    
    int N;
    int a[505][505];
    int temp[505];
    
    int max_oneVec(int an[])            //一维数组的动态规划
    {
        int dp2[505];
        dp2[1]=an[1];                   //边界条件,第1个结尾的子串只能是自己
        int maxnum=dp2[1];              //标记最大值
        for(int i=2;i<=N;i++)           //从第2个开始
        {
            if(dp2[i-1]>0)
            {
                dp2[i] = dp2[i-1]+an[i];
            }else
            {
                dp2[i] = an[i];
            }
            if(dp2[i]>maxnum)
            {
                maxnum = dp2[i];        //更新最大值
            }
        }
        return maxnum;
    }
    
    int main()
    {
        cin>>N;
        for(int i=1;i<=N;i++)
        {
            for(int j=1;j<=N;j++)
            {
                cin>>a[i][j];
            }
        }
        int maxres=0;
        for(int i=1;i<=N;i++)   //从第一行开始搜索
        {
            memset(temp,0,sizeof(temp));        //重置当前的dp数组
            for(int j=i;j<=N;j++)
            {
                for(int k=1;k<=N;k++)           //累加当前的从第i行到j行的数组值放入一维数组中
                {
                    temp[k] += a[j][k];
                }
            }
            int maxtemp = max_oneVec(temp);     //该一维数组的最大值即为当前从i行到j行矩阵的最大值
    
            if(maxtemp>maxres)
            {
                maxres = maxtemp;
            }
        }
        cout<<maxres<<endl;
        return 0;
    }
    

     

    展开全文
  • 题目是这样的:已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵,你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。比如,如下4 * 4的矩阵0 -2 -7 09 2 -6 2-4 1 -4 1-1 8 0 -2的最大子矩阵是9 2-4 1-1 8这...

    题目是这样的:

    已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵,你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。

    比如,如下4 * 4的矩阵

    0 -2 -7 0

    9 2 -6 2

    -4 1 -4 1

    -1 8 0 -2

    的最大子矩阵是

    9 2

    -4 1

    -1 8

    这个子矩阵的大小是15。

    输入

    输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。

    再后面的若干行中,依次(首先从左到右给出第一行的N个整数,再从左到右给出第二行的N个整数……)给出矩阵中的N2个整数,整数之间由空白字符分隔(空格或者空行)。

    已知矩阵中整数的范围都在[-127, 127]。

    输出

    测试数据可能有多组,对于每组测试数据,输出最大子矩阵的大小。

    样例输入

    1

    27

    3

    -40 29 -16

    38 18 22

    24 -35 5

    样例输出

    27

    78

    其实吧,这题不难,主要就是要能转过来一个弯:

    将二维数组转化为一维数组,然后通过该一维数组来找到最大连续子序列。

    比如最大的连续子矩阵的和为从第 i 行 到 第 j 行的元素在列的方向上相加,得到一个一维数组arrtemp[],然后计算出这个一维数组的最大子序列的和maxtemp,通过对 i 和 j 进行枚举(1<=i<=N, i<=j<=N),计算出N(N-1)/2 个 maxtemp,取其中最大的那个作为最终的最大子矩阵的值。

    /*

    实际上就是最大连续子序列和的问题,只不过要对从i行到j行的所有的可能都枚举

    然后要设置一个Max值来进行保存并更新当前的最大值

    */

    #include#includeusing namespace std;

    int N;

    int a[505][505];

    int temp[505];

    int max_oneVec(int an[]) //一维数组的动态规划

    {

    int dp2[505];

    dp2[1]=an[1]; //边界条件,第1个结尾的子串只能是自己

    int maxnum=dp2[1]; //标记最大值

    for(int i=2;i<=N;i++) //从第2个开始

    {

    if(dp2[i-1]>0)

    {

    dp2[i] = dp2[i-1]+an[i];

    }else

    {

    dp2[i] = an[i];

    }

    if(dp2[i]>maxnum)

    {

    maxnum = dp2[i]; //更新最大值

    }

    }

    return maxnum;

    }

    int main()

    {

    cin>>N;

    for(int i=1;i<=N;i++)

    {

    for(int j=1;j<=N;j++)

    {

    cin>>a[i][j];

    }

    }

    int maxres=0;

    for(int i=1;i<=N;i++) //从第一行开始搜索

    {

    memset(temp,0,sizeof(temp)); //重置当前的dp数组

    for(int j=i;j<=N;j++)

    {

    for(int k=1;k<=N;k++) //累加当前的从第i行到j行的数组值放入一维数组中

    {

    temp[k] += a[j][k];

    }

    }

    int maxtemp = max_oneVec(temp); //该一维数组的最大值即为当前从i行到j行矩阵的最大值

    if(maxtemp>maxres)

    {

    maxres = maxtemp;

    }

    }

    cout<

    展开全文
  • Problem A第一题最笨的思路(by:LittleSec)都规定输入的最大深度是5了,所以直接穷举深度为1-5的满二叉树前序->中序方案,主要就是下标转换:eg:输入ABC对应的下标是012,输出是顺序变成102而已。...

    Problem A

    第一题最笨的思路(by:LittleSec)

    都规定输入的最大深度是5了,所以直接穷举深度为1-5的满二叉树前序->中序方案,主要就是下标转换:

    eg:输入ABC对应的下标是012,输出是顺序变成102而已。

    eg:高度为3的情况则构造下标数组:a[] = {2,1,3,0,5,4,6},假设输入的字符串存在str,那么输出就是

    for(int i = 0; i < pow(2,n)-1; i++)

    {

    if(str[a[i]]=='#') continue;

    else cout << str[a[i]];

    }

    5种情况而已,草稿纸上列举不用10分钟。

    亲测能通过所有测试样例。(:逃

    第一题稍微不那么笨但还是很笨的思路(by:六月雪Yuni)

    只要知道如何从满二叉树的先序遍历推出原树就可以做。根据定义,满二叉树的某一棵子树的先序遍历是[根][左子树序列][右子树序列]的形式,而且左子树序列和右子树序列长度相同。那么先取出根,然后递归处理左子树和右子树就可以构造出原树。得到原树之后中序遍历乱搞就可以啦。

    另外值得注意的是有一些原本可以得到300分的大佬因为读题失误,把#节点认为是不存在的节点,而忽略了#节点也可能作为父节点的情况,导致本题只能做到80分或90分。呜呼哀哉————读题果然也是重要的一环呢。

    这个思路得到了AC(100pts)。

    伪代码:

    void ConstructTree(int l, int r){

    root = s[l];

    root.leftChild = s[l+1];

    root.rightChild = s[l+1+(r-l)/2];

    ConstructTree(l+1,l+(r-l)/2);

    ConstructTree(l+(r-l)/2+1,r);

    }

    void Output(int root){

    Output(root.leftChild);

    print(root);

    Output(root.rightChild);

    }

    Problem B

    第二题菜鸡拿分经验贴(by:还是最笨的LittleSec

    题中给定输入是s t,千万认为s一定比t小。当s比t大的话,也就是农夫在牛的后面,那么农夫每次都只能执行后退即-1操作,因此最短步数就是s-t步。亲测能通过4个测试样例(噗

    第二题思路1 广度优先搜索(by:六月雪Yuni)

    直接从点s开始BFS。用一个数组vis[]维护元素x是否被加入过队列,d[]记录扩展到元素x需要搜索几步。

    每次取出队首元素fr时,测试fr+1是否在队中,不在则加入队列,并且更新d[fr+1]。对fr-1和fr*2同样这么做。

    需要注意的是加入队列的元素不能是负数,因为0<=s,t<=100000,加入负数没有意义。fr*2也不能超过100000。

    这个思路做到了AC(100pts)。

    部分代码:

    int BFS(int s, int t){

    memset(d,0x3f,sizeof(d)); //这一步将d中所有元素初始化为一个“无限大”,即在题目语境里非常大的数

    const int inf = 0x3f3f3f3f;

    d[s] = 0;

    queue Q;

    while(!Q.empty())Q.pop();

    Q.push(s);

    while(!Q.empty()){

    int fr = Q.front();

    if(fr-1>=0 && d[fr-1]>=inf){

    Q.push(fr-1);

    d[fr-1] = d[fr] + 1;

    }

    if(d[fr+1]>=inf){

    Q.push(fr+1);

    d[fr+1] = d[fr] + 1;

    }

    if(fr*2<=100000 && d[fr*2]>=inf){

    Q.push(fr*2);

    d[fr*2] = d[fr] + 1;

    }

    Q.pop(fr);

    }

    return d[t];//因为我们知道本题一定有解,所以不判定是否存在。

    }

    第二题思路3 DP

    听说有大佬用动态规划解了这题,待补充。

    Problem C

    第三题思路1 DP(by 笔试爆炸啦qaq)

    我们令dp[i][j]为串s[1..i]和t[1..j]的最长公共子序列长度。例如,对s="abcde"和t="acefg",s[1..4]="abcd",t[1..3]="ace",所以dp[4][3]=2。(最长公共子序列是"ac")

    这样,就有了以下的递推式:

    s[i] == t[j] : dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+1).

    s[i] != t[j] : dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

    初始条件 dp[0][0] = 0

    时间复杂度O(L^2),L = max(s.length, t.length).

    然后dp[s.length][t.length]就是串s和串t的公共子序列长度。将这个过程重复n次、取最大就可以求得题目的解。因为1<=n<=200,L<=2000,所以可以在时限内得到解。

    这个思路得到了AC(100pts)。

    展开全文
  • 三道题,每道题10个数据点,每数据点10分,合计300分。300分制的得分折算成50分制计入复试总成绩中。题目来源:六月雪Yuni(SnowyJune973)第一题给出一棵满二叉树的先序遍历,有两种节点:字母节点(A-Z,无重复)和空...

    三道题,每道题10个数据点,每数据点10分,合计300分。300分制的得分折算成50分制计入复试总成绩中。

    题目来源:六月雪Yuni(SnowyJune973)

    第一题

    给出一棵满二叉树的先序遍历,有两种节点:字母节点(A-Z,无重复)和空节点(#)。要求这个树的中序遍历。输出中序遍历时不需要输出#。满二叉树的层数n满足1<=n<=5。

    Sample Input:

    ABC#D#E

    Sample Output:

    CBADE

    第二题

    农夫John的奶牛跑路了。将地图视作一条数轴,John的初始位置在s而奶牛的位置在t(0<=s,t<=100000)。John可以花费一分钟的时间使自己作如下移动:

    1 从点x移动到点x+1

    2 从点x移动到点x-1

    3 从点x移动到点x*2

    奶牛的位置一直在点t。现在给定s,t,要求John要追上奶牛最少需要几分钟。

    Sample Input:

    5 17

    Sample Output:

    4

    Description:

    5->4->8->16->17

    第三题

    一个串的“子序列”(subsequence)是将这个串中的一些字符提取出来得到一个新串,并且不改变它们的相对位置关系。例如,串"XDoi","XianYu!","TaiQiangLa!","loa"都是串"XianYuDalaoTaiQiangLa!"的子序列。

    我们说串t是串s1和s2的公共子序列,当且仅当t是s1的子序列且t是s2的子序列。定义串s1和s2的相似度为它们最长公共子序列的长度。

    现在给定一个文本串S和一组模式串T[1]、T[2]、……、T[n]。求T[i]中和S具有最高相似度的那个,然后输出最高的相似度。S和所有的T[i]都只含有小写字母。

    输入规则:先是一行字符串S。第二行是n(1<=n<=100)。第三行以降的n行是n个模式串T[1]...T[n]。S和所有的T[i]的长度都不超过2000.

    Sample Input:

    abcdef

    4

    acfaff

    appont

    emmm

    bdxeuf

    Sample Output:

    bdxeuf

    4

    Description:

    串abcdef和bdxeuf的最长公共子序列是bdef,长度为4.

    Hint:

    经确认,所有的数据都满足有且仅有一组解,这是原题面中未说明的。

    参考思路

    展开全文
  • 2018年南京大学夏令营机试-1 题目描述 Count number of binary strings without consecutive 1’s 输入 Given a positive integer n(3≤n≤90), count all possible distinct binary strings of length n such that ...
  • 2018南京大学夏令营机试第一题

    千次阅读 2018-07-27 18:46:27
    (题目来自tonygsw) 题目大意: 就是输入一个N*N的矩阵,找出在矩阵中,所有元素加起来之和最大的子矩阵。 例如在  0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 ......
  • 2018南京大学夏令营机试第二题

    千次阅读 2018-07-27 19:02:53
    (题目来自tonygsy) 这道题出自(LeetCode 130)Surrounded Regions 题目: Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'. A region is captured by flipping all 'O's...
  • 2018南京大学夏令营机试第三题

    千次阅读 2018-07-27 19:15:55
    (题目来自tonygsw) 题目大意: 有n种零件,每种零件有mi个,每个零件有b,p两种属性,然后每种零件选出1个, 使得n个零件有最小的b/n,当b/n一致时,n个零件p的和最大 此题还未找到出处 ...
  • 2018南京大学计算机夏令营机试

    万次阅读 多人点赞 2018-08-12 11:39:47
    1. Count number of binary strings without consecutive 1’s Given a positive integer n(3≤n≤90), count all possible distinct binary strings of length n such that there are no consecutive 1's . ...
  • 2018年南大计算机机试-2

    千次阅读 2019-06-27 10:36:58
    2018年南大计算机机试-2 题目描述 2. Missing number Given a positive integer n(n≤40), pick n-1 numbers randomly from 1 to n and concatenate them in random order as a string s, which means there is a ...
  • 5. P2121 拆地毯=========很经典的一个题 ...考点:最小生成树(kruskal)、并查集、图论 #include <iostream> #include <algorithm> #define maxn 100005 using namespace std;...struct Edg...
  • 南京某理工类高校机试题 并查集+kruskal+坐标处理 1 const int MAXN=110;//最大点数 2 const int MAXM=100005;//最大边数 3 int F[MAXN];//并查集使用 4 struct Node { 5 int x; 6 int y; 7 } ...
  • 南京大学计算机考研机试2019-1 给定l,r(0≤l,r≤3e8)l,r(0\le l,r\le 3e8)l,r(0≤l,r≤3e8),问[l,r][l,r][l,r]中的自然数满足下述条件的数有多少个? 条件:数字的任意相邻两位差值都恰好为111,且数字至少有两位。...
  • 南大 计算机 机试 1. 输入一串数字,移除 k 个数字,数字相对位置不变,使得剩下的数字组成最小的数 输入: 12321 3 输出: 11 输入: 12 1 输出: 1 2. 有 n 个男孩, m 个女孩,他们站一排,要求 至多 K 个男孩...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 530
精华内容 212
关键字:

南京大学机试