首页 > 其他分享 >AtCoder Beginner Contest 348

AtCoder Beginner Contest 348

时间:2024-04-12 12:55:07浏览次数:28  
标签:AtCoder cout Beginner int res IOS cin 348 define




B - Farthest Point

难度: ⭐

题目大意

一个坐标系有x个点, 对于每个点找出距离其最远的点;

解题思路

数据很小, 暴力就行;

神秘代码

#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 = 2e5 + 10, mod = 998244353, inf = 1e18;
typedef pair<int, int> PII;
int n, m, k;
PII p[N];
signed main(){
    IOS;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> p[i].first >> p[i].second;
    }
    for(int i = 1; i <= n; i++){
        int maxn = 0, pos = i;
        for(int j = n; j >= 1; j--){
            if(i == j) continue;
            int dis = (p[i].first - p[j].first) * (p[i].first - p[j].first) + (p[j].second - p[i].second) * (p[j].second - p[i].second);
            if(dis >= maxn){
                maxn = dis;
                pos = j;
            }
        }
        cout << pos << endl;
    }
	return 0;
}




C - Colorful Beans

难度: ⭐⭐

题目大意

现在有若干个分组, 每个分组里都有若干个数值; 找出所有分组的最小值中的最大值;

解题思路

也是打暴力;

神秘代码

#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 = 2e5 + 10, mod = 998244353, inf = 1e18;
typedef pair<int, int> PII;
int n, m, k;
map<int, int> mp;
signed main(){
    IOS;
    cin >> n;
    for(int i = 1; i <= n; i++){
        int a, b;
        cin >> a >> b;
        mp[b] = mp[b] ? min(mp[b], a) : a;
    }
    int res = 0;
    for(auto t : mp){
        res = max(res, t.second);
    }
    cout << res;
	return 0;
}




D - Medicines on Grid

难度: ⭐⭐⭐

题目大意

给定一个网格, 确定起点和终点; 网络中某些位置是障碍物; 小莫从起点开始出发, 每上下左右走一步都会消耗一个能量, 初始的能量为0; 网格中的某些位置可以补充能量, 形式为(x, y, a)在(x, y)位置可以将小莫的能量补充a; 每个位置的补充只能用一次;

解题思路

因为能量的补充形式是补充到a, 并非补充a; 所以我们可以贪心地想只要到达(x, y)时自身的能量小于a, 那么直接使用就可以了; 而bfs时, 记录经过每个格子时的最大能量, 当重复到达某个格子时, 只有当此时能量大于之前记录的该格子的最大值才可以重复走;

神秘代码

#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 = 2e5 + 10, mod = 998244353, inf = 1e18;
typedef pair<int, int> PII;
int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
int n, m, k;
int sx, sy, ex, ey;
char g[250][250];
int st[250][250], eng[250][250];
bool est[250][250];
struct node{
    int x, y, e;
};
int idx = 0;
bool bfs(){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            st[i][j] = -1;
        }
    }
    queue<node> q;
    if(!eng[sx][sy]) return false;
    q.push({sx, sy, eng[sx][sy]});
    st[sx][sy] = eng[sx][sy];
    while(q.size()){
        node t = q.front();
        q.pop();
        if(t.x == ex && t.y == ey) return true;
        if(!t.e) continue;
        for(int i = 0; i < 4; i++){
            int x = t.x + dx[i], y = t.y + dy[i];
            if(x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] != '#'){
                int e = t.e - 1;
                if(eng[x][y] && !est[x][y]){
                    if(eng[x][y] > e){
                        e = eng[x][y];
                        est[x][y] = true;
                    }
                }
                if(e > st[x][y]){
                    st[x][y] = e;
                    q.push({x, y, e});
                }
            }
        }
    }
    return false;
}
signed main(){
    IOS;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> g[i][j];
            if(g[i][j] == 'S'){
                sx = i, sy = j;
            }
            else if(g[i][j] == 'T'){
                ex = i, ey = j;
            }
        }
    }
    cin >> k;
    for(int i = 1; i <= k; i++){
        int a, b, c;
        cin >> a >> b >> c;
        eng[a][b] = c;
    }
    if(bfs()){
        cout << "Yes";
    }
    else cout << "No";
	return 0;
}




E - Minimize Sum of Distances

难度: ⭐⭐⭐⭐

题目大意

给定一个长的为n的数值C; 现在有一颗节点个数为n的树; 设函数d(a, b)表示节点a和b之间最短路径的边数; 设 $\displaystyle f(x) = \sum_{i=1}^{N} (C_i \times d(x, i))$. 找到$\displaystyle \min_{1 \leq v \leq N} f(v)$.

解题思路

题解说这个是换根dp, 当时是纯当是图论做的, 不过思路和换根dp基本一致; 因为数据范围是1e5, 所以肯定没法暴力; 考虑O(n)的做法就只能考虑相邻两个节点之间转换时f(x)的变化规律; 我们设p[u]表示为以u为根节点的子树中所有Ci的和, len[x]表示节点x到此时目标节点之间边的个数; 设节点v是u的子节点之一, 我们需要用f(u)来求f(v); 转移后, 以v为根节点的子树中的点的len[i]都会减一, 其对f(v)的影响就是f(u) - p[v]; 相应的, 除了该子树中的点, 其他点的len[i]都会加一, 这个其他点包括两部分, 一是节点u的其他子节点的子树, 可以用p[u] - p[v]表示; 二是节点u之前的那些节点, 这个在dfs时用个变量保存一下, 比如ls; 那么最终f(v) = f(u) + (p[u] - p[v]) + ls - p[v];

神秘代码

#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 = 2e5 + 10, mod = 998244353, inf = 1e18;
typedef pair<int, int> PII;
int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
int n, m, res;
int l, r;
vector<int> v[N];
int p[N], f[N];
int ini(int u, int fa, int num){
    int sum = 0;
    for(int x : v[u]){
        if(x == fa) continue;
        r += p[x];
        res += p[x] * num;
        f[u] += ini(x, u, num + 1);
    }
    return f[u];
}
void solve(int u, int fa, int ls){
    for(int x : v[u]){
        if(x == fa) continue;
        res = min(res, res + ls + f[u] - f[x] - f[x]);
        solve(x, u, ls + f[u] - f[x]);
    }
}
signed main(){
    IOS;
    cin >> n;
    for(int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i = 1; i <= n; i++){
        cin >> p[i];
        f[i] = p[i];
    }
    ini(1, -1, 1);
    solve(1, -1, 0);
    cout << res;
	return 0;
}




F - Oddly Similar

难度: ⭐⭐⭐⭐

题目大意

现在有N个长度为M的数组, 对于两个数组, 如果他们在某一位置的数相同, 并且这样的数的个数是奇数个, 那么这两个数组被称为相似的; 请判断有多少对这样的(i, j)数组相似; 1 <= i < j <= M

解题思路

本题的暴力解法是O(n * n * m), 肯定会超时; 题解是用了bitset来进行优化, 用bitset可以快64倍, 也就是差不多1e7的水平; 开一个bitset的二维数组f[i][j]表示第i列数值为j的情况; 因为bitset可以看作是一个01字符串, 所以f[i][j][k] = 1表示第k行第i列的值为j; 也就是说, f[i][j]表示所有行在第i列的情况;
所以我们可以遍历所有行i, 对于每行我们遍历其每一列j, 并且逐列进行异或操作, 最终如果bitset中1的个数即为其第i行相似的行的个数; 又因为题目要求(i, j)中i < j; 所以我们可以先异或再赋值, 可以最后就不用去重了;

神秘代码

#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 = 2e3 + 10, mod = 998244353, inf = 1e18;
typedef pair<int, int> PII;
int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
int n, m, res;
int p[N][N];
bitset<N> x, f[N][N];
signed main(){
    IOS;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> p[i][j];
        }
    }
    for(int i = 0; i < n; i++){
        x.reset();
        for(int j = 0; j < m; j++){
            x ^= f[j][p[i][j]];
            f[j][p[i][j]][i] = 1;
        }
        res += x.count();
    }
    cout << res;
	return 0;
}

标签:AtCoder,cout,Beginner,int,res,IOS,cin,348,define
From: https://www.cnblogs.com/mostimali/p/18130943

相关文章

  • ABC348G Max(Sum-Max)
    将\(b\)升序排序考虑问题,那么最大值就是下标最大的\(b_i\)。下文的\(a_i,b_i\)都是排序过后的。考虑\(k\)固定怎么做:枚举\(b_i\)作为最大值,那么最大值为\(b_i\)时的答案最大值为此时\(a\)的前\(i\)项的前\(k\)大值的和减去\(b_i\)。将每次计算的结果取max即......
  • [ABC348] Atcoder ABC 248 A~G 题解
    [ABC348]AtcoderABC248A~G题解A模拟B模拟,不卡精度。C模拟D注意,药不可以拿着,只可以在那个格子吃掉。这就意味着,我们无论何时到达某个点,到达的点的集合都是固定的。所以对于每个药店跑BFS,然后看起点到终点是否连通即可。intn,m,k,ad[N][N],f[N][N],in[N][N],......
  • AtCoder Beginner Contest 348 A-F 题解
    A-PenaltyKickQuestion高桥将在一场足球比赛中获得\(N\)个点球。对于第\(i\)个罚球,如果\(i\)是\(3\)的倍数,他将罚球失败,否则罚球成功。请打印他罚球的结果。Solution当\(i\%3==0\)时说明能被\(3\)整除Code#include<bits/stdc++.h>usingnamespacest......
  • AtCoder Beginner Contest 348
    地址。赛时情况A、B题都很显然,C题大概推了好一会儿,最后还是做出来了。D题感觉十分难做,估计很难写,看了E。感觉还是不会,听说是原题,搜了一下,发现是树的重心,我还不会。直接贺题解,发现不对。修改了一下还是不对,最后发现INF取小了,过了。后面的不看了。赛后总结还行,跳过D......
  • AT_abc348_e 的题解
    (一)感觉D>E。考虑换根DP,把节点\(1\)当作一开始的根节点。先搜一遍,把\(f(1)\)算出。当将计算的节点从父结点往子节点转移时,每个节点到计算的节点的距离要么\(-1\)要么\(+1\),取决于是否在子节点的子树内。可以提前处理字数内\(C\)的值的和,来计算\(f\)的变化量。(二)......
  • ABC348G题解
    令\(f_i\)为当\(k=i\)时的答案。令\(g_i\)为\(f_i+\max\limits_{j\inS}b_j\)。也就是不减去\(b\)的最大值的结果。直接做是\(O(n^2)\)的,考虑分治,令两个子问题的\(f,g\)分别为\(fl,gl\)和\(fr,gr\)。合并的时候做一个\[f_i=\max(\max\limits_{c+d=i}(gl_c+fr......
  • AtCoder Beginner Contest 204
    E-RushHour2设函数f(t)=t+ci+di/(t+1);易得当t=sqrt(di)-1时取最小所以根据时间来做dij当时间大于sqrt(di)-1时直接加入即可同时用并查集来查看1和n是否联通即可accode:点击查看代码#include<bits/stdc++.h>#defineintlonglong#defineall(x)x.begin(),x.end()......
  • AtCoder Beginner Contest 348
    A-PenaltyKick(abc348A)题目大意给定\(n\),输出\(ooxooxoox...\),长度为\(n\)。解题思路按题意模拟即可。神奇的代码n=int(input())ans="oox"*(n//3)+"o"*(n%3)print(ans)B-FarthestPoint(abc348B)题目大意给定\(n\)个点,对每个点,求出与其......
  • ABC348F 题解
    一些注意点:一看到这种题就应该往bitset的方向想。如果用bitset,就应该跳脱之前的思维,尝试从最朴素的暴力重新想起。看到这道题,发现直接做非常的不可做的样子,考虑bitset。我们可以先枚举左端点\(l\)。这样,当我们枚举\(j\)时,对于所有的\(k\)使得\(a_{k,j}=a_......
  • AISing Programming Contest 2021(AtCoder Beginner Contest 202)
    D-aabababaa根据题意从左往右进行分析如果当前该字母为a那么存在两种情况一种为b的数量为0一种为剩余的k的数量小于右边所有情况的总和其总和对应为C(剩余的长度,b的个数)反之则为b点击查看代码intget(intx,inty){intans=1;for(inti=1;i<=y;i++){ans=(x-i......