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

AtCoder Beginner Contest 351

时间：2024-04-28 22:23:03浏览次数：34  
标签：AtCoder Beginner int res sum back long 351 define



B - Spot the Difference

难度: ⭐

题目大意

给定两个矩阵, 找不同

解题思路

数据很小, 暴力就行;

神秘代码

#include<bits/stdc++.h>
#define int unsigned long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 1e6 + 10, mod = 998244353, inf = 131;
typedef pair<int, int> PII;
int n, m;
char g1[110][110], g2[110][110];
signed main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> g1[i][j];
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> g2[i][j];
            if(g2[i][j] != g1[i][j]){
                cout << i << ' ' << j;
            }
        }
    }
	return 0;
}



C - Merge the balls

难度: ⭐⭐

题目大意

现在有一个空序列, 进行n次操作; 每次操作会把一个数字球x放到序列右端, 然后开始检查: 如果最右边的球和次右边的球数字相同, 那么就可以取出这两个球, 并新加入一个数字球为(2 * x); 并且加入后可以继续检查; 最后输出序列中还有几个球

解题思路

用一个堆来维护一下就行;

神秘代码

#include<bits/stdc++.h>
#define int unsigned long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 1e6 + 10, mod = 998244353, inf = 131;
typedef pair<int, int> PII;
int n, m;
vector<int> v;
signed main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        v.push_back(x);
        while(v.size() > 1){
            int a = v.back();
            v.pop_back();
            int b = v.back();
            v.pop_back();
            if(a == b){
                v.push_back(a + 1);
            }
            else{
                v.push_back(b);
                v.push_back(a);
                break;
            }
        }
    }
    cout << v.size();
	return 0;
}



D - Jump Distance Sum

难度: ⭐⭐⭐

题目大意

现有一个n * n的网格, 其中有若干个磁铁; 小莫身穿铁衣在网格中行走, 当他走到与磁铁相邻的位置(上下左右)时便会无法移动; 定义坐标(x, y)的自由度: 即从(x, y)为起点, 所能到达的网格数(包括起点);

解题思路

根据题意, 因为到达磁铁相邻位置时便无法移动, 可以理解是遇到了空气墙; 所以可以看成是磁铁和空气墙把整个网格分成了连通块, 题目问的就是格子数量最多的连通块的格子数; 我们可以对格子进行染色; 其中比较特殊的是, 磁铁相邻的位置是可以被归属于多个连通块的, 所以可以被染成多种颜色, 而其他的空格子在被染上颜色后就不能再被染成别的颜色了, 当然, 既然已经被染上颜色, 那么其他颜色的格子也不会遍历到他, 所以不用担心;

神秘代码

#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 = 1e3 + 10, mod = 998244353, inf = 131;
typedef pair<int, int> PII;
int n, m, idx;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
char g[N][N];
bool _is[N][N];
int p[N][N];
int num[N * N];
void bfs(int a, int b){
    queue<PII> q;
    q.push({a, b});
    p[a][b] = idx;
    while(q.size()){
        PII t = q.front();
        q.pop();
        num[idx]++;
        for(int i = 0; i < 4; i++){
            int x = t.first + dx[i], y = t.second + dy[i];
            if(x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] == '.'){
                if(_is[x][y]){
                    if(p[x][y] != idx){
                        p[x][y] = idx;
                        num[idx]++;
                    }
                }
                else{
                    if(!p[x][y]){
                        q.push({x, y});
                        p[x][y] = idx;
                    }
                }
            }
        }
    }
}
signed main(){
    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] == '#'){
                _is[i - 1][j] = true;
                _is[i + 1][j] = true;
                _is[i][j - 1] = true;
                _is[i][j + 1] = true;
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(p[i][j] == 0 && g[i][j] == '.' && !_is[i][j]){
                idx++;
                bfs(i, j);
            }
        }
    }
    int res = 1;
    for(int i = 1; i <= idx; i++) res = max(res, num[i]);
    cout << res;
	return 0;
}



E - Jump Distance Sum

难度: ⭐⭐⭐⭐

题目大意

在一个平面上有n个物品Pi, 给定他们的坐标; 小莫每次可以从(x, y)移动到(x + 1, y + 1)或(x + 1, y - 1)或(x - 1, y + 1)或(x - 1, y - 1); 定义两个物品A, B之间距离dist(A, B)为小莫从A到B所需要的移动次数; 如果无法到达就定为0;
计算 $\displaystyle\sum_{i=1}{N-1}\displaystyle\sum_{j=i+1}N \text{dist}(P_i, P_j)$.

解题思路

因为斜着走不好处理, 那么我们可以把坐标系进行旋转45°, 让小莫的移动方向变为上下左右; 同时旋转后根据数学公式, 我们可以把原坐标(x, y)改为现坐标(x + y, x - y), 并且小莫移动的步幅变为2, 这样就和之前的图等效了, 但是因为当前步幅为2, 所以最后结果要除以2;
这样我们就是把任意两点之间的曼哈顿距离进行求和, 暴力是O(n2); 但是曼哈顿距离我们可以通过把x和y分开来处理; 以x为例: 处理时先从小到大进行排序, 对于其中第i个xi, 因为只有前i - 1个坐标会到达xi, 所以xi对答案的贡献就是(i - 1) * xi - sum; sum即为前i - 1个x的和;
另外还需要判断是否可以到达, 通过观察可以发现, 对于坐标(x1, y1)和(x2, y2), 如果x1 + y1和x2 + y2对2取余相同, 那么他们就可以相互到达; 所以我们可以把所有坐标分成两拨来处理;

神秘代码

#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 = 4e5 + 10, mod = 998244353, inf = 131;
typedef pair<int, int> PII;
int n, m, idx;
struct node{
    int x, y;
}p[N];
vector<int> X[2], Y[2];
int check(vector<int> &v){
    sort(v.begin(), v.end());
    int sum = 0;
    int res = 0;
    if(v.size()) sum = v[0];
    for(int i = 1; i < v.size(); i++){
        res = res + i * v[i] - sum;
        sum += v[i];
    }
    return res;
}
signed main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        int a, b;
        cin >> a >> b;
        p[i] = {a + b, a - b};
        if((a + b) % 2){
            X[1].push_back(a + b);
            Y[1].push_back(a - b);
        }
        else{
            X[0].push_back(a + b);
            Y[0].push_back(a - b);
        }
    }
    int res = 0;
    for(int i = 0; i <= 1; i++){
        res += check(X[i]);
        res += check(Y[i]);
    }
    cout << res / 2;
    return 0;
}



F - Double Sum

难度: ⭐⭐⭐(⭐)

题目大意

给定一个长度为n的数列A; 计算$\displaystyle \sum_{i=1}^N \sum_{j=i+1}^N \max(A_j - A_i, 0)$, 答案保证小于263;

解题思路

根据题意可以知道, 对于Ai, 我们要求它后面所有比他大的数的和, 暴力是O(n2)的复杂度; 转念一想, 我们新开一个数组P[x]表示数列A中值为x的总和是多少, P[x] = num * x, num为x的数量; 设数列中的最大值是maxn, 求所有比Ai大的数的和, 不就是求P[Ai]到P[maxn]的前缀和吗; 但是用普通的前缀和还是O(n2), 所以可以考虑用树状数组来做, 既然要求它后面所有比他大的数的和, 所以需要逆序来处理; 设num是Ai后面所有比他大的数的个数, sum是后面所有比他大的数的和, 那么Ai对答案的贡献就是sum - num * Ai;
另外因为Ai的范围是1e8, 所以开数组会MLE; 但是n为4e5, 所以可以进行离散化处理;

神秘代码

#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 = 4e5 + 10, mod = 998244353, inf = 131;
typedef pair<int, int> PII;
int n, m, idx;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int p[N], f[N];
int trs[N], trn[N];
map<int, int> mp1, mp2;
int lowbit(int x){
    return x & -x;
}
void add(int x){
    for(int i = x; i <= n; i += lowbit(i)){
        trs[i] += mp2[x];
        trn[i] ++;
    }
}
int sum(int x){
    int res = 0;
    for(int i = x; i > 0; i -= lowbit(i)){
        res += trs[i];
    }
    return res;
}
int num(int x){
    int res = 0;
    for(int i = x; i > 0; i -= lowbit(i)){
        res += trn[i];
    }
    return res;
}
signed main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> p[i];
        f[i] = p[i];
    }
    sort(f + 1, f + 1 + n);
    for(int i = 1; i <= n; i++){
        mp1[f[i]] = i;
        mp2[i] = f[i];
    }
    int res = 0;
    for(int i = n; i >= 1; i--){
        int s1 = sum(n);
        int s2 = sum(mp1[p[i]]);
        int n1 = num(n);
        int n2 = num(mp1[p[i]]);
        res = res + (s1 - s2) - p[i] * (n1 - n2);
        if(p[i]) add(mp1[p[i]]);
    }
    cout << res;
    return 0;
}

标签：AtCoder,Beginner,int,res,sum,back,long,351,define
From： https://www.cnblogs.com/mostimali/p/18164621

相关文章

  • AtCoder-abc351_f讲解
    原题翻译给定一个序列\(A\)，求出：\[\sum\limits_{i=1}^N\sum\limits_{j=i+1}^N\max(A_j-A_i,0)\]答案小于\(2^{63}\)。思路这里提供三种思路（分块经XXR尝试，卡常卡不过）：1权值树状数组将\(A\)离散化，设\(rk_i\)为\(A_i\)离散化后的排名，去重后元素个数为\(M\)。每......
  • AtCoder-abc351_d 题解
    原题翻译题意简述给定\(H\timesW\)的网格图，如果一个字符是#，则不能走到该字符上；如果是.，则可以走到该字符上，但如果它周围\(4\)个格子中有#字符，则不能再继续行走了。自由度是指从一个格子出发，能走到不同格子的数量（可以出发多次）。求出所有格子的最大自由度。思路考虑......
  • AtCoder Beginner Contest 208 E
    E-DigitProducts点击查看代码map<int,int>f[20];voidsolve(){intn,k;cin>>n>>k;autos=to_string(n);intm=s.size();function<int(int,int,int,int)>dfs=[&](inti,intlimit,intis_num,intmul)->int{if(i......
  • AtCoder Beginner Contest 351 E - Jump Distance Sum 切比雪夫距离与曼哈顿距离的转
    先说知识点。曼哈顿距离:横纵坐标距离差的绝对值的和，即|X1-X2|+|Y1-Y2|,离(0,0)点曼哈顿距离为1的点形成的是一个旋转45度后的正方形切比雪夫距离:横纵坐标距离差的绝对值的最大值，即max(|X1-X2|,|Y1-Y2|),离(0,0)点切比雪夫距离为1的点形成的是一个不旋转的正方形曼哈......
  • abc351g 题解
    这场abcF、G质量堪忧。怎么能扔板子上来呢？板子：P4719【模板】"动态DP"&动态树分治Solution这种每次修改对后面询问有影响，又每次都要输出答案的，离线就基本做不了了，这时候就往动态算法想，其实做过几道ddp的题就看出来这是个板子。由于题目中的式子性质优良，我们很明显可以把......
  • atcoder集
    AtCoderBeginnerContest351A-Thebottomoftheninth(签到题) Code:#include<bits/stdc++.h>usingnamespacestd;#definedebug(x)cerr<<#x<<":"<<x<<'\n';intmain(){ios::sync_w......
  • ABC351
    A.Thebottomoftheninth答案为\(\suma_i-\sumb_i+1\)B.SpottheDifference模拟C.Mergetheballs直接按题意模拟就是\(O(n)\)的，那么这题的瓶颈就在于两个球做合并，注意到\(2^a+2^a=2^{a+1}\)，那么我们就可以不考虑底数\(2\)，而直接处理指数即可代码实......
  • ABC351G题解
    考虑动态dp的套路，先树剖一下，令\(son(x)\)为点\(x\)的重儿子。\(g_x=\prod\limits_{u\inC(x)\landu\neqson(x)}f_u\)。于是有\(f_x=f_{son(x)}g_x+a_x\)。于是\(\begin{bmatrix}f_x&1\end{bmatrix}=\begin{bmatrix}f_{son(x)}&1\end{bmatrix}\begin{bmatrix}g_......
  • 【BFS】abc351D Grid and Magnet 题解
    传送门D-GridandMagnet题意：给定h行w列的图表，其中部分位置有磁铁，人物会在磁铁四周（(x+1,y),(x-1,y),(x,y+1),(x,y-1)）停止，某点的自由度定义为从该点出发最多可到的方块数目可以走重复路前置例题：求连通块大小洛谷P1141思路：由自由度的定义联想到连通块的大小，从而决定用BFS......
  • ABC351
    我多久没更新这个系列了啊E把格子分成两类，每一类之间的坐标均可互相走到。然后将这里面的点都旋转\(45\)度，于是这个问题就被转换成曼哈顿距离的问题了。我们可以把\(x\)和\(y\)拆开计算。然后我们排个序，求个差分，然后对于每一个区间算贡献即可。code......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99