526互联

AtCoder Beginner Contest(abc) 309

发布时间 2023-10-26 18:32:47作者: mostimali



B - Rotate

题目大意

给定一个n*n的矩阵, 要求把矩阵的最外围按照顺时针转动一个数据, 输出转动后的矩阵;

解题思路

数据不大, 暴力即可;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;
int n, m;
char g[110][110];
bool f = false;
signed main(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> g[i][j];
        }
    }
    int x = g[1][1];
    for (int i = 1; i < n; i++) g[i][1] = g[i + 1][1];
    for (int i = 1; i < n; i++) g[n][i] = g[n][i+1];
    for (int i = n; i > 1; i--) g[i][n] = g[i - 1][n];
    for (int i = n; i > 1; i--) g[1][i] = g[1][i-1];
    g[1][2] = x;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout<< g[i][j];
        }
        cout << endl;
    }
    return 0;
}



C - Medicine

题目大意

小莫有一个吃药列表, 每个药物有两个参数a, b; 表示从吃a天, 每天吃b个; 给定一个数量k, 问第一次吃药数量小于等于k的的第几天;

解题思路

算是一个比较明显的二分, 需要注意的一点是二分的上限要大于最大的天数, 否则当k=0的时候会输出0, 而正确答案应该是最大天数+1;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 3e5 + 10;
int n, m;
int a[N], b[N];
bool f=false;
bool check(int u) {
    int res=0;
    for (int i = 1; i <= n; i++) {
        if (a[i] >= u) res += b[i];
    }
    if (res <= m) return true;
    else return false;
}
signed main(){
    cin >> n >> m;
    int maxn=0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        maxn=max(maxn,a[i]);
    }
    int l = 1, r = maxn+10;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) {
            r=mid;
            f=true;
        }
        else l = mid + 1;
    }
    if(f) cout<<l;
    else cout<<0;
    return 0;
}



D - Add One Edge

题目大意

现在有n1+n2个节点和m条边, 这些节点被分到节点1和节点n1+n2的两个连通块中, 节点1的连通块有n1个节点, 节点n1+n2的连通块有n2个节点; 现在我们在两个连通块中各找一个节点, 在这两个节点之间连一条边; 问从节点1到节点n1+n2的最短路径(边的个数)的最大值为多少;

解题思路

该题的题面多少有点坑, 很容易把人的思考重心放到该怎么确定两边要连通的点, 但是思考过后才发现一个样; 我们只需要两边各进行一次最短路, 找到两个连通块中的点到各自中心点的距离, 然后找到两边各自距离中心点最远的点, 这两个距离相加后+1就是答案了;

神秘代码

#include<bits/stdc++.h>
//#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 3e5 + 10;
typedef pair<int, int> PII;
int n1,n2, m;
vector<int> v[N];
int d1[N], d2[N];
bool st[N];
int dijkstra(int u,int d[]) {
    int res = 0;
    d[u]=0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({ 0,u });
    while (heap.size()) {
        auto t = heap.top();
        heap.pop();
        int id = t.second;
        res = max(res, d[id]);
        if (st[id]) {
            continue;
        }
        st[id] = true;
        for (int j : v[id]) {
            if (d[j] > d[id] + 1) {
                d[j] = d[id] + 1;
                heap.push({ d[j],j });
            }
        }
    }
    return res;
}
signed main() {
    cin >> n1 >> n2 >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    memset(d1, 0x3f, sizeof d1);
    memset(d2, 0x3f, sizeof d2);
    int a=dijkstra(1,d1);
    int b=dijkstra(n1 + n2,d2);
    cout << a + b + 1;
    return 0;
}



E - Family and Insurance

题目大意

首先给出2~n中每人的父亲是谁(1是辈分最大的), 组成一个家庭族谱; 该家族一共录有m份保险, 每份保险有两个参数a, b; a表示是给谁录的保险, b表示该保险同样可以作用于a往下的b代子孙; 问该家族中一共多少人有保险;

解题思路

保险个数和家族人数都是3e5, 所以我想着每遍历一个保险就去操作一遍家族成员就很费时间的; 所以我想着能不能在遍历保险的时候只打标记, 最后只遍历一次家族成员; 在尝试过后发现是可以的; 我们用一个数组作为标记st[a] = b, 表示成员a上有保险, 并且其子孙b代都可以享用; 打完标记后用bfs遍历家族成员, 遇到有保险的成员就可以把保险传递下去, st[c] = st[a] - 1; 这样就需要遍历一遍家庭成员就可以得到所有有保险的人员个数;

神秘代码

#include<bits/stdc++.h>
//#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 3e5 + 10;
typedef pair<int, int> PII;
int n, m, res;
int p[N];
vector<int> v[N];
int st[N];
void bfs() {
    queue<int> q;
    q.push(1);
    while (q.size()) {
        int t = q.front();
        q.pop();
        if (st[t]) res++;
        for (int x : v[t]) {
            if (st[t]) {
                st[x] = max(st[x],st[t] - 1);
            }
            q.push(x);
        }
    }
}
signed main() {
    cin >> n >> m;
    for (int i = 2; i <= n; i++) {
        cin >> p[i];
        v[p[i]].push_back(i);
    }
    while (m--) {
        int x, y;
        cin >> x >> y;
        st[x] = max(st[x], y+1);
    }
    bfs();
    cout << res;
    return 0;
}



F - Box in Box

题目大意

解题思路

神秘代码