HRBUST2023新生赛题解

A.Two Rectangles @ Hrbust Online Judge

定位:本场签到，但是由于题面是英文，所以没有人写

题意:给定两张可区分的矩形牌，你需要把这两张牌完全放在一个矩形棋盘里(卡牌可以重合,但是不能旋转)。输出恰好能覆盖整个棋盘的方案数.

通过观察容易发现,能恰好覆盖棋盘的情况只有两种:

1. 有一张卡牌能够直接覆盖整个棋盘,剩下一张卡牌可以随便放.
2. 两张卡牌的长度和棋盘长度相等,宽度加起来可以覆盖棋盘.此时两张卡牌并排放可以覆盖棋盘,并且将两张卡牌交换可以视作另一种方案.方案数为2.对称的情况同理,即卡牌宽度和棋盘宽度相等

其他情况输出0

/*
 * @author: yihang_01
 * @Date: 2023-11-14 13:38:32
 * @LastEditTime: 2023-11-22 23:34:41
 * QwQ 加油加油
 */
#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int mod = 1e9 + 7;
int H, W, h1, h2, w1, w2;
void solve() {
    cin >> H >> W >> h1 >> w1 >> h2 >> w2;
    if (H > W) {
        swap(H, W);
        swap(h1, w1);
        swap(h2, w2);
    }
    if (h1 == H && w1 == W) {
        cout << (H - h2 + 1) * (W - w2 + 1) % mod << '\n';
    } else if (h2 == H && w2 == W) {
        cout << (H - h1 + 1) * (W - w1 + 1) % mod << '\n';
    } else if (h1 == h2 && h1 == H) {
        if (w1 + w2 < W) {
            cout << 0 << '\n';
            return;
        } else {
            cout << 2 << '\n';
            return;
        }
    } else if (w1 == w2 && w1 == W) {
        if (h1 + h2 < H) {
            cout << 0 << '\n';
            return;
        } else {
            cout << 2 << '\n';
            return;
        }
    } else
        cout << 0 << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    // system("pause");
    return 0;
}

B.爱学算法的小H @ Hrbust Online Judge

ICPC原题改编，缩小了数据范围，暴力dfs能过

统计完所有算法难度的个数之后，枚举所有难度的学习顺序，即枚举全排列，然后一旦无法将下一个难度学习进今天的日程里，就放到下一天。

/*
 * @author: yihang_01
 * @Date: 2023-11-21 18:58:58
 * @LastEditTime: 2023-11-23 19:28:17
 * QwQ 加油加油
 */
#include <bits/stdc++.h>
using namespace std;

int w, n, b[20], x, ans, cnt, f[20], sum;

void dfs(int num, int cnt, int ans) {
    // if(ans>::ans)   return;
    ++sum;
    if (cnt == ::cnt) {
        ::ans = min(::ans, ans);
        return;
    }
    for (int i = 10; b[i]; i--) {
        if (!f[i]) {
            f[i] = 1;
            if (num + b[i] <= w)
                dfs(num + b[i], cnt + 1, ans);
            else
                dfs(b[i], cnt + 1, ans + 1);
            f[i] = 0;
        }
    }
}

void solve() {
    memset(b, 0, sizeof(b));
    memset(f, 0, sizeof(f));
    cnt = 0;
    cin >> n >> w;
    for (int i = 1; i <= n; i++) {
        cin >> x, b[x]++, cnt += b[x] == 1;
    }
    sort(b + 1, b + 11);
    ans = INT_MAX;
    f[10] = 1;
    dfs(b[10], 1, 1);
    cout << ans << '\n';
    // cout << sum << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    // system("pause");
    return 0;
}

C.好心的小林同学 @ Hrbust Online Judge

签到题，对于长度更短的那个数，只需要在后面补0即可，由于数据范围不超过longlong的长度，所以不需要使用字符串模拟，只需要用longlong存储，加0只需要乘10就可以了。

/*
 * @author: yihang_01
 * @Date: 2023-11-23 16:51:20
 * @LastEditTime: 2023-11-23 23:09:43
 * QwQ 加油加油
 */
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a,b;

void solve(){
    cin>>a>>b;
    if(a>b) swap(a,b);
    auto len=[&](int x){
        int cnt=0;
        while(x)    x/=10,++cnt;
        return cnt;
    };
    while(len(a)<len(b))    a*=10;
    cout<<a+b<<'\n';
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    int T=1;
    cin>>T;
    while(T--){  solve();  }
    //system("pause");
    return 0;
}

D.王金刚走迷宫 @ Hrbust Online Judge

第一种解法：二分+dfs，二分枚举答案，然后用dfs来check是否有某条路径中的最大值不超过mid即可

第二种解法：二分+bfs枚举所有路径，查看是否有路径中能到达终点经过的最大点即可

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

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 100 + 10;

int g[N][N];
int n, m;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
bool st[N][N];

bool check(int val, int x, int y) {
    st[x][y] = true;
    bool res = false;
    for (int i = 0; i < 4; i ++ ) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
        if (st[nx][ny]) continue;
        res |= check(val, nx, ny);
    }
    return res;
}

void solve() {
    int x, y;
    cin >> n >> m >> x >> y;
    int max_val = 0;
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            cin >> g[i][j];
            max_val = max(max_val, g[i][j]);
        }
    }

    int l = 0, r = max_val;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid, x, y)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }

    cout << l << endl;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;
    cin >> T;
    while (T --) {
        solve();
    }
    return 0;
}

E.《是男人就下100层》 @ Hrbust Online Judge

模板题改编，缩小了数据范围，使得dfs暴力可以跑过，从最上面的点开始dfs，每次递归调用(x + 1, y - 1), (x + 1, y), (x + 1, y + 1)，当递归到第n层之后，返回这块板子的值，每次。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[60][60];
int ned[60];
int n, m;

int dfs(int i, int j) {
    if ((ned[i] != 0) && (ned[i] != j)) return -1;
    if (i == n) return a[i][j];

    int val1 = (j != 1) ? dfs(i + 1, j - 1) : -1;
    int val2 = dfs(i + 1, j);
    int val3 = dfs(i + 1, j + 1);

    if ((val1 == -1) && (val2 == -1) && (val3 == -1)) {
        return -1;
    } else {
        return max({val1, val2, val3}) + a[i][j];
    }
}

void solve() {
    memset(a, 0, sizeof(a));
    memset(ned, 0, sizeof(ned));
    int tmp1, tmp2;
    bool errflag = false;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++) cin >> a[i][j];
    for (int i = 1; i <= m; i++) {
        cin >> tmp1 >> tmp2;
        if ((ned[tmp1] != 0) && (tmp2 != ned[tmp1])) {
            errflag = 1;
        } else {
            ned[tmp1] = tmp2;
        }
    }
    cout << (errflag ? -1 : dfs(1, 1)) << endl;
}

signed main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}

最好的解法是使用动态规划来实现，加上滚动数组优化后可以解决1e4的数据量

/*
 * @author: yihang_01
 * @Date: 2023-11-22 21:09:44
 * @LastEditTime: 2023-11-23 11:40:28
 * QwQ 加油加油
 */
#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[30][30][11], a[30][30], f[30][30], n, m, k, v,h[30];

void solve() {
    memset(h,0,sizeof(h));
    memset(f, 0, sizeof(f));
    memset(dp, 0xf3, sizeof(dp));
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) cin >> a[i][j];
    }
    int cnt = 0;
    for (int i = 1; i <= m; i++) {
        cin >> k >> v;
        if (!f[k][v]) f[k][v] = 1, ++cnt,h[k]++;
    }
    for(int i=n-1;i>=1;i--)  h[i]+=h[i+1];
    for (int i = 1; i <= n; i++) {
        if (f[n][i])
            dp[n][i][1] = a[n][i];
        else
            dp[n][i][0] = a[n][i];
    }
    for (int i = n - 1; i; i--) {
        for (int j = 1; j <= i; j++) {
            if(f[i][j]){
                if(j==1)    dp[i][j][h[i]]=max({dp[i][j][h[i]],dp[i+1][j][h[i]-1]+a[i][j],dp[i+1][j+1][h[i]-1]+a[i][j]});
                else    dp[i][j][h[i]]=max({dp[i][j][h[i]],dp[i+1][j-1][h[i]-1]+a[i][j],dp[i+1][j][h[i]-1]+a[i][j],dp[i+1][j+1][h[i]-1]+a[i][j]});
            }
            else{
                if(j==1)    dp[i][j][h[i]]=max({dp[i][j][h[i]],dp[i+1][j][h[i]]+a[i][j],dp[i+1][j+1][h[i]]+a[i][j]});
                else    dp[i][j][h[i]]=max({dp[i][j][h[i]],dp[i+1][j-1][h[i]]+a[i][j],dp[i+1][j][h[i]]+a[i][j],dp[i+1][j+1][h[i]]+a[i][j]});
            }
        }
    }
    cout << (dp[1][1][cnt] > 0 ? dp[1][1][cnt] : -1) << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    // system("pause");
    return 0;
}

F.幸运点 @ Hrbust Online Judge

直接遍历一遍整棵数，判断父亲节点和子节点的插值是不是k就行了

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

#define endl '\n'

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 1e5 + 10;
int n, k;
vector<int> g[N];
int a[N], ans;

void dfs(int u, int fa) {
    for (auto v : g[u]) {
        if (v == fa) continue;
        if (a[u] - a[v] == k || a[v] - a[u] == k) ans ++;
        dfs(v, u);
    }
}

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i ++ ) g[i].clear();
    for (int i = 1; i < n; i ++ ) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

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

    ans = 0;
    dfs(1, -1);
    cout << ans << endl;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;
    cin >> T;
    while (T --) {
        solve();
    }
    return 0;
}

G.落在南京的衣服 @ Hrbust Online Judge

模板题，分别以s、t为起点，跑两边dijkstra，然后对于每个点，取一个最大值即可（因为两个人可以同时出发，所以是取最大值）

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

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 1e5 + 10;

struct Edge {
    int to, w;
};
vector<Edge> g[2][N];
int dist[2][N];
bool st[N];

void dijkstra(vector<Edge> g[], int dist[], int n, int s) {
    priority_queue<PII, vector<PII>, greater<PII> > q;
    q.push({0, s});
    memset(dist, 0x3f, N * sizeof(int));
    memset(st, 0, sizeof(st));
    dist[s] = 0;
    while (q.size()) {
        PII t = q.top(); q.pop();
        int u = t.second;
        if (st[u]) continue;
        st[u] = true;
        for (auto e : g[u]) {
            int v = e.to, w = e.w;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                q.push({dist[v], v});
            }
        }
    }
}

void solve() {
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= n; i ++ ) g[0][i].clear(), g[1][i].clear();
    while (m --) {
        int a, b, c, d;
        cin >> a >>b >> c >> d;
        g[0][a].push_back({b, c});
        g[0][b].push_back({a, c});
        g[1][a].push_back({b, d});
        g[1][b].push_back({a, d});
    }

    dijkstra(g[0], dist[0], n, s);
    dijkstra(g[1], dist[1], n, t);

    int ans = 0x3f3f3f3f;
    for (int i = 1; i <= n; i ++ ) {
        ans = min(ans, max(dist[0][i], dist[1][i]));
    }

    cout << ans << endl;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;
    // freopen("cloth.in", "r", stdin);
    cin >> T;
    while (T --) {
        solve();
    }
    return 0;
}

H.Multiset @ Hrbust Online Judge

读题意，发现题目中的集合就长下图这样

这样可以贡献1的答案

而当一个节点周围连了好多个节点时，就可以以图中的橙色点为中心，选择与它相连的任意两个点，组成题意中的集合

即橙色点的度为cnt，那它的贡献就是$cnt*(cnt - 1) / 2$

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

#define endl '\n'

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 2e5 + 10;

int d[N];

void solve() {
    int n;
    cin >> n;
    memset(d, 0, sizeof(int) * (n + 1));
    for (int i = 1; i < n; i ++ ) {
        int a, b;
        cin >> a >> b;
        d[a] ++;
        d[b] ++;
    }
    long long ans = 0;
    for (int i = 1; i <= n; i ++ ) {
        if (d[i] >= 2) ans += (LL) d[i] * (d[i] - 1) / 2;
    }
    cout << ans << endl;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;
    cin >> T;
    while (T --) {
        solve();
    }
    return 0;
}