001

[RonDen]

图的存储，如果是稀疏图，即图的节点数与边数在一个量级，则使用邻接表存储。 如果是稠密图，则使用邻接矩阵存储。 邻接表推荐使用数组实现，遍历更快。

邻接矩阵：

#include <cstring> // memset
#include <iostream>
#include <cstdio>
#include <algorithm>
// 图中的顶点数
// 如果是1000个点，多开10个
const int N = 1010;
const int inf = 0x3f3f3f3f;

int g[N][N];

int main()
{
    memset(g, 0x3f, sizeof g);
    // ...
}

邻接表：

#include <cstring> // memset
#include <iostream>
#include <cstdio>
#include <algorithm>
// 图中的顶点数
const int N = 1010;
const int M = 2010;
const int inf = 0x3f3f3f3f;

int h[N], e[M], ne[M], w[M], idx;

// 将a->b的边添加进去，权重为c
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

// 访问以u为顶点的边
void visit(int u)
{
     for (int i = h[u]; i != -1; i = ne[i]) {
           int j = e[i];
           // u->j
    }
}

int main()
{
    memset(h, -1, sizeof h);
    // ...
}

[FarmerLiuAng]

[liboning1996]

11111

[CAEsarer]

te

[FarmerLiuAng]

Description

给定一个正整数 m 以及一个由 n 个非负整数 x1,⋯,xn​ 构成的序列, 每一轮可以从序列中选取若干个元素并执行如下运算: xi=(xi+1) mod m

请给出一种方案, 用最少的轮数把给定序列变成一个非递减序列, 输出需要经过的最少的轮数.

Input

输入包含两行,

第一行为两个正整数 n,m∈[1,300000], 分别表示序列中元素个数以及模运算中 m 的值.

第二行为 n 个整数 x1,⋯,xn∈[0,m−1], 表示序列中每个元素的值.

Output

输出最少的轮数.

Sample Input 1

5 7 0 6 1 3 2

Sample Output 1

1

Sample Input 2

4 6 1 2 3 4

Sample Output 2

0

[dpbnnp]

给定一个正整数 mmm 以及一个由 nnn 个非负整数 x1,⋯ ,xnx_1,\cdots, x_nx1​,⋯,xn​ 构成的序列, 每一轮可以从序列中选取若干个元素并执行如下运算: xi=(xi+1) mod mx_i = (x_i + 1) \bmod mxi​=(xi​+1)modm.

请给出一种方案, 用最少的轮数把给定序列变成一个非递减序列, 输出需要经过的最少的轮数. 输入包含两行,

第一行为两个正整数 n,m∈[1,300000]n, m \in [1,300000]n,m∈[1,300000], 分别表示序列中元素个数以及模运算中 mmm 的值.

第二行为 nnn 个整数 x1,⋯ ,xn∈[0,m−1]x_1, \cdots, x_n \in [0, m-1]x1​,⋯,xn​∈[0,m−1] 输出最少的轮数

[dpbnnp]

![Uploading 图片.png…]()

[RonDen]

图片显示不了

[weikm]

//搜到啦

include<bits/stdc++>

include

include

include

include

include

include

include

include

include

define LL long long

define ull unsigned long long

define inf 0x7f7f7f7f

using namespace std;

int n, m; const int maxn = 3e5 + 5; int num[maxn];

int main() { scanf("%d%d", &n, &m); for(int i = 0; i < n; i++){ scanf("%d", &num[i]); } int l = 0, r = m; int ans; while(l < r){ bool flag = false; int mid = (l + r) / 2, prev = 0; for(int i = 0; i < n; i++){ int x = num[i], y = num[i] + mid; if(x <= prev && y >= prev || x <= prev + m && y >= prev + m){ continue; } if(prev >= x){ flag = true; break; } prev = num[i]; } if(flag){ l = mid + 1; } else{ //ans = mid; r = mid; } } printf("%d\n", l); return 0; }

[weikm]

第一题，上面那个格式出了问题，源代码见https://www.cnblogs.com/wyboooo/p/10957958.html

[RonDen]

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

#define LL long long
#define ull unsigned long long
#define inf 0x7f7f7f7f

using namespace std;

int n, m;
const int maxn = 3e5 + 5;
int num[maxn];

int main()
{
   // freopen("2.in", "r", stdin);
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &num[i]);
    }
    int l = 0, r = m;
    int ans;
    while (l < r)
    {
        bool flag = false;
        int mid = (l + r) / 2, prev = 0;
        for (int i = 0; i < n; i++)
        {
            int x = num[i], y = num[i] + mid;
            if (x <= prev && y >= prev || x <= prev + m && y >= prev + m)
            {
                continue;
            }
            if (prev >= x)
            {
                flag = true;
                break;
            }
            prev = num[i];
        }
        if (flag)
        {
            l = mid + 1;
        }
        else
        {
            //ans = mid;
            r = mid;
        }
    }
    printf("%d\n", l);
    return 0;
}