ABC343

ABC 题解

题解

发布日期: 2024-03-05

A Wrong Answer

A

题意

给定两个整数A和B，输出0~9之间，不等于A+B的整数

解题思路

直接0~9遍历即可

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 1e6 + 10, inf = 1 << 30;

void solve() {
    int a, b;
    cin >> a >> b;
    int x = a + b;
    for (int i = 0; i < 10; i ++ ) {
        if (i != x) {
            cout << i;
            return ;
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
    //int t; cin >> t; while (t -- ) 
    solve();
    return 0;
}

B Adjacency Matrix

B

题意

简而言之，给定一个二维矩阵，每一行与对应的列值为1的边相连。输出连边即可。

解题思路

每一行的列值为 1 ，代表一条连边。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 1e6 + 10, inf = 1 << 30;

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= n; j ++ ) {
            int x;
            cin >> x;
            if (x) {
                cout << j << " " ;
            }
        }
        cout << endl;
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
    //int t; cin >> t; while (t -- ) 
    solve();
    return 0;
}

C 343

C

题意

给定一个数N，求一个不大于N的满足以下条件的最大数 K：

存在一个正整数 x，使得 $x^3=K$
K 为回文数

解题思路

条件2看不大懂，直接看样例就可以猜出来。。。

N 的范围是1e18，x 的取值为 1e6，直接暴力找就可以。

tips：如果是 q 组询问，那么预处理出结果，存入数组，即可实现 O(1) 查询。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 1e6 + 10, inf = 1 << 30;

bool judge(ll x) {
    string s = to_string(x);
    int n = s.size();
    for (int i = 0; i < n / 2; i ++ ) {
        if (s[i] != s[n - i - 1]) {
            return false;
        }
    }
    return true;
}

void solve() {
    vector<ll> v;
    for (ll i = 0; i <= 1000000; i ++ ) {
        ll x = i * i * i;
        if (judge(x)) {
            v.pb(x);
        }
    } 
    ll n;
    cin >> n;
    for (int i = v.size() - 1; i >= 0; i -- ) {
        if (v[i] <= n) {
            cout << v[i] << endl;
            return ;
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
    //int t; cin >> t; while (t -- ) 
    solve();
    return 0;
}

D Diversity of Scores

D

题意

有 N 名选手，初始积分为0。
给定每一秒分数的变化，需要输出每次变化后，玩家分数中不同的值的数量。

解题思路

用set存储有多少种分数。
用map存储每个分数出现的次数，当次数为0时，就从set中删去。
这样set的size() 就是每次变化后的答案。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 1e6 + 10, inf = 1 << 30;

void solve() {
    int n, m;
    cin >> n >> m;
    map<ll,int> mp;
    set<ll> st;
    vector<ll> a(n + 1);
    st.insert(0);
    mp[0] = n;
    while (m -- ) {
        ll id, count;
        cin >> id >> count;
        ll x = a[id];
        mp[x] -- ;
        if (mp[x] == 0) {
            st.erase(x);
        }
        a[id] += count;
        mp[a[id]] ++ ;
        st.insert(a[id]);
        cout << st.size() << endl;
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
    //int t; cin >> t; while (t -- ) 
    solve();
    return 0;
}

E 7x7x7

E

题意

在一个三维空间内，需要放置三个边长为7的立方体。

需要满足以下条件：

三个立方体相交的体积为 $V_1$
每两个立方体的相交的总体积为$V_2$
三个立方体总和的体积为$V_3$

解题思路

固定一个立方体，使其一个点位于$(0,0,0)$ ，这样只需要找到另两个立方体的位置即可，也就是$14^6$ ，不会超时，所以直接暴力循环即可。
需要注意的是计算相交体积的方法，想一想线段之间的相交怎么求，扩展到三维就可以（我也不是很理解的说）。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 1e6 + 10, inf = 1 << 30;

int f(int a1, int b1, int c1, int a2, int b2, int c2) {
    int ans = 1;
    ans *= max(0, min(a1, a2) + 7 - max(a1, a2));
    ans *= max(0, min(b1, b2) + 7 - max(b1, b2));
    ans *= max(0, min(c1, c2) + 7 - max(c1, c2));
    return ans;
}   

int f(int a1, int b1, int c1, int a2, int b2, int c2, int a3, int b3, int c3) {
    int ans = 1;
    ans *= max(0, min({a1, a2, a3}) + 7 - max({a1, a2, a3}));
    ans *= max(0, min({b1, b2, b3}) + 7 - max({b1, b2, b3}));
    ans *= max(0, min({c1, c2, c3}) + 7 - max({c1, c2, c3}));
    return ans;
}

void solve() {
    int a, b, c; 
    cin >> a >> b >> c;
    for (int a2 = -7; a2 <= 7; a2 ++ ) {
        for (int b2 = -7; b2 <= 7; b2 ++ ) {
            for (int c2 = -7; c2 <= 7; c2 ++ ) {
                for (int a3 = -7; a3 <= 7; a3 ++ ) {
                    for (int b3 = -7; b3 <= 7; b3 ++ ) {
                        for (int c3 = -7; c3 <= 7; c3 ++ ) {
                            int v3 = f(0, 0, 0, a2, b2, c2, a3, b3, c3);
                            int v2 = f(0, 0, 0, a2, b2, c2) + f(0, 0, 0, a3, b3, c3) + 
                                 f(a2, b2, c2, a3, b3, c3) - 3 * v3;
                            int v1 = 3 * 7 * 7 * 7 - v2 * 2 - v3 * 3;
                            if (v1 == a && v2 == b && v3 == c) {
                                cout << "Yes" << endl;
                                cout << "0 0 0 " << a2 << " " << b2 << " " << c2<< " " << a3 << " " << b3 << " " << c3 << endl;
                                return ;
                            }
                        }
                    }
                }
            }
        }
    }
    cout << "No" << endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
    //int t; cin >> t; while (t -- ) 
    solve();
    return 0;
}

F Second Largest Query

F

题意

单点修改，区间查询，很板的线段树

解题思路

总而言之，学过线段树，就可做。只用改pushup的内容即可。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 2e5 + 10, inf = 1 << 30;

struct Node{
    int l, r;
    int m1 = -1, m2 = -2;
    int cnt1 = 0, cnt2 = 0;
}tr[N * 4];

vector<int> w(N);

void pushup(Node &u, Node &l, Node &r) {   
    if (l.m1 == r.m1) {
        u.m1 = l.m1;
        u.cnt1 = l.cnt1 + r.cnt1;
        if (l.m2 == r.m2) {
            u.m2 = l.m2;
            u.cnt2 = l.cnt2 + r.cnt2;
        }
        else if (l.m2 > r.m2) {
            u.m2 = l.m2;
            u.cnt2 = l.cnt2;
        } else {
            u.m2 = r.m2;
            u.cnt2 = r.cnt2;
        }
    } else if (l.m1 > r.m1) {
        u.m1 = l.m1;
        u.cnt1 = l.cnt1;
        if (l.m2 == r.m1) {
            u.m2 = l.m2;
            u.cnt2 = l.cnt2 + r.cnt1;
        }
        else if (l.m2 > r.m1) {
            u.m2 = l.m2;
            u.cnt2 = l.cnt2;
        } else {
            u.m2 = r.m1;
            u.cnt2 = r.cnt1;
        }
    } else {
        u.m1 = r.m1;
        u.cnt1 = r.cnt1;
        if (r.m2 == l.m1) {
            u.m2 = r.m2;
            u.cnt2 = r.cnt2 + l.cnt1;
        }
        else if (r.m2 > l.m1) {
            u.m2 = r.m2;
            u.cnt2 = r.cnt2;
        } else {
            u.m2 = l.m1;
            u.cnt2 = l.cnt1;
        }
    }
} 

void pushup(int u) {
    pushup(tr[u], tr[u << 1], tr[u << 1|1]);
}

void build(int u, int l, int r) {
    tr[u] = {l, r, 0, 0, 0, 0};
    if (l == r) {
        tr[u] = {l, r, w[l], 0, 1, 0};
    }
    else {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1|1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int x, int v) {
    if (tr[u].l == x && tr[u].r == x) {
        tr[u].m1 = v;
    } 
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1|1, x, v);
        pushup(u);
    }
}

Node query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) {
        return tr[u];  
    } 
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid) return query(u << 1, l, r);
        else if (l > mid) return query(u << 1|1, l, r);
        else {
            Node left = query(u << 1, l, r);
            Node right = query(u << 1|1, l, r);
            Node res;
            pushup(res, left, right);
            return res;
        }
    }
}

void solve() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i ++ )  {
        cin >> w[i];
    }
    build(1, 1, n);
    while (q -- ) {
        int op;
        cin >> op;
        if (op == 1) {
            int p, x;
            cin >> p >> x;
            modify(1, p, x);
        } else {
            int l, r;
            cin >> l >> r;
            auto t = query(1, l, r);
            if (t.m2 != 0) {
                cout << t.cnt2 << endl;
            } else {
                cout << 0 << endl;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
    //int t; cin >> t; while (t -- ) 
    solve();
    return 0;
}

han yue

https://ich-liebe.github.io/2024/03/05/ABC343/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 han yue !

ABC 题解

大臣的旅费

2024-03-06 题解

题解

求组合数

2024-03-04 板子

板子

A

题意

解题思路

代码

B

题意

解题思路

代码

C

题意

解题思路

代码

D

题意

解题思路

代码

E

题意

解题思路

代码

F

题意

解题思路

代码

你的赏识是我前进的动力