首页 > 其他分享 >AGC044B 题解

AGC044B 题解

时间:2024-08-03 11:06:36浏览次数:13  
标签:int 题解 更新 eb AGC044B front dis

考虑每次更新就跑一遍 bfs。

\(O(n^4)\),复杂度不对?

但是注意到 \(dis\) 的最大值也就是 \(n\),每次更新 \(dis\) 至少减一。

所以最大值最多被更新 \(n\) 次,一共更新 \(O(n^3)\) 次,复杂度是对的。

直接暴力。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define eb emplace_back

const int N = 505;

int a[N][N], dis[N][N], n;

int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

void upd(int x, int y)
{
    deque<pair<int, int>> q;
    q.eb(x, y);
    while(q.size())
    {
        auto [x, y] = q.front(); q.pop_front();
        for(int o = 0; o < 4; o ++)
        {
            int u = x + dx[o], v = y + dy[o];
            if(u > 0 && v > 0 && u <= n && v <= n && dis[u][v] > dis[x][y] + a[u][v])
            {
                dis[u][v] = dis[x][y] + a[u][v];
                if(a[u][v]) q.eb(u, v);
                else q.push_front({u, v});
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++)
    for(int j = 1; j <= n; j ++)
        a[i][j] = 1;
    memset(dis, 0x3f, sizeof dis);
    for(int i = 1; i <= n; i ++)
    for(int j = 1; j <= n; j ++)
        dis[i][j] = min(min(i, j), min(n - i + 1, n - j + 1));
    ll ans = 0;
    for(int i = 1; i <= n * n; i ++)
    {
        int k; cin >> k;
        int x = (k - 1) / n + 1, y = (k - 1) % n + 1;
        a[x][y] = 0, dis[x][y] --;
        ans += dis[x][y];
        upd(x, y);
    }
    cout << ans;

    return 0;
}

标签:int,题解,更新,eb,AGC044B,front,dis
From: https://www.cnblogs.com/adam01/p/18340191

相关文章

  • ABC267F 题解
    注意到,对于一棵树\(T\)的任一直径\(a-b\),对于任意一点\(u\),离\(u\)最远的点一定是\(a\)或\(b\)。考虑反证:如图,如果存在点\(c\)使得\(dis(u,c)>\max(dis(u,a),dis(u,b))\)。如图,\(a-b\)为直径,\(d2>d1\)。因为有\(d4>d3+d2\),所以有\(d2+d3+d4>2d2+2d3>d1+d2\),所以......
  • ABC266F 题解
    输入的图是一颗基环树。对于\(x,y\),如果把环上的边去掉,得到的森林里\(x,y\)仍然在同一颗树内,那么显然只有一条路。否则一定要经过环,有两条路。于是dfs或着拓扑排序找环即可。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=2e5+......
  • 2024集训8.2模拟赛题解
    考试历程8:30开始考试8:40快速浏览了T1并想了一下,是一道质数的题目,准备打表,打到一半的时候发现空间复杂度会爆,于是改打质数筛暴力了9:30打完T1开始看T2刚开始没思路,先看了T3,跟着样例打了一点,估计可以拿点分吧9:50打完了T3会看T2发现了一点规律(后来知道是错的)跟着思路写了一......
  • gym105167E Erdős-Ginzburg-Ziv 题解
    题意:给\(p\)和\(p-1\)个边权,要用这些边权构造树,每个点编号\(0\simp-1\),使得每个点\(u\)到\(0\)的距离\(\bmod\p=u\),无解输出-1,保证\(p\)是质数、\(p\le10^6\)、边权\(\in[1..p-1]\).Solution考虑加边的过程,树最开始只有根节点0,然后通过加边不断地引入新的点......
  • 优秀的树 - 题解(数学)
    优秀的树时间限制:C/C++2000MS,其他语言4000MS内存限制:C/C++256MB,其他语言512MB描述给定一棵树,其所有边权重均为\(1\),定义\(f(u)=Σ_vdis(u,v)\),v表示树上的所有结点,\(dis(u,v)\)表示结点\(u\)和\(v\)的简单路径的长度。一棵树被称为“优秀”,当且仅当存在两个......
  • 【题解】走路
    I题意简述从原点出发,一步只能向右走、向上走或向左走。恰好走\(N\)步且不经过已走的点共有多少种走法?多组数据,每行输入一个数\(N\)。对于每一组测试数据,每行输出一个数,答案对\(12345\)取模。对于100%的数据,保证\(1\leqN\leq1000\)。时间限制\(1\text{s}\),空......
  • 树(tree) - 题解(带权并查集)
    树(tree)时间限制:C/C++2000MS,其他语言4000MS内存限制:C/C++256MB,其他语言512MB描述给定一个\(n\)个结点,\(n−1\)条边的有根树。第\(i\)条边可以用(\(a_i,b_i\))来描述,它表示连接结点\(a_i\)和结点\(b_i\)的一条边,其中结点\(a_i\)是结点\(b_i\)的父节点。......
  • Luogu P5005 中国象棋 - 摆上马 / Luogu P8756 国际象棋 题解 [ 蓝 ] [ 状压 dp ] [
    国际象棋:模板棋盘状压。摆上马:需要点思维的棋盘状压,相比上一道题加了“蹩马脚”的设定。Easy_version:国际象棋概述一下此类棋盘问题的思路:用二进制数表示出棋盘上某一行的状态。用位运算预处理出合法的单行状态,以及需要用到的一些东西。用位运算判断前一行或者前几行能否......
  • Luogu P3959 宝藏 题解 [ 紫 ] [ 状压 dp ] [ 二项式定理 ]
    宝藏:一个对着蓝书代码调都能调两个小时的大毒瘤,但是思路还是很值得借鉴的,有普通状压和三进制状压两种做法,或者暴搜剪枝也可以(这里不介绍暴搜剪枝做法)。普通状压做法观察到\(n\le12\),首先想到状压。但考虑到普通的状压不太行,因为\(K\)这个数算在代价里,会导致这个dp有后效......
  • BZOJ2839/LG10596 集合计数 题解(二项式反演+扩展欧拉定理)
    题目大意:一个有\(N\)个元素的集合有\(2^N\)个不同子集(包含空集),现在要在这\(2^N\)个集合中取出若干集合(至少一个),使得它们的交集的元素个数为\(K\),求取法的方案数,答案模\(10^9+7\)。为表述方便,不妨设这\(i\)个元素分别为\(1\simn\)。前置知识:二项式反演。考虑设\(g(......