首页 > 其他分享 >AtCoder Beginner Contest(abc) 309

AtCoder Beginner Contest(abc) 309

时间:2023-10-26 18:34:10浏览次数:34  
标签:AtCoder abc 309 int res long st 节点 define




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

题目大意

解题思路

神秘代码


标签:AtCoder,abc,309,int,res,long,st,节点,define
From: https://www.cnblogs.com/mostimali/p/17790080.html

相关文章

  • 76th 2023/10/10 Atcoder 10/8-ARC-T3
    这道题题目很有意思,看上去是很简单明显的计数,但一思考会发现要死很多重复状态因为标记的线很容易让人从一个方框开始思考起,所以很容易带入关于重复考虑的误区观察到线是斜着的,思考影响到的范围若涂上一个格子或左一个格子的右下,则该格子不能填涂左上观察到影响范围是一个个斜......
  • [ABC256E] Takahashi's Anguish
     题目 https://www.luogu.com.cn/problem/AT_abc256_e 图论题,是个环套树发现环上的边要取掉一条(min),其他的不用取https://www.luogu.com.cn/record/131488937......
  • [ABC176F] Brave CHAIN
    [ABC176F]BraveCHAIN洛谷:[ABC176F]BraveCHAINAtcoder:[ABC176F]BraveCHAINProblemhhoppitree有\(3n\)张卡片,其中每张卡片上都写着\(1\simn\)中的一个数,他会重复以下操作\(n-1\)次:将最左侧的\(5\)张牌任意排列,排列后,删去最左侧的\(3\)张牌,如果这三张牌上写......
  • abc205
    B-PermutationCheck16检查给定数组是不是一个排列C-POW63判断\(a^c\)和\(b^c\)谁大(int范围,\(c\ge1\),\(a,b\)可能是负数)c=c%2?1:2,然后特判相等的情况,最后直接做pow比较D-KthExcluded713给定无重复正序数组,多次询问不在数组中的第\(k\)小的正整数......
  • 名人名言_20230901-
    日常学习名人名言,激励自己......
  • CSP20230917-3 梯度求解 题解
    〇、题目太长了懒得写。简单来说就是求对于一个后缀表达式,每个询问给出一个下标和一些值,求以该下标变量为自变量其它变量为常数时的偏导数。一、思路考虑直接对于表达式建出表达式树。建树的过程比较直接:每次栈里面放节点编号,遇到符号就取出当前栈顶两个节点作为子节点。每......
  • AT_abc260_e
    给出 n 对点ai,bi ,在[1,m] 之间取一段区间。当每一对点都有一个点在这个区间内时,这个区间合法。求出不同长度的合法区间分别有多少个。 枚举l, 右边r有个最小值R(l),而(l,j)j>r之后的点都是合法点,后面就是区间加,用差分维护 考虑这个R(l),可以预处理:先......
  • 2023-2024-1 20231309 《计算机基础与程序设计》第四周学习总结
    作业信息这个作业属于哪个课程2023-2024-1-计算机基础与程序设计这个作业要求在哪里2023-2024-1计算机基础与程序设计第四周作业这个作业的目标作业正文2023-2024-120231309《计算机基础与程序设计》第四周学习总结教材学习内容总结本周主要学习了C语言......
  • 洛谷题解 | AT_abc321_c Primes on Interval
    目录题目翻译题目描述输入格式输出格式样例#1样例输入#1样例输出#1样例#2样例输入#2样例输出#2样例#3样例输入#3样例输出#3题目简化题目思路AC代码题目翻译【题目描述】你决定用素数定理来做一个调查.众所周知,素数又被称为质数,其含义就是除了数字一和本身之外不能......
  • [ABC234E] Arithmetic Number 题解
    题目传送门一道枚举题。暴力枚举数字位数、首位、等差数列的公差即可。注意公差的枚举范围,并且需要看看末尾合不合法。顺便提一下,我是用字符串存储枚举的数字的,所以写了一个check函数代替大于号。Code#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;......