玖的数学&算法录

void JiuCherish(){
    int n;
    std::cin >> n;
    i64 sum = 0;
    for(int i=1;i<=n;i++) {
        i64 x;
        std::cin >> x;
        while(!(x & 1) && (x > 0)) {
            x /= 2;
        }
        sum += x;
    }
    std::cout << sum << endl;
}

B.勉强拼凑的记忆

题意：

给你 n 块矩形来构造正方形，可以自行选择积木大小，但是限定为 1*k 的长和宽，其中约定了 1 <= k <= ceil(n/2) ,其中ceil()函数表示取上界。问最大可以搭建多大的正方形，请输出其边长，如果无法构造成正方形，请输出 -1。

数据范围：

t 表示询问次数。

$$1 \leq t \leq 200000, 1 \leq n \leq 10^{18}$$

题解：

代码：

void JiuCherish(){
   i64 n;
   std::cin >> n;
   if(n == 2) {
      std::cout << -1 << endl;
      return;
   }
   if(n & 1) {
      std::cout << n / 2 + n / 6 + 1 << endl;
   } else {
      std::cout << n / 2 + n / 6 << endl;
   }
}

C.忽远忽近的距离

题意：

构造一个长度为 n 的排列，并且对于所有a_i 满足下式：

$$2 \leq |a_i - i| \leq 3$$

排列：长度为n的数组，每个数字（1~n）只会出现一次

数据范围：

$$1 \leq n \leq 10^5$$

题解：构造、模拟

代码：

void JiuCherish(){
    i64 n;
    std::cin >> n;
    if(n <= 3) {
        std::cout << -1 << endl;
        return;
    }
    if(n % 4 == 0) {
        int a = 3,b = 4,c = 1,d = 2;
        for(int i=1;i<=n / 4;i++) {
            std::cout << a + (i - 1) * 4 << " " << b + (i - 1) * 4 << " " << c + (i - 1) * 4 << " " << d + (i - 1) * 4 << " ";
        }
        return;
    } else if(n % 4 == 1) {
        std::cout << 3 << " " << 4 << " " << 5 << " " << 1 << " " << 2 << " ";
        if(n == 5) {
            return;
        } else{
            int a = 8,b = 9,c = 6,d = 7;
            for(int i=1;i<=(n - 4) / 4;i++)  {
            std::cout << a + (i - 1) * 4 << " " << b + (i - 1) * 4 << " " << c + (i - 1) * 4 << " " << d + (i - 1) * 4 << " ";
            }
        }
    } else if(n % 4 == 2) {
        std::cout << 3 << " " << 5 << " " << 1 << " " << 6 << " " << 2 << " " << 4 << " ";
        if(n == 6) {
            return;
        }
        int a = 9,b = 10,c = 7,d = 8;
        for(int i=1;i<=(n - 6) / 4;i++) {
            std::cout << a + (i - 1) * 4 << " " << b + (i - 1) * 4 << " " << c + (i - 1) * 4 << " " << d + (i - 1) * 4 << " ";
        }
    } else if(n % 4 == 3) {
        if(n == 7) {
            std::cout << -1 << endl;
            return;
        } else {
            std::cout << "3 4 1 6 2 8 5 10 11 7 9" << " ";
            int a = 14,b = 15,c = 12,d = 13;
            for(int i=1;i<=(n - 11) / 4;i++) {
                std::cout << a + (i - 1) * 4 << " " << b + (i - 1) * 4 << " " << c + (i - 1) * 4 << " " << d + (i - 1) * 4 << " ";
            }
        }
    }
}

D.宿命之间的对决

题意：

A和B玩游戏，给定一个 n，A先手，每次取 n 的一个因子，使得 n 减去 x ，谁将n 减到 0 就算输。

问：A和B足够聪明的情况下，谁会获胜。

数据范围：

$$1 \leq n \leq 10^{18}$$

题解：博弈

代码：

void JiuCherish(){
   i64 n;
   std::cin >> n;
   if(n & 1) std::cout << "yukari" << endl;
   else std::cout << "kou" << endl;
}

E.公平守望的灯塔

题意：

在平面直角坐标系上，给定了两个点 A 和 B（保证两点不会重合），现在选择一个 C 点，满足三角形 ABC 是以 AB 为斜边的等腰直角三角形。

若找到，输出C点的坐标，有多解的情况下输出任意解即可。若找不到输出”No Answer!”

数据范围：

$$-10^9 \leq x_a,y_a,x_b,y_b \leq 10^9$$

题解：几何，模拟

代码：

此处的 i64 为 double类型。

i64 getmid(i64 a,i64 b) {
    return (a - b) / 2;
}
void JiuCherish(){
   i64 xa,xb,ya,yb;
   std::cin >> xa >> ya >> xb >> yb;
   i64 midx = getmid(xa,xb);
   i64 midy = getmid(ya,yb);
   i64 nowxc = getmid(xa,-xb) - midy;
   i64 nowyc = getmid(ya,-yb) + midx;
   i64 x = abs(nowxc - (int)nowxc);
   i64 y = abs(nowyc - (int)nowyc);
   if(x < eps && y < eps) {
      std::cout << (int)nowxc << " " << (int)nowyc << endl;
   } else {
      std::cout << "No Answer!" << endl;
   }
}

F.迎接终结的寂灭

题意：

给你点屁话，让你输出宇宙最终答案：42。

代码：

1
2
3

void JiuCherish(){
   std::cout << 42 << endl;
}

G.严肃古板的秩序

题意：

给你一个运算式，对于‘？’可以转换成’+’,’-‘,’#’(不能添加括号)。

对于’#’的定义为： a # b 为 a 的 a 次方对 b取模。

例如：3 # 5

$$= 3 ^ 3 mod 5 = 27 mod 5 = 2$$

问最终式子能否成立，如果可以输出任意一个合法解，否则输出-1。

数据范围：

‘?’的数量不超过12个，所有阿拉伯数字为不超过1e9的非负整数。给定的运算式只会有阿拉伯数字、’?’ 和 ‘=’ 组成。

题解：dfs

代码：

H.穿越万年的轮回

I.灵魂碎片的收集

J.无法磨灭的悔恨

K.永恒守候的爱恋

2023牛客寒假算法训练营2

发表于 2023-01-17 更新于 2023-01-20
本文字数： 1.8k 阅读时长 ≈ 2 分钟

A.Tokitsukaze and a+b=n (easy)

easy 与 medium 的唯一区别是输入的数据范围，直接见medium

B.Tokitsukaze and a+b=n (medium)

题意：

给你一个 n ，两个区间 [l1,r1],[l2,r2] ,分别从两个区间内任选两个数 a,b，使得 a + b = n

数据范围

T :测试数据组数

两个区间的范围一致

$$1\leq T \leq 5, 1 \leq n \leq 2\cdot10^5,1\leq L \leq R\leq 10^5$$

题解：结论，模拟，数学

根据 a + b = n 得出 b = n - a ，因此知道只需要找到 b 与 n - a 的区间交即可

代码：

void JiuCherish(){
    ll n;
    std::cin >> n;
    ll l1 = 0,r1 = 0;
    ll l2 = 0,r2 = 0;
    std::cin >> l1 >> r1 >> l2 >> r2;
    ll a = n - r1;
    ll b = n - l1;
    if(l2 > b || a > r2) {
        std::cout << 0 << endl;
        return;
    }
    if(a <= l2 && b >= r2) {
        std::cout << r2 - l2 + 1 << endl;
        return;
    }
    if(a >= l2 && b <= r2) {
        std::cout << b - a + 1 << endl;
        return;
    }
    if(a <= l2 && b <= r2) {
        std::cout << b - l2 + 1 << endl;
        return;
    }
    if(a >= l2 && b >= r2) {
        std::cout << r2 - a + 1 << endl;
        return;
    }
}

C.Tokitsukaze and a+b=n (hard)

D.Tokitsukaze and Energy Tree

E.Tokitsukaze and Function

F.Tokitsukaze and Gold Coins (easy)

G.Tokitsukaze and Gold Coins (hard)

H.Tokitsukaze and K-Sequence

I.Tokitsukaze and Musynx

J.Tokitsukaze and Sum of MxAb

题意：

给你一个长度为 n 的序列 a

同时定义

$$MxAb(i,j) = max(|a_i-a_j|,|a_i+a_j|)$$

问：

$$\displaystyle \sum_{i = 1}^{n} \sum_{j = 1}^{n} MxAb(i,j)$$

题解：模拟、数学

对待绝对值进行讨论：不难发现结果就是

$$|a_i|+|a_j|$$

因此最大值就是上面的式子

那么原式为：

$$\displaystyle \sum_{i = 1}^{n} \sum_{j = 1}^{n} MxAb(i,j)$$

$$\displaystyle = \sum_{i = 1}^{n} \sum_{j = 1}^{n} (|a_i|+|a_j|)$$

$$\displaystyle = \sum_{i = 1}^{n} (n * |a_i|+ \sum_{j = 1}^{n} |a_j|)$$

$$\displaystyle = \sum_{i = 1}^{n} n * |a_i|+ n * \sum_{j = 1}^{n} |a_j|$$

$$\displaystyle = n * \sum_{i = 1}^{n} |a_i|+ n * \sum_{i = 1}^{n} |a_i|$$

$$\displaystyle = 2 * n * \sum_{i = 1}^{n} |a_i|$$

代码：

void JiuCherish(){
   int n;
   std::cin >> n;
   for(int i=1;i<=n;i++) {
      std::cin >> a[i];
      pre[i] = pre[i - 1] + abs(a[i]);
   }
   std::cout << pre[n] * n * 2 << endl;
}

K.Tokitsukaze and Synthesis and Traits

L.Tokitsukaze and Three Integers

2023牛客寒假算法训练营1

发表于 2023-01-17 更新于 2023-01-23
本文字数： 6k 阅读时长 ≈ 5 分钟

感受：感觉整场都是诈骗题和一小部分妙妙结论题。

难度：

签到：ALCH

简单：DKM

中等偏下：GFE

中等偏上：BIJ

A.World Final? World Cup! (I)

题意：

本题需要模拟一次点球大战，约定对战双方为AB，按照ABABABABAB的方式来进行罚点球，即交替点球，各罚五次，A先手，若进球则加一分。

问：从第几球开始胜负已经出来了，如果点完十球仍不知道结果，则输出 -1 。

题解一：模拟

约定 cntA 为 A 的进球得分， cntB 为 B 的进球得分，nowA 为 A 剩下几次罚球，nowB 为 B 剩下几次罚球。

模拟每一场的进球情况，并且保证每一次进球后对 A 均有

$$\displaystyle cntA + nowA < cntB 且 cntB + nowB < cntA$$

同样对 B 也有

$$\displaystyle cntB + nowB < cntA 且 cntA + nowA < cntB$$

代码一：

void JiuCherish(){
    std::string s;
    std::cin >> s;
    s = " " + s;
    int n = s.length();
    int cntA = 0,cntB = 0;
    int nowA = 5,nowB = 5;
    for(int i=1;i<n;i++) {
        if(i & 1) {
            if(s[i] == '1') ++cntA;
            nowA--;
            if(cntA + nowA < cntB) {
                std::cout << i << endl;
                return;
            } else if(cntB + nowB < cntA) {
                std::cout << i << endl;
                return;
            }
        } else {
            if(s[i] == '1') ++cntB;
            nowB--;
            if(cntB + nowB < cntA) {
                std::cout << i << endl;
                return;
            } else if(cntA + nowA < cntB) {
                std::cout << i << endl;
                return;
            }
        }
    }
    std::cout << -1 << endl;
}

官方题解：

检查前 i 场是否能确定结果的方式：剩下的 10-i 场里，假设最后 A 最高 A1 分、最低 A2 分，B 最高 B1 分，最低 B2 分，其确定胜负当前仅当：

$$\displaystyle (A1 - B2) * (B1 - A2) < 0$$

上面式子分成两部分：第一部分为：A最好时能赢B吗，第二部分为：B最好时能赢A吗。

官方题解思路的代码（自写的）：

void JiuCherish(){
    std::string s;
    std::cin >> s;
    int n = s.length();
    int A1 = 0,A2 = 5;
    int B1 = 0,B2 = 5;
    for(int i=0;i<10;i++) {
        if((i + 1) & 1) {
            if(s[i] == '1'){
                ++A1;
                ++A2;
            }
            A2--;
        }
        else {
            if(s[i] == '1'){
                ++B1;
                ++B2;
            }
            B2--;
        }
        if((A1 - B2) * (B1 - A2) < 0) {
            std::cout << i + 1 << endl;
            return;
        }
    }
    std::cout << -1 << endl;
}

B.World Final? World Cup! (II)

C.现在是，学术时间 (I)

题意：

一位教授可以发表多篇论文，每篇论文有一个引用量。定义一位教授的H指数为使得 “ 该教授发表的所有论文中，有至少 H 篇论文的引用量大于等于 H “这一命题成立的最大的 H。

现在某院决定以最优的方式重新分配这些论文，他可以任意指定一篇论文由谁发表，也可以规定每篇论文只能被一位教授，一位教授可以发表多篇论文。

在重新分配后的第 i 位教授的 H 指数为 h_i , 院长希望最大化所有教授的 H 指数之和，请帮忙计算这一最大的值是多少？

数据范围：

有 T 组数，n 个教授数量， a_i 表示论文发表后的引用量。

$$\displaystyle 1\leq T \leq 10^5 , 1\leq n\leq 10^5, 0\leq a_i \leq 10^9$$

且保证

$$\displaystyle \sum n\leq 5 \times 10^5$$

题解一：模拟

根据 H 指数的定义，有 H 篇论文的引用量大于等于 H , 那么不妨每个人都分配一篇，容易发现：除开 a[i] == 0 的情况，其他分配方式都是成立的。

代码一：

void JiuCherish(){
   int n;
   std::cin >> n;
   for(int i=1;i<=n;i++) std::cin >> a[i];
   int ans = 0;
   for(int i=1;i<=n;i++) {
      if(a[i] >= 1) {
         ++ans;
      }
   }
   std::cout << ans << endl;
}

D.现在是，学术时间 (II)

E.鸡算几何

F.鸡玩炸蛋人

G.鸡格线

题意：

有一个长度为 n 的数组 a ，你需要支持以下两种操作：

1、读入l，r，k 对区间**[l,r]** 中所有数字执行 a_i = f(a_i) 操作 k 次，其中

$$f(x) = round(10\sqrt{x}) , round为四舍五入函数$$

2、输出当前数组所有数字的和。

数据范围：

$$1 \leq n,m \leq 10^5, 0 \leq a_i \leq10^9, op\in(1 or 2)$$

$$1 \leq l \leq r \leq n ,1\leq k \leq10^5$$

题解一：数据结构、模拟

f(x)经过不多次数的操作会收敛到一个不变的值，即：不动点。

该不动点有三个：0、99、100。

因此总的操作次数不会太大。

考虑用set来存所有未到达的x_0 的下标。

对该数字进行修改。

代码一：

int f(int x) {
    return round(10 * sqrt(x));
}
void JiuCherish(){
    int n,m;
    std::cin >> n >> m;
    std::set<int> s;
    i64 sum = 0;
    for(int i=1;i<=n;i++) {
        std::cin >> a[i];
        sum += a[i];
        if(f(a[i]) != a[i]) s.insert(i);
    }
    s.insert(n + 1);
    while(m --) {
        int op;
        std::cin >> op;
        if(op == 1){
            int l,r,k;
            std::cin >> l >> r >> k;
            int pos = l;
            while(1) {
                int nxt = (*s.lower_bound(pos));
                if(nxt > r) break;
                for(int i=1;i<=std::min(k,15);i++) {
                    sum -= a[nxt];
                    a[nxt] = f(a[nxt]);
                    sum += a[nxt]; 
                }
                if(f(a[nxt]) == a[nxt]) {
                    s.erase(nxt);
                }
                pos = nxt + 1;
            }
        } else {
            std::cout << sum << endl;
        }
    }
}

H.本题主要考察了DFS

题意：

有一款拼图游戏，其拼图是由 n*n 个大小为 1*1 的拼图块组成，每个拼图块都是正方形的 1*1 拼图块基础上生成，生成方法：对于每一条边，可以选择不变（记为 0 ）、向里削出一个半圆形的缺口(记为 1 )、向外补上一个半圆形的凸出(记为 2 )三种操作之一，一个拼图块是由一个长度为 4 的字符串描述，分别表示着上右下左四条边的顺序。

其中，每块拼图还有一个制作成品 p ，对于一块削去了 x 个半圆、补上了 y 个半圆的 1 * 1 拼图，其制做成本为 p = 10 - x + y

现会隐藏其中一块，并打乱 n * n - 1 块拼图，告诉你对应的字符串，现在需要你完成该游戏，还原拼图原本的样子，输出还原后缺失拼图块的制作成本。

题解一：模拟

因为对于结果来说无论如何都是能拼成的，因此只需要考虑有几个削去的半圆和补上的半圆即可。

代码一：

void JiuCherish(){
    int n;
    std::cin >> n;
    int sum = 0;
    for(int i=1;i<=n * n - 1;i++) {
        sum += 10;
        for(int j=1;j<=4;j++) {
            std::cin >> c[i][j];
            if(c[i][j] == '1') sum--;
            else if(c[i][j] == '2') sum++;
        }
    }
    int total = n * n * 10;
    std::cout << total - sum << endl;
}

I.本题也主要考察了DFS

J.本题竟也主要考察了DFS

K.本题主要考察了dp

题意：

给你一个长度为 n 的字符串，要求之中恰好有 m 个字符是 1 。

现在，规定对于原序列中一个长恰好为 3 的子区间（子区间是连续的），若之中 1 的个数多于 0 的个数，那么称为坏区间。

请求出满足条件的字符串中，坏区间总数最少的字符串有几个坏区间。

数据范围：

$$\displaystyle 1\leq m \leq n \leq 1000$$

题解一：模拟、贪心、暴力

以100100100….的形式去构造字符串，保证前面基本上没有坏区间，最后0用完之后将多余的1补上，由于数据范围较小，所以直接暴力去遍历构造的字符串，统计坏区间即可。

代码一：

void JiuCherish(){
   int n,m;
   std::cin >> n >> m;
   std::string s;
   std::cin >> s;
   int zero = n - m;
   int cnt = 0;
    //构造字符串
   for(int i=1;i<=n;i++) {
      if(i == 1) {
         s += '1';
         m--;
         continue;
      }
      if(zero && cnt != 2) {
         s += '0';
         cnt++;
         zero--;
         continue;
      }
      if(cnt == 2) {
         s += '1';
         cnt = 0;
         continue;
      }
      if(!zero) {
         s += '1';
      }
   }
   //暴力跑每一个字符串的位置，以及该位置的下一位和下下位。
   int ans = 0;
   for(int i=0;i<=n-3;i++) {
      int cnt0 = 0,cnt1 = 0;
      for(int j=i;j<=i+2;j++) {
         if(s[j] == '1') ++cnt1;
         else ++cnt0;
      }
      if(cnt1 > cnt0) ++ans;
   }
   std::cout << ans << endl;
}

L.本题主要考察了运气

题意：

某p–j–s–k游戏中有20名原创角色，分别属于5个团体，每个团体恰好4个人，为了猜出某个人最爱的角色，他会回答以下两类问题：

1、ta属于第 i (from 1 to 5) 个团体吗？

2、ta是第 i (from 1 to 5) 个团体的第 j (from 1 to 4) 个人吗？

在你百分百肯定之前，你需要不停的提问。

现在，你想知道，在选择最优的提问策略使提问数尽可能少的情况下，你的期望提问次数是多少次？本题要求输出该期望次数。

给定你式子

$$最终期望结果 = 3.45 + 0.05 * i$$

请输出 i 是多少（本题只有一个样例，且答案只会在 1~100）

题解一：数学、概率

1、首先进行猜团：前三次猜到的概率均为 0.2 , 第四次猜的时候为 0.4 （如果猜不到那就是另一个，反之亦然）。

2、其次再去猜人：前两次猜到的概率为 0.25 , 第三次猜的时候为 0.5 理由同上。

故结果为

$$E(X) = 1 * 0.2 + 2 * 0.2 + 3 * 0.2 + 4 * 0.4 + 1 * 0.25 + 2 * 0.25 + 3 * 0.5 = 5.05$$

解得 i = 32

M.本题主要考察了找规律

题意：

X有 m 个章鱼仙贝，需要把这些仙贝分给 n 个朋友。

约定一开始X对所有朋友的好感度均为0，当X当前还剩下x（正数）个仙贝，并且送给了一位朋友y个仙贝，那么这位朋友对X的好感度增加y/x。

现在请帮X算一下，在最优送仙贝策略下，X和所有人的好感度之和最大为多少？

数据范围：

$$1 \leq n,m \leq 500$$

题解一：dp

代码

void JiuCherish(){
    int n,m;
    std::cin >> n >> m;
    dp[0][0] = 0;
    for(int i=1;i<=n;i++) {
        for(int j=0;j<=m;j++) {
            for(int k=0;k<=j;k++) {
                dp[i][j] = std::max(dp[i][j],dp[i - 1][j - k] + double(k) / (m - (j - k)));
            }
        }
    }
    double ans = 0;
    for(int i=0;i<=n;i++) {
        for(int j=0;j<=m;j++) {
            ans = std::max(ans,dp[i][j]);
        }
    }
    std::cout << std::fixed << std::setprecision(9) << ans << endl;
}

算法笔记（06）：KMP

发表于 2023-01-07 更新于 2023-01-09
本文字数： 441 阅读时长 ≈ 1 分钟

kmp

const int MAXN = 2e5 + 10;
int n,m;
int nxt[MAXN],f[MAXN];
char s[MAXN],p[MAXN];
//kmp head

void kmp() {
    n = strlen(s + 1);
    m = strlen(p + 1);
    int j = 0;
    nxt[1] = 0;
    for(int i = 2; i <= m; i++) {
        while(j > 0 && p[j + 1] != p[i]) 
            j = nxt[j];
        if(p[j + 1] == p[i])
            j++;
        nxt[i] = j;
    }

    j = 0;
    //回退
    for(int i = 1; i <= n; i++) {
        while((j == m) || (j > 0 && p[j + 1] != s[i]))
            j = nxt[j];
        if(p[j + 1] == s[i])
            j++;
        f[i] = j;
    }
}

时间复杂度

O（n + m)

ABC283

发表于 2023-01-01 更新于 2023-01-10
本文字数： 2.1k 阅读时长 ≈ 2 分钟

D - Scope

题面

给你一个字符串只包括了”(“,”)”和小写字母，如果通过以下步骤，能使字符串为空，那么称字符串是好的：

删除所有小写字母
不停地删除连续的**()**

给定一个好的字符串，并且你有一个盒子，你有以下的操作：

1.如果当前 s[i] 是小写字母，将小写字母放入盒子中，盒子中不能出现两个相同的小写字母。

2.如果当前 s[i] 是 “(“ ，那么什么都不做。

3.如果当前 s[i] 是 “)” ，取小于 i 的最大的 j , 使 Si ~ Sj 这个子串是好的，将 j 到 i 操作中放入的小球全部取出。

如果违背了1，那么输出No，否则输出Yes。

数据范围

$$1 \leq |S| \leq 3 \times 10^5$$

思路：模拟

1：如果当前字符为”(“，那么将cnt 增加1，为一个左括号。

2：如果当前字符为小写字母，如果说当前字符没有出现过，那么让它的值为cnt，反之输出No。

3：如果当前字符为”)”,那么遍历一次26个字母，如果满足等于cnt，那么将其清0。

代码

int st[30];

void JiuCherish(){
    std::string s;
    std::cin >> s;
    int n = s.length();
    int cnt = 1;
    memset(st,false,sizeof(st));
    for(int i=0;i<s.length();i++) {
        if(s[i] == '(') ++cnt;
        else if(s[i] >= 'a' && s[i] <= 'z') {
            if(st[s[i] - 'a']) {
                std::cout << "No" << endl;
                return;
            } else {
                st[s[i] - 'a'] = cnt;
            }
        } else if(s[i] == ')'){
            for(int j=0;j<26;j++) {
                if(st[j] == cnt) st[j] = false;
            }
            --cnt;
        }
    }
    std::cout << "Yes" << endl;
}

E - Don’t Isolate Elements

题面

给定一个 n * m 的 01 矩阵 a,称位于第 i 行第 j 列的元素为 ai,j。

你可以进行如下的操作任意次（可以为0次）：

选择任意一行，翻转此行内的所有元素。

如果当前 [i,j] 的 01 性与 [i-1] [j], [i + 1] [j], [i] [j - 1],[i] [j + 1] 均不相同，那么我们称其点为被隔离点。

请输出使得给定矩阵中没有元素被隔离所需要的最小操作数，如果无论如何操作都无法满足要求则输出 -1。

数据范围

$$2 \leq n,m\leq1000$$

F - Permutation Distance

题面：

你有一个1~n 的排列 p = (p1,p2,…,pn)

你需要对每个 i 求得

$$\displaystyle D_i = \min_{j \neq i} {(|p_i - p_j| + |i - j|)}$$

数据范围：

$$\displaystyle 2 \leq n \leq 2 \times 10^5$$

思路一：暴力

对于每个点，向两边暴力枚举更新答案，如果下标太远则不可能更新到。

时间复杂度：O(n ^ {3 / 2})。

没明白：copy by ppip的思路

复杂度证明：显然一个点向两边最多跑 O(D_i) 次就会停止。所以复杂度为 O*(∑D**i)。

而每个点取离它最近的一个点连边，这个显然能构成一个基环树森林。

同时，在最小生成基环树森林中，每个点都必须要有一个出边，所以给每个点钦定最短的那个出边是一定能构成最小生成基环树森林的。

而平面曼哈顿距离最小生成基环树（森林）在点的横纵坐标范围均是 [1,n] 的整数时，上界是 O(n\sqrt n) 的。

代码

int a[MAXN];

int dis(int x,int y) {
    return abs(x - y) + abs(a[x] - a[y]);
}

void JiuCherish(){
    int n;
    std::cin >> n;
    for(int i=1;i<=n;i++) std::cin >> a[i];
    for(int i=1;i<=n;i++) {
        int d = 1e9; 
        for(int j = i + 1;j - i < d && j <= n;j++) {
            d = std::min(d,dis(i,j));
        }
        for(int j = i - 1;i - j < d && j >= 1;j--) {
            d = std::min(d,dis(i,j));
        }
        std::cout << d << " ";
    }
}

思路二：

算法笔记（05）：并查集

发表于 2022-10-25 更新于 2023-01-09
本文字数： 0 阅读时长 ≈ 1 分钟

致谢

2022 暑假

标签

代码模板

2022目标

A.不断减损的时间

题意：

数据范围

题解：模拟

代码

B.勉强拼凑的记忆

题意：

数据范围：

题解：

代码：

C.忽远忽近的距离

题意：

数据范围：

题解：构造、模拟

代码：

D.宿命之间的对决

题意：

数据范围：

题解：博弈

代码：

E.公平守望的灯塔

题意：

数据范围：

题解：几何，模拟

代码：

F.迎接终结的寂灭

题意：

代码：

G.严肃古板的秩序

题意：

数据范围：

题解：dfs

代码：

H.穿越万年的轮回

I.灵魂碎片的收集

J.无法磨灭的悔恨

K.永恒守候的爱恋

A.Tokitsukaze and a+b=n (easy)

B.Tokitsukaze and a+b=n (medium)

题意：

数据范围

题解：结论，模拟，数学

代码：

C.Tokitsukaze and a+b=n (hard)

D.Tokitsukaze and Energy Tree

E.Tokitsukaze and Function

F.Tokitsukaze and Gold Coins (easy)

G.Tokitsukaze and Gold Coins (hard)

H.Tokitsukaze and K-Sequence

I.Tokitsukaze and Musynx

J.Tokitsukaze and Sum of MxAb

题意：

题解：模拟、数学

K.Tokitsukaze and Synthesis and Traits

L.Tokitsukaze and Three Integers

A.World Final? World Cup! (I)

题意：

题解一：模拟

代码一：

官方题解：

官方题解思路的代码（自写的）：

B.World Final? World Cup! (II)

C.现在是，学术时间 (I)

题意：

数据范围：

题解一：模拟

代码一：

D.现在是，学术时间 (II)

E.鸡算几何

F.鸡玩炸蛋人

G.鸡格线

题意：

数据范围：

题解一：数据结构、模拟

代码一：