题目描述

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

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

例如，在数组 [−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算法讲解第二章第二讲视频内容

两种方法

法1：双指针

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, k;
int a[N];
bool b[N];
LL sum1 = 0;
LL sum2 = 0,maxSum2 = 0;
int main(){
    scanf("%d %d", &n, &k);
    for(int i = 0; i < n; i++){
        scanf("%d",&a[i]);
    }
    for(int i = 0; i < n; i++){
        scanf("%d",&b[i]);
        if(b[i]) sum1 += a[i];
    }
    for(int i = 0,j = 0; i < n; i++){
        if(!b[i]) sum2 += a[i];
        while(j < i && i - j + 1 > k){
            if(!b[j]) sum2 -= a[j];
            j++;
        }
        maxSum2 = max(maxSum2, sum2);
    }
    printf("%lld",maxSum2 + sum1);



    return 0;
}

法2：一个前缀和

#include<bits/stdc++.h>
using namespace std;


typedef long long LL;
const int N = 100010;
LL presum[N];
int a[N], b[N];
int n, k;
LL sum1 = 0,sum2 = 0, maxSum2 = 0;
int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++){
        cin >> b[i];
        if(b[i]) sum1 += a[i];
        presum[i] = presum[i - 1] + a[i] * (1 - b[i]);
    }
    // for(int i = 1; i <= n ; i++){
    //     cout<<presum[i]<<" ";
    // }
    for(int i = k; i <= n; i++){
        sum2 = presum[i] - presum[i - k];
        maxSum2 = max(maxSum2, sum2);
    }
    cout<<maxSum2 + sum1;
    return 0;
}

初看这个题，校检值可以排序后枚举最前最后来计算
但怎么得到计算的范围
我们可以用二分来解决 二分枚举区间范围 然后计算 然后恭喜你TLE
用倍增 每次枚举 排好序计算如果满足条件就递增距离就乘以二
然后区间长度加上他 直到k+1是枚举的递增的长度为len时 刚好不满足校检值小于t
那么就从k开始
枚举递增len的一半直到不能枚举
这样你就能AC了 /kk
注意longlong 不开longlong见祖宗

#include <bits/stdc++.h>

using namespace std ;

typedef long long LL ;

inline LL read(register LL x = 0 , register char ch = getchar() , register bool f = false ) {
    for (;!isdigit(ch);ch = getchar()) f |= (ch == '-') ;
    for (;isdigit(ch);ch = getchar()) x = (x<<1) + (x<<3) + (ch^48) ; return f ? ~ x + 1 : x ;
}

const LL N = 5e5 + 5 ;

LL T ;
LL n , m , t , ans ;
LL a[N] , res[N] , b[N] ;

LL qpow(LL x,LL y){
    LL ans = 1 ; for (; y ; y >>= 1 , x = x*x ) if(y&1) ans *= x ; return ans ;
}

void merge(LL l,LL mid,LL r) {
    LL x = l , y = mid ;
    for (LL i = l ; i <= r ; ++i ) {
        if (y > r || x < mid && res[x] <= res[y]) b[i] = res[x ++] ;
        else b[i] = res[y ++] ;
    }
}

bool chk(LL l,LL mid,LL r) {
    for (LL i = mid ; i <= r ; ++i ) res[i] = a[i] ;
    sort(res + mid,res + r + 1) ;
    merge(l,mid,r) ;
    LL kk = 0 ;
    for (LL i = 0 ; i < (r - l + 1) / 2 && i < m ; ++i ) kk += (LL)qpow(b[r - i] - b[l + i],2) ;
    if (kk > t) return false ;
    else {
        for(LL i = l ; i <= r ; ++i) res[i] = b[i] ;
        return true ;
    }
}
void solve(LL l,LL r) {
    res[l] = a[l] ;
    LL len = 1 ;
    while (r <= n) {
        if (!len) {
            len = 1 ;   
            ++ ans , l = ++ r ;
            res[l] = a[l] ;
        } else if (r + len <= n&&chk(l,r + 1,r + len)) {
            r += len ; len <<= 1 ; if (r == n) break ;
        } else len >>= 1 ;
    }
    ans += (r == n) ;
}

signed main() {
    T = read() ;
    for (LL _ = 1 ; _ <= T ; ++_ ) {
        ans = 0 ;
        n = read() , m = read() , t = read() ;
        for (LL i = 1 ; i <= n ; ++i )
            a[i] = read() ;
        solve(1,1) ;
        printf("%lld\n",ans) ;
    }
}

#include<iostream>
#include<cstdio>

using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;

int n, m;
int ne[N];
char s[M], p[N];

int main() {

     cin >> n >> p + 1 >> m >> s + 1;

     //开始对ne数组解释了；
     // i表示字符串的后缀， 就表示字符串的前缀；
     for(int i = 2, j = 0; i <= n; i++) {
        // 表示前后缀不相同的情况； j 表示无路可退；
        // while表示可退多次，直到二者相同；
         while (j && p[i] != p[j + 1]) j = ne[j];
         // 表示前后缀相同的情况；
         if(p[i] == p[j + 1]) j++;
         //更新ne数组；
         ne[i] = j;
     }
     for(int i = 1,j = 0; i <= m; i++) {

         while(j && s[i] != p[j + 1]) j = ne[j];
         if(s[i] == p[j + 1])  j++;
         if(j == n) {
             printf("%d ", i - n);
             j = ne[j];
         }
     }

    return 0;
}

题目链接

最大上升子序列和

题解思路

和最长上升子序列的思路一样 改动的是去求和最大的解

通过代码

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

using namespace std;

const int N = 1010;

int n, res;
int a[N], f[N];

int main()
{
    cin >> n;

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

    for (int i = 1; i <= n; i ++ )
    {
        f[i] = a[i];
        for (int j = 1; j < i; j ++ )
            if (a[j] < a[i]) f[i] = max(f[i], a[i] + f[j]);
        res = max(res, f[i]);
    }

    cout << res << endl;

    return 0;
}