n = int(input())
alist = list(map(int,input().split()))
setList = [0] * 100000
def findMax(q, n, s):
    j = 0
    res = 0
    for i in range(n):
        s[q[i]] += 1
        while s[q[i]] > 1:
            s[q[j]] -= 1
            j += 1
        res = max(res, i - j + 1)
    return res

res = findMax(alist, n, setList)
print(res)

邻接表 加 模拟队列

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

using namespace std;

const int N=1e5+10;
const int M=2*N;

int h[N],e[M],ne[M],idx;
int d[N];
int q[N];  // 模拟队列
int n,m;

void Init(){
    memset(h,-1,sizeof h);
    memset(d,-1,sizeof d);
}

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

int bfs(){
    int hh=0,tt=0;
    q[0]=1;
    d[1]=0;

    while(hh<=tt){
        int u=q[hh++];  // 取出 对头
        for(int i=h[u];i!=-1;i=ne[i]){
            int j=e[i];
            if(j==n) return d[u]+1;
            if(d[j]==-1) {   //没有被搜过
                d[j]=d[u]+1;
                q[++tt]=j;
            }
        }
    }
    return -1;
}

int main(){
    Init();
    cin>>n>>m;
    while(m--){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }

    cout<<bfs()<<endl;

    return 0;
}

邻接表 加 stl队列

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

using namespace std;

const int N=1e5+10;
const int M=2*N;

int h[N],e[M],ne[M],idx;
bool st[N];
int n,m;
struct node{
    int id;
    int cnt;
};

void Init(){
    memset(h,-1,sizeof h);
}

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

int bfs(){
    queue<node>q;
    node p;
    p.id=1,p.cnt=0;
    q.push(p);
    st[1]=true;

    while(q.size()){
        node p1=q.front();
        for(int i=h[p1.id];i!=-1;i=ne[i]){
            int j=e[i];
            if(j==n) return p1.cnt+1;
            if(!st[j]) {
                st[j]=true;
                node pp;
                pp.cnt=p1.cnt+1;
                pp.id=j;
                q.push(pp);
            }
        }

        q.pop();
    }

    return -1;
}

int main(){
    Init();
    cin>>n>>m;
    while(m--){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }

    cout<<bfs()<<endl;

    return 0;
}

最长公共子序列

题目描述

出两个长度为 $n$ 的整数序列，求它们的最长公共子序列（LCS）的长度，保证第一个序列中所有元素都不重复。

注意：

• 第一个序列中的所有元素均不重复。
• 第二个序列中可能有重复元素。
• 一个序列中的某些元素可能不在另一个序列中出现。

输入格式

第一行包含一个整数 $n$。

接下来两行，每行包含 $n$ 个整数，表示一个整数序列。

输出格式

输出一个整数，表示最长公共子序列的长度。

数据范围

$1≤n≤10^6$
序列内元素取值范围$ [1,10^6]$。

输入样例1：

5
1 2 3 4 5
1 2 3 4 5

输出样例1：

5

输入样例2：

5
1 2 3 5 4
1 2 3 4 5

输出样例2：

4

思路

最长上升子序列

将最长公共子序列问题转化为最长上升子序列问题，因为其中有一个序列是不重复的，也就是每个元素都唯一，只要将其中的数转化为下标映射，然后对于另一个数组b来说，首先找到在a数组中的下标，然后求出最长上升子序列的长度

代码

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

using namespace std;

const int N = 1e6 + 10;
int q[N], idx[N];

int main()
{
    int n;
    scanf("%d",&n);
    memset(idx,-1,sizeof idx);
    for(int i = 0;i < n;i ++)
    {
        int x;
        scanf("%d",&x);
        idx[x] = i;
    }
    q[0] = -1;
    int tt = 0;
    for(int i = 0;i < n;i ++)
    {
        int x;
        scanf("%d",&x);
        int k = idx[x];
        if(k == -1) continue;
        int l = 0, r = tt;
        // 找到小于k的最大数
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < k) l = mid;
            else r = mid - 1;
        }
        q[r + 1] = k;
        tt = max(tt, r +1);

    }
    printf("%d\n",tt);
    return 0;
}

最大的和

题目描述

给定一个长度为 $n$ 的正整数数列 $a_1,a_2,…,a_n$

初始时，数列中的每个元素要么处于可选状态，要么处于不可选状态。

你可以选择一个长度恰好为 kk 的区间$[i,i+k−1]$，使得 $a_i∼a_{i+k−1}$这 $k$个元素的状态全部变为可选。

请问，在经过此操作后，所有处于可选状态的元素之和最大是多少。

输入格式

第一行包含两个整数 $n$ 和 $k$。

第二行包含 $n$个整数 $a_i$。

第三行包含一个长度为 $n$ 的 $01$序列，如果第 $i$ 个数为 $1$，表示 $a_i$ 的初始状态为可选，如果第 $i$个数为 $0$，表示 $a_i$ 的初始状态为不可选。

输出格式

一行一个整数，表示答案。

数据范围

对于 $30\%$的数据，$1≤k≤n≤1000$
对于 $100\%$ 的数据，$1≤k≤n≤10^5$,$1≤a_i≤10^5$

输入样例1：

3 1
2 5 4
0 0 1

输出样例1：

9

输入样例2：

4 3
10 5 4 7
0 1 1 0

输出样例2：

19

思路

双指针 + 前缀和

首先将为1的元素添加到和中，然后遍历整个数组，如果当前元素不可选，则将他修改为可选加入到和中，然后判断如果当前已经超过窗口m的大小并且之前数不可选，就删除该数，然后取最大值

实现代码

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
int a[N], b[N];

int main()
{
    LL sum = 0;
    int n,m;
    scanf("%d%d",&n,&m);    
    for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
    for(int i = 1;i <= n;i ++) scanf("%d",&b[i]);
    for(int i = 1;i <= n;i ++) if(b[i]) sum += a[i];
    LL res = 0;
    for(int i = 1;i <= n;i ++)
    {
        if(!b[i]) sum += a[i];
        if(i > m && !b[i - m]) sum -= a[i-m];
        res = max(res,sum);
    }
    cout << res << endl;
    return 0;
}

C++

#include <cctype>
#include <iostream>
#include <stack>
#include <unordered_map>
using namespace std;

unordered_map<char, int> isp{
    {'(', 1}, {'*', 5}, {'/', 5}, {'+', 3}, {'-', 3}, {')', 6}
};
unordered_map<char, int> icp{
    {'(', 6}, {'*', 4}, {'/', 4}, {'+', 2}, {'-', 2}, {')', 1}
};

stack<int> nums;
stack<char> ops;

string toRPN(const string& expr) {
    string rpn;
    bool parenthesis = false;
    int i = 0;

    while (i < expr.length()) {
        if (isdigit(expr[i])) {
            while (i < expr.length() && isdigit(expr[i])) {
                rpn += expr[i++];
            }
            rpn += 'n';
        } else {
            char c = expr[i++];
            while (!ops.empty() && isp[ops.top()] >= icp[c]) {
                if (isp[ops.top()] > icp[c]) {
                    rpn += ops.top();
                    ops.pop();
                } else {
                    ops.pop();
                    parenthesis = true;
                }
                if (parenthesis) {
                    break;
                }
            }
            if (parenthesis) {
                parenthesis = false;
                continue;
            }
            ops.push(c);
        }
    }
    while (!ops.empty()) {
        rpn += ops.top();
        ops.pop();
    }

    return rpn;
}

int calcRPN(const string& rpn) {
    int i = 0;

    while (i < rpn.length()) {
        if (isdigit(rpn[i])) {
            int num = 0;
            while (rpn[i] != 'n') {
                num = 10 * num + rpn[i++] - '0';
            }
            nums.push(num);
            ++i;
        } else {
            char c = rpn[i++];
            int rhs = nums.top(); nums.pop();
            int lhs = nums.top(); nums.pop();
            if (c == '+') {
                nums.push(lhs + rhs);
            } else if (c == '-') {
                nums.push(lhs - rhs);
            } else if (c == '*') {
                nums.push(lhs * rhs);
            } else {
                nums.push(lhs / rhs);
            }
        }
    }

    return nums.top();
}

int main() {
    string expr;
    cin >> expr;
    string rpn = toRPN(expr);
    cout << calcRPN(rpn) << endl;

    return 0;
}

题目描述

假设一个单调递增的数组里的每个元素都是整数并且是唯一的。

请编程实现一个函数找出数组中任意一个数值等于其下标的元素。

例如，在数组 [−3,−1,1,3,5] 中，数字 3 和它的下标相等。

样例

输入：[-3, -1, 1, 3, 5]

输出：3
注意:如果不存在，则返回-1。

算法

(二分) $O(logn)$

可以证明nums[i] - i 是单调递增数组，即转化为求数组 nums[i]-i 中 等于0的元素
故可二分查找

C++ 代码1

class Solution {
public:
    int getNumberSameAsIndex(vector<int>& nums) {
        if(nums.empty()) return 0;

        int l = 0, r = nums.size()-1;
        while(l < r){
            int mid = (l + r) >> 1;
            if(nums[mid] - mid < 0)  l = mid + 1;
            else r = mid;
        }
        if(nums[r] != r) return -1;
        return l;
    }
};

C++ 代码2

class Solution {
public:
    int getNumberSameAsIndex(vector<int>& nums) {
        if(nums.empty()) return 0;

        int l = 0, r = nums.size()-1;
        while(l < r){
            int mid = (l + r + 1) >> 1;
            if(nums[mid] - mid > 0) r = mid - 1;
            else l = mid;
        }
        if(nums[r] != r) return -1;
        return l;
    }
};

分析

• 本题可以看成一个动态规划的题目。

• 我们使用f(i)表示从i跳到N的期望长度，边界f(N)=0。最终我们的答案就是f(1)。考虑从i有k条出边，如下图：

• 则事件X满足下式：

$$
X = \frac{1}{k} (w_1 + X_1) + \frac{1}{k} (w_2 + X_2) + … + \frac{1}{k} (w_k + X_k)
$$

• 两边同时求期望可得：

$$
EX = E \big(\frac{1}{k} (w_1 + X_1) + \frac{1}{k} (w_2 + X_2) + … + \frac{1}{k} (w_k + X_k)\big) \\
= \frac{1}{k} (w_1 + EX_1) + \frac{1}{k} (w_2 + EX_2) + … + \frac{1}{k} (w_k + EX_k)
$$

• 因为f(i)=EX，因此有：

$$
f(i) = \frac{1}{k} (w_1 + f(S_1)) + \frac{1}{k} (w_2 + f(S_2)) + … + \frac{1}{k} (w_k + f(S_k))
$$

• 我们可以使用记忆化搜索求解该问题。

代码

• C++

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010, M = 200010;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
int dout[N];  // 每个点的出度
double f[N];  // 记录每个点到N的期望长度

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

double dp(int u) {
    if (f[u] > 0) return f[u];
    f[u] = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        f[u] += (w[i] + dp(j)) / dout[u];
    }
    return f[u];
}

int main() {

    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        dout[a]++;
    }

    memset(f, -1, sizeof f);
    printf("%.2lf", dp(1));

    return 0;
}

三个点儿，被这道题劝退了。。。。

题目描述

最长上升子序列 II
在I的基础上优化时间复杂度

算法

贪心

主要使用的是一个单调队列
贪心的思想是每次都希望使得队列中维护的同长度子序列的末尾值最小
夏季每日一题 3510. 最长公共子序列 里面的视频讲解证明了正确性。

时间复杂度

$$nlogn$$

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int nmax = 1e5 + 10;
int n;
long long q[nmax]; //模拟单调队列
int main()
{
    cin >> n;
    int tt = 0;
    q[0] = -1; // 
    for(int i=0; i<n; i++)
    {
        long long  tempnum;
        scanf("%ld", &tempnum);
        //二分模板1 l==r的时候停在tempnum的右边 所以采用二分模板2， 使得r去-1，让最后l跟r的值指向tempnum左边
        int l = 0, r = tt;
        while(l < r)
        {
            int mid = l + r + 1>> 1;
            if(q[mid] >= tempnum) r = mid - 1; //这个>=要注意，如果加=的话保证在相等的时候l跟r也指在tempnum的左边
            else l = mid;
        }
        q[l+1] = tempnum;
        tt = max(tt, l+1);
    }
    cout << tt;
    return 0;

}

#include <iostream>
using namespace std;

const int N=1e5+10;
int a[N*31][2],s[N],idx;

void Insert(int x)
{
    int p=0;
    for(int i=30; i>=0; i--)
    {
        int u=x>>i&1;
        if(a[p][u]==0)  a[p][u]=++idx;
        p=a[p][u];
    }
}

int Querry(int x)
{
    int p=0,res=0;
    for(int i=30; i>=0; i--)
    {
        int u=x>>i&1;
        if(a[p][!u])
        {
            p=a[p][!u];
            res=res*2+!u;
        }
        else
        {
            p=a[p][u];
            res=res*2+u;
        }
    }
    return res;
}

int main()
{
    int n;
    scanf("%d",&n);

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

参考：yxc算法讲解第二章第二讲视频内容