第四天作业

Fishlinsihan · 2025-07-10 21:00:48 · 个人记录

第一题

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
struct node{
    int l,r;
}a[1001000];//记录每个节点的左右节点
int Max=-1,n;
void dfs(int root,int step){
    if(root==0) return;//如果该节点为0（即上它的爸爸没有这个儿子），返回
    Max=max(Max,step);//记录最大值
    dfs(a[root].l,step+1);//搜索它的左儿子
    dfs(a[root].r,step+1);//搜索它的右儿子
}
int main(){
    cin>>n;//输入n
    for(int i=1;i<=n;i++){
        cin>>a[i].l>>a[i].r;//输入该节点的左节点和右节点
    }
    dfs(1,1);//从1号节点，深度为1开始搜索 
    cout<<Max;//输出最大值
    return 0;
}

第二题

#include <iostream>
#include <vector>
using namespace std;
void dfs(int node, vector<vector<int>>& children, vector<int>& subtree_size) {
    for (int child : children[node]) {
        dfs(child, children, subtree_size);
        subtree_size[node] += subtree_size[child];
    }
}
int main() {
    int n;
    cin >> n;
    vector<vector<int>> children(n + 1);
    for (int i = 2; i <= n; ++i) {
        int parent;
        cin >> parent;
        children[parent].push_back(i);
    }
    vector<int> subtree_size(n + 1, 1);
    dfs(1, children, subtree_size);
    for (int i = 1; i <= n; ++i) {
        cout << subtree_size[i] << endl;
    }
    return 0;
}

第三题

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
vector<int> c[maxn];
int weight[maxn];
int sum[maxn];
int n;
void dfs(int node) {
    sum[node] = weight[node];
    for(int i=0; i<c[node].size(); i++) {
        int child = c[node][i];
        dfs(child);
        sum[node] += sum[child];
    }
}
int main() {
    cin >> n;
    for(int i=1; i<=n; i++) {
        int f, w;
        cin >> f >> w;
        weight[i] = w;
        if(f != 0) {
            c[f].push_back(i);
        }
    }
    dfs(1);
    for(int i=1; i<=n; i++) {
        cout << sum[i] << endl;
    }
    return 0;
}

第四题

#include<iostream>
#define ll long long
using namespace std;
void dfs(ll i,ll x,ll n){
    if(x == 1){
        return;
    }
    if(i*i>n){
        if(x>1){
            cout<<x;
        }
        return ;
    }
    while(x%i==0){
        x/=i;
        cout<<i;
    }
    dfs(i+1,x,n);
}
int main(){
    int t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        dfs(2,n,n);
        cout<<endl;
    }
    return 0;
}

第五题

#include<bits/stdc++.h>
using namespace std;
vector <int> g[123456];
bool vis[123456];
int ans,n,d;
void dfs(int now,int dis)
{
    vis[now]=1;
    if(dis==d) return;
    for(int i=0;i<g[now].size();i++)
    {
        if(!vis[g[now][i]])
        {
            dfs(g[now][i],dis+1);
            ans++;
        }
    }
}
int main()
{
    cin>>n>>d;
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1,0);
    cout<<ans;
    return 0;
}

第六题

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<string> maze(n);
    for (int i = 0; i < n; i++) {
        cin >> maze[i];
    }
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    queue<pair<int, int>> q;
    q.push({0, 0});
    visited[0][0] = true;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        if (x == n - 1 && y == m - 1) {
            cout << "Yes" << endl;
            return 0;
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && maze[nx][ny] == '.' && !visited[nx][ny]) {
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

第七题

#include<iostream>
using namespace std;

int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int n, m;
char grid[105][105];

void dfs(int x, int y) {
    grid[x][y] = '.';
    for (int i = 0; i < 8; i++) {
        int xa = x + dx[i];
        int ya = y + dy[i];
        if (xa >= 1 && xa <= n && ya >= 1 && ya <= m && grid[xa][ya] == 'W') {
            dfs(xa, ya);
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> grid[i][j];
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (grid[i][j] == 'W') {
                ans++;
                dfs(i, j);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

第八题

#include<iostream>
using namespace std;
int n,m,t,sx,sy,fx,fy,vis[1000][1000],ans;
int dx[]={0,0,-1,1},dy[]={-1,1,0,0};
void dfs(int x,int y){
    if(x==fx&&y==fy){
        ans++;
        return;
    }
    for(int i=0;i<4;i++){
        int xa=x+dx[i],ya=y+dy[i];
        if(vis[xa][ya]==0&&xa<=n&&xa>0&&ya<=m&&ya>0){
            vis[xa][ya]=1;
            dfs(xa,ya);
            vis[xa][ya]=0;
        }
    }
}
int main(){
    cin>>n>>m>>t>>sx>>sy>>fx>>fy;
    for(int i=0,x,y;i<t;i++){
        cin>>x>>y;
        vis[x][y]=1;
    }
    vis[sx][sy]=1;
    dfs(sx,sy);
    cout<<ans;
    return 0;
}

第九题

#include <iostream>
#include <vector>
using namespace std;
void dfs(int n, int k, vector<int>& path, vector<bool>& used) {
    if (path.size() == k) {
        for (int num : path) {
            cout << num << " ";
        }
        cout << endl;
        return;
    }   
    for (int i = 1; i <= n; ++i) {
        if (!used[i]) {
            used[i] = true;
            path.push_back(i);
            dfs(n, k, path, used);
            path.pop_back();
            used[i] = false;
        }
    }
}
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> path;
    vector<bool> used(n + 1, false);
    dfs(n, k, path, used);
    return 0;
}

第十题

#include <iostream>
using namespace std;

int n, m;
int arr[25]; // 存储当前组合

void dfs(int start, int depth) {
    // 如果已经选择了m个数，输出当前组合
    if (depth == m) {
        for (int i = 0; i < m; i++) {
            cout << arr[i];
            if (i < m - 1) cout << " ";
        }
        cout << endl;
        return;
    }
    // 从start到n枚举下一个数
    for (int i = start; i <= n; i++) {
        arr[depth] = i; // 选择当前数
        dfs(i + 1, depth + 1); // 递归选择下一个数
    }
}

int main() {
    cin >> n >> m; // 输入n和m
    dfs(1, 0); // 从1开始深度优先搜索
    return 0;
}

https://chat.deepseek.com/