育华周赛 第十五期

本期题目深入思考一下的话,挺简单

题解

T1

基础计算题，不做分析

#include<bits/stdc++.h>
using namespace std;

int main() {
    int x, y, t;
    cin >> x >> y >> t;
    cout << (t * x * y) / (y - x);
    return 0;
}

T2

二维数组操作基本功

#include<bits/stdc++.h>
using namespace std;

// g数组用于存储方阵元素，tot用于给方阵元素赋值，f数组充当临时数组
int g[510][510], tot, f[510][510];

int main() {
    int n, m;
    // 输入方阵大小n和操作次数m
    scanf("%d %d", &n, &m);

    // 初始化方阵，按从左到右、从上到下的顺序给元素赋值
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            g[i][j] = ++tot;
        }
    }

    // 进行m次旋转操作
    for (int i = 1; i <= m; i++) {
        int a, b, r, opt;
        // 输入旋转中心坐标(a, b)、旋转方阵的半径r和旋转方向opt
        scanf("%d %d %d %d", &a, &b, &r, &opt);

        if (opt == 0) {
            // 顺时针旋转
            // 把g数组元素复制到临时数组f中进行旋转
            for (int i = a - r; i <= a + r; i++) {
                for (int j = b - r; j <= b + r; j++) {
                    f[a - b + j][a + b - i] = g[i][j];
                }
            }
            // 把临时数组f中的元素复制回g数组
            for (int i = a - r; i <= a + r; i++) {
                for (int j = b - r; j <= b + r; j++) {
                    g[i][j] = f[i][j];
                }
            }
        } else {
            // 逆时针旋转
            // 把g数组元素复制到临时数组f中进行旋转
            for (int i = a - r; i <= a + r; i++) {
                for (int j = b - r; j <= b + r; j++) {
                    f[a + b - j][b - a + i] = g[i][j];
                }
            }
            // 把临时数组f中的元素复制回g数组
            for (int i = a - r; i <= a + r; i++) {
                for (int j = b - r; j <= b + r; j++) {
                    g[i][j] = f[i][j];
                }
            }
        }
    }

    // 输出最终的方阵
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%d ", g[i][j]);
        }
        printf("\n");
    }

    return 0;
}

T3

一道典型的bfs题目，用字符串来表示举证，用hash表来表示某种状态是否出现过。

#include <bits/stdc++.h>
using namespace std;
string t="123456789";
map<string,int> h;
void bfs()
{
    queue<string> q;
    q.push(t);
    h[t]=1;
    while(q.size())
    {
        string u=q.front();
        q.pop();
        string v[4]= {u,u,u,u};
        v[0][0]=u[1],v[0][1]=u[4],v[0][3]=u[0],v[0][4]=u[3]; // 左上角
        v[1][1]=u[2],v[1][2]=u[5],v[1][4]=u[1],v[1][5]=u[4]; // 右上角
        v[2][3]=u[4],v[2][4]=u[7],v[2][6]=u[3],v[2][7]=u[6]; // 左下角
        v[3][4]=u[5],v[3][5]=u[8],v[3][7]=u[4],v[3][8]=u[7]; // 右下角
        // 注意这是一个逆推的过程，要逆时针转
        for(int i=0; i<4; i++)
            if(!h[v[i]])
            {
                h[v[i]]=h[u]+1;
                if(v[i]==t) break;
                q.push(v[i]);
            }
    }
}

int main()
{
    int _=1;
    scanf("%d",&_);
    bfs(); // 从终点开始预找出所有可能结果的步数
    while(_--)
    {
        string s;
        for(int i=0; i<9; i++)
        {
            char c;
            scanf(" %c",&c);
            s+=c;
        }
        printf("%d\n",h[s]-1);
    }
    return 0;
}

T4

#include <bits/stdc++.h>
using namespace std;

int findn(long long n) {

    // 表示1位数 有9个 从1开始
    // 表示2位数 有90个 从10开始
    // 表示3位数 有900个 从100开始
    // 依此类推
    long long digit = 1, count = 9, start = 1;
    // 确定n所在的数字位数
    while (n > digit * count) {
        n -= digit * count;
        digit++;
        count *= 10;
        start *= 10;
    }
    // 计算具体的数字和位置
    long long num = start + (n - 1) / digit;
    int pos = (n - 1) % digit;
    // 提取第pos位的数字
    for (int i = 0; i < digit - 1 - pos; i++) {
        num /= 10;
    }
    return num % 10;
}

int main() {
    long long n;
    cin >> n;
    cout << findn(n) << endl;
    return 0;
}

T5

离线做法，倒推思路

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

struct Node {
    int l, r;
    long long v;
};

int a[N];
int q[N];
Node b[N];

long long ans[N];


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

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= n; i++) {
        cin >> q[i];
    }

    long long nmax = 0;
    for (int i = N; i >= 1; i--) {
        int pos = q[i];

        Node res = {pos, pos, a[pos]};
        if (b[pos - 1].l != 0) {
            res.l = b[pos - 1].l;
            res.v += b[pos - 1].v;
        }
        if (b[pos + 1].r != 0) {
            res.r = b[pos + 1].r;
            res.v += b[pos + 1].v;
        }

        b[res.l] = res;
        b[res.r] = res;

        nmax = max(res.v, nmax);
        ans[i - 1] = nmax;
    }

    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " ";
    }

    return 0;
}

T6

一道简单的树形DP， 首先思考如何设计状态， 考虑到他是通过边来同时开关边上的两个灯，节点又存在父子关系，所以关灯的状态有两种，和子节点一起关或者和父节点一起关。 状态表达如下

$f_{i,j} =\begin{cases} \text{子节点一起关的最少操作次数} & \text{当 } j = 0 \\ \text{开着的最少操作次数} & \text{当 } j = 1 \\ \text{和父节点一起关的最少操作次数} & \text{当 } j = 2 \end{cases}$

状态转移方程为：

$dp[u][0]=\sum_{v\in\text{children}(u)}\min(dp[v][0], dp[v][1])+\min_{v\in\text{children}(u)}(dp[v][2] - \min(dp[v][0], dp[v][1]))$

解释：

• 首先，$\sum_{v\in\text{children}(u)}\min(dp[v][0], dp[v][1])$ 表示将所有子节点的最小代价（子节点关闭或开启的最小代价）累加起来。
• 然后，$\min_{v\in\text{children}(u)}(dp[v][2] - \min(dp[v][0], dp[v][1]))$ 用于保证至少有一个子节点处于开启状态，通过调整一个子节点从开启状态（dp[v][2]）转换为关闭状态（min(dp[v][0], dp[v][1])）的最小额外代价。

$dp[u][1]=\sum_{v\in\text{children}(u)}dp[v][0]$

解释：当节点 u 开启时，所有子节点都关闭，所以将所有子节点处于关闭状态的代价 dp[v][0] 累加起来。

$dp[u][2]=\sum_{v\in\text{children}(u)}\min(dp[v][0], dp[v][1]) + 1$

解释：

• $\sum_{v\in\text{children}(u)}\min(dp[v][0], dp[v][1])$ 表示将所有子节点的最小代价（子节点关闭或开启的最小代价）累加起来。
• 最后加 1 表示关闭节点 u 本身需要的代价。

#include<bits/stdc++.h>
using namespace std;
vector<long long> adj[100010];
long long dp[100010][3];

void dfs(long long u, long long p) {
    if (adj[u].size() == 1) {
        dp[u][0] = 1e9;
        dp[u][1] = 0;
        dp[u][2] = 1;
        return;
    }

    long long mim2 = 1e18;
    for (int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if (v != p) {
            dfs(v, u);
            mim2 = min(mim2, dp[v][2] - min(dp[v][0], dp[v][1]));
            dp[u][0] += min(dp[v][0], dp[v][1]);
            dp[u][1] += dp[v][0];
            dp[u][2] += min(dp[v][0], dp[v][1]);
        }
    }
    dp[u][0] += mim2;
    dp[u][2] += 1;
}

int main() {
    long long n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        long long u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    adj[1].push_back(0);
    dfs(1, 0);
    cout << min(dp[1][0], dp[1][1]) << endl;


    // for (int i = 1; i <= n; i++) {
    //     cout <<i <<" : "<< dp[i][0] << " " << dp[i][1] << " " << dp[i][2] << endl;
    // }
    return 0;
}