报名第九次CCF认证，是为了能参加第二届的CCSP，做了一下题库里的C\C++模拟，发现真是够水了……

前三题，过于简单，不再赘述，发一下题目和对应答案~~~

出现次数最多的数

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int MAXN = 1010;

int S[MAXN];

int main(int argc, const char * argv[])
{
    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        scanf("%d", S + i);
    }

    sort(S, S + n);

    int res = S[0], times = 1, res_ = S[0], times_ = 1;

    for (int i = 1; i < n; i++)
    {
        if (S[i] == S[i - 1])
        {
            times_++;
        }
        else
        {
            res_ = S[i];
            times_ = 1;
        }
        if (times_ > times)
        {
            res = res_;
            times = times_;
        }
    }

    cout << res << '\n';

    return 0;
}

ISBN号码

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN = 10;
const int MOD = 11;

int ISBN[MAXN];
char X;

int main(int argc, const char * argv[])
{

    scanf("%1d-%1d%1d%1d-%1d%1d%1d%1d%1d-%c",
          ISBN + 0, ISBN + 1, ISBN + 2, ISBN + 3, ISBN + 4, ISBN + 5,
          ISBN + 6, ISBN + 7, ISBN + 8, &X);

    int sum = 0;
    for (int i = 0; i < 9; i++)
    {
        sum += ISBN[i] * (i + 1);
    }
    sum %= MOD;
    int num = X == 'X' ? 10 : X - '0';

    if (num == sum)
    {
        cout << "Right\n";
    }
    else
    {
        cout << ISBN[0] << '-';
        cout << ISBN[1] << ISBN[2] << ISBN[3] << '-';
        cout << ISBN[4] << ISBN[5] << ISBN[6] << ISBN[7] << ISBN[8] << '-';
        if (sum == 10)
        {
            cout << "X\n";
        }
        else
        {
            cout << sum << '\n';
        }
    }

    return 0;
}

最大的矩阵

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN = 1010;

int h[MAXN];

int main(int argc, const char * argv[])
{
    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        scanf("%d", h + i);
    }

    int res = 0;
    for (int i = 0; i < n; i++)
    {
        int j, k;
        for (j = i - 1; j >= 0; j--)
        {
            if (h[j] < h[i])
            {
                j++;
                break;
            }
        }
        if (j == -1)
        {
            j++;
        }
        for (k = i + 1; k < n; k++)
        {
            if (h[k] < h[i])
            {
                k--;
                break;
            }
        }
        if (k == n)
        {
            k--;
        }
        int temp = (k - j + 1) * h[i];
        if (temp > res)
        {
            res = temp;
        }
    }

    cout << res << '\n';

    return 0;
}

有趣的数

遇见这种问题，不用多想，百分之***十就是dp，观察数位之间的关系，寻找状态转移方程，具体的状态转移方程看代码~~~不难理解。

#include <iostream>

using namespace std;

typedef long long ll;

const int MAXN = 1010;
const ll MOD = 1e9 + 7;
const int MAXM = 6;

ll dp[MAXN][MAXM];

int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < MAXM; i++)
    {
        dp[0][i]=0;
    }
    /*6种状态 * 0－－剩013 * 1－－剩13 * 2－－剩01 * 3－－剩3 * 4－－剩1 * 5－－无 */
    for (int i = 1; i <= n; i++)
    {
        int temp = i - 1;
        dp[i][0] = 1;
        dp[i][1] = (dp[temp][0] + dp[temp][1] * 2) % MOD;
        dp[i][2] = (dp[temp][0] + dp[temp][2]) % MOD;
        dp[i][3] = (dp[temp][1] + dp[temp][3] * 2) % MOD;
        dp[i][4] = (dp[temp][1] + dp[temp][2] + dp[temp][4] * 2) % MOD;
        dp[i][5] = (dp[temp][3] + dp[temp][4] + dp[temp][5] * 2) % MOD;
    }

    cout << dp[n][5] << endl;

    return 0;
}

I’m stuck!

这道题是常规的搜索题，思路就是dfs或者bfs，并且需要满足两个条件，而这两个条件我们可以分别先满足，然后把同时满足的计数，一般做法是先正向dfs一遍，然后把所有S能达到的方格再dfs一遍，但是这样的话时间代价太高，不知道会不会超时，比较快捷的解法就是先正向，然后反向，正向十分简单，反向比较难想一些，考到逆向思维，你需要判断是否可以原路折返回去，而这里就需要判断上一步的格子和这一步的格子之间的连通性，代码写起来比较费劲儿，需要考虑很多种情况，具体的还是看代码吧~~~

#include <iostream>
#include <cstring>

using namespace std;

const int MAXR = 55;
const int MAXC = MAXR;
const int dir[4][2] = {
  {-1, 0}, {
  1, 0}, {
  0, -1}, {
  0, 1}};

int R, C;
char map[MAXR][MAXC];
int visS[MAXR][MAXC];
int visT[MAXR][MAXC];
bool flag;

void dfsS(int x, int y)
{
    visS[x][y] = 1;

    switch (map[x][y])
    {
        case '+':
            for (int i = 0; i < 4; i++)
            {
                if (x + dir[i][0] >= 0 && x + dir[i][0] < R &&
                    y + dir[i][1] >= 0 && y + dir[i][1] < C &&
                    map[x + dir[i][0]][y + dir[i][1]] != '#' &&
                    visS[x + dir[i][0]][y + dir[i][1]] == 0)
                {
                    dfsS(x + dir[i][0], y + dir[i][1]);
                }
            }
            break;
        case '-':
            for (int i = 2; i < 4; i++)
            {
                if (x + dir[i][0] >= 0 && x + dir[i][0] < R &&
                    y + dir[i][1] >= 0 && y + dir[i][1] < C &&
                    map[x + dir[i][0]][y + dir[i][1]] != '#' &&
                    visS[x + dir[i][0]][y + dir[i][1]] == 0)
                {
                    dfsS(x + dir[i][0], y + dir[i][1]);
                }
            }
            break;
        case '|':
            for (int i = 0; i < 2; i++)
            {
                if (x + dir[i][0] >= 0 && x + dir[i][0] < R &&
                    y + dir[i][1] >= 0 && y + dir[i][1] < C &&
                    map[x + dir[i][0]][y + dir[i][1]] != '#' &&
                    visS[x + dir[i][0]][y + dir[i][1]] == 0)
                {
                    dfsS(x + dir[i][0], y + dir[i][1]);
                }
            }
            break;
        case '.':
            if (x + 1 < R && map[x + 1][y] != '#' && visS[x + 1][y] == 0)
            {
                dfsS(x + 1, y);
            }
            break;
    }
}

void dfsT(int x, int y, int preX, int preY)
{
    if (visT[x][y] || map[x][y] == '#')
    {
        return ;
    }

    if (map[x][y] == '.' && preX == x + 1 && preY == y)
    {
        visT[x][y] = 1;
    }
    else if (map[x][y] == '-' && preX == x)
    {
        visT[x][y] = 1;
    }
    else if (map[x][y] == '|' && preY == y)
    {
        visT[x][y] = 1;
    }
    else if (map[x][y] == '+')
    {
        visT[x][y] = 1;
    }

    if (visT[x][y] == 0)
    {
        return ;
    }

    if (x - 1 >= 0)
    {
        dfsT(x - 1, y, x, y);
    }
    if (x + 1 < R)
    {
        dfsT(x + 1, y, x, y);
    }
    if (y - 1 >= 0)
    {
        dfsT(x, y - 1, x, y);
    }
    if (y + 1 < C)
    {
        dfsT(x, y + 1, x, y);
    }
}

int main(int argc, const char * argv[])
{
    memset(visS, 0, sizeof(visS));
    memset(visT, 0, sizeof(visT));

    cin >> R >> C;

    int xS = 0, xT = 0, yS = 0, yT = 0;
    for (int i = 0; i < R; i++)
    {
        scanf("%s", map[i]);
        for (int j = 0; j < C; j++)
        {
            if (map[i][j] == 'S')
            {
                xS = i;
                yS = j;
                map[i][j] = '+';
            }
            else if (map[i][j] == 'T')
            {
                xT = i;
                yT = j;
                map[i][j] = '+';
            }
        }
    }

    dfsS(xS, yS);

    if (visS[xT][yT] == 0)
    {
        cout << "I'm stuck!\n";
        return 0;
    }

    dfsT(xT, yT, xT, yT);

    int counts = 0;

    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            if (map[i][j] != 'S' && map[i][j] != 'T' &&
                visS[i][j]  && !visT[i][j])
            {
                counts++;
            }
        }
    }

    std::cout << counts << '\n';

    return 0;
}

前三题就是秀智商的问题，不算笨的人30分钟内就能搞定前三题，拿到300分，第四题、第五题需要略微思考些，就算拿不全分，也不至于0分~~~