1.出现次数最多的数 (100)

给定 n 个正整数,找出其中出现次数最多的数。

输入格式

  • 第一行:一个正整数 n 表示数字的个数。
  • 第二行:包含 n 个整数 s1, s2, ..., sn,相邻的数用空格分隔。

输出格式

  • 输出出现次数最多的数,如果有多个,输出最小的一个。

数据范围

  • 1 <= n <= 1000
  • 1 <= i <= 10000

输入样例:

6
10 1 10 20 30 20

输出样例:

10

题目解析

哈希表, 离散化, 摩尔投票

代码实现

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
const int N = 1e4 + 10;

typedef struct {
    int a, b;
}node;
int n, idx;
node ans[N];
map <int,int> mp;
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    while(n--) {
        int val;
        cin >> val;
        ++mp[val];
    }
    for(auto t : mp) {
        ans[idx].a = t.first, ans[idx].b = t.second;
        ++idx;
    }
    sort(ans, ans + idx + 1, [](const node& a, const node& b) {
        if (a.b == b.b) return a.a < b.a;
        return a.b > b.b;
    });
    cout << ans[0].a;
    return 0;
} 

2.ISBN号码 (100)

每一本正式出版的图书都有一个 ISBN 号码与之对应。

ISBN 码包括 9 位数字、1 位识别码和 3 位分隔符,其规定格式如 x-xxx-xxxxx-x,其中符号 - 是分隔符(键盘上的减号),最后一位是识别码,例如 0-670-82162-4 就是一个标准的ISBN码。

ISBN 码的首位数字表示书籍的出版语言,例如 0 代表英语;第一个分隔符 - 之后的三位数字代表出版社,例如 670 代表维京出版社;第二个分隔之后的五位数字代表该书在出版社的编号;最后一位为识别码。

输入格式

  • 一行字符序列,表示一本书的 ISBN 号码(保证输入符合 ISBN 号码的格式要求)。

输出格式

  • 输出一行,如果输入的 ISBN 号码的识别码正确,输出 Right;否则,按照规定的格式,输出正确的 ISBN 号码(包括分隔符 -)。

输入样例1:

0-670-82162-4

输出样例1:

Right

输入样例2:

0-670-82162-0

输出样例2:

0-670-82162-4

题目分析

模拟

代码实现

#include <iostream>
#include <cstring>
using namespace std;

int idx, res;
string s;
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> s;
    for (auto& ch : s) {
        if (idx == 9) break;
        if (ch != '-') {
            res = (res + (ch - '0') * (++idx)
        }
    }
    if (res == 10) {
        if (*(s.end() - 1) == 'X') {
            cout << "Right";
        }
        else {
            *(s.end() - 1) = 'X';
            cout << s;
        }
    }
    else {
        if (*(s.end() - 1) - '0' == res) {
            cout << "Right";
        }
        else {
            *(s.end() - 1) = res + '0';
            cout << s;
        }
    }
    return 0;
} 

3.最大的矩形 (100)

在横轴上放了 n 个相邻的矩形,每个矩形的宽度是 1,而第 i(1≤i≤n)个矩形的高度是 hi

n 个矩形构成了一个直方图。

输入格式

  • 第一行:一个整数 n,即矩形的数量。
  • 第二行:包含 n 个整数 h1, h2, ..., hn,相邻的数之间由空格分隔。hi 是第 i 个矩形的高度。

输出格式

  • 输出一行,包含一个整数,即给定直方图内的最大矩形的面积。

数据范围

  • 1 <= n <= 1000
  • 1 <= hi <= 40000

输入样例:

6
3 1 6 5 2 3

输出样例:

10

题目分析

ST表, DP, 区间问题

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e3 + 10, M = __lg(N) + 1;

int n, w[N], dp[N][M];
int query(int l, int r) {
    int len = r - l + 1;
    int k = __lg(len);
    return min(dp[l][k], dp[r - (1 << k) + 1][k]);
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> w[i];
    for (int j = 0; (1 << j) <= n; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
            if(!j) dp[i][j] = w[i];
            else dp[i][j] = min(dp[i][j - 1],dp[i + (1 << j) - (1 << (j - 1))][j - 1]);
    int res = 0;
    for (int r = 1; r <= n; ++r) {
        for (int l = 1; l <= r; ++l)
            res = max(res, query(l,r) * (r - l + 1));
    }
    cout << res;
    return 0;
} 

4.有趣的数 (20)

我们把一个数称为有趣的,当且仅当:

  • 它的数字只包含 0, 1, 2, 3,且这四个数字都出现过至少一次。
  • 所有的 0 都出现在所有的 1 之前,而所有的 2 都出现在所有的 3 之前。
  • 最高位数字不为 0。

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

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

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

输入格式

  • 一行,包括一个正整数 n

输出格式

  • 一行,包括 n 位的整数中有趣的数的个数除以 10^9 + 7 的余数。

数据范围

  • 4 <= n <= 1000

输入样例:

4

输出样例:

3

题目分析

呃呃呃,这是一道 组合计数 的问题,但是我数论没怎么学,只好先贴出DFS啦,过段时间回过头来一定AC。

代码实现

#include <iostream>
#include <unordered_set>
#include <cstring>
using namespace std;
const int MOD = 1000000007;

int n, ans;
int flag0 = 0, flag2 = 0;
string s;
unordered_set <string> st;
void dfs() {
    if (s.length() == n) {
        bool flag = 1, bt[4];
        memset(bt, 0, sizeof bt);
        for (auto& ch : s)
            bt[ch - '0'] = 1;
        for (int i = 0; i < 4; ++i)
            flag &= bt[i];
        if (flag && st.find(s) == st.end()) {
            st.insert(s);
            ans = (ans + 1)
        }
        return ;
    }
    for (int i = 0; i < 4; ++i) {
        if (!i) {
            if (!s.length()) continue;
            if (flag0) continue;
            s += '0';
            dfs();
            s.erase(s.end() - 1);
        }
        else if (i == 1) {
            ++flag0;
            s += '1';
            dfs();
            s.erase(s.end() - 1);
            --flag0;
        }
        else if (i == 2) {
            if (flag2) continue; 
            s += '2';
            dfs();
            s.erase(s.end() - 1);
        }
        else if (i == 3) {
            ++flag2;
            s += '3';
            dfs();
            --flag2;
            s.erase(s.end() - 1);
        }
    }
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    dfs();
    cout << ans;
    return 0;
} 

5.I’m stuck!

给定一个 R 行 C 列的地图,地图的每一个方格可能是 #, +, -, |, ., S, T 七个字符中的一个,表示不同的移动规则。玩家初始位置为 S,目标位置为 T。

规则说明:

  • #: 任何时候玩家都不能移动到此方格;
  • +: 玩家到达后,可向上下左右四个方向相邻的非 # 方格移动一格;
  • -: 玩家到达后,可向左右两个方向相邻的非 # 方格移动一格;
  • |: 玩家到达后,可向上下两个方向相邻的非 # 方格移动一格;
  • .: 玩家到达后,只能向下移动一格,若下方为 #,则不能再移动;
  • S: 玩家初始位置,可向四个方向相邻的非 # 方格移动一格;
  • T: 玩家目标位置,可选择完成任务或继续向四个方向相邻的非 # 方格移动一格。

玩家不能移出地图。找出满足两个性质的方格个数:

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

输入格式:

两个整数 R 和 C 表示地图的行和列数。接下来的 R 行每行包含 C 个字符,表示地图格子。地图上有且仅有一个 S 和一个 T。

输出格式:

若初始位置不能到达终点,输出 I'm stuck!;否则,输出满足性质的方格个数。

数据范围:

1 ≤ R, C ≤ 50

输入样例:

5 5
--+-+
..|#.
..|##
S-+-T
####.

输出样例:

2
样例解释:

在地图上用 X 标记出满足性质的方格,地图如下:

--+-+
..|#X
..|##
S-+-T
####X

题目分析

BFS, DFS 但是在CCF官网只得了90分,应该是有什么小细节没有考虑到。

代码实现

#include <iostream>
#include <cstring>
#include <unordered_set>
#include <queue>
#define x first 
#define y second 
using namespace std;
using PII = pair <int,int>;
const int N = 55;

int n, m;
char g[N][N];
queue <PII> pathNode;
unordered_set <int> mp;
PII dir[4] = {{-1,0},{1,0},{0,-1},{0,1}}, str = {-1,-1}, tar = {-1,-1};
int idx(PII node) {return node.x * n + node.y;}
bool check(PII t, PII p, int k, bool st[N][N]) {
    int I = p.x, J = p.y;
    if (I >= 0 && I < n && J >= 0 && J < m && g[I][J] != '#' && !st[I][J]) {
        char ch = g[t.x][t.y];
        if (ch == 'S' || ch == 'T' || ch == '+') return 1;
        if (ch == '-' && (k == 2 || k == 3)) return 1;
        if (ch == '|' && (k == 0 || k == 1)) return 1;
        if (ch == '.' && k == 1) return 1;
    }
    return 0;
}
bool isDirection(PII o) {
    queue <PII> que;
    bool st[N][N];
    memset(st, 0, sizeof st);
    que.push(o);
    st[o.x][o.y] = 1;
    while(que.size()) {
        PII t = que.front(); que.pop();
        for (int k = 0; k < 4; ++k) {
            int I = t.x + dir[k].x, J = t.y + dir[k].y;
            PII p = {I,J};
            if (check(t,p,k,st)) {
                st[I][J] = 1;
                if (p == tar) return 1;
                if(mp.find(idx(p)) == mp.end()) que.push(p);
            }
        }
    }
    mp.insert(idx(o));
    return 0;
}
void accessiable() {
    queue <PII> que;
    bool st[N][N];
    memset(st, 0, sizeof st);
    que.push(str);
    st[str.x][str.y] = 1;
    while(que.size()) {
        PII t = que.front(); que.pop();
        if(t != tar) pathNode.push(t);
        for (int k = 0; k < 4; ++k) {
            int I = t.x + dir[k].x, J = t.y + dir[k].y;
            PII p = {I,J};
            if (check(t,p,k,st)) {
                st[I][J] = 1;
                que.push(p);
            }
        }
    }
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            cin >> g[i][j];
            if (g[i][j] == 'S') str = {i,j};
            if (g[i][j] == 'T') tar = {i,j};
        }
    PII cop = {-1,-1};
    if(str == cop || tar == cop) cout << "I'm stuck!";
    else if (isDirection(str)) {
        accessiable();
        int res = 0;
        while(pathNode.size()) {
            PII t = pathNode.front(); pathNode.pop();
            if (!isDirection(t)) ++res;
        }
        cout << res;
    }
    else cout << "I'm stuck!";
    return 0;
} 

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status