舟航
3分钟前

题目描述

给定三个整数,请你找出它们中的最大值。

算法

使用三目运算符 ? :

注:

表达式1 ? 表达式2 : 表达式3表示:表达式1如果满足,则返回表达式2;表达式1如果不满足,则返回表达式3。其等价于

if(表达式1)
{
    表达式2;
}
else
{
    表达式3;
}

例如:c=a>b?a:b就会返回a,b中的较大值,并赋值给c。

C++代码:

#include<iostream>

using namespace std;

int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    cout<<( a > b ? a > c ? a : c : b > c ? b : c )<<" eh o maior"<<endl;  
    /*这里要注意加括号,因为三目运算符的优先级比左移运算符的优先级要低!
    括号里面的没有再加括号的原因是:三目运算符中?总是与其右边最近的:相匹配,所以,上边一行等价于:
    cout<<( a > b  ? (a > c ? a : c) : (b > c ? b : c) )<<" eh o maior"<<endl;
    这里的判断顺序为:
        先判断a>b
            如果a>b为真,则判断a>c
                为真返回a,为假返回c
            如果a>b为假,则判断b>c
                为真返回b,为假返回c
    这样就找到了三者中的最大值*/
}



Windness
8分钟前

题目描述

链接在此
AcWing 845

解题思路

本题思维量很大,很难。不得不说,y总的解题思路太妙了。下面来详细的分析一下y总的思路。

首先第一个突破点就是,为什么会想到用 BFS 。我们首先要将每一个三阶方阵的数值状态抽象为一个状态,这道题中需要求得的是一个最少的交换次数。那么,其实就是相当于求从初始状态到达最后规范状态的最短路长度。那么提到了最短路,而且本题中状态之间的距离都是相同的,距离就可以设为 $1$ ,这样的话就满足了使用 BFS 的所有条件了。那么好了,本题我们使用 BFS 进行搜索。

之后就需要考虑的点有两个:如何表征每个状态?状态之间应该如何转移?

首先来看第一个问题:如何表征每个状态?事实上,不难发现,每一个状态其实对应一个唯一的 $3\times3$ 方阵, 讲这个二维方阵降为一维行值,就得到了一个唯一的字符串。那么,可以看到实际上在搜索树中,每一个字符串都和唯一的距离值对应,这里定义距离值是根结点到当前状态的搜索路径最短长度,也就是 BFS 搜索出的长度。由于这种一一对应关系,不难想到要使用哈希表进行映射。所以我们使用 unordered_map 或各个语言中的 dictHashmap 等类似的结构来构建映射关系。这样的话第一个问题就解决了,我们得到了表征每个状态的方式。

那么接下来,第二个问题,状态之间应该如何转移?事实上,对于每一个状态中的 $x$​​​​​ ,它的下一个状态只能有四种移动方式。这个移动方式其实和走迷宫问题 AcWing 844 走迷宫 是一样的。都是在这样的一个二维坐标系下进行移动。那么处理思路就可以完全照搬过来了。由于我们表征每一个状态是将二维矩阵转换成了一维的数组,首先我们找到字符 $x$​​​​ 所在一维字符串中的位置,之后需要进行运算求得其在二维中的位置。记 $k$​​ 为字符 $x$​​ 在一维字符串中的位置,矩阵大小为 $n\times m$​​ ,则运算公式为:$x=\lfloor k/n\rfloor,y=k\mod m$​ 。之后我们进行移动,移动后的坐标满足矩阵大小边界,我们就可以判定该移动后的状态就是搜索树中的一个状态点(结点)。我们得到了一个状态点的字符串形式,如果这个状态还没有被我们搜索到过,那么就更新其距离值,并加入状态与距离映射的哈希表中​​。这里不同语言的处理可能不相同,但如果是修改了原状态的字符串应注意要恢复现场,因为枚举四种移动方式时都是从原状态开始移动的。

有了以上的两个问题的解决作为基础,我们就可以套用 BFS 的模板了。将初始状态入队,之后当队列不空时持续出队队首元素,如果该元素就是最终的状态,证明已经搜索结束, BFS 也随之结束,返回搜索得出的距离最小值;如果该元素还处于中间的某一个状态的话,就需要向下继续搜索。我们枚举其状态的转移,如果状态没有出现过,便将其入队以便于后续的操作。最终如果以上的过程全都执行完毕,但还是没有搜索到最终的状态,证明以该初始状态为起点所构建的状态树(搜索树)中最后没有最终状态这一结点。则搜索结束,返回 $-1$ 。

代码

C++

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <unordered_map>
using namespace std;

int bfs(string start) {
    string end = "12345678x";
    unordered_map<string, int> d;
    queue<string> q;
    d[start] = 0;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    q.push(start);
    while (q.size()) {
        auto t = q.front(); q.pop();
        if (t == end) return d[t];
        int dist = d[t];
        int k = t.find('x');
        int x = k / 3, y = k % 3;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
                swap(t[k], t[3 * nx + ny]);
                if (!d.count(t)) {
                    d[t] = dist + 1;
                    q.push(t);
                }
                swap(t[k], t[3 * nx + ny]);
            }
        }
    }
    return -1;
}

int main() {
    string start;
    for (int i = 0; i < 9; i++) {
        char c;
        cin >> c;
        start += c;
    }
    cout << bfs(start);
    return 0;
}

Python

from collections import deque

def swap(src, a, b):
    edit = list(src)
    edit[a], edit[b] = edit[b], edit[a]
    return ''.join(edit)

def bfs(start):
    end = '12345678x'
    d = {start: 0, }
    q = deque()
    q.append(start)
    dx = [1, 0, -1, 0]; dy = [0, 1, 0, -1]
    while q:
        t = q.popleft()
        if t == end:
            return d[t]
        dist = d[t]
        k = t.index('x')
        x = k // 3; y = k % 3
        for i in range(4):
            nx = x + dx[i]; ny = y + dy[i]
            if 0 <= nx < 3 and 0 <= ny < 3:
                cur = swap(t, k, nx * 3 + ny)
                if cur not in d:
                    d[cur] = dist + 1
                    q.append(cur)
    return -1



if __name__ == '__main__':
    start = ''.join(input().split())
    print(bfs(start))

参考

y总讲解视频




Windness
12分钟前

题目描述

链接在此
AcWing 841

字符串前缀哈希法:

定义 ${h_n}$ 为字符串 $str$ 的前缀哈希值,其中 $h_i$ 为前 $i$ 位的哈希值。

那么该如何定义某一前缀字符串的哈希值?

​ 假定字符串为 $s_1s_2\cdots s_n$ ,那么字符串的 $h_i$ 对应的前缀为 $s_1s_2\cdots s_i$ ,定义字符串的数值为 $val$ ,我们把字符串转换成一个 $p$ 进制的数。那么,字符串 $s_1s_2\cdots s_i$ 对应的值为 $val=s_1\times p^{i-1}+s_2\times p^{i-2}+\cdots+s_i\times p^0$ ,定义哈希函数为 $h(x)=x\mod Q$ ,则最后得到的 $h(val)$ 就是 $h_i$ 的值。显然,$h(x)\in (0,Q)$​

这里需要注意两点。首先,对于一个字符我们不能将其换算为 $0$​​ 。假如将 $A$​​ 映射成 $0$​​ ,那么 $AA$​​ 也就是 $0$​​ ,将会无法区分,这里我们采用其 ASCII 码去进行换算;第二,这里我们假设我们的哈希方法是不存在冲突的。一般经验值为 $p=131/13331$​​ 、 $Q=2^{64}$​​ 。

以上就是定义的字符串哈希方式。我们通过这样的定义方式就可以得到所有子串的哈希值。假定给出区间 $[l,r]$ ,那么根据前缀和的思想,我们需要的是 $h_r,h_{l-1}$ 这两个数。对于字符串 $str$ 内部而言,由于我们定义了要将字符串转化为一个 $k$ 进制的数,则从 $s_1$ 到 $s_n$ 为字符串的高位到低位。那么,我们再分别单独看两个子串,这两个前缀子串当中,$s_1$ 是高位,而 $s_{l-1},s_r$ 是低位。但两个子串相对而言,虽然他们的高位相同,但是,其实在数值上,以 $s_1$ 为例,这里我们用前缀字符串哈希值来代表某一个前缀子串,那么 $h_r$ 的 $s_1$ 对应的值应当是 $s_1\times p^{r-1}$ ,而相对应的 $h_{l-1}$ 中是 $s_1\times p^{l-2}$ 。可以看到,其实两个字符串的哈希值差了 $p^{r-1-(l-2)}=p^{r-l+1}$ 倍的。那么,如果想要进行 ”同等“ 的运算,我们就应当将小的哈希值字符串按位扩大相差的倍数才能进行运算。所以,我们就得到了计算区间 $[l,r]$ 的子串哈希值的公式为:$h_{l,r}=h_r-h_l\times p^{r-l+1}(l\leq r)$ 。这里需要说明的一点是,我们定义的哈希函数是 $h(x)=x\mod Q$ ,这里并不是不进行取模运算了,我们用 unsigned long long 存储所有的哈希值,unsigned long long 的阈值是 $2^{64}$ ,所以如果溢出了范围,也就相当于是对 $2^{64}$​ 进行取模运算了。

仿照我们上面扩大倍数的思想,我们得到哈希值的方式也很简单。相邻两位上相差的倍数就是 $p$ ,那么就有如下公式成立:$h_i=h_{i-1}\times p+s_i$ 。

typedef unsigned long long ULL;
const int P = 131;
char str[N];
ULL h[N], p[N];     // h stores hash values, p stores the pow of P

预处理

p[0] = 1;
for (int i = 1; i <= n; i++) {
    p[i] = p[i - 1] * P;
    h[i] = h[i - 1] * P + str[i];
}

获取某一区间内子串的哈希值

ULL get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

判断两个子串是否完全相同:如果两个子串的哈希值完全相同,那么就判定两者完全相同。因为对于任意的每一个不同的字符串而言,其哈希值是唯一的。

bool judge(int l1, int r1, int l2, int r2) {
    if (get(l1, r1) == get(l2, r2)) return true;
    else return false;
}

代码

C++

#include <iostream>
using namespace std;

typedef unsigned long long ULL;

const int N = 100010, P = 131;

ULL h[N], p[N];
char str[N];

inline ULL gethash(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    scanf("%s", str + 1);
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        h[i] = h[i - 1] * P + str[i];
        p[i] = p[i - 1] * P;
    }
    while (m--) {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if (gethash(l1, r1) == gethash(l2, r2)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

Python

def gethash(l, r):
    return (h[r] - h[l - 1] * p[r - l + 1]) % (1 << 64)

if __name__ == '__main__':
    n, m = map(int, input().split())
    P = 131
    s = ' ' + input()
    h = [0] * len(s)
    p = [0] * len(s)
    p[0] = 1
    for i in range(1, n + 1):
        h[i] = (h[i - 1] * P + ord(s[i])) % (1 << 64)
        p[i] = (p[i - 1] * P) % (1 << 64)
    for _ in range(m):
        l1, r1, l2, r2 = map(int, input().split())
        if gethash(l1, r1) == gethash(l2, r2):
            print("Yes")
        else:
            print("No")



Windness
15分钟前

题目描述

链接在此
AcWing 240

解题思路

看了各位大佬的题解知道了,本题的实质其实是一个带权并查集。所有能产生关系的元素最后都应该属于一个大集合,区别元素种类的方式就是节点到根结点的距离。对于这道题而言,我们把他提到的产生的关系(不论是谁吃谁还是谁和谁是同类)都扔进一个集合中。原因是只要两个元素之间产生关系,那么扔进集合当中必定可以推断出他们之间的关系。有了这个基础之后,我们应当怎样推断出并查集树中两个节点直接的关系呢?我们需要定义节点间的距离,这也就是带权并查集的核心所在。我们定义如果存在食物链 $A\to B$​ ,那么两节点间距离为 $1$​ ,每个节点到其自身的距离为 $0$​ 。那么对于两个任意节点 $A,B$​ 我们不难发现其关系如下:(假设两点之间距离小于等于 $3$​)
$$
d(A,B):=
\begin{cases}
0&A=B\\
1&B\to A\\
2&A\to B\\
\end{cases}
$$
其中 $d(A,B)$​​ 代表了两点间的距离。

那么,我们就很容易能通过距离知道任意节点 $A$​ 和根结点 $r$​ 的关系:
$$
d(A)-d(r)=d(A)\equiv
\begin{cases}
0&A=r\\
1&r\to A\\
2&A\to r\\
\end{cases}\ \
(\text{mod } 3)
$$
定义 $d(x)$ 为节点 $x$ 进行路径压缩后到根结点的距离。

推广到任意节点,将 $r$ 替换成任意节点 $B$​​ ,我们就能得到并查集树中两个节点之间的关系:
$$
d(A)-d(B)\equiv
\begin{cases}
0&A=B\\
1&A\to B\\
2&A\leftarrow B\\
\end{cases}\ \
(\text{mod } 3)
$$
思路清楚了,接下来来分析代码如何实现。我们定义数组 ${d_n}$ 为每个节点到其父节点的距离。首先将两种一定为假话的情况抛去。之后来看剩下的情况。

我们首先应该重定义 find() 函数,因为我们需要在 find() 结束后同时去维护过某一个节点到其根结点的距离,也就是进行路径压缩后到其父节点的距离。由于我们之前实现的 find() 函数使用递归实现了路径压缩的原理,所以我们这里维护一轮递归中的思路就是每次都要将当前所选中的结点向上提到其父节点的父亲上去,能够和其父节点在同一层级上。所以我们每轮递归中都需要找到其父亲的父节点,也就是 find(p[x]) ,之后,由于路径压缩,这时当前节点的父节点已经改变。那么同时的我们就需要维护这个结点到其父节点的距离 $d_x$ 了。显然,距离需要增加其父节点到父节点的父节点之间的距离,即 $d_{p_x}$​ 。最后,重新绑定父节点为原结点的父节点的再上一层父节点。一轮递归完成。当所有递归都退出后,正好我们完成了路径压缩的全过程,而此时,我们的 $d_x$ 存储的也恰好就是当前节点到根结点的距离了。

所以我们重定义了 find() 函数,我们就可以先使用该函数来判断输入进来的两个节点是否属于同一个集合当中。此时也同时完成了对两个节点的路径压缩。我们也知晓了两个节点到根结点的距离,我们也就能够通过与根结点之间的关系推断两个节点之间之间的关系了。

第一种情况,两个节点当前属于同一个集合中,证明这两个节点之前必定能产生某种关系。那么此时这句话就可能是假的。那么就套用对于并查集树中任意两节点关系的定义,我们不难得到两个条件语句中的条件。当然假话应当是怎么样的也显而易见。第一种情况结束。

第二种情况,如果两个节点当前不属于同一个集合中,证明两个节点之前没有任何关系,那这句话必定是真话。此时我们要做的就是更新两个节点之间的关系和距离数组的值。显然,我们首先需要将两个集合合并。这里不妨设合并的方式是将 $x$​​ 作为 $y$​​ 的子树。这时就需要从节点 $p_x$​​ 向节点 $p_y$​​ 增加一条边,$p_y$​​​ 作为新的根结点,并赋予距离值使得输入的关系成立。

设新增加的边的权值为 $i$​​ 。如果输入两个节点是同类,即 $y=x$​​,那么有 $d(x)+i-d(y)\equiv0(\text{mod }3)$​​ 成立,不妨设 $d(x)+i-d(y)=0$​​ ,解得 $d(p_x)=i=d(y)-d(x)$​​ ;如果输入的关系是 $y\to x$​​ ,那么有 $d(x)+i-d(y)\equiv1(\text{mod }3)$​ 成立,不妨设 $d(x)+i-d(y)=1$ ,解得 $d(p_x)=i=1+d(y)-d(x)$ 。需要说明的是,此处的 $d(k)$ 仍表示节点 $k$​ 到其父节点的距离。

本题结束。​

代码

C++

#include <iostream>
using namespace std;

const int N = 50010;

int p[N], d[N];
int res;

int find(int x) {
    if (p[x] != x) {
        int pa = find(p[x]);
        d[x] += d[p[x]];
        p[x] = pa;
    }
    return p[x];
}

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) p[i] = i;
    int att, x, y;
    while (k--) {
        scanf("%d%d%d", &att, &x, &y);
        if (x > n || y > n) res++;
        else if (att == 2 && x == y) res++;
        else {
            int px = find(x), py = find(y);
            if (px == py) {
                if (att == 1 && (d[x] - d[y]) % 3) res++;
                if (att == 2 && (d[x] - d[y] - 1) % 3) res++;
            }
            else {
                p[px] = py;
                if (att == 1) d[px] = d[y] - d[x];
                if (att == 2) d[px] = 1 + d[y] - d[x];
            }
        }
    }
    printf("%d", res);
    return 0;
}

Python

def find(x):
    if p[x] != x:
        pa = find(p[x])
        d[x] += d[p[x]]
        p[x] = pa
    return p[x]

if __name__ == '__main__':
    n, k = map(int, input().split())
    p = [i for i in range(n + 1)]
    d = [0] * (n + 1)
    res = 0
    for _ in range(k):
        att, x, y = map(int, input().split())
        if x > n or y > n:
            res += 1
        elif att == 2 and x == y:
            res += 1
        else:
            px = find(x); py = find(y)
            if px == py:
                if att == 1 and (d[x] - d[y]) % 3:
                    res += 1
                if att == 2 and (d[x] - d[y] - 1) % 3:
                    res += 1
            else:
                p[px] = py
                if att == 1:
                    d[px] = d[y] - d[x]
                if att == 2:
                    d[px] = 1 + d[y] - d[x]
    print(res)

参考

y总讲解视频




NgAgo
15分钟前

多重背包问题优化中至于为什么可以表示出所有的可能,注意这里是 “表示” 可以参考这个图,对于下一个组而言前面的所有可能都已经表示过了,只关注本组的选择与不选择,因为dp数组本身是集合的一个属性的表示,而优化过后的枚举过程实际上是符合数学表达的,所以拥有正确性

比如:

当在选择是否选择两个物品的时候就包含了是否选择一个物品,以此类推在选择是否选三个物品的时候就包含了前面所有的可能,从而表示了0~7这么多种可能性

1.png




Windness
23分钟前

题目描述

链接在此
AcWing 143

解题思路

先想暴力做法:首先读入这一堆的数,之后进行二重循环遍历,每次都将两个数进行异或运算,最后输出一个异或结果得到的最大值。

代码实现如下:

C++

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100010;

int a[N];

int main() {
    int n;
    scanf("%d", &n);
    int res = 0;
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            res = max(res, a[i] ^ a[j]);
        }
    }
    printf("%d", res);
    return 0;
}

显而易见的这个 $O(n^2)$​ 复杂度的算法绝对会 TLE 。那么如何优化呢?

这里实际上涉及到了贪心的思想。我们这样考虑,异或实质上就是一个数展开成为二进制之后的运算。我们假设当前我们选中了数 $a_k$ ,其对应的二进制展开为 $b_1b_2\cdots b_r$ 。每一次我们都想找到在所有数中与我们选中的数进行异或值最大的那个数。那么我们怎么才能让最后的异或值最大呢?当然是越高位产生越多的 $1$​ ,这个值就会越大。那么好了,我们怎么才能产生更多的 $1$ 呢?这里就要回到异或的定义上来,相对应二进制位不同,异或值当前位值为 $1$ 。那么,我们也就希望被运算的那个数(不是 $k$ )尽可能的能够更多的有和数 $k$​ 产生反的值。这里也就是贪心的体现。思想有了,接下来就应该去优化数据结构从而能够实现这种想法了。可以看到,按照我们这个思想,实质上思维的过程就类似一个决策树的结构。那么相应的,我们这个题也就可以用 Trie 树去存储每个数的二进制展开,由于 Trie 树可以从根结点知道每一个数的信息,而且这个题中一个节点最多有两个子节点,因为二进制只有0,1两个数。所以通过 Trie 树可以很方便查询到从当前展开位的取反(0,1取反)位是否可以向下走,如果可以,那么这个位就产生最后异或的一个 $1$ ,最后结果要加上 $1$​ 在这个位置上所产生的一个值。循环过二进制展开的所有位后,我们便得到了这一个数所对应的这个最大异或值了。那么遍历过整个数组都进行一遍这个过程之后,我们便得到了答案。

代码

C++

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100010, M = 31 * 100010;

int a[N];
int son[M][2];
int idx;

void insert(int x) {
    int p = 0;
    for (int i = 30; i >= 0; i--) {
        int b = x >> i & 1;
        if (!son[p][b]) son[p][b] = ++idx;
        p = son[p][b];
    }
}

int doxor(int x) {
    int p = 0;
    int res = 0;
    for (int i = 30; i >= 0; i--) {
        int b = x >> i & 1;
        if (son[p][!b]) {
            p = son[p][!b];
            res += 1 << i;
        }
        else p = son[p][b];
    }
    return res;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        insert(a[i]);
    }
    int res = 0;
    for (int i = 0; i < n; i++) res = max(res, doxor(a[i]));
    printf("%d", res);
    return 0;
}

Python

def insert(x):
    global idx
    p = 0
    for i in range(30, -1, -1):
        b = x >> i & 1
        if not son[p][b]:
            idx += 1
            son[p][b] = idx
        p = son[p][b]

def doxor(x):
    p = 0
    res = 0
    for i in range(30, -1, -1):
        b = x >> i & 1
        if son[p][not b]:
            p = son[p][not b]
            res += 1 << i
        else:
            p = son[p][b]
    return res

if __name__ == '__main__':
    n = int(input())
    nums = list(map(int, input().split()))
    M = 31 * n
    son = [[0] * 2 for _ in range(M)]
    idx = 0
    for num in nums:
        insert(num)
    res = 0
    for num in nums:
        res = max(res, doxor(num))
    print(res)

参考

y总讲解视频




Windness
26分钟前

题目描述

链接在此
AcWing 789

解题思路

找边界!!找边界!!边界将序列分为两部分,顾想到二分。

依题意,要找到被查询元素的上界和下界。首先看上界。上界的意味是第一个 $\geq x$ 的数,这时就可以定义 check() 的性质是 q[mid] >= x ,当然这里定义为 q[mid] < x 也未尝不可,只不过变成了反方向的寻找,找到的是上界的前一个数,更新区间的时候 $l$ 应该被更新成 $mid+1$ 。之后依据区间的变化和 $x$ 被囊括在哪一个区间内去更新区间和判断要不要改动 $mid$ 的取值即可。再看下界,下界的意味是最后一个 $\leq x$ 的数,则思路和上面一样,可以找到上下界。本题结束。

代码

C++

#include <iostream>
using namespace std;

const int N = 100010;

int q[N];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &q[i]);
    while (k--) {
        int x;
        scanf("%d", &x);
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }
        /* or write as following
        while (l < r) {
            int mid = l + r >> 1;
            if (q[mid] < x) l = mid + 1;
            else r = mid;
        }
        */
        if (q[l] != x) printf("-1 -1\n");
        else {
            printf("%d ", l);
            l = 0, r = n - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }
            printf("%d\n", l);
        }
    }
    return 0;
}

Python

n, q = map(int, input().split())
arr = list(map(int, input().split()))
for i in range(1, q + 1):
    x = int(input())
    l = 0
    r = n - 1
    while (l < r):
        mid = l + r >> 1
        if arr[mid] >= x:
            r = mid
        else:
            l = mid + 1
    if (arr[l] != x):
        print("-1 -1")
    else:
        temp = l
        l = 0
        r = n - 1
        while (l < r):
            mid = l + r + 1 >> 1
            if arr[mid] <= x:
                l = mid
            else:
                r = mid - 1
        print(' '.join(map(str, [temp, l])))



Windness
30分钟前

题目描述

链接在此
AcWing 788

解题思路

由于最大是 $10^6$ ,所以最坏情况会爆 int ,需要使用 long long

思路:使用归并排序,假设 merge_sort() 可以返回当前区间内的逆序对数量

  1. 递归左右区间,计算当前左右区间内部存在的逆序对数量。
  2. 合并,双指针算法。由于部分区间已有序(左右区间已分别有单调性),双指针游动时,当 $q_i>q_j$ 时,由于要求左区间内部所有元素均小于右区间,则对于元素 $q_j$ 而言产生逆序对。又由于左区间内 $i$ 后所有元素均是满足 $q_x>q_j(x\geq i)$ ,则可以计算得对于 $q_j$ 而言产生了逆序对数量是 $mid-i+1$ 。
  3. 收尾。由于对于右区间的所有元素的逆序对数量都已经计算完毕,则左区间若剩余则直接复制下来进入序列。右区间内若剩余元素,因本来的要求就是右区间的元素应大于左区间,所以直接复制下来也没有问题。

代码

C++

#include <iostream>
using namespace std;

const int N = 100010;

int q[N];
int temp[N];

long long merge_sort(int q[], int l, int r) {
    if (l >= r) return 0;
    int mid = l + r >> 1;
    long long res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
    int i = l, j = mid + 1;
    int k = 0;
    while (i <= mid && j <= r) {
        if (q[i] <= q[j]) temp[k++] = q[i++];
        else {
            temp[k++] = q[j++];
            res += mid - i + 1;
        }
    }
    while (i <= mid) temp[k++] = q[i++];
    while (j <= r) temp[k++] = q[j++];
    for (i = 0, j = l; j <= r; i++, j++) q[j] = temp[i];
    return res;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &q[i]);
    long long res = merge_sort(q, 0, n - 1);
    printf("%lld", res);
    return 0;
}

Python

def merge_sort(arr, l, r):
    if l >= r:
        return 0
    mid = l + r >> 1
    left = merge_sort(arr, l, mid)
    right = merge_sort(arr, mid + 1, r)
    res = left + right
    i = l
    j = mid + 1
    temp = []
    while i <= mid and j <= r:
        if arr[i] <= arr[j]:
            temp.append(arr[i])
            i += 1
        else:
            temp.append(arr[j])
            j += 1
            res += mid - i + 1
    temp += arr[i:mid + 1]
    temp += arr[j:r + 1]
    arr[l:r + 1] = temp
    return res

if __name__ == '__main__':
    n = int(input())
    q = list(map(int, input().split()))
    res = merge_sort(q, 0, n - 1)
    print(res)



季末
32分钟前
#include<iostream>

using namespace std;
int main()
{
    for(int i=1;i<=100;i++)
    if(i%2==0)cout<<i<<endl;
    return 0;
}



leoma
38分钟前

题目描述

实现一个单链表,链表初始为空,支持三种操作:

1.向链表头插入一个数;
2.删除第 k个插入的数后面的数;
3.在第 k个插入的数后插入一个数。

现在要对该链表进行 M 次操作,进行完所有操作后,从头到尾输出整个链表。

注意:题目中第 k
个插入的数并不是指当前链表的第 k
个数。例如操作过程中一共插入了 n
个数,则按照插入的时间顺序,这 n
个数依次为:第 1
个插入的数,第 2
个插入的数,…第 n
个插入的数。

本人蒟蒻
主要内容在代码里

样例

输入
第一行包含整数 M ,表示操作次数。接下来 M 行,每行包含一个操作命令,操作命令可能为以下几种:H x,表示向链表头插入一个数 x。D k,表示删除第 k 个插入的数后面的数(当 k 为 0 时,表示删除头结点)。I k x,表示在第 k 个插入的数后面插入一个数 x(此操作中 k 均大于 0)。

输出
共一行,将整个链表从头到尾输出。

举个例子🌰

输入样例

10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6

输出样例

6 4 6 5

(不怎么华丽的分割线)

主要算法

时间复杂度分析:链表在插入的时候可以达到O(1)的复杂度

C++ 代码

#include <iostream>

using namespace std;

const int N = 100010;

int n;
int h[N], e[N], ne[N], head, idx;

//对链表进行初始化
void init(){
    head = -1;//最开始的时候,链表的头节点要指向-1,
    //为的就是在后面进行不断操作后仍然可以知道链表是在什么时候结束
    /*
    插句题外话,我个人认为head其实就是一个指针,是一个特殊的指针罢了。
    刚开始的时候它负责指向空结点,在链表里有元素的时候,它变成了一个指向第一个元素的指针

    当它在初始化的时候指向-1,来表示链表离没有内容。
    */
    idx = 0;//idx在我看来扮演两个角色,第一个是在一开始的时候,作为链表的下标,让我们好找
    //第二在链表进行各种插入,删除等操作的时候,作为一个临时的辅助性的所要操作的元素的下
    //标来帮助操作。并且是在每一次插入操作的时候,给插入元素一个下标,给他一个窝,感动!
    /*
    再次插句话,虽然我们在进行各种操作的时候,元素所在的下标看上去很乱,但是当我们访问的
    时候,是靠着指针,也就是靠ne[]来访问的,这样下标乱,也就我们要做的事不相关了。
    另外,我们遍历链表的时候也是这样,靠的是ne[]
    */
}
//将x插入到头节点上
void int_to_head(int x){//和链表中间插入的区别就在于它有head头节点
    e[idx] = x;//第一步,先将值放进去
    ne[idx] = head;//head作为一个指针指向空节点,现在ne[idx] = head;做这把交椅的人换了
    //先在只是做到了第一步,将元素x的指针指向了head原本指向的
    head = idx;//head现在表示指向第一个元素了,它不在是空指针了。(不指向空气了)
    idx ++;//指针向下移一位,为下一次插入元素做准备。
}

//将x插入到下标为k的点的后面
void add(int k, int x){
    e[idx] = x;//先将元素插进去
    ne[idx] = ne[k];//让元素x配套的指针,指向它要占位的元素的下一个位置
    ne[k] = idx;//让原来元素的指针指向自己
    idx ++;//将idx向后挪
    /*
    为了将这个过程更好的理解,现在
    将指针转变的这个过程用比喻描述一下,牛顿老师为了省事,想插个队,队里有两个熟人
    张三和李四,所以,他想插到两个人中间,但是三个人平时关系太好了,只要在一起,就
    要让后面的人的手插到前面的人的屁兜里。如果前面的人屁兜里没有基佬的手,将浑身不
    适。所以,必须保证前面的人屁兜里有一只手。(张三在前,李四在后)
    这个时候,牛顿大步向前,将自己的手轻轻的放入张三的屁兜里,(这是第一步)
    然后,将李四放在张三屁兜里的手抽出来放到自己屁兜里。(这是第二步)
    经过这一顿骚操作,三个人都同时感觉到了来自灵魂的战栗,打了个哆嗦。
    */
}

//将下标是k的点后面的点个删掉
void remove(int k){
    ne[k] = ne[ne[k]];//让k的指针指向,k下一个人的下一个人,那中间的那位就被挤掉了。
}
int main(){
    cin >> n;
    init();//初始化
    for (int i = 0; i < n; i ++ ) {
        char s;
        cin >> s;
        if (s == 'H') {
            int x;
            cin >> x;
            int_to_head(x);
        }
        if (s == 'D'){
            int k;
            cin >> k;
            if (k == 0) head = ne[head];//删除头节点
            else remove(k - 1);//注意删除第k个输入后面的数,那函数里放的是下标,k要减去1
        }
        if (s == 'I'){
            int k, x;
            cin >> k >> x;
            add(k - 1, x);//同样的,第k个数,和下标不同,所以要减1
        }
    }

    for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ' ;
    cout << endl;

    return 0;
}