中南大学第九届大学生程序设计竞赛网络预选赛

时间：2021-07-31 19:17:56

A 最多的数字

Description

数字的每一位都由0~9组成，现在给出一个数，问你它所有位数中使用哪个数字最多。

Input

输入包含多个测试实例，每行为一个数字（所有数据小于10的1000次方）。

Output

每一行对应一个要求的答案。（答案为0~9之间的一个数,如果有一样多的情况，输出最小的数字）

Sample Input

1234567891
1122
1111111111111111111111111111111111111111111111111111111

Sample Output

1
1
1
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<set>
#include<algorithm>
#include<map>
#include<climits>
using namespace std;
typedef long long LL;
char s[1002];
int a['9'+1];
int main()
{
    int i,j,k,m,n;
    while(scanf("%s",s) == 1)
    {
        memset(a,0,sizeof(a));
        for(i=0; s[i]; i++)
            a[s[i]]++;
        int mx = -1;
        char ans;
        for(i='0';i<='9';i++)
            if(a[i]>mx)
            mx=a[i], ans=i;
        printf("%c\n",ans);
    }
    return 0;
}


B 和与积

Description

构造N个正数（每个数不超过1000000），使所有数的和与所有数的积相差刚好等于D，按非递减序输出。

Input

多组测试数据(不超过1000组)，每行两个正整数N和D。(2<=N<=1000,D<=1000)

Output

每行应该按非递减序输出对应的N个数。


Sample Input

2 1
3 5

Sample Output

2 3
1 2 8

分析：另前n-2个数均为1，第n-1个为2，设最后一个为X(X>=2)。积=2X，和=n+X。 另 积-和=D， 即2X-（n+X）=D，得 X=n+D， 满足X>=2，直接输出即可。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<set>
#include<algorithm>
#include<map>
#include<climits>
using namespace std;
typedef long long LL;
char s[1002];
int a['9'+1];
int main()
{
    int i,j,k,m,n;
    while(scanf("%d %d",&n,&m)==2)
    {
        for(i=1; i<=n-2; i++) printf("1 ");
        printf("%d %d\n",2,m+n);
    }
    return 0;
}


C 外卖的撕‘哔’大战

Description

“订外卖就上XXX，满X减Y，满X减Y...”这样的声音老回荡在我们耳旁。发传单，拉条幅的宣传手段也屡见不鲜。外卖的撕‘哔’大战充满血雨腥风，不过作为消费者，我们的问题是：“已知N种类似满X减Y的优惠，请问你想点M次外卖，最少出多少钱呢？”。（P.S：各优惠不能叠加，外卖不能拼单拆单。） 

Input

多组数据，第一行有一个整数T，表示有T组数据。（T<=100）

以下每组数据第一行有两个整数N和M，表示外卖网站的优惠种数和你想点的外卖个数。(1<=N,M<=100)

然后接下来N行，每行两个整数ai,bi，表示一种优惠为满ai元可减bi元。（ai>=bi）

最后一行是M个整数，表示你每次点的外卖的价格。

所有的数据不会超过int。

Output

每组数据输出一行，为一个整数，是你在所有外卖上的花销。

Sample Input

2
3 3
5 3
10 6
20 8
5 10 20
3 3
5 5
10 10
20 20
6 10 20

Sample Output

18
1
分析：暴力，对每次外卖找最大的优惠。 

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<set>
#include<algorithm>
#include<map>
#include<climits>
using namespace std;
typedef long long LL;
const int INF = INT_MAX;
struct YH
{
    int a, b;
    bool operator < (const YH&cmp) const
    {
        return b > cmp.b || b == cmp.b && a < cmp.a;
    }
};
YH yh[101];
int a[101];
int main()
{
    int i,j,k,m,n;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        LL sum = 0;
        scanf("%d %d",&m,&n);
        for(i=1; i<=m; i++)
            scanf("%d %d",&yh[i].a,&yh[i].b);
        sort(yh+1,yh+1+m);
        LL ans = 0;
        while(n--)
        {
            scanf("%d",&k);
            for(i=1; i<=m; i++)
                if(yh[i].a <= k)
            {
                k-=yh[i].b;
                //printf("jian %d\n",yh[i].b);
                 break;
            }
            ans += (LL) k;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

D “正直角三角形”

Description

在平面直角坐标系的第一象限内有M个点。“正直角三角形”是一种奇特的三角形，它的三个顶点分别在原点、X轴的正方向和Y轴的正方向。请用一个面积最小的“正直角三角形”将这些点全部围住，求解面积的大小。题目中所有的坐标（包括正直角三角形的顶点坐标）都为整数。

Input

有多组样例（不超过100组），每组样例第一行包括一个正整数M，接下来M行每行包括两个正整数xi,yi表示第i个点的坐标。

(1<=M,xi,yi<=100)

Output

每行一个答案（保留一位小数）。

Sample Input

2
1 1
1 2
2
1 2
1 3

Sample Output

4.0
6.0

分析：本题突破点在于数据范围比较小。设所给点最大X坐标xmax，最大Y坐标ymax，则过（xmax,ymax）点的右下45度方向的直线与坐标轴围城的三角形一定包围所有点，面积为xmax*ymax/2。 所求三角形X轴正方向点的X坐标大于xmax，可得该三角形Y轴正方向的点的Y坐标<4*ymax。

           故：暴力枚举y轴上的点，然后根据n个点，确定x轴上的点，更新最小面积即可。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<set>
#include<algorithm>
#include<map>
#include<climits>
using namespace std;
typedef long long LL;
int xx[110],yy[110];
int main()
{
    int i,j,k,m,n;
    while(scanf("%d",&n) == 1)
    {
        int ans = 40000;
        int ymx = -1, xmx=-1;
        for(i=1; i<=n; i++) scanf("%d %d",xx+i, yy+i),xmx = max(xmx,xx[i]),ymx=max(ymx,yy[i]);
        for(int h=ymx+1; h<=ymx<<2; h++)
        {
            int w = 0;
            for(i=1; i<=n; i++)
            {
                w = max(w, (int)(ceil(xx[i]*yy[i]*1.0/(h-yy[i])+xx[i]) + 0.5));
            }
            //printf("h=%d w=%d\n",h,w);
            ans = min(ans,h*w);
        }
        printf("%.1lf\n",ans/2.0);
    }
    return 0;
}


E 图书管理员的表白方式

Description

小V是中南大学图书馆的图书管理员，每天要整理很多同学们还回来的书。久而久之，他认识了很多常来图书馆的同学，比如说小L。简而言之吧，就是小V喜欢上了小L，并且想在下一次她来还书的时候表白。
小V的创意还是不错的，他精心准备了各种材料，打算构成“L”，“O”，“V”，“E”四个字母，在小L来的时候悄悄组合起来给她看。但是意外来了：在小L来的时候，小V只准备好了“L”，“O”，和“E”，“V”还没有拼好！但是机智的小V立刻想到了一个办法：他可以随手把旁边别人还的书合在一起，并且抽掉其中一部分，令剩下的书的高度构成了一个“V”形。
那么问题来了：已知N本书的高度，在不改变他们的顺序的前提下，能不能得到小V想要的“V”，如果可以的话，最少去掉多少本书呢？
（组成“V”的前提：h1>h2...<hn,即整个高度必须先递减再递增）

Input


多组数据，第一行有一个整数T，表示有T组数据。（T<=100）
以下每组数据第一行有一个整数N，表示这一排书的数量。(1<=N<=100)
然后接下来一行是N个整数，h1,h2...hn分别代表每本书的高度。（1<=hi<=100）

Output

如果可以构成”V”，输出“HAPPY”，并在下一行输出所需拿掉的最少数量。
如果不能，输出“SAD”。

Sample Input

7
3
3 2 3
4
3 2 4 3
5
1 2 4 6 7
1
22
2
25 8
3
98 16 68
4
88 14 82 69

Sample Output

HAPPY
0
HAPPY
1
SAD
SAD
SAD
HAPPY
0
HAPPY
1

分析：枚举最低点，分别在其两边（从该数开始）找最长上升序列，维护所包含的数目个数的最大值即可。特殊情况是两边至少有一边最长上升序列只包含枚举的数。输出SAD当且仅当一直处于特殊情况。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<set>
#include<algorithm>
#include<map>
#include<climits>
using namespace std;
typedef long long LL;
const int INF = INT_MAX;
int n;
int a[110];
int cal(int id, int sp)
{
   // printf("id = %d  sp = %d\n",id,sp);
    int ans = 0;
    int dp[110] = {0};
    for(int i=id+sp; i>0&&i<=n; i+=sp)
    {
        for(int j=id; sp>0 ? (j<i) : (j>i); j+=sp) {
            //printf("i=%d j=%d\n",i,j);
            if(a[i] > a[j])
            dp[i] = max(dp[i],dp[j]+1),
            ans = max(ans, dp[i]);
        }
    }
    return ans;
}
int main()
{
    int i,j,k,m;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int ans = 1<<20;
        scanf("%d",&n);
        for(i=1; i<=n; i++) scanf("%d",a+i);
        for(i=2; i<n; i++)
        {
            int aa = cal(i,-1);
            int bb = cal(i,1);
            if(aa == 0 || bb == 0) continue;
            ans = min(ans, n-aa-bb-1);
        }
        if(ans != 1<<20) printf("HAPPY\n%d\n",ans);
        else printf("SAD\n");
    }
    return 0;
}


F 组合问题

Description

有N个正整数a 1,a 2,a 3,...,a N，从中选出若干个数，使其之和等于S，这样的选择组合有多少种？

Input

有多组测试数据（不超过100组）。每组测试数据的第一行有两个整数N和S，第二行有n个整数a1,a2,a3,...,aN。(1<=N<=40,1<=ai,S<=10^16) 

Output

每行一个答案。

Sample Input

5 3
1 1 1 1 1
5 4
1 1 1 1 1
5 5
1 1 1 1 1
30 20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 3
2 2
10 9
4 1 8 3 9 3 8 7 8 6
36 53
5 31 9 30 34 48 28 34 38 8 3 21 42 50 38 38 15 38 16 12 23 37 31 15 53 18 25 1 37 27 5 32 2 32 15 4
10 8269629821015715
1653925964203143 826962982101571 1653925964203144 1653925964203143 1653925964203143 1653925964203144 1653925964203144 1653925964203143 826962982101572 1653925964203143

Sample Output

10
5
1
30045015
0
6
1038
6
分析：记忆化搜索，WW（id, val, num）表示在前id个数中选择的数的和为val，到目标状态（前n个数中选择数的和为s）的种数为num。

           预处理rear[i]表示a[i]+a[i+1]+......a[n]

           剪枝1：rear[id+1] + val < s  ，即后面的数全选还是小

           剪枝2：val > s ，   即已经大于s

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
struct WW {
    int id;
    LL val, num;
    WW(int id=0, LL val=0, LL num=0) : id(id), val(val), num(num) {}
    bool operator < (const WW&cmp) const
    {
        return id<cmp.id || id==cmp.id&&val<cmp.val;
    }
};
set<WW>st;
int n;
LL s;
LL a[50];
LL rear[50];
LL DFS(int id, LL val)
{
    if(val > s) return 0;
    if(rear[id+1]+val < s) return 0;
    if(id == n)
    {
        if(val == s) return 1;
        return 0;
    }
    if(st.count(WW(id,val)))
    {
        return (*st.find(WW(id,val))).num;
    }
    else {
        LL tp = 0;
        tp+=DFS(id+1,val);
        tp+=DFS(id+1,val+a[id+1]);
        st.insert(WW(id,val,tp));
        return tp;
    }
}
int main()
{
    int i,j,k,m;
    while(scanf("%d %lld",&n,&s) == 2)
    {
        st.clear();
        for(i=1; i<=n; i++) scanf("%lld",a+i);
        rear[n+1] = 0;
        for(i=n; i>=1; i--)
            rear[i] = rear[i+1] + a[i];
        printf("%lld\n",DFS(0,0));
    }
    return 0;
}


G Xyang learning Data Structure

Description

中南大学第九届大学生程序设计竞赛网络预选赛
      This term, Xyang has learned the “Lowest common ancestor” inData Structure course.
      In graph theory and computer science, the lowest common ancestor (LCA) of two nodes v and w in a tree or directed acyclic graph (DAG) is the lowest (i.e. deepest) node that has both v and w as descendants, where we define each node to be a descendant of itself (so if v has a direct connection from w, w is the lowest common ancestor). The LCA of v and w in T is the shared ancestor of v and w that is located farthest from the root. Computation of lowest common ancestors may be useful, for instance, as part of a procedure for determining the distance between pairs of nodes in a tree: the distance from v tow can be computed as the distance from the root to v, plus the distance from the root to w, minus twice the distance from the root to their lowest common ancestor (Djidjev, Pantziou & Zaroliagis 1991). In ontologies, the lowest common ancestor is also known as the least common subsumer.                    
      In a tree data structure where each node points to its parent, the lowest common ancestor can be easily determined by finding the first intersection of the paths fromv and w to the root. In general, the computational time required for this algorithm is O(h) whereh is the height of the tree (length of longest path from a leaf to the root). However, there exist several algorithms for processing trees so that lowest common ancestors may be found more quickly. Tarjan's off-line lowest common ancestors algorithm, for example, preprocesses a tree in linear time to provide constant-time LCA queries. In general DAGs, similar algorithms exist, but with super-linear complexity.     ------------from Wikipedia
       Now , Xyang is thinking about a new question : If I tell you the lowest common ancestor of every two nodes, can you build the tree?

Input
      There are several test cases, in each test case, there is one number N(1<=N<=500). The next N lines each contains N numbers. The j-th number in the i-th line is the lowest common ancestor of i and j. It’s guaranteed that the j-th number in the i-th line and the i-th number in the j-th line are the same. It’s also guaranteed that the input data descriptions a correct rooted tree.

Output

      For each test case, output N numbers which are the parents of nodes from 1 to N. The root’s parent is 0.

Sample Input

3
1 2 2
2 2 2
2 2 3
5
1 1 1 1 5
1 2 4 4 5
1 4 3 4 5
1 4 4 4 5
5 5 5 5 5

Sample Output

2
0
2
5
4
4
1
0
题意：给一个n*n矩阵，a[i][j]表示i结点和j结点的最近公共祖先。求此树，输出每个结点 的父亲结点，根节点的父亲为0.。

分析：i是j的父亲当且仅当 ： a[i][j] = i ，并且 对于任意k(k!=i,j)，如果a[k][j]==k,  那么a[k][i]!=i，即 i是j的祖先并且j->i路径上再无第三者。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<set>
#include<algorithm>
#include<map>
#include<climits>
using namespace std;
typedef long long LL;
const int INF = INT_MAX;
int a[501][501];
int main()
{
    int i,j,k,m,n;
    while(scanf("%d",&n) == 1)
    {
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
            scanf("%d",a[i]+j);
        for(i=1; i<=n; i++)
        {
            bool ook = false;
            for(j=1; j<=n; j++)
            {
                if(i!=j && a[i][j] == j)
                {
                    bool ok = true;
                    for(k=1; k<=n; k++)
                        if(k!=i&&k!=j && a[i][k]==k && a[k][j]==j)
                        ok = false;
                    if(ok) printf("%d\n",j), ook = true;
                }
            }
            if(!ook) puts("0");
        }
    }
    return 0;
}

H Xyang学习《信息论与编码》

Description

      学完《信息论与编码》这门课后，Xyang终于明白了“单义可译码”的概念。
      在现代通信过程中，信息必须经过无失真编码，成为单义可译的码字序列，才能保证解码后得到的信息是准确无误的。
      无失真信源编码必须符合两个条件：其一，信源编码编出的每一种码字Wi（i=1,2,...,q），与信源S发出的每一种不同的符号Si（i=1,2,...,q）一一对应；其二，每一种由N个信源符号组成的信源符号序列（消息），与每一种由对应的N个码字组成的码字序列一一对应。只有这样，才能保证任何一个码字或码字序列，能唯一地翻译成相对应的符号或消息，达到无失真信源编码的目的，具有这种单义可译性的信源编码W：{W1,W2,...,Wq}称为单义可译码。 ------------姜丹《信息论与编码》
      现在Xyang想让你帮他判断信源编码W：{W1,W2,...,Wq}是否是单义可译码。

Input

      包含多组测试数据。每组测试数据第一行是一个整数q（1<=q<=100），接着q行描述信源符号S1,S2,...,Sq所对应的码字W1,W2,...,Wq，每行一个字符串（仅由0和1构成，长度不超过100）。

Output

     对于每组测试数据，如果信源编码W：{W1,W2,...,Wq}是单义可译码，则输出YES，否则输出NO 。

Sample Input

3
0
11
00
4
1
10
100
1000

Sample Output

NO
YES

HINT

      样例一:假如发送端发送了消息“S2S1S3”，接受端收到的码字序列是“11000”，但是这时却存在多种解码方式，“S2S1S3”、“S2S3S1”和“S2S1S1S1”都可能是解码后得到的消息，故不是单义可译码。样例二:满足单义可译码的两个条件。by 0909122215


思考中。。。

标签：

相关文章