头像

醉生梦死

西北工业大学




离线:16分钟前


最近来访(1747)
用户头像
我最喜欢学习了捏
用户头像
nwpu
用户头像
kuuga2003
用户头像
折纸人.
用户头像
13520285907
用户头像
acwing_1558
用户头像
z0n3
用户头像
小脸蛋WT
用户头像
Spider
用户头像
烟绯
用户头像
zst_2001
用户头像
lastice
用户头像
彼此不舍ァ不弃
用户头像
Jsss
用户头像
Mamba_Chu
用户头像
百京周杰伦
用户头像
未央灬
用户头像
不死不休
用户头像
ericf
用户头像
Ac过家家


输入输出

OJ在线编程常见输入输出练习场

答案参考本文最后

C++

单行不定长输入

while(cin >> x, cin.get() != '\n')

非字符串多行输入

while(n--)

while(cin >> a >> b)

while(cin >> a >> b, a || b)

字符串多行输入

#include <iostream>     // 标准输入输出
#include <string>           
#include <sstream>      // 输入流

string s;

while(getline(cin, s))  // 空白符分隔的不定行输入
{
    stringstream line(s);

    while(line >> s)
}

while(getline(cin, s))  // 逗号分隔的不定行输入
{
    stringstream line(s);

    while(getline(line, s, ','))
}

cin 可用作条件判断

cin >> n 返回 cin

getline(cin, s) 返回 cin

Python

多行输入

python 输入都是 str 类型, 根据需要用 map 进行批量类型转换

# 定行输入 

for _ in range(int(input())):
    l = list(map(int, input().split()[::]))


# 不定行输入

import sys

for line in sys.stdin.readlines()[::]:
    l = list(map(int, line.split()[::]))

for line in sys.stdin:
    l = line.strip().split(',')     # 非空白符分隔时先把前后空白符去掉(主要是换行符)

input() 返回 str

split() 返回 list

map() 返回 iterator

代码参考

C++

A

#include <iostream>

using namespace std;

int main()
{
    int a, b;

    while(cin >> a >>b)
        cout << a + b << endl;

    return 0;
}

B

#include <iostream>

using namespace std;

int main()
{
    int a, b, n;
    cin >> n;

    while(n--)
    {
        cin >> a >> b;
        cout << a + b << endl;
    }

    return 0;
}

C

#include <iostream>

using namespace std;

int main()
{
    int a, b;

    while(cin >> a >> b, a || b)
        cout << a + b << endl;

    return 0;
}

D

#include <iostream>

using namespace std;

int main()
{
    int n;    
    while(cin >> n, n)
    {
        int x, sum = 0;

        while(n--) cin >> x, sum += x;
        cout << sum << endl;
    }

    return 0;
}

E

#include <iostream>

using namespace std;

int main()
{
    int t, n;
    cin >> t;

    while(t--)
    {
        int x, sum = 0;

        cin >> n;
        while(n--) cin >> x, sum += x;

        cout << sum << endl;
    }

    return 0;
}

F

#include <iostream>

using namespace std;

int main()
{
    int n;
    while(cin >> n)
    {
        int x, sum = 0;

        while(n--) cin >> x, sum += x;
        cout << sum << endl;
    }

    return 0;
}

G

#include <iostream>
#include <string>
#include <sstream>

using namespace std;

int main()
{
    string s;
    while(getline(cin, s))
    {
        int x, sum = 0;
        stringstream line(s);

        while(line >> x) sum += x;
        cout << sum << endl;
    }

    return 0;
}

H

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;

    string s[n];

    for(int i = 0; i < n; i++) cin >> s[i];

    sort(s, s + n);

    for(int i = 0; i < n; i++) cout << s[i] << ' ';

    return 0;
}

I

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <sstream>

using namespace std;

int main()
{
    string s;

    while(getline(cin, s))
    {
        stringstream line(s);

        vector<string> arr;
        while(line >> s) arr.push_back(s);

        sort(arr.begin(), arr.end());

        for(auto &t : arr) cout << t << ' ';
        cout << endl;
    }

    return 0;
}

J

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <sstream>

using namespace std;

int main()
{
    string s;

    while(getline(cin, s))
    {
        stringstream line(s);

        vector<string> arr;

        while(getline(line, s, ',')) arr.push_back(s);

        sort(arr.begin(), arr.end());

        for(int i = 0; i < arr.size(); i++)
        {
            cout << arr[i];
            if(i != arr.size() - 1) cout << ',';
        }
        cout << endl;
    }

    return 0;
}

Python

A

import sys

for line in sys.stdin:
    print(sum(map(int, line.split())))

B

for _ in range(int(input())):
    print(sum(map(int, input().split())))

C

import sys

for line in sys.stdin.readlines()[:-1]:
    print(sum(map(int, line.split())))

D

import sys

for line in sys.stdin.readlines()[:-1]:
    print(sum(map(int, line.split()[1:])))

E

for _ in range(int(input())):
    print(sum(map(int, input().split()[1:])))

F

import sys
for line in sys.stdin:
    print(sum(map(int, line.split()[1:])))

G

import sys

for line in sys.stdin:
    print(sum(map(int, line.split())))

H

input()

print(' '.join(sorted(input().split())))

I

import sys

for line in sys.stdin:
    print(' '.join(sorted(line.split())))

J

import sys

for line in sys.stdin:
    print(','.join(sorted(line.strip().split(','))))



醉生梦死
2个月前

双指针算法模型定义

双指针算法本质剖析: 从起源, 到优化, 到双指针, 到变形

双指针经典例题分析总结

目前分类:

  • 单调性双指针

    $j = f(i)$ 单调性, 主要证明单调性

  • 循环不变双指针

    $(i,j)$ 表示一个循环不变对象, 主要证明循环不变式

二者应该是能够相互转化的

随着题目的增多, 会慢慢发现这两种方法本质上是一样的, 只不过思路不同, 角度不同, 证明的方法不同

单调性双指针

特征: $j = f(i)$ 单调性

类似于偏导数, 固定变量 $i$, 研究 $j$,

视角固定在 $i$ 上, 然后研究 $j$

循环不变双指针

特征: $(i,j)$ 表示循环不变量

类似于全导数, 将变量 $i$ 和 $j$ 放在一起研究

视角放眼全局, 研究各种情况下 $i$ 和 $j$ 的变化

最长连续不重复子序列

解法一: 单调性

$(i,j)$含义:

$(i,j)$ 指代某个区间

对于每个 $i$, $i$ 为区间右端点,

$j$ 表示所有不含重复元素区间 $[j,i]$ 中离 $i$ 最远的左端点

样例:

1 2 2 3 5

$i = 1$ 时, $j = 1$, 区间为 $[1,1]$

$i = 2$ 时, $j = 1$, 区间为 $[1,2]$

$i = 3$ 时, $j = 3$, 区间为 $[3,3]$

$i = 4$ 时, $j = 3$, 区间为 $[3,4]$

$i = 5$ 时, $j = 3$, 区间为 $[3,5]$

答案为所有满足条件 $(i,j)$ 中最长区间的长度, 即区间 $[3,5]$ 的长度 3

单调性证明:

对于 $j = f(i)$, 当 $i$ 递增后, 即 $j^{\prime} = f(i + 1)$

需要说明 $j^{\prime}$ 与 $j$ 的大小关系

假定 $j^{\prime} < j$

根据定义可知 $[j^{\prime},i+1]$ 是不含重复元素的区间

$\therefore$ $[j^{\prime},i]$ 也是不含重复元素的区间

根据 $j = f(i)$ 的定义, 显然 $j^{\prime} \geq j$, 产生矛盾

$\therefore$ $j^{\prime} \geq j$, $j = f(i)$ 单调递增, 符合单调性

遍历方向:

由于 $j = f(i)$ 单调递增, 所以 $j$ 的遍历方向为 $1\rightarrow m$

结果:

所需结果为所有 $(i,j)$ 中最大区间的长度

核心代码:

int res = 0;
for(int i = 0, j = 0; i < n; i++)
{
    cnt[a[i]]++;

    while(j <= i && cnt[a[i]] > 1) cnt[a[j++]]--;

    res = max(res, i - j + 1);
}

$~$

解法二: 循环不变

int res = 0;
cnt[a[0]]++;

for(int i = 0, j = 0; i < n && j <= i;)
{
    if(cnt[a[i]] > 1) cnt[a[j++]]--;
    else
    {
        res = max(res, i - j + 1);
        cnt[a[++i]]++;
    }
}

数组元素的目标和

解法一: 单调性

$(i,j)$含义:

$(i,j)$ 指代 $a_i+b_j$

对于每个 $i$, $j$ 表示满足 $a_i + b_j \leq x$ 的最大 $j$

样例:

a: 1 2 4 7
b: 3 4 6 8 9
x = 6

$i = 1$ 时, $j = 2$, 指代 1 + 4

$i = 2$ 时, $j = 2$, 指代 2 + 4

$i = 3$ 时, $j = 0$

$\dots$

所需结果为所有 $(i,j)$ 中与 x 相等的那个, 即 $(2,2)$

单调性证明:

对于 $j = f(i)$, 当 $i$ 递增后, 即 $j^{\prime} = f(i + 1)$

需要说明 $j^{\prime}$ 与 $j$ 的大小关系

假定 $j^{\prime} > j$

则 $j^{\prime} \geq j + 1$

根据定义可知 $a_i + b_j \leq x$ 和 $a_i + b_{j+1} > x$

则 $a_{i+1} + b_{j^{\prime}} \geq a_i + b_{j+1} > x$

这与 $j^{\prime} = f(i + 1)$ 的含义矛盾

$\therefore$ $j^{\prime} \leq j$, $j = f(i)$ 单调递减, 符合单调性

遍历方向:

由于 $j = f(i)$ 单调递减, 所以 $j$ 的遍历方向为 $m \rightarrow 1$

结果:

所需结果为所有 $(i,j)$ 中与 x 相等的那个

核心代码:

for(int i = 0, j = m - 1; i < n; i++)
{
    while(j >= 0 && a[i] + b[j] > x) j--;

    if(j >= 0 && a[i] + b[j] == x)
        输出答案
}

事实上, 如这个贴子的最后和下面所述, 这道题也可以用循环不变双指针的方法来做

$~$

解法二: 循环不变

for(int i = 0, j = m - 1; i < n && j >= 0;)
{
    if(a[i] + b[j] == x)
        输出答案
    else if(a[i] + b[j] > x) j--;
    else i++;
}

判断子序列

解法一: 单调性

$(i,j)$含义:

$(i,j)$ 指代当前匹配的进度

具体来说,

$i$ 表示 a 序列进度, 即 $[a_1,\dots,a_{i-1}]$ 均已在 b 序列中找到匹配对象, 当前正在寻找 $a_i$ 匹配对象

$j$ 表示在上述前提下尽可能靠左与 $a_i$ 匹配的对象

样例:

a: 1 3 5
b: 1 2 3 4 5

$i = 1$ 时, $j = 1$

$i = 2$ 时, $j = 3$

$i = 3$ 时, $j = 5$

单调性证明:

对于 $j = f(i)$, 当 $i$ 递增后, 即 $j^{\prime} = f(i + 1)$

需要说明 $j^{\prime}$ 与 $j$ 的大小关系

假定 $j^{\prime} \leq j$

则与子序列的定义矛盾

$\therefore$ $j^{\prime} > j$, $j = f(i)$ 严格单调递增

换句话说, 就是显然 $j^{\prime} > j$

遍历方向:

由于 $j = f(i)$ 严格单调递增, 所以 $j$ 的遍历方向为 $1 \rightarrow m$

而且由于是严格单调递增, 所以代码与上面的两道题稍有不同

结果:

所需结果需要判断 $j = f(n)$ 是否合法

核心代码:

for(int i = 0, j = 0; i < n; i++)
{
    while(j < m && a[i] != b[j]) j++;

    if(j < m) j++;  // j = f(i) 严格单调递增的影响
    else
        输出 No
}
输出 Yes

$~$

解法二: 循环不变

for(int i = 0, j = 0; i < n && j < m)
{
    if(a[i] == b[j]) i++;
    j++;
}

if(i == n)
    输出 Yes
else
    输出 No

验证回文串

解法一: 单调性

class Solution {
public:
    bool isPalindrome(string s) {
        for(int i = 0, j = s.size() - 1; i < j; i++)
        {
            if(!isalnum(s[i])) continue;

            while(i < j && !isalnum(s[j])) j--;

            if(i < j && tolower(s[i]) != tolower(s[j])) 
                return false;
            else j--;
        }
        return true;
    }
};

解法二: 循环不变

class Solution {
public:
    bool isPalindrome(string s) {
        for(int i = 0, j = s.size() - 1; i < j;)
        {
            if(isalnum(s[i]) && isalnum(s[j]))
            {
                if(tolower(s[i]) == tolower(s[j])) i++, j--;
                else return false;
            }
            else
            {
                if(!isalnum(s[i])) i++;
                if(!isalnum(s[j])) j--;
            }
        }
        return true;
    }
};

盛最多水的容器

解法一: 单调性

class Solution {
public:
    int maxArea(vector<int>& arr) {
        int res = 0;
        for(int i = 0, j = arr.size() - 1; i < arr.size(); i++)
        {
            res = max(res, (j - i) * min(arr[i], arr[j]));
            while(j > i && arr[j] < arr[i]) 
            {
                j--;
                res = max(res, (j - i) * min(arr[i], arr[j]));
            }
        }
        return res;
    }
};

根据本题经典方法(循环不变)改写

改的时候有点艰难, 换个思路后的代码果然不好写

解法二: 循环不变

class Solution {
public:
    int maxArea(vector<int>& arr) {
        int res = 0;
        for(int i = 0, j = arr.size() - 1; i < j;)
        {
            res = max(res, (j - i) * min(arr[i], arr[j]));

            if(arr[i] <= arr[j]) i++;
            else j--;
        }
        return res;
    }
};

循环不变的证明思路可以参考这篇帖子

前置:

根据 for(int i = 0, j = arr.size() - 1; i < j;)

整个搜索空间呈倒三角形状

搜索空间坐标 $(i,j)$ 含义:

左上角为零点, $i$ 表示行坐标, $j$ 表示列坐标

图片可参考上面那个帖子, 不会画那么好看的动态图

证明:

$(i,j)$ 对应的循环不变式:

以 $(i,j)$ 为右上角顶点的倒三角区域为待搜索空间, 剩余搜索空间为已搜索空间, res 表示已搜索空间中容器的最大储水量

初始化:

$i = 0, j = arr.size() - 1, res = 0$

$(i,j)$ 对应整个搜索空间, 已搜索空间为空, res = 0, 显然成立

保持:

假设某轮循环开始前循环不变式成立

执行循环体

res = max(res, (j - i) * min(arr[i], arr[j]));  // 搜索 (i,j) 点, 更新 res

if(arr[i] <= arr[j]) i++;   // 排除该行的其他点, 证明下述
else j--;                   // 排除该列的其他点

定义 $S_{ij} = (j - i) \times \min(a[i],a[j])$, 即 $(i,j)$ 对应的储水量

若 $a[i] \leq a[j]$:

该行的其他点为 $(i,k), k \in (i,j)$

则 $S_{ik} = (k - i) \times \min(a[i],a[k])$

$\because$ $k < j$

$\therefore$ $k - i < j - i$

$\because$ $a[i] \leq a[j]$

$\therefore$ $\min(a[i],a[j]) = a[i]$

又 $\because$ $\min(a[i],a[k]) \leq a[i]$

$\therefore$ $\min(a[i],a[k]) \leq \min(a[i],a[j])$

$\therefore$ $S_{ik} < S_{ij}$

$\therefore$ 该行的其他点都可以排除掉

同理, $a[i] > a[j]$ 情况下该列的其他点都可以排除掉

$~$

根据 $a[i]$ 与 $a[j]$ 的大小关系可以排除该行或该列的其他点, 又因 $(i,j)$ 已搜索过, 所以该行或该列相当于搜索过

$\therefore$ 在 $i$ 或 $j$ 更新之后, 下一轮循环开始之前, 循环不变式成立

终止:

循环结束时, $i \geq j$, 则整个搜索空间已全部搜索, res 表示整个搜索空间中所有点的最大储水量

颜色分类

循环不变

感觉很不好改编成单调性做法

class Solution {
public:
    void sortColors(vector<int>& arr) {
        for(int i = 0, j = 0, k = 0; i < arr.size(); i++)
        {
            if(arr[i] == 0)
            {
                swap(arr[i], arr[j]);
                swap(arr[j], arr[k]);
                j++, k++;
            }
            else if(arr[i] == 1)
                swap(arr[i], arr[j++]);
        }
    }
};

证明:

$(i,j,k)$ 对应的循环不变式:

$[0,k)$ 全 0, $[k,j)$ 全 1, $[j,i)$ 全 2, $a_i$ 为当前待搜索点, $[0,i)$ 为已排好序区间

初始化:

循环开始前 $i = j = k = 0$,

则区间全为空, 循环不变式成立

保持:

假设某轮循环开始前, 循环不变式成立

执行循环体

if(arr[i] == 0) 
{
    swap(arr[i], arr[j]);
    swap(arr[j], arr[k]);
    j++, k++;
}
else if(arr[i] == 1)
    swap(arr[i], arr[j++]);

会将 $a[i]$ 交换到对应的位置, 且 $(i,j,k)$ 发生相应变化

这段分析并不难, 略过

所以 $(i,j,k)$ 更新之后, 下一轮循环开始之前, 循环不变式成立

终止:

循环结束时, $i = n$, 则说明区间 $[0,n)$ 已排好序, 符合题目要求

三数之和

单调性

两数之和的简单应用

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& arr) {
        sort(arr.begin(), arr.end());

        vector<vector<int>> res;
        for(int i = 0; i < arr.size(); i++)
        {
            if(i && arr[i] == arr[i - 1]) continue;

            for(int j = i + 1, k = arr.size() - 1; j < k; j++)
            {
                if(j > i + 1 && arr[j] == arr[j - 1]) continue;

                while(j < k && arr[k] > -arr[i] - arr[j]) k--;

                if(j < k && arr[k] == -arr[i] - arr[j])
                    res.push_back({arr[i], arr[j], arr[k]});
            }

        }
        return res;
    }
};

去重方式的分析:

关键代码

if(i && arr[i] == arr[i - 1]) continue;     // 对 i 去重

if(j > i + 1 && arr[j] == arr[j - 1]) continue; // 对 j 去重, k 不需要去重

i 来说, 若 $a_i = a_{i+1}$

第一个元素为 $a_i$ 时, $j$ 和 $k$ 要从 $(i,n]$ 中选择

第一个元素为 $a_{i+1}$ 时, $j$ 和 $k$ 要从 $(i+1,n]$ 中选择

$\because$ $a_i = a_{i+1}$ 且明显第一个候选空间 ${a_i,a_j,a_k}$ 包含第二个候选空间 ${a_{i+1},a_j,a_k}$

$\therefore$ 这种情况下要直接跳过

删除有序数组中的重复项

循环不变

// 自己的想法
class Solution {
public:
    int removeDuplicates(vector<int>& arr) {
        int j = 0;
        for(int i = 0; i < arr.size(); i++)
        {
            if(j && arr[i] == arr[j - 1]) continue;
            else arr[j++] = arr[i];
        }
        return j;
    }
};

// y 总的做法
class Solution {
public:
    int removeDuplicates(vector<int>& arr) {
        int j = 0;
        for(int i = 0; i < arr.size(); i++)
        {
            if(i && arr[i] == arr[i - 1]) continue;
            else arr[j++] = arr[i];
        }
        return j;
    }
};



醉生梦死
2个月前

双指针算法本质剖析: 从起源, 到优化, 到双指针, 到变形

双指针经典例题分析总结

双指针算法模型定义

概述

双指针算法概念比较广泛, 只要使用了两个有关联的循环变量, 也许都能叫做双指针算法

分类

根据循环方向的不同, 可以分类为:

  • 同向双指针: 循环变量方向相同
  • 相向双指针: 循环变量方向不同

根据遍历对象的不同, 可以分类为:

  • 同一对象双指针: 两个循环变量在同一对象上遍历
  • 不同对象双指针: 两个循环变量在不同对象上遍历

上述分类方法有点太抽象, 根据实际问题可以这样分类:

  • 快慢指针

常用于链表中

  • 滑动窗口

常用于数组中

  • 同一序列中的相向双指针

如快排

定义

由于双指针算法应用太广泛, 这里狭义地定义一下双指针算法, 以缩小研究对象, 更好地研究问题的解决办法

由于本人水平有限, 这里我并不清楚这种定义方法是否“狭义”, 即是否适用于所有双指针算法

双指针算法:

两个关联的循环变量 $i$ 和 $j$, 下标对 $(i,j)$ 指代某个对象,

其中, $j = f(i)$ 具有单调性, 即随着 $i$ 的递增, $j$ 递增或递减

问题的结果跟对象的属性由对象属性延伸出的某个信息有关

注意, 一般认为 $(i,j)$ 可以表示二重循环中的任一情况,

这里定义的 $(i,j)$ 是上述的子集, 可以认为对于每个 $i$, 都有唯一一个 $j = f(i)$ 与之对应

举例

问题:

给定长度为 n 的序列, 找出最长不含重复元素区间的长度

$(i,j)$含义:

$(i,j)$ 指代某个区间

对于每个 $i$, $i$ 为区间右端点,

$j$ 表示所有不含重复元素区间 $[j,i]$ 中离 $i$ 最远的左端点

样例:

1 2 2 3 5

下标从 1 开始

$i = 1$ 时, $j = 1$, 区间为 $[1,1]$

$i = 2$ 时, $j = 1$, 区间为 $[1,2]$

$i = 3$ 时, $j = 3$, 区间为 $[3,3]$

$i = 4$ 时, $j = 3$, 区间为 $[3,4]$

$i = 5$ 时, $j = 3$, 区间为 $[3,5]$

答案为所有满足条件 $(i,j)$ 中最长区间的长度, 即区间 $[3,5]$ 的长度 3

单调性证明:

对于 $j = f(i)$, 当 $i$ 递增后, 即 $j^{\prime} = f(i + 1)$

需要说明 $j^{\prime}$ 与 $j$ 的大小关系

假定 $j^{\prime} < j$

根据定义可知 $[j^{\prime},i+1]$ 是不含重复元素的区间

$\therefore$ $[j^{\prime},i]$ 也是不含重复元素的区间

根据 $j = f(i)$ 的定义, 显然 $j^{\prime} \geq j$, 产生矛盾

$\therefore$ $j^{\prime} \geq j$, $j = f(i)$ 单调递增, 符合单调性

准确来说 $j = f(i)$ 单调不减, 即非严格单调递增

循环方向:

由于 $j = f(i)$ 单调递增, 所以 $j$ 的遍历方向为 $1\rightarrow m$

代码

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], cnt[N];

int main()
{
    int n;
    cin >> n;

    for(int i = 0; i < n; i++) cin >> a[i];

    int res = 0;
    for(int i = 0, j = 0; i < n; i++)
    {
        cnt[a[i]]++;

        while(j <= i && cnt[a[i]] > 1) cnt[a[j++]]--;

        res = max(res, i - j + 1);  // 跳出 while 循环后的 j 就是定义中对应 i 的那个 j, 可以用来筛选最终结果
    }

    cout << res << endl;

    return 0;
}



醉生梦死
2个月前

双指针算法模型定义

双指针经典例题分析总结

双指针算法本质剖析: 从起源, 到优化, 到双指针, 到变形

1. 问题

已知升序数组 $a$ 和 $b$ , 给定目标值 $x$

求出满足 $a_i + b_j = x$ 的下标数对 $(i,j)$

2. y 总做法简单回顾

步骤:

  1. 先用暴力做法
  2. 再找单调性优化为双指针

暴力做法 $O(nm)$

枚举所有情况

for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
        if(a[i] + b[j] == x)
            输出答案

双指针 $O(n+m)$

寻找单调性进行优化

尽管 $(i,j)$ 表示 $nm$ 种情况中的任一情况

这里还是定义了另一种含义:

$j = f(i):$ 对于每个 $i$, $j$ 表示满足 $a_i + b_j \geq x$ 的最小 $j$

由于两个数组是升序的

所以在 $i$ 递增的时候, 发现 $j$ 是递减的(准确来说是单调不增)

$~$

举例来说:

a: 1 2 4 7
b: 3 4 6 8 9
x = 6

下标从 1 开始

$i = 1$ 时, 满足条件的 $j$ 为 3

$i = 2$ 时, 满足条件的 $j$ 为 2

$i = 3$ 时, 满足条件的 $j$ 为 1

$i = 4$ 时, 满足条件的 $j$ 为 1

$~$

总结, 在 $i$ 递增的时候, $j$ 单调不增, 满足单调性

双指针代码

for(int i = 1, j = m; i <= n; i++)
{
    while(j >= 1 && a[i] + b[j] > x) j--;   // 这里实际上使用 ai + bj <= x 来做划分
    if(j >= 1 && a[i] + b[j] == x)
        输出答案
}

思考

对于每个 $i$, 令 $j$ 表示满足 $a_i + b_j \geq x$ 的最小 $j$

提问: 为什么 $j$ 要这么定义 ?

答: 因为在 $i$ 固定的前提下, 如此定义的 $j$ 最有可能满足 $a_i + b_j = x$

只需判断这一次, 就相当于判断了 $i$ 固定情况下 $j$ 的所有情况

$~$

提问: 为什么不用 $\leq$ ?

答: 可以用 $\leq$ , 这里使用哪个都不影响分析, 因为这里的分析带一点模糊性

实际上 $j$ 的具体定义为: 对于每个 $i$, 最有可能满足 $a_i + b_j = x$ 的 $j$

再具体来说, 有两种情况:

  1. $j$ 表示满足 $a_i + b_j \geq x$ 的最小 $j$
  2. $j$ 表示满足 $a_i + b_j \leq x$ 的最大 $j$

$~$

这里指出 y 总讲解时一个不严谨的地方:

y 总在分析时用的 $\geq$, 但在代码中却用的 $\leq$, 前后不一致

所以你会在上面的举例分析中看到与视频中不一样的结果

3. 前置

定义

数组 a 元素 $a_1 \; a_2 \; \dots \; a_n$

数组 b 元素 $b_1 \; b_2 \; \dots \; b_m$

$(i,j)$ 表示下标对 $(i,j)$, 有时根据上下文表示 $a_i + b_j$

单调性/同向性

单调性和同向性应该是同一样东西, 我记得 y 总在别的视频里叫过同向性

对下标 $[1..n]$ 有两种遍历方向:

for(int i = 1; i <= n; i++)
    ...

for(int i = n; i >= 1; i--)
    ...

双指针算法的同向性

对循环变量 $i$ 和 $j$,

遍历 $i$ 时, $j$ 遍历方向不变

解释:

  1. $i$ 和 $j$ 往往只初始化一次
  2. $i$ 和 $j$ 遍历方向不改变

例:

for(int i = 1, j = 1; i <= n; i++)
    while(...) j++;

简单分析

找到 $(i,j)$ 和 $x$ 相等

其中, $i \in [1,n]$, $j \in [1,m]$

则需要找到 $(i,j) \in [1,n] \times [1,m]$ 与 $x$ 相等

笛卡尔积 $[1,n] \times [1,m]$ 共 $mn$ 种情况

4. 剖析

性质:

  • 数组 a 升序

  • 数组 b 升序

剖析过程:

  1. 枚举-利用 0 条性质
  2. 枚举优化-利用 1 条性质
  3. 双指针-利用 2 条性质
  4. 变形-问题等价变形后的双指针做法

起源: 枚举 $O(nm)$

最简单的解决办法就是枚举 $(1,1) \; \dots \; (i,j) \; \dots \; (n,m)$ 所有情况, 挨个判断是否与 $x$ 相等

for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
        if(a[i] + b[j] == x)
            输出答案

总结:

  • 并未跳过任何元素
  • 并未利用任何性质进行优化
  • 尽管 $i$ 和 $j$ 的遍历方向不变, 但不算双指针同向性

枚举优化 $O(nm)$

优化方法:

对于每个 $i$, 找到最有可能满足 $a_i + b_j = x$ 的 $j$, 然后进行判断

for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
    {
        if(a[i] + b[j] == x)        
            输出答案
        else if(a[i] + b[j] > x)    // 优化
            break;
    }

优化部分跳过了元素 $(i,j+1 \sim m)$

$~$

对代码做一个等价变形

$j$ 遍历方向: $1 \rightarrow m$

for(int i = 1; i <= n; i++)
{
    int j = 1;
    while(j <= m && a[i] + b[j] < x) j++;   // 划分为 < x 和 >= x 两部分

    if(j <= m && a[i] + b[j] == x)  // j 表示满足 ai + bj >= x 的最小 j
        输出答案
}

事实上, $j$ 还可以换个遍历方向

$j$ 遍历方向: $m \rightarrow 1$

for(int i = 1; i <= n; i++)
{
    int j = m;
    while(j >= 1 && a[i] + b[j] > x) j--;   // 划分为 > x 和 <= x 两部分

    if(j >= 1 && a[i] + b[j] == x)  // j 表示满足 ai + bj <= x 的最大 j
        输出答案
}

总结:

  • 利用了数组 b 升序的性质
  • 跳过了部分元素, 减少了循环次数
  • 尽管进行了部分优化, 但时间复杂度依然是 $O(nm)$
  • 尽管 $i$ 和 $j$ 的遍历方向不变, 但依然不算双指针同向性

双指针 $O(n+m)$

分析:

首先确定 $i$ 的遍历方向: $1 \rightarrow n$ 或 $n \rightarrow 1$

事实上, 选哪个都可以,

但由于习惯使然, 我们往往选用 $1 \rightarrow n$

for(int i = 1; i <= n; i++)
    ...

然后确定 $j$ 的遍历方向: $1 \rightarrow m$ 或 $m \rightarrow 1$

$~$

若 $j: 1 \rightarrow m$

for(int i = 1, j = 1; i <= n; i++)
{
    while(j <= m && a[i] + b[j] < x) j++;

    if(j <= m && a[i] + b[j] == x)
        输出答案
}

对比上一部分的代码

for(int i = 1; i <= n; i++)
{
    int j = 1;
    while(j <= m && a[i] + b[j] < x) j++;

    if(j <= m && a[i] + b[j] == x)  
        输出答案
}

分析:

某一时刻, 对处于循环中的 $(i,j)$:

  • 若 $(i,j) = x$

    则找到答案

  • $(i,j) < x$, 执行 j++

    则跳过了元素 $(i+1 \sim n,j)$

    但由于数组 a 升序, 这些元素递增, 不能判断与 $x$ 的大小关系, 显然不能跳过

  • $(i,j) > x$, 执行 i++

    显然 $(i,j-1) < x$

    跳过了元素 $(i,j+1 \sim m)$ 和 $(i+1,1 \sim j-1)$

    因为双指针同向性, i++ 时的 j 不可能为 [1..j-1] 里的值

    $(i,j+1 \sim m)$ 显然大于 $x$, 可跳过

    $(i+1,1 \sim j-1)$ 与 $x$ 的关系不确定, 不能被跳过

$\therefore$ $j$ 的遍历方向不能为 $1 \rightarrow m$

如果按 y 总的方法来分析, 会比较好理解一些, 但可能不太具体

若 $j: m \rightarrow 1$

for(int i = 1, j = m; i <= n; i++)
{
    while(j >= 1 && a[i] + b[j] > x) j--;   

    if(j >= 1 && a[i] + b[j] == x)
        输出答案
}

对比上一部分的代码

for(int i = 1; i <= n; i++)
{
    int j = m;
    while(j >= 1 && a[i] + b[j] > x) j--;   

    if(j >= 1 && a[i] + b[j] == x)  
        输出答案
}

分析:

某一时刻, 对处于循环中的 $(i,j)$:

  • 若 $(i,j) = x$

    则找到答案

  • $(i,j) > x$, 执行 j--

    跳过了元素 $(i+1 \sim n,j)$

    $\because$ 数组 a 升序, 这些元素递增, 则显然都 $> x$

    $\therefore$ 这些元素能够跳过

  • $(i,j) < x$, 执行 i++

    显然 $(i,j+1) > x$

    跳过了元素 $(i, 1 \sim j-1)$ 和 $(i+1, j+1 \sim m)$

    $(i, 1 \sim j-1)$ 显然小于 $x$, 可跳过

    $(i+1, j+1 \sim m)$ 显然大于 $x$, 可跳过

    利用了数组 a 和 b 升序这 2 条性质

所以若 $i$ 遍历方向为 $1 \rightarrow n$ 且 $j$ 遍历方向为 $m \rightarrow 1$ 时能够满足双指针同向性的要求

总结:

  • 利用了数组 a 和数组 b 升序的性质
  • 利用 $j = f(i)$ 的单调性跳过了大量元素进行优化

顺带一提 $i$ 的遍历方向为 $n \rightarrow 1$ 时的代码

此时 $j$ 的遍历方向需要为 $1 \rightarrow m$

for(int i = n, j = 1; i >= 1; i--)
{
    while(j <= m && a[i] + b[j] < x) j++;

    if(j <= m && a[i] + b[j] == x)
    {
        cout << i << ' ' << j << endl;
        return 0;
    }
}

思考

提问: 为什么要确定 $i$ 的遍历方向 ?

答: 事实上, 这个问题的关键不在于 $i$ 的遍历方向是什么, 而是要把 $i$ 给固定下来

在研究多因素问题时, 往往会固定其余因素, 研究单一因素对问题的影响

例如在微积分中, 研究多元函数的导数问题时, 会把其余变量看作常数, 对单一变量进行求导, 研究该单一变量对结果的影响, 这就是偏导数的概念

双指针问题也一样, 双指针意味着有两个循环变量, 即 $i$ 和 $j$

由于习惯使然, 往往会先固定 $i$, 再研究 $j$ 对问题的影响

$i$ 的遍历方向对结果往往没有影响, 而 $j$ 遍历方向对结果的影响是根据 $i$ 变化的, 一般是对称变化

变形 $O(n+m)$

原题:

已知升序数组 $a$ 和 $b$ , 给定目标值 $x$

求出满足 $a_i + b_j = x$ 的下标数对 $(i,j)$

变形题目:

给定矩阵 A, 从左到右和从上到下都递增, 寻找是否存在元素 x, 并返回下标

则可以定义矩阵元素 $A_{ij} = a_i + b_j$ 将原题转化为该题

leetcode 原题搜索二维矩阵 II

上一部分的分析思路就来自于这道题

$~$

这道题尽管是双指针做法, 但个人觉得并不算经典的双指针:

  • 将 $i$ 和 $j$ 放在平等地位看待, 并不利于分析
  • 未能总结一个做题模式
  • 升序性质的利用并不经典
  • 但是作为上一部分的图画分析会很形象, 具体参考 leetcode 这道题 两数之和 II - 输入有序数组 的分析
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], b[N];

int main()
{
    int n, m, x;
    cin >> n >> m >> x;

    for(int i = 0; i < n; i++) cin >> a[i];
    for(int j = 0; j < m; j++) cin >> b[j];

    for(int i = 0, j = m - 1; i < n && j >= 0;)
    {
        if(a[i] + b[j] == x)
        {
            cout << i << ' ' << j << endl;
            return 0;
        }
        else if(a[i] + b[j] > x) j--;
        else i++;
    }

    return 0;
}

分析方法可参考双指针经典例题分析总结中的第5道题

5. 总结

按照双指针算法模型定义中的定义, 对本题做个总结

$(i,j)$含义:

$(i,j)$ 指代 $a_i+b_j$

对于每个 $i$, $j$ 表示满足 $a_i + b_j \leq x$ 的最大 $j$

样例:

a: 1 2 4 7
b: 3 4 6 8 9
x = 6

$i = 1$ 时, $j = 2$, 指代 1 + 4

$i = 2$ 时, $j = 2$, 指代 2 + 4

$i = 3$ 时, $j = 0$

$\dots$

答案为所有满足条件 $(i,j)$ 中与 x 相等的那个, 即 $(2,2)$

下标从 1 开始

单调性证明:

对于 $j = f(i)$, 当 $i$ 递增后, 即 $j^{\prime} = f(i + 1)$

需要说明 $j^{\prime}$ 与 $j$ 的大小关系

假定 $j^{\prime} > j$

则 $j^{\prime} \geq j + 1$

根据定义可知 $a_i + b_j \leq x$ 和 $a_i + b_{j+1} > x$

则 $a_{i+1} + b_{j^{\prime}} \geq a_i + b_{j+1} > x$

这与 $j^{\prime} = f(i + 1)$ 的含义矛盾

$\therefore$ $j^{\prime} \leq j$, $j = f(i)$ 单调递减, 符合单调性

准确来说 $j = f(i)$ 单调不增, 即非严格单调递减

循环方向:

由于 $j = f(i)$ 单调递减, 所以 $j$ 的遍历方向为 $m \rightarrow 1$

代码:

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], b[N];

int main()
{
    int n, m, x;
    cin >> n >> m >> x;

    for(int i = 0; i < n; i++) cin >> a[i];
    for(int j = 0; j < m; j++) cin >> b[j];

    for(int i = 0, j = m - 1; i < n; i++)
    {
        while(j >= 0 && a[i] + b[j] > x) j--;

        if(j >= 0 && a[i] + b[j] == x)
        {
            cout << i << ' ' << j << endl;
            return 0;
        }
    }

    return 0;
}


分享 题库

醉生梦死
9个月前

输入输出

牛客输入输出练习

数据结构

线性结构

堆排序

验证栈序列

表达式求值

单调栈

单调栈

单调队列

滑动窗口

非线性结构

并查集

连通块中点的数量

食物链

字典树

Trie字符串统计

最大异或对

哈希表

模拟散列表

字符串哈希

基础算法

快速排序

归并排序

逆序对的数量

前缀和与差分

子矩阵的和

差分

差分矩阵

高精度

高精度加法

高精度减法

高精度乘法

高精度除法

二分

数的范围

$~$

搜索旋转排序数组

寻找峰值

找到 K 个最接近的元素

寻找旋转排序数组中的最小值 II

寻找两个正序数组的中位数

找出第 K 小的数对距离

双指针

最长连续不重复子序列

数组元素的目标和

判断子序列

$~$

两数之和 II - 输入有序数组

DFS

n 皇后

树的重心

红与黑

马走日

单词接龙

分成互质组

小猫爬山

数独

木棒

生日蛋糕

加成序列

送礼物

$~$

二叉树中的列表

克隆图

二叉树的最近公共祖先

二叉树的序列化与反序列化

太平洋大西洋水流问题

找到最终的安全状态

课程表 II

组合总和

子集 II

活字印刷

边界着色

BFS

八数码

城堡问题

山峰和山谷

迷宫问题

武士风度的牛

抓住那头牛

矩阵距离

魔板

电路维修

字串变换

第K短路

八数码

拓扑排序

有向图的拓扑序列

最短路

dijkstra

Dijkstra求最短路 I

Dijkstra求最短路 II

spfa

spfa求最短路

spfa判断负环

floyd

Floyd求最短路

最小生成树

Kruskal算法求最小生成树

二分图

染色法判定二分图

二分图的最大匹配/匈牙利算法

数学

质数

试除法判定质数

分解质因数

筛质数

约数

试除法求约数

约数个数

约数之和

欧几里得

最大公约数

快速幂

快速幂

序列的第k个数

越狱

斐波那契前 n 项和

组合数

求组合数 I

动态规划

路径/记忆化搜索

方格取数

传纸条

$~$

统计所有可行路径

出界的路径数

最大得分的路径数目

组合

宠物小精灵之收服

二维费用的背包问题

潜水员

机器分配

背包问题求方案数

整数划分

背包问题求具体方案

金明的预算方案

能量石

多重背包问题 II

多重背包问题 III

混合背包问题

$~$

盈利计划

子序列

最长上升子序列

最长上升子序列 II

最长公共子序列

最短编辑距离

登山

合唱队形

友好城市

最大上升子序列和

拦截导弹

导弹防御系统

最长公共上升子序列

$~$

最低加油次数

鸡蛋掉落

组合总和 Ⅳ

目标和

下降路径最小和 II

最长有效括号

交错字符串

扰乱字符串

区间

环形石子合并

能量项链

加分二叉树

凸多边形的划分

棋盘分割

$~$

合并石头的最低成本

状态机

股票买卖 IV

股票买卖 V

$~$

带维度单串 dp[i][k]

安排邮筒

通配符匹配

正则表达式匹配

状态压缩

蒙德里安的梦想

小国王

炮兵阵地

最短Hamilton路径

毕业旅行问题

树形

没有上司的舞会

有依赖的背包问题

树的最长路径

树的中心

数字转换

二叉苹果树

战略游戏

皇宫看守

$~$

博弈论

Nim游戏

台阶-Nim游戏

集合-Nim游戏

拆分-Nim游戏

贪心

区间合并

区间选点

最大不相交区间数量

区间分组

区间覆盖

货仓选址

耍杂技的牛

$~$

最大子数组和

跳跃游戏

跳跃游戏 II




醉生梦死
9个月前

问题

给定一个正整数 n, 将其分为若干正整数之和, 问有多少种分法 ?

$n = n_1+ n_2 + \dots + n_k, n_1 \geq n_2 \geq \dots \geq n_k$

动态规划分析

状态定义

动态规划的状态定义需要做到:

  1. 能够部分或完全描述出问题的含义, 对此题而言就是上述表达式
  2. 并且能够通过状态迁移将当前问题划分为一些相同类型的子问题

状态

总和 $n$ 与最大数 $n_1$

由于存在关键要素: 整数 n排序

1. 描述问题含义

我们可以用 $n$最大数 这两个要素来描述问题

即: $f[n][n_1]$ 中 $n$ 表示总和, $n_1$ 表示最大的那个数

$f[n][n_1]$ 表示其分法的数量, 那么将所有的 $f[n][n_1], 1 \leq n_1 \leq n$ 累加起来就是 $n$ 的分法数量

2. 划分出相同类型子问题

$f[n][n_1]$ 的含义确定下来后, 就可以考虑如果划分子问题了

首先, 根据 $n$ 和 $n_1$, 我们能够算出剩下的数的大小为 $n - n_1$

那么, 我们就可以通过枚举总和为 $n - n_1$ 时最大的数 $n_1’$ 来确定子问题了

此时子问题为 $f[n - n_1][n_1’]$

$\therefore f[n][n_1] = \sum f[n - n_1][n_1’] \qquad n_1’\in [1, \min {n - n_1, n_1}]$

3. 代码实现

时间复杂度 $O(n^3)$

#include <iostream>

using namespace std;

const int N = 1010, MOD = 1e9 + 7;

int n, f[N][N];

int main()
{
    cin >> n;
    f[0][0] = 1;

    for(int i = 1; i <= n; i++)         // 总和 n
        for(int j = 0; j <= i; j++)     // 最大数 n1
            for(int k = 0; k <= min(i - j, j); k++)     // n - n1 的最大数 n1'
                f[i][j] = (f[i][j] + f[i - j][k]) % MOD;

    int res = 0;
    for(int j = 1; j <= n; j++)         // 累加f[n][n1] n1 属于 [1, n] 区间
        res = (res + f[n][j]) % MOD;
    cout << res << endl;

    return 0;
}

总和 $n$ 与最小数 $n_k$

1. 描述问题含义

同样地, 我们也可以用总和 $n$ 与最小数 $n_k$ 来描述问题

即 $f[n][n_k]$ 表示总和为 $n$, 最小数为 $n_k$ 的分法数量

2. 划分出相同类型子问题

同样地, 子问题的总和为 $n - n_k$, 我们可以枚举其最小数 $n_k’$ 来确定子问题

子问题为 $f[n - n_k][n_k’]$

$\therefore f[n][n_k] = \sum f[n - n_k][n_k’] \qquad n_k’\in [n_k, n - n_k]$

3. 代码实现

时间复杂度 $O(n^3)$

#include <iostream>

using namespace std;

const int N = 1010, MOD = 1e9 + 7;

int n, f[N][N];

int main()
{
    cin >> n;

    for(int i = 0; i <= n; i++) f[i][i] = 1;    // 由于 f[i][i] 没有方法通过下面的代码进行状态转移得到正确的值 1, 于是就需要将其设置为初始状态, 手动赋值

    for(int i = 1; i <= n; i++)         // 总和 n
        for(int j = 0; j <= i; j++)     // 最小数 nk
            for(int k = j; k <= i - j; k++)     // n - nk 的最小数 nk'
                f[i][j] = (f[i][j] + f[i - j][k]) % MOD;

    int res = 0;
    for(int j = 1; j <= n; j++)         // 累加f[n][nk] nk 属于 [1, n] 区间
        res = (res + f[n][j]) % MOD;
    cout << res << endl;

    return 0;
}

总和 $n$ 与数的个数 k

1. 描述问题含义

考虑用总和 $n$ 与数的个数 k 是否可行

即 $f[n][k]$ 表示总和 $n$ 由 $k$ 个数累加而成的分法数量

2. 划分出相同类型子问题

巧妙的分类讨论:

根据最小数 $n_k$ 是否为 1 进行分类讨论

case1: $n_k = 1$

那么剩下数的总和为 $n - 1$, 个数为 $k - 1$

即子问题为 $f[n - 1][k - 1]$

case2: $n_k \neq 1$

那么可以通过等价变换转换为等价的子问题:

$\because n_k \neq 1$

$\therefore n_1 \geq n_2 \geq \dots \geq n_k > 1$

$\therefore n_1 - 1 \geq n_2 - 1 \geq \dots \geq n_k - 1 > 0$

于是问题可以转化为: 总和为 $n - k$, 数的个数为 $k$ 的子问题

即 $f[n - k][k]$

$\therefore f[n][k] = f[n - 1][k - 1] + f[n - k][k]$

3. 代码实现

时间复杂度 $O(n^2)$

#include <iostream>

using namespace std;

const int N = 1010, MOD = 1e9 + 7;

int n, f[N][N];

int main()
{
    cin >> n;

    f[0][0] = 1;
    for(int i = 1; i <= n; i++)         // 总和 n
        for(int j = 1; j <= i; j++)     // 个数 k
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % MOD;

    int res = 0;
    for(int j = 1; j <= n; j++)         // 累加f[n][k]
        res = (res + f[n][j]) % MOD;

    cout << res << endl;

    return 0;
}

物品个数 n 与总和 n

上述三种状态定义我们都是站在一个已经分好的角度来描述的

已经分好的角度指定义的第二维度都是与 $n_1, n_2, \dots, n_k$ 直接相关的

1. 抽象模型

下面, 我们将站在待选集合 ${1, 2, \dots, n}$ 的角度来描述状态

我们能够这样做的原因是该问题模型可以抽象为组合模型

因为 $n$ 的划分不要求次序, 即 $3 = 1 + 2$ 与 $3 = 2 + 1$ 是同一个分法

2. 具体模型

抽象出组合模型后, 我们可以考虑背包解法

物品: 待选集合 ${1, 2, \dots, n}$ 的元素

个数: 每个物品可以用任意次, 于是考虑完全背包解法

体积: $n$

状态: 分法的数量

初始化: 要求体积恰好用完, 则 $f[0][0] = 1, f[0][j] = 0$

3. 代码实现

时间复杂度 $O(n^2)$

#include <iostream>

using namespace std;

const int N = 1010, MOD = 1e9 + 7;

int n, f[N][N];

int main()
{
    cin >> n;

    f[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= n; j++)
            if(j >= i)
                f[i][j] = (f[i - 1][j] + f[i][j - i]) % MOD;
            else 
                f[i][j] = f[i - 1][j];

    cout << f[n][n] << endl;

    return 0;
}



醉生梦死
10个月前

标准做法, 和自己的思路没本质区别

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 3;

int n, m;

void multi(int c[], int a[][N], int b[])
{
    int res[N] = {0};
    for(int i = 0; i < N; i++)
        for(int k = 0; k < N; k++)
            res[i] = (res[i] + (LL)a[i][k] * b[k]) % m;
    memcpy(c, res, sizeof res);
}

void multi(int c[][N], int a[][N], int b[][N])
{
    int res[N][N] = {0};
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            for(int k = 0; k < N; k++)
                res[i][j] = (res[i][j] + (LL)a[i][k] * b[k][j]) % m;
    memcpy(c, res, sizeof res);
}

void quick_mi(int a[][N], int k, int f[])
{
    while(k)
    {
        if(k & 1) multi(f, a, f);
        multi(a, a, a);
        k >>= 1;
    }
}

int main()
{
    cin >> n >> m;
    int f[N] = {1, 1, 1};
    int a[N][N] = {
        {0, 1, 0},
        {1, 1, 0},
        {0, 1, 1}
    };

    quick_mi(a, n - 1, f);

    cout << f[2] << endl;

    return 0;
}

自己的做法, 构造矩阵乘法, 然后用矩阵快速幂

#include <iostream>
#include <vector>

using namespace std;

typedef long long LL;

int n, m;

void multi(int a[][3], int b[][3], int p)
{
    int res[3][3] = {0};
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            for(int k = 0; k < 3; k++)
                res[i][j] = (res[i][j] + (LL)a[i][k] * b[k][j]) % p;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            a[i][j] = res[i][j];
}

vector<vector<int>> quick_mi(int a[][3], int k, int p)
{
    int arr[3][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
    while(k)
    {
        if(k & 1) multi(arr, a, p);
        multi(a, a, p);
        k >>= 1;
    }
    vector<vector<int>> res(3, vector<int>(3));
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            res[i][j] = arr[i][j];
    return res;
}

int main()
{
    cin >> n >> m;
    int a[3][3] = {{1, 1, 0}, {1, 0, 0}, {1, 1, 1}};

    if(n < 2) cout << 1 << endl;
    else 
    {
        auto res = quick_mi(a, n - 2, m);
        cout << ((LL)res[2][0] + res[2][1] + res[2][2] * 2) % m << endl;
    }

    return 0;
}


活动打卡代码 AcWing 1290. 越狱

醉生梦死
10个月前
#include <iostream>

using namespace std;

typedef long long LL;

const int MOD = 1e5 + 3;

LL quick_mi(LL a, LL k)
{
    LL res = 1;
    while(k)
    {
        if(k & 1) res = res * a % MOD;
        a = a * a % MOD;
        k >>= 1;
    }
    return res;
}

int main()
{
    LL m, n;
    cin >> m >> n;

    int res = (quick_mi(m % MOD, n) - m % MOD * quick_mi((m - 1) % MOD, n - 1) % MOD + MOD) % MOD;
    cout << res << endl;

    return 0;
}



醉生梦死
10个月前
#include <iostream>

using namespace std;

typedef long long LL;

const int MOD = 200907;

LL quick_mi(int a, int k)
{
    LL res = 1;
    while(k)
    {
        if(k & 1) res = (LL) res * a % MOD;
        a = (LL) a * a % MOD;
        k >>= 1;
    }
    return res;
}

int main()
{
    int T;
    cin >> T;

    while(T--)
    {
        int a, b, c, k;
        cin >> a >> b >> c >> k;
        if(2 * b == a + c)
            cout << (a + (LL)(k - 1) * (b - a)) % MOD << endl;
        else
            cout << (LL)a * quick_mi(b / a, k - 1) % MOD << endl;
    }   
    return 0;
}


活动打卡代码 AcWing 1077. 皇宫看守

醉生梦死
11个月前

状态机

f[u][0] : u 没放, u 被父节点看到
f[u][1] : u 没放, u 被子节点看到
f[u][2] : u 放了

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

using namespace std;

const int N = 2000, M = 2 * N, INF = 1e9;

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

int f[N][3];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u, int father)
{
    f[u][0] = 0, f[u][2] = w[u];

    for(int i = h[u]; ~i; i = ne[i])
    {
        int v = e[i];
        if(v == father) continue;

        dfs(v, u);

        f[u][0] += min(f[v][1], f[v][2]);
        f[u][2] += min({f[v][0], f[v][1], f[v][2]});
    }

    f[u][1] = INF;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int v = e[i];
        if(v == father) continue;
        f[u][1] = min(f[u][1], f[v][2] + f[u][0] - min(f[v][1], f[v][2]));
    }
}

int main()
{
    cin >> n;

    memset(h, -1, sizeof h);
    for(int i = 0; i < n; i++)
    {
        int a, b, t;
        cin >> a;
        cin >> w[a] >> t;
        while(t--)
        {
            cin >> b;
            add(a, b), add(b, a);
        }
    }

    dfs(1, -1);
    cout << min(f[1][1], f[1][2]) << endl;

    return 0;
}