暑期总结

签到题

数数，然后算出一个你觉得最卷的人，打印就好啦。本题是Special Judge ，两个人都是正确答案

最长括号匹配

动态规划，栈

本题考察动态规划的运用，栈的运用。

动态规划思路

令 $dp[i]$ 为表示以 $s[i]$ 为结尾的字符串的最长括号匹配的长度。

那么如果 $s[i − 1 − dp[i − 1]]$ 与 $s[i]$ 匹配的话，$dp[i]$ 一定等于 $dp[i − 1] + 2 + dp[i − dp[i − 1] − 2]$

最后可以推出当匹配成立时的转移方程，$dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2]$

要是觉得讲的有些迷糊还可以参考一下洛谷题解

参考C++代码

代码来源，搬题人@

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 100000 + 10;
char st[maxn];
int ans;
int dp[maxn];
int main() {
    scanf("%s", st + 1);
    int len = strlen(st + 1);
    for (int i = 1; i <= len; i++) {
        if (st[i] == '(' || st[i] == '[')
            continue;
        if (st[i] == ')' || st[i] == ']') {
            if ((st[i] == ')' && st[i - 1 - dp[i - 1]] == '(') ||
                (st[i] == ']' && st[i - 1 - dp[i - 1]] == '[')) {
                dp[i] = dp[i - 1] + 2 + dp[i - 2 - dp[i - 1]];
                ans = max(ans, dp[i]);
            }
        }
    }
    for (int i = 1; i <= len; i++)
        if (dp[i] == ans) {
            for (int j = i - ans + 1; j <= i; j++)
                printf("%c", st[j]);
            return 0;
        }
}

模拟栈思路

直接扫一遍字符串，如果括号能成对就标记一遍，然后扫一遍标记，找出最长的连续标记区间，这个标记区间的字符切片就是答案。

参考rust代码实现

看不懂代码就按照思路自己写一遍，或者根据动态规划的方法来写吧

use std::io::stdin;

fn main() {
    // 读一行字符串，并且转换成字符数组（可访问下标）
    let mut line = String::new();
    let _ = stdin().read_line(&mut line);
    let line: Vec<char> = line.chars().map(|c| c).collect();
    // 初始化标记数组和栈
    let mut visited = vec![false; line.len()];
    let mut stack = Vec::new();
    // 扫一遍字符串并标记可以成对的
    for i in 0..line.len() {
        if line[i] == '(' || line[i] == '[' {
            stack.push(i);
            continue;
        }
        if let Some(&idx) = stack.last() {
            if (line[idx] == '(' && line[i] == ')') || (line[idx] == '[' && line[i] == ']') {
                visited[idx] = true;
                visited[i] = true;
                stack.pop();
                continue;
            }
            stack.clear();
            continue;
        }
    }
    // 找出最长的连续标记区间
    let mut cnt = 0usize;
    let mut l = 0usize;
    let mut maxn = 0usize;
    let mut maxl = 0usize;
    let mut maxr = 0usize;
    for i in 0..line.len() {
        if !visited[i] {
            cnt = 0;
            l = i + 1;
            continue;
        }
        cnt += 1;
        if cnt > maxn {
            maxn = cnt;
            maxl = l;
            maxr = i;
        }
    }
    // 这个切片就是答案
    for i in maxl..=maxr {
        print!("{}", line[i]);
    }
}

ACM足球队

动态规划

这题就是个 $01$ 背包的模板题，需要注意的是，你需要压缩成一维数组，否则就会 MLE

参考C++实现

代码来源@

#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int dp[N], k[N], m[N];
int n, v, c, d;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> v >> n >> c;

    for(int i = 1; i <= n; i ++ )
    {
        cin >> k[i] >> m[i];
    }

    cin >> d;

    for(int i = 1; i <= n; i ++ )
        for(int j = c + d; j >= m[i]; j -- )
            dp[j] = max(dp[j], dp[j - m[i]] + k[i]);

    int res = -1;
    for(int i = 1; i <= c + d; i ++ )
        if(dp[i] >= v)
        {
            cout << c + d - i;
            return 0;
        }

    cout << "Impossible\n";
    return 0;
}

rust实现

Scanner 是我自己写的输入功能模块，方便输入而已

use std::io::stdin;
use scanner::Scanner;

fn main() {
    let mut scan = Scanner::new(stdin());
    // 由于rust中访问数组下标必须用无符号size类型，这里一开始直接用usize存
    let s = scan.next_usize().unwrap();
    let n = scan.next_usize().unwrap();
    // 原生支持的int128_t，效率高
    let c = scan.next_i128().unwrap();
    // 初始化价值和体积数组
    let mut v = vec![0; n + 1];
    let mut w = vec![0; n + 1];
    for i in 1..=n {
        v[i] = scan.next_usize().unwrap();
        w[i] = scan.next_usize().unwrap();
    }
    let d = scan.next_i128().unwrap();
    // 01背包
    let mut dp = vec![0; (c + d) as usize + 1];
    let mut answer = -1i128;
    for i in 1..=n {
        for j in (w[i]..dp.len()).rev() {
            dp[j] = dp[j].max(dp[j - w[i]] + v[i]);
            if dp[j] >= s {
                answer = answer.max(c + d - j as i128);
            }
        }
    }
    // 打印
    let str = format!("{}", answer);
    println!("{}", if answer == -1 { "Impossible" } else { str.as_str() })
}

LYF和ZHY

排序，树状数组

归并排序

学冒泡排序的时候，我们就可以发现冒泡的过程其实就隐含了一个求逆序对的过程，但是对于这个数据范围，直接使用冒泡排序会超时，考虑更优秀的算法。结合归并排序的性质，我们又可以发现归并排序的过程也隐含了一个求逆序对的过程，我们直接结合归并排序来求解即可。

C++归并排序实现

代码来源@

// res 储存的就是逆序对的个数
void merge_sort(int l, int r)
{
    if(l == r)return;
    int mid = l + r >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);

    int i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r)
    {
        if(q[i] <= q[j])t[k ++] = q[i ++];
        else
            t[k ++] = q[j ++], res = (res + mid - i + 1);
    }
    while(i <= mid)t[k ++] = q[i ++];
    while(j <= r)t[k ++] = q[j ++];
    for(int i = l; i <= r; i ++ )
        q[i] = t[i];
}

树状数组

离散化后对数组从大到小排序，对排序的数组，从大到小对树状数组进行单点加上一，然后在查询当前这个数前面位置的数就是逆序对的个数。

rust核心代码实现

fn solve(scan: &mut Scanner) {
    let n: usize = scan.next_line().unwrap().parse().unwrap();
    let mut arr = vec![(0i128, 0i128); n];
    for i in 0..n {
        arr[i] = (scan.next_i128().unwrap(), i as i128 + 1)
    }
    // 反向排序（正向排序是从小到大）
    arr.sort_by_key(|&val| Reverse(val));
    // 构建树状数组
    let mut fenwick = Fenwick::new(n + 1);
    let mut answer = 0;
    for i in 0..n {
        let (_, idx) = arr[i];
        fenwick.add_point(idx, 1);
        answer += fenwick.query_point(idx - 1);
    }
    println!("{}", answer);
}

看不懂？

可以再看看详细的洛谷题解

zhy学画画

线段树，位运算

这道题倒是个压轴题，有人用维护 $30$ 个线段树的方法过的，我们这里用的还是一个位处理的思想。我们可以这样想，当一个数的二进制表示中，第 $i$ 个位是 $1$ 的时候，表示这个数被涂上了第 $i$ 种颜色。

进一步想，要求区间的颜色有多少种，就是要求这个区间所有的数的位或和。当我们知道这个区间的位或和之后，C++选手就可以通过 $popcount(val)$ 来计算val中有多少个 $1$ ，也就是我们的颜色有多少种。

其他语言也有各自实现的 popcount 函数，名字不一样和用法稍微不一样，你也可以自己写一个。

# 一个简单的，python实现的popcount
def popcount(n):
    # 零肯定不含有 1 啦
    if n == 0:
        return 0
    # 每次计算最后一个位是不是 1，是就 + 1
    else:
        return (n & 1) + popcount(n >> 1)

说回我们的区间操作，很容易就想到了线段树，毕竟是区间修改，区间查询嘛，知道了上面的逻辑，我们就知道我们的树怎么写了，这里给出一个参考实现

rust参考实现

想看C++代码可以去洛谷

fn main() {
    let mut scan = Scanner::new(stdin());
    let l = scan.next_usize().unwrap();
    let _ = scan.next_usize().unwrap();
    let o = scan.next_usize().unwrap();
    let mut tree = SegmentTree::new(l);
    for _ in 0..o {
        let c = scan.next_char().unwrap();
        let mut l = scan.next_usize().unwrap() - 1;
        let mut r = scan.next_usize().unwrap() - 1;
        if l > r {
            swap(&mut l, &mut r);
        }
        match c {
            'C' => {
                tree.add(l, r, 1 << (scan.next_i128().unwrap() as u128 - 1));
            }
            _ => {
                println!("{}", tree.ask(l, r).count_ones());
            }
        }
    }
}


pub struct SegmentTree {
    tree: Vec<u128>,
    lazy: Vec<u128>,
    size: usize,
}

impl SegmentTree {
    pub fn new(len: usize) -> Self {
        let mut st = SegmentTree {
            tree: vec![0; len << 4],
            lazy: vec![0; len << 4],
            size: len,
        };
        st.build(0, 0, len - 1);
        st
    }

    fn build(&mut self, idx: usize, s: usize, e: usize) {
        if s == e {
            self.tree[idx] = 1;
            return;
        }
        let mid = (s + e) >> 1;
        let lk = idx << 1 | 1;
        let rk = lk + 1;
        self.build(lk, s, mid);
        self.build(rk, mid + 1, e);
        self.tree[idx] = self.tree[lk] | self.tree[rk];
    }
    fn push_down(&mut self, idx: usize) {
        if self.lazy[idx] == 0 {
            return;
        }
        let lk = idx << 1 | 1;
        let rk = lk + 1;
        self.lazy[lk] = self.lazy[idx];
        self.tree[lk] =  self.lazy[idx];
        self.lazy[rk] = self.lazy[idx];
        self.tree[rk] =  self.lazy[idx];
        self.lazy[idx] = 0;
    }

    fn add_re(&mut self, idx: usize, s: usize, e: usize, l: usize, r: usize, v: u128) {
        if l <= s && e <= r {
            self.lazy[idx] = v;
            self.tree[idx] =  v;
            return;
        }
        self.push_down(idx);
        let mid = (s + e) >> 1;
        let lk = idx << 1 | 1;
        let rk = lk + 1;
        if l <= mid  {
            self.add_re(lk, s, mid, l, r, v);
        }
        if mid < r {
            self.add_re(rk, mid + 1, e, l, r, v);
        }
        self.tree[idx] = self.tree[lk] | self.tree[rk];
    }

    pub fn add(&mut self, l: usize, r: usize, v: u128) {
        self.add_re(0, 0, self.size - 1, l, r, v);
    }

    fn ask_re(&mut self, idx: usize, s: usize, e: usize, l: usize, r: usize) -> u128 {
        if l <= s && e <= r {
            return self.tree[idx];
        }
        self.push_down(idx);
        let mid = (s + e) >> 1;
        let lk = idx << 1 | 1;
        let rk = lk + 1;
        let mut result = 0;
        if l <= mid  {
            result |= self.ask_re(lk, s, mid, l, r);
        }
        if mid < r {
            result |= self.ask_re(rk, mid + 1, e, l, r);
        }
        result
    }

    pub fn ask(&mut self,l: usize, r: usize) -> u128 {
        self.ask_re(0, 0, self.size - 1, l, r)
    }
}