cspccf备考

13年12月CCF计算机软件能力认证

3192. 出现次数最多的数

给定 $n$ 个正整数，找出它们中出现次数最多的数。
如果这样的数有多个，请输出其中最小的一个。

输入格式

输入的第一行只有一个正整数 $n$ ,表示数字的个数。
输入的第二行有 $n$ 个整数 $s_1,s_2,\ldots,s_n$ 。
相邻的数用空格分隔。

输出格式

输出这 $n$ 个次数中出现次数最多的数。
如果这样的数有多个，输出其中最小的一个。

数据范围

$\begin{aligned}&1\leq n\leq1000,\\&1\leq s_i\leq10000\end{aligned}$

输入样例：

6
10110203020

输出样例：

}

数组模拟

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int c[N];
int n;
int mx = 1e5 + 10, cnt;

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    while (n -- )
    {
        int x;
        cin >> x;
        c[x] ++;
        if(c[x] > cnt)
        {
            cnt = c[x];
            mx = x;
        }
        if(c[x] == cnt && x < mx)
            mx = x;
    }
    cout << mx << endl;
    return 0;
}

Map

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int mx = N, cnt;
int n;
map<int, int> mp;

int main()
{
    cin >> n;
    while (n -- )
    {
        int x;
        cin >> x;
        mp[x] ++;
        if(mp[x] > cnt)
        {
            cnt = mp[x];
            mx = x;
        }
        if(mp[x] == cnt && x < mx)
            mx = x;
    }
    cout << mx << endl;
    return 0;
}

每一本正式出版的图书都有一个 ISBN 号码与之对应。
ISBN 码包括9位数字、1位识别码和3位分隔符，其规定格式如 x-xxx-xxxxx-x ,其中符号 - 是分隔符 (键盘上的减号),最后一位是识别码，例如 0-670-82162-4 就是一个标准的ISBN码。
ISBN 码的首位数字表示书籍的出版语言，例如0代表英语；第一个分隔符 - 之后的三位数字代表出版社，例如670代表维京出版社；第二个分隔之后的五位数字代表该书在出版社的编号；最后一位为识别码。
识别码的计算方法如下：
首位数字乘以1加上次位数字乘以2…以此类推，用所得的结果mod 11,所得的余数即为识别码，如果余数为 10,则识别码为大写字母 $X .$
例如ISBN 号码 0-670-82162-4 中的识别码4是这样得到的：对067082162这 9 个数字，从左至右，分别乘以
$1,2,\ldots,9$ ,再求和，即 $0\times1+6\times2+\ldots\ldots+2\times9=158$ ,然后取158 mod 11的结果 4 作为识别码。
编写程序判断输入的 ISBN 号码中识别码是否正确，如果正确，则仅输出 Right;如果错误，则输出是正确的ISBN 号码。
输入格式
输入只有一行，是一个字符序列，表示一本书的 ISBN 号码 (保证输入符合 ISBN 号码的格式要求)。
输出格式
输出一行，假如输入的ISBN 号码的识别码正确，那么输出 Right,否则，按照规定的格式，输出正确的 ISBN号码(包括分隔符 -)。
输入样例1：

0-670-82162-4

输出样例1：

Right

输入样例2：

0-670-82162-0

输出样例2：

0-670-82162-4

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); i ++)
        if(s[i] == '-')
            s.erase(i, 1);

    int res = 0;
    for(int i = 0; i < s.size() - 1; i ++)
        res += (s[i] - '0') * (i + 1);
    
    int m = res % 11;
    if(m == s[s.size() - 1] - '0')
        cout << "Right" << endl;
    else if(m == 10 && s[s.size() - 1] == 'X')
        cout << "Right" << endl;
    else
    {
        for(int i = 0; i < s.size() - 1; i ++)
        {
            cout << s[i];
            if(i == 0 || i == 3 || i == 8)
                cout << '-';
        }
        if(m == 10)
            cout << 'X';
        else
            cout << m;            
    }
    return 0;
}

3194. 最大的矩形

在横轴上放了 $n$ 个相邻的矩形，每个矩形的宽度是1，而第 $i$ ( $1\leq i\leq n$ )个矩形的高度是 $h_i$ 。
这 $n$ 个矩形构成了一个直方图。
例如，下图中六个矩形的高度就分别是3，1,6,5,2,3.

请找出能放在给定直方图里面积最大的矩形，它的边要与坐标轴平行。对于上面给出的例子，最大矩形如下图所示的阴影部分，面积是10。

输入格式

第一行包含一个整数 $n$ ,即矩形的数量。
第二行包含 $n$ 个整数 $h_1,h_2,\ldots,h_n$ ,相邻的数之间由空格分隔。 $h_i$ 是第 $i$ 个矩形的高度。
输出格式
输出一行，包含一个整数，即给定直方图内的最大矩形的面积。

数据范围

$1\leq n\leq1000$ , $1\leq h_i\leq10000$ 经实测 $h_i$ 在官网的实际范围是 $1\leq h_i\leq40000$ ,这与其给出的题面描述不符，属于官网出题人的失误，也因此卡住了一些同学的代码，望大家加以注意。

输入样例：

6
3 1 6 5 2 3

输出样例：

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int h[N];
int n;
int res;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> h[i];
    
    for(int i = 1; i <= n; i ++)
    {
        int l, r;
        for(int j = i; j >=1; j --)
        {
            if(h[i] > h[j]) break;
            l = j;
        }
        for(int j = i; j <= n; j ++)
        {
            if(h[i] > h[j]) break;
            r = j;
        }
        res = max(res, h[i] * (r - l + 1));
    }
    cout << res << endl;
    return 0;
}

3195. 有趣的数

我们把一个数称为有趣的，当且仅当：

1.它的数字只包含0，1,2,3 ,且这四个数字都出现过至少一次。

2.所有的0都出现在所有的 1 之前，而所有的2都出现在所有的 3 之前。

3.最高位数字不为0。

因此，符合我们定义的最小的有趣的数是 2013

除此以外，4位的有趣的数还有两个：2031 和2301。

请计算恰好有 $n$ 位的有趣的数的个数。

由于答案可能非常大，只需要输出答案除以 $10^9+7$ 的余数。

输入格式

输入只有一行，包括恰好一个正整数 $n$ 。

输出格式

输出只有一行，包括恰好 $n$ 位的整数中有趣的数的个数除以 $10^9+7$ 的余数。

数据范围
$4\leq n\leq1000$
输入样例：

输出样例：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1010, mod = 1e9 + 7;
int n, c[N][N];
LL res;

int main()
{
    cin >> n;
    for(int i = 0; i <= n; i ++)
        for(int j = 0; j <= i; j ++)
            if(!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    
    for(int k = 2; k <= n - 2; k ++)
        res = (res + (LL)c[n - 1][k] * (k - 1) * (n - k - 1)) % mod;
    
    cout << res << endl;
    return 0;
}

3196. I’m stuck!

给定一个 $R$ 行 $C$ 列的地图，地图的每一个方格可能是 #,+,-,1,.,s,T 七个字符中的一个，分别表

示如下意思：

$\#:$ 任何时候玩家都不能移动到此方格；
· + :当玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非 # 方格移动一格；
· - :当玩家到达这一方格后，下一步可以向左右两个方向相邻的一个非 # 方格移动一格； · |!当玩家到达这一方格后，下一步可以向上下两个方向相邻的一个非 # 方格移动一格； ····当玩家到达这一方格后，下一步只能向下移动一格。如果下面相邻的方格为 #,则玩家不能再移动；
· S:玩家的初始位置，地图中只会有一个初始位置。玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非#方格移动一格；

· T:玩家的目标位置，地图中只会有一个目标位置。玩家到达这一方格后，可以选择完成任务，也可以选择不完成任务继续移动。如果继续移动下一步可以向上下左右四个方向相邻的任意一个非 # 方格移动一格。

此外，玩家不能移动出地图。

请找出满足下面两个性质的方格个数：

玩家可以从初始位置移动到此方格； 2.玩家不可以从此方格移动到目标位置。

输入格式

输入的第一行包括两个整数 $R$ 和 $C$ ,分别表示地图的行和列数
接下来的 $R$ 行每行都包含 $C$ 个字符。它们表示地图的格子。地图上恰好有一个 s 和一个 T。
输出格式
如果玩家在初始位置就已经不能到达终点了，就输出 I’m stuck! 。
否则的话，输出满足性质的方格的个数。

数据范围
$1\leq R,C\leq50$
输入样例：

–±+

$\ldots|_{\#}.$

$\ldots|_{\#\#}$

$s - + - T$

$\#\#\#\#.$

输出样例：

样例解释

如果把满足性质的方格在地图上用 x 标记出来的话，地图如下所示：

–±+

$\ldots|\#X$

$\ldots|_{\#\#}$

$S - + - T$

$\#\#\#\#X$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 55;
int n, m;
int st1[N][N], st2[N][N];
char g[N][N];
int tx, ty;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0 , -1};
int res;

bool check(int x, int y, int k)
{
    char c = g[x][y];
    if(c == '+' || c == 'S' || c == 'T') return true;
    if(c == '|' && k % 2 == 0) return true;
    if(c == '-' && k % 2 == 1) return true;
    if(c == '.' && k == 2) return true;
    return false;
}

void dfs1(int x, int y)
{
    st1[x][y] = true;
    for(int i = 0; i < 4; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(a < 0 || a >= n || b < 0 || b >= m || g[a][b] == '#' || st1[a][b]) continue;
        if(check(x, y, i))
            dfs1(a, b);
    }
}

void dfs2(int x, int y)
{
    st2[x][y] = true;
    for(int i = 0; i < 4; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(a < 0 || a >= n || b < 0 || b >= m || g[a][b] == '#' || st2[a][b]) continue;
        if(check(a, b, i ^ 2))
            dfs2(a, b);
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++) cin >> g[i];
    
    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < m; j ++)
        {
            if(g[i][j] == 'S') dfs1(i, j);
            else if(g[i][j] == 'T')
            {
                tx = i, ty = j;
                dfs2(i, j);
            }
        }
    }
    
    if(!st1[tx][ty])
        cout << "I'm stuck!" << endl;
    else
    {
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < m; j ++)
                if(st1[i][j] && !st2[i][j])
                    res ++;
        cout << res << endl;
    }
    return 0;
}

第一次CCF计算机软件能力认证

3197. 相反数

输入格式

有 $N$ 个非零且各不相同的整数。
请你编一个程序求出它们中有多少对相反数( $a$ 和 $- a$ 为一对相反数)。
第一行包含一个正整数 $N$ 。
第二行为 $N$ 个用单个空格隔开的非零整数，每个数的绝对值不超过1000，保证这些整数各不相同。
输出格式
只输出一个整数，即这 $N$ 个数中包含多少对相反数。

数据范围
$1\leq N\leq500$
输入样例：

123-1-2

输出样例：

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
set<int> s;
bool st[N];
int n;
int cnt;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        int x;
        cin >> x;
        s.insert(x);
        if(s.count(-x) && !st[abs(x)])
        {
            st[abs(x)] = true;
            cnt ++;
        }
    }
    cout << cnt << endl;
    return 0;
}