解题报告

#include <iostream>
#include <unordered_map>
using namespace std;
int main()
{
    int n, x;
    unordered_map<int, int> umap;  // 用于存放质数 i 被包含的数的个数
    cin >> n;
    while (n--)
    {
        cin >> x;
        for (int i = 2; i * i <= x; i++)  // 进行质因数分解
        {
            if (x % i == 0)  // 找到一个质数
            {
                umap[i]++;  // 这个质数被包含的次数加一
                while (x % i == 0)  // 相除
                    x /= i;      // 直至这个数不能被 i 整除
            }
            if (x > 1)  // 再将这个数本身加入 map 中
                umap[x]++;  // 以避免自己本身就是质数
        }
    }
    int res = 1;
    for (auto it = umap.begin(); it != umap.end(); it++)
        res = max(res, it->second);   // 找到被包含次数最多的质数
    cout << res << endl;
    return 0;
}

int candy(vector<int> &ratings)
{
    vector<int> candies(ratings.size(), 0); // 对应下标元素的糖果数
    stack<int> s;                           // 单调递减栈
    for (int i = 0; i < ratings.size(); i++)
    {   // 如果遇到严格单调递减序列，则持续入栈
        if (i + 1 < ratings.size() && ratings[i] > ratings[i + 1])
            s.push(i);
        else
        {   // 非单调递减，则依据前一个人的糖果数进行判断
            if (i < ratings.size() && i - 1 >= 0 && ratings[i] > ratings[i - 1])
                // 如果前一个人存在并且当前严格大于前一个，则 c[i] = c[i-1]+1
                candies[i] = candies[i - 1] + 1;
            else  // 否则不是严格大于（其实是相等），可以只给 1 个
                candies[i] = 1;
            // 对已经压栈的单调序列进行处理
            while (!s.empty())
            {
                int p = s.top();
                s.pop();
                // 如果当前元素的评分为“坡峰”，那么就选择两侧最大糖果+1
                if (p - 1 >= 0 && ratings[p] > ratings[p - 1])
                    candies[p] = max(candies[p + 1], candies[p - 1]) + 1;
                else // 否则对栈中的元素逐个取出，爬坡
                    candies[p] = candies[p + 1] + 1;
            }
        }
    }
    return sum(candies);
}

         1/1
    ______|______
    |           |
   1/2         2/1
 ___|___     ___|___
 |     |     |     |
1/3   3/2   2/3   3/1
...

1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, ...

#include <iostream>
#include <queue>
using namespace std;
struct TreeNode
{
    int p, q;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x, int y) : p(x), q(y), left(NULL), right(NULL) {}
};
TreeNode* buildTree(TreeNode *root, int n)
{
    root = new TreeNode(1, 1);  // 根结点
    queue<TreeNode *> q;    // 队列
    q.push(root);        // 根结点入队
    int i = 0;          // 用于计数
    TreeNode *tmp;
    while (!q.empty())
    {
        tmp = q.front();    // 取出队头的节点
        q.pop();
        TreeNode *left = new TreeNode(tmp->p, tmp->p + tmp->q);
        tmp->left = left;    // 创建左子节点
        q.push(left);
        i++;
        if (i >= n)        // 如果到达索引值
            break;        // 就不再创建
        TreeNode *right = new TreeNode(tmp->p + tmp->q, tmp->q);
        tmp->right = right;    // 创建右子节点
        q.push(right);
        i++;
        if (i >= n)        // 如果到达索引值
            break;        // 就不再创建
    }
    while (!q.empty())
    {
        tmp = q.front();    // 持续出队，直到最后一个元素
        q.pop();
    }
    cout << tmp->p << "/" << tmp->q << endl;  // 输出结果
    return root;
}
int main()
{
    TreeNode* root;
    root = buildTree(root, 3);  // 建树
    destroyTree(root);      // 销毁树
    return 0;
}

#include <iostream>
using namespace std;
const int N = 5000;
int choose(int a, int k)
{
  if (k == 0) return 1;
  if (k == 1) return a;
  if (k == 2) return a * (a - 1) / 2;
}
int main()
{
    int n, maxa = 0x80000000, ans = 0;
    int a[N] = {0}, num[N] = {0};
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        num[a[i]] ++;           // 记录长度为 a[i] 的木棍个数
        maxa = max(a[i], maxa); // 最长的木棍
    }

    for (int i = 2; i <= maxa; i++)  // 边长至少为 2
    {
        if (num[i] >= 2)  // 至少有 2 根长木棍
        {
            int long_stick = choose(num[i], 2);  // 长木棍的方法数，为 n 选 2 的组合数
            for (int j = 1; j <= i / 2; j++)  // 枚举拼接边
            {
                int combine_stick = 0;
                if (j != i - j && num[j] >= 1 && num[i - j] >= 1)  // 如果拼接边不等长
                    combine_stick = num[j] * num[i - j];  // 那么各选其一
                else if (j == i - j && num[j] >= 2)  // 如果拼接边等长
                    combine_stick = choose(num[j], 2);  // 那么选择其中两根
                ans += long_stick * combine_stick;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

void Turn(int m[ROW][COL], int r, int c)
{  // 按下一盏灯, 包含了对周围灯的影响
    m[r][c] = !m[r][c];
    for (int i = 0; i < 4; i++)
    {
        int x = r + dx[i], y = c + dy[i];
        if (x >= 0 && x < ROW && y >= 0 && y < COL)
            m[x][y] = !m[x][y];
    }
}
void PressOneRowOfLights(int puzzle[ROW][COL], int press[ROW][COL], int r)
{  // 按照 press 数组按下某一行的灯
    for (int i = 0; i < COL; i++)
        if (press[r][i] == 1)
            Turn(puzzle, r, i);
}
void ProcessRemainedRows(int puzzle[ROW][COL], int press[ROW][COL])
{  // 处理从第二行开始的剩余行
    for (int i = 1; i < ROW; i++)
        for (int j = 0; j < COL; j++)
            if (puzzle[i - 1][j] == 1)  // 如果上一行出现没灭的灯
            {
                Turn(puzzle, i, j);     // 那么就按下这一行同列的灯, 使上一行的这盏灯熄灭
                press[i][j] = 1;
            }
}
bool EnumerateRow(int puzzle[ROW][COL], int press[ROW][COL], int r)
{
    int k = 2;
    int puzzle_copy[ROW][COL] = {0};
    while (1)
    {
        CopyPuzzle(puzzle, puzzle_copy, ROW, COL);      // 拷贝原始状态
        ResetPress(press, ROW, COL);              // 重置需要按下的矩阵至0, 除第一行外
        PressOneRowOfLights(puzzle_copy, press, r);     // 按下第一行指定要按下的灯
        ProcessRemainedRows(puzzle_copy, press);        // 按下剩余行的灯
        if (IsEntireRowOff(puzzle_copy, ROW - 1)) // 如果最后一行的灯都熄灭了, 那么解决成功
            return true;
        // 将 press 数组的第一行按二进制枚举, 共 64 种状态
        int i;
        for (i = COL - 1; i >= 0 && press[r][i] == k - 1; i--) ;
        if (i == -1)
            break;
        press[r][i]++;
        for (i++; i < COL; i++)
            press[r][i] = 0;
    }
    return false;   // 解决失败, 无解
}

5 6         // 迷宫大小
.....#
S....#
.#....
.#....
...E..    // 迷宫内容
333300012  // 可分配的操作

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int N = 51;
int per[24][4] = {0};
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
pair<int, int> start;
void init_permutation()
{
    int tmp[4] = {0,1,2,3}; bool flag = true; int i = 0;
    do {
        flag = next_permutation(tmp, tmp + 4);
        copy(tmp, tmp + 4, per[i]);
        i++;
    } while (flag);
}
bool can_find(int n, int m, char g[N][N], int pattern, const string &steps)
{
    pair<int, int> cur = start;
    for (int i = 0; i < steps.length(); i++)
    {
        int op = steps[i] - '0';
        int ddx = dx[per[pattern][op]], ddy = dy[per[pattern][op]];
        cur.first += ddx, cur.second += ddy;
        if (cur.first < 0 || cur.first >= n || cur.second < 0 || cur.second >= m || g[cur.first][cur.second] == '#')
            return false;
        if (g[cur.first][cur.second] == 'E')
            return true;
    }
    return false;
}
int get_answer(int n, int m, char g[N][N], string &steps)
{
    int res = 0;
    init_permutation();
    for (int i = 0; i < 24; i++)
    {
        if (can_find(n, m, g, i, steps))
            res++;
    }
    return res;
}
int main()
{
    int t;
    cin >> t;
    char grid[N][N];
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
            {
                cin >> grid[i][j];
                if (grid[i][j] == 'S')
                    start = {i, j};
            }
        string steps;
        cin >> steps;
        int res = get_answer(n, m, grid, steps);
        cout << res << endl;
    }
    return 0;
}

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 8;
int dx[N] = {-2, -2, -1, 1, 2, 2, 1, -1};
int dy[N] = {1, -1, -2, -2, -1, 1, 2, 2};
int row2index(char ch)
{
    return 7 - (ch - '1');
}
int col2index(char ch)
{
    return ch - 'a';
}
struct Pos
{
    int row, col;
    Pos(int r, int c) : row(r), col(c) {}
    Pos(string pos)
    {
        row = row2index(pos.at(1));
        col = col2index(pos.at(0));
    }
};
void vehicle_can_reach(vector<vector<bool>> &m, const Pos &v_pos)
{   // 车可以到达的位置
    for (int i = 0; i < N; i++)
        m[v_pos.row][i] = 1;
    for (int i = 0; i < N; i++)
        m[i][v_pos.col] = 1;
}
void horse_can_reach(vector<vector<bool>> &m, const Pos &h_pos)
{   // 马可以到达的位置
    for (int i = 0; i < N; i++)
    {
        int n_r = h_pos.row + dx[i], n_c = h_pos.col + dy[i];
        if (n_r >= 0 && n_r < N && n_c >= 0 && n_c < N)
            m[h_pos.row + dx[i]][h_pos.col + dy[i]] = 1;
    }
}
bool judge_can_put(vector<vector<bool>> &m, Pos &new_pos, Pos &h_pos, Pos &v_pos)
{   // 判断能否放马
    if (m[new_pos.row][new_pos.col] == 1)
        return false;
    for (int i = 0; i < N; i++)
    {
        int n_r = new_pos.row + dx[i], n_c = new_pos.col + dy[i];
        if ((n_r == h_pos.row && n_c == h_pos.col) ||
      (n_r == v_pos.row && n_c == v_pos.col))
            return false;
    }
    return true;
}
int main()
{
    string horse, vehicle;
    cin >> vehicle >> horse;
    Pos h_pos = Pos(horse);
    Pos v_pos = Pos(vehicle);
    vector<vector<bool>> m(N, vector<bool>(N, 0));
    vehicle_can_reach(m, v_pos);
    horse_can_reach(m, h_pos);
    int count = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
        {
            Pos p = Pos(i, j);
            if (judge_can_put(m, p, h_pos, v_pos))
                count++;
        }
    cout << count - 1 << endl;
    return 0;
}

void Permutation(char a[], int n, int ith)
{
    if (ith == n)      // 没有剩余字母
        Output(a, n);  // 输出序列
    else
    {
        for (int k = ith; k < n; k++)  // 从第 ith 个开始，向后排列
        {
            swap(a[ith], a[k]);         // 交换 k 和 ith 的位置，成为一个新的序列
            Permutation(a, n, ith + 1); // 对剩余的序列继续排列
            swap(a[ith], a[k]);         // 恢复原来的序列
        }
    }
}

def divide_and_conquer(P):
  if P in condition:
    Solve(P)    # 解决小规模的问题
  sub_P_list = divide_P_into_smaller_subinstances(P)  # 分解问题
  for P_i in sub_P_list:
    y_i = divide_and_conquer(P_i)  # 递归去解各子问题
  return merge(y_1, y_2, ..., y_k)  # 将各子问题解合并为原问题解

// 在M中,对以(si,sj)为左上角的，n*n的矩阵，进行操作
void Solve(vector<vector<bool>> &M, int si, int sj, int n)
{
  if (n == 1) return;
  n /= 2;  // 分割矩阵
  // 左上角的处理
  for (int i = si; i < si + len; i++)
    for (int j = sj; j < sj + len; j++)
      M[i][j] = 1;
  // 右上角的递归
  Solve(M, si,     sj + n, n);
  // 左下角的递归
  Solve(M, si + n, sj,     n);
  // 右下角的递归
  Solve(M, si + n, sj + n, n);
}

int qmid(int a, int k)
{
  if (k == 0) return 1;
  int ans = qmid(a, k / 2);  // 分治计算降解后的幂
  if (k % 2 == 0)  // 针对奇偶的判断
    return ans * ans;
  else
    return ans * ans * a;
}

int qmid(int a, int k)
{
  int ans = 1;  // 结果
  while (k)    // 指数连续右移
  {
    if (k & 1)  // 如果当前位为 1，即需要乘上相应的幂
      ans *= a;  // 对结果乘上a^i
    a *= a;    // a^i 变为 a^2i
    k >>= 1;
  }
  return ans;
}

#include <iostream>
using namespace std;
// x, y 为特殊格子位置，sx, sy 为当前处理棋盘的左上角坐标
void chessBoard(int x, int y, int sx, int sy, int size)
{
    if (size == 1)
        return;
    size /= 2;
    if (x - sx < size && y - sy < size)
    { // 左上角，骨牌拐角在右下子棋盘的左上角
        cout << sx + size << " " << sy + size << " " << 1 << endl;
        chessBoard(x, y, sx, sy, size);
        chessBoard(sx + size - 1, sy + size, sx, sy + size, size); // 右上
        chessBoard(sx + size, sy + size - 1, sx + size, sy, size); // 左下
        chessBoard(sx, sy, sx + size, sy + size, size);            // 右下
    }
    else if (x - sx < size && y - sy >= size)
    { // 右上角，骨牌拐角在左下子棋盘的右上角
        cout << sx + size << " " << sy + size - 1 << " " << 2 << endl;
        chessBoard(x, y, sx, sy + size, size);
        chessBoard(sx + size - 1, sy + size - 1, sx, sy, size);    // 左上
        chessBoard(sx + size, sy + size - 1, sx + size, sy, size); // 左下
        chessBoard(sx, sy, sx + size, sy + size, size);            // 右下
    }
    else if (x - sx >= size && y - sy < size)
    { // 左下角，骨牌拐角在右上子棋盘的左下角
        cout << sx + size - 1 << " " << sy + size << " " << 3 << endl;
        chessBoard(x, y, sx + size, sy, size);
        chessBoard(sx + size - 1, sy + size - 1, sx, sy, size);    // 左上
        chessBoard(sx + size - 1, sy + size, sx, sy + size, size); // 右上
        chessBoard(sx, sy, sx + size, sy + size, size);            // 右下
    }
    else if (x - sx >= size && y - sy >= size)
    { // 右下角，骨牌拐角在左上子棋盘的右下角
        cout << sx + size - 1 << " " << sy + size - 1 << " " << 4 << endl;
        chessBoard(x, y, sx + size, sy + size, size);
        chessBoard(sx + size - 1, sy + size - 1, sx, sy, size);    // 左上
        chessBoard(sx + size - 1, sy + size, sx, sy + size, size); // 右上
        chessBoard(sx + size, sy + size - 1, sx + size, sy, size); // 左下
    }
}
int main()
{
    int k, x, y;
    cin >> k >> x >> y;
    chessBoard(x, y, 1, 1, 1 << k);
    return 0;
}