# include <iostream>

using namespace std;

void divide(int x){
    if (x <= 2){
        cout << x << " " << 1 << endl;
        return;
    }
    for (int i=2; i <= x / i; i++){ 
        // n中最多只包含一个大于sqrt(n)的因子
        if (x % i == 0){
            // i一定是质数(2到i-1的因子都已除干净)
            int s = 0;
            while(x % i == 0){
                x /= i;
                s++;
            }
            cout << i << " " << s << endl;
        }
    }
    if (x > 1) cout << x << " " << 1 << endl;
    cout << endl;
    return;
}

int main(){
    int n;
    cin >> n;
    while(n--){
        int x;
        cin >>x;
        divide(x);
    }
    return 0;
}

# include <iostream>
# include <cstring>

using namespace std;

const int N = 510;
int g[N][N];
int dist[N];
bool st[N];

int main(){
    int n, m;
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while(m--){
        int x, y, z;
        cin >> x>> y >> z;
        g[x][y] = g[y][x] = min(g[x][y], z);
    }

    int res = 0;
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;  // 1号元素
    for (int i=0; i<n; i++){
        int t = -1;
        for (int j = 1; j <= n; j++){
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }

        if (dist[t] == 0x3f3f3f3f){
            res = 0x3f3f3f3f;
            break;
        }
        st[t] = true;
        res += dist[t];
        for (int j=1; j<=n; j++){
            if (!st[j])
                dist[j] = min(dist[j], g[t][j]);
        }
    }
    if (res == 0x3f3f3f3f) cout << "impossible" << endl;
    else cout << res << endl;
    return 0;
}

1. 维护一个单调减小的栈，若当前柱子高于栈顶的柱子，退栈直到符合单调性；否则加入栈顶。
2. 每次退栈时，累加雨水的体积（每次算一层）。
3. 最后栈是一个单调栈，结束程序即可

# include <iostream>
# include <stack>

using namespace std;

const int N = 100010;
int a[N];

int main(){
    int n, res = 0;
    cin >> n;
    for (int i=0; i<n ; i++) cin >> a[i];

    stack<int> st;
    for (int i=0; i<n; i++){
        while(!st.empty() && a[st.top()] < a[i]){
            int t = st.top();
            st.pop();
            if (!st.empty()){
                int l = i - st.top() - 1;
                int h = min(a[i], a[st.top()]) - a[t];
                res += l * h;
            }
        }
        st.push(i);
    }
    cout << res << endl;
    return 0;
}

01背包2维dp，思路比较清晰。
res数组存方案数，注意base case为1。

# include <iostream>

using namespace std;

const int N = 1010, V = 1010, MOD = 1e9 + 7;
int dp[N][V], res[N][V];
int v[N], w[N];

int main(){
    int n, vol;
    cin >> n >> vol;
    for (int i=0; i<n; i++) cin >> v[i] >> w[i];

    for (int j=0; j <= vol; j++) res[0][j] = 1;
    for (int i=0; i <= n; i++) res[i][0] = 1;

    for(int i=1; i<=n; i++){
        for (int j=1; j <=vol; j++){
            int maxv = dp[i-1][j];
            int t = res[i-1][j];
            if (j - v[i-1] >= 0){
                if (maxv == dp[i-1][j-v[i-1]] + w[i-1]){
                    t = (t + res[i-1][j-v[i-1]]) % MOD;
                }else if (maxv < dp[i-1][j-v[i-1]] + w[i-1]){
                    t = res[i-1][j-v[i-1]];
                    maxv = dp[i-1][j-v[i-1]] + w[i-1];
                }
            }
            res[i][j] = t;
            dp[i][j] = maxv;
        }
    }


    cout << res[n][vol] << endl;
    return 0;

}

思路

为了记录bfs的路径，使用额外的二维数组（每个元素是一个pair）记录当前位置的下一个位置。反方向bfs（从右下到左上）可完成路径的记录。

C++ 代码

#include <iostream>
#include <queue>

using namespace std;

const int N = 1010;

int g[N][N], v[N][N], n;
queue<pair<int, int> > q;
pair<int, int> mem[N][N];

void bfs(){
    int dx[4] = {0, 0, 1, -1}, dy[4] = {-1, 1, 0, 0};
    q.push({n-1, n-1});
    v[n-1][n-1] = 1;
    while(!q.empty()){
        auto t = q.front();
        q.pop();
        if(t.first == 0 && t.second == 0) return;
        for(int i=0; i<4; i++){
            int x = t.first + dx[i], y = t.second + dy[i];
            if(x>=0 && x < n && y>=0 && y < n && g[x][y] == 0 && v[x][y] == 0){
                q.push({x, y});
                v[x][y] = 1;
                mem[x][y] = {t.first, t.second};
            }
        }
    }
    return;    
}

int main(){
    cin >> n;
    for(int i=0; i<n; i++)
        for(int j=0; j< n; j++)
            cin >> g[i][j];

    bfs();

    int x = 0, y = 0;
    while(x < n -1 || y < n - 1){
        cout << x << " " << y << endl;
        int tx = x, ty = y;
        x = mem[tx][ty].first;
        y = mem[tx][ty].second;
    }
    cout << x << " " << y << endl;
}

按行搜索

#include <iostream>

using namespace std;

const int N = 20;
int n;
char mat[N][N];
int col[N], dg1[N], dg2[N];

void dfs(int x){
    if(x == n){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                cout << mat[i][j];
            }
            cout << endl;
        }
        cout << endl;
        return;
    }

    for(int i=0; i<n; i++){
        if(col[i] || dg1[i-x+n] || dg2[i+x]) continue;
        col[i] = 1;
        dg1[i - x + n] = 1;
        dg2[i + x] = 1;
        mat[x][i] = 'Q';
        dfs(x+1);
        col[i] = 0;
        dg1[i-x+n] = 0;
        dg2[i+x] = 0;
        mat[x][i] = '.';
    }
}

int main(){
    cin >> n;

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            mat[i][j] = '.';

    dfs(0);
    return 0;

}

每一个格子搜索

#include <iostream>

using namespace std;

const int N = 20;
int n;
char mat[N][N];
//int col[N], dg1[N], dg2[N];
int row[N], col[N], dg1[N], dg2[N];

void dfs(int x, int s_i, int s_j){
    if(s_i >= n){
        if(x == n){
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    cout << mat[i][j];
                }
                cout << endl;
            }
            cout << endl;
        }
        return;
    }

    dfs(x, s_i+(s_j+1)/n, (s_j+1)%n);
    if(!row[s_i] && !col[s_j] && !dg1[s_j-s_i+n] && !dg2[s_j+s_i]){
        row[s_i] = col[s_j] = dg1[s_j-s_i+n] = dg2[s_j+s_i] = 1;
        mat[s_i][s_j] = 'Q';
        dfs(x+1, s_i+(s_j+1)/n, (s_j+1)%n);
        row[s_i] = col[s_j] = dg1[s_j-s_i+n] = dg2[s_j+s_i] = 0;
        mat[s_i][s_j] = '.';
    }
    return;

}

int main(){
    cin >> n;

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            mat[i][j] = '.';

    dfs(0, 0, 0);
    return 0;

}