算法

(暴力枚举) $O(n)$

我们可以用last记录从开始到现在还剩有多少草，这样每次比较枚举的i和i+1的天数之差和last的最小值，答案加上这个值，不要忘了last每次要减去i到i+1要经历的天数。

C++ 代码

//  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
#define SZ(a) (int)a.size()

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;

LL n, m, t;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n>>t;

    vector<PLL> w(n + 2, {0, 0});
    rep(i, 1, n) cin>>w[i].fi>>w[i].se;
    w[n + 1].fi = t + 1, w[0].fi = 1;

    LL res = 0, last = 0;
    rep(i, 0, n)
    {
        last += w[i].se;
        res += min(last, w[i + 1].fi - w[i].fi);
        last = max(0ll, last - (w[i + 1].fi - w[i].fi));
        //  cout<<res<<" "<<last<<endl;
    }

    cout<<res<<endl;

    return 0;
}

Java 代码

import java.util.*;

public class Main{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        long[] d = new long[n + 10];
        long[] t = new long[n + 10];
        for(int i=1;i<=n;i++) {d[i] = sc.nextLong();t[i] = sc.nextLong();}
        d[0] = 1;d[n + 1] = k + 1;
        long res = 0, last = 0;
        for(int i=0;i<=n;i++)
        {
            last += t[i];
            res += Math.min(last, d[i+1] - d[i]);
            last = Math.max(0, last - (d[i+1] - d[i]));
        }

        System.out.println(res);
    }
}

Python 代码

n, k = map(int, input().split())

d, t = [0] * (n + 2), [0] * (n + 2)

for i in range(1, n + 1): d[i], t[i] = map(int, input().split())

res, last = 0, 0
d[0], d[n + 1] = 1, k + 1

for i in range(n + 1):
    last += t[i]
    res += min(last, d[i + 1] - d[i])
    last = max(0, last - (d[i + 1] - d[i]))

print(res)

//  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
#define SZ(a) (int)a.size()

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;

LL n, m, t;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n>>t;

    vector<PLL> w(n + 2, {0, 0});
    rep(i, 1, n) cin>>w[i].fi>>w[i].se;
    w[n + 1].fi = t + 1, w[0].fi = 1;

    LL res = 0, last = 0;
    rep(i, 0, n)
    {
        last += w[i].se;
        res += min(last, w[i + 1].fi - w[i].fi);
        last = max(0ll, last - (w[i + 1].fi - w[i].fi));
        //  cout<<res<<" "<<last<<endl;
    }

    cout<<res<<endl;

    return 0;
}

codeforce每日一题

题目链接

题目分数：1400

题目描述

输入 u n(1≤u,n≤2000)。
输出有多少个长为 n 的数组 a，满足：
1. 1≤a[1]≤a[2]≤…≤a[n]≤u。
2. a[i] 整除 a[i+1]（或者说 a[i] 是 a[i+1] 的因子）。
答案模 1e9+7。

样例

输入样例1

3 2

输出样例1

5

输入样例2

6 4

输出样例2

39

算法

(dp) $O(n*m*log(m))$

我们可以用$dp$，$f[i][j]$表示前$i$位最后一位数字是$j$的总的方案数，转移方程$f[i][j*k]=(f[i][j*k] + f[i-1][j])%mod$.

C++ 代码

//  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
#define SZ(a) (int)a.size()

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 2000 + 10, M = N * 2, INF = 0x3f3f3f3f, mod = 1e9+7;

int n, m;
LL f[N][N];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>m>>n;

    rep(i, 1, m) f[1][i] = 1;
    rep(i, 2, n)
        rep(j, 1, m)
            rep(k, 1, m)
                if(k * j <= m) f[i][k * j] = (f[i][k * j] + f[i - 1][j]) % mod;
                else break;

    LL res = 0;
    rep(i, 1, m) res = (res + f[n][i]) % mod;

    cout<<res<<endl;

    return 0;
}

Java 代码

//  https://www.acwing.com/blog/content/34755/

import java.util.*;

public class Main{

    public static int N = 200005, M = N * 2, INF = 0x3f3f3f3f, mod = 1000000007;

    public static void solve()
    {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();int n = sc.nextInt();
        long[] f = new long[m + 1];
        f[1] = 1;
        for(int i = 0; i < n; i ++)
            for(int j = m; j > 0; j --)
                for(int k = j * 2; k <= m; k += j)
                    f[k] = (f[k] + f[j]) % mod;
        long res = 0;
        for(int i = 1; i <= m; i ++) res = (res + f[i]) % mod;
        System.out.println(res);
    }

    public static void main(String[] args)
    {
        solve();
    }
}

Python 代码

#  https://www.acwing.com/blog/content/34755/

mod = int(1e9 + 7)

def solve():
    m, n = map(int, input().split())

    f = [0] * (m + 1)
    f[1] = 1
    for i in range(n):
        for j in range(m, 0, -1):
            k = j * 2
            while k <= m:
                f[k] = (f[k] + f[j]) % mod
                k += j

    res = sum(f[1 : m + 1])
    print(res % mod)


def main():
    solve()

if __name__ == '__main__':
    main()

算法

(floyd) $O(n^3)$

直接用floyd求得所有点的最短路，再遍历一遍找出最大值就好了。

C++ 代码

//  codeforce每日一题  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=a;i>=b;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
#define SZ(a) (int)a.size()

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 2e5 + 10, M = N * 2, INF = 0x3f3f3f3f, mod = 1e9 + 7;

int n, m;
int g[11][11], dist[11][11];

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

    cin>>n;
    rep(i, 1, n)
        rep(j, 1, n) cin>>g[i][j];

    rep(k, 1, n)
        rep(i, 1, n)
            rep(j, 1, n)
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);

    int res = 0;
    rep(i, 1, n)
        rep(j, 1, n)
            res = max(res, g[i][j]);
    cout<<res<<endl;

    return 0;
}

算法

(堆) $O(n*log(n))$

我们可以用来记录每个点的上一个点和下一个点是什么，堆中记录的是每一对相邻的男女相差值和他们的位置，每次从中取出最小的一个，加到答案里，再将他们的上一个和下一个加到堆里，并改变指针数组。别忘了用$set$记录一下那些点已经用过，用过后存进$set$中，如果发现从堆中取出的点至少有一个已经用过的话，就$continue$.

C++ 代码

//  codeforce每日一题  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=a;i>=b;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
#define SZ(a) (int)a.size()

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<int,PII> PIII;
typedef pair<double, double> PDD;

const int N = 2e5 + 10, M = N * 2, INF = 0x3f3f3f3f, mod = 1e9 + 7;

int n, m;
char str[N];
int w[N], ne[N], pre[N];

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

    cin>>n>>str + 1;
    rep(i, 1, n) cin>>w[i], ne[i] = i + 1, pre[i] = i - 1;

    set<int> s;
    priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
    rep(i, 1, n - 1)
        if(str[i]!=str[i+1])
            heap.push({abs(w[i] - w[i + 1]), {i, i + 1}});

    vector<PIII> res;
    while(heap.size())
    {
        auto u = heap.top();
        heap.pop();
        if(s.count(u.se.fi) || s.count(u.se.se)) continue;
        res.pd({u.fi,{u.se.fi, u.se.se}});
        if(pre[u.se.fi]!=0 && 
            ne[u.se.se]!=n+1 && 
            str[pre[u.se.fi]]!=str[ne[u.se.se]])
                heap.push({abs(w[pre[u.se.fi]] - w[ne[u.se.se]]), {pre[u.se.fi], ne[u.se.se]}});
        pre[ne[u.se.se]] = pre[u.se.fi];
        ne[pre[u.se.fi]] = ne[u.se.se];
        s.insert(u.se.se);s.insert(u.se.fi);
    }

    //  sort(all(res));
    cout<<res.size()<<endl;
    for(auto u : res) cout<<u.se.fi<<" "<<u.se.se<<endl;

    return 0;
}

codeforce每日一题

题目链接

题目分数：2200

题目描述

输入两个长度不超过 $200$ 的字符串 $s$ 和 $t$，只包含左右括号。输出 $s$ 和 $t$ 的最短公共超序列，要求这个超序列是一个合法括号字符串。（多解输出任意解。）
最短公共超序列

样例

输入样例1

(())(()
()))()

输出样例1

(())()()

输入样例2

)
((

输出样例2

(())

输入样例3

)
)))

输出样例3

((()))

输入样例4

())
(()(()(()(

输出样例4

(()()()(()()))

算法

(递归) $O(n*m)$

类似于记忆化搜索，我们先确定这一位是填$”(“$还是$”)”$，判断哪个得到的字符串最短，就选择哪个。$dfs$中的$k$代表当前$”(“$多于$”)”$的次数，$l$表示枚举$str1$的位数，$r$表示枚举$str2$的位数。我们用$ma$记忆每一次搜索的结果，避免重复搜索。

C++ 代码

//  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
#define SZ(a) (int)a.size()

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;

int n, m;
int ma[210][210][410];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    memset(ma, -1, sizeof ma);
    string str1, str2;
    cin>>str1>>str2;
    n = str1.size(), m = str2.size();

    str1 += "!", str2 += "!";

    int tmp = 0;
    function<int(int,int,int)> dfs = [&](int l, int r, int k){
        if(k > n + m) return INF;
        if(l == n && r == m && !k) return 0;
        if(ma[l][r][k]!=-1) return ma[l][r][k];
        ma[l][r][k] = INF;
        int res = dfs(l + (str1[l]=='('), r + (str2[r] == '('), k + 1) + 1;
        if(k > 0) res = min(res, dfs(l + (str1[l] == ')'), r + (str2[r] == ')'), k - 1) + 1);
        ma[l][r][k] = res;
        return res;
    };

    string res;
    function<void(int,int,int)> f = [&](int l, int r, int k){
        if(l==n && r==m && !k) return;

        if(dfs(l + (str1[l] == '('), r + (str2[r] == '('), k + 1) + 1 == dfs(l, r, k)){
            res.push_back('(');
            f(l + (str1[l] == '('), r + (str2[r] == '('), k + 1);
        }else res.push_back(')'), f(l + (str1[l] == ')'), r + (str2[r] == ')'), k - 1);
    };
    f(0, 0, 0);
    cout<<res<<endl;

    return 0;
}

codeforce每日一题

题目链接

题目分数：1900

题目描述

输入 $n，k(1≤k≤n≤4e5)$ 和长为 $n$ 的数组 $a(1≤a[i]≤1e9)$。
统计有多少个连续子数组 $b$，满足 $b$ 中有至少 $k$ 个相同的数。

样例

输入样例1

4 2
1 2 1 2

输出样例1

3

输入样例2

5 3
1 2 1 1 3

输出样例2

2

输入样例3

3 1
1 1 1

输出样例3

6

算法

(双指针) $O(n)$

这道题我们可以用双指针来做。用双指针，就要证明两个指针具有单调性，我们可以假设$i，j (j < i)$ 是两个指针，表示的是在这个区间内恰好只有一个数字并且刚好满足出现次数等于$k$次，当$i$变成$i+1$时，$j$到$i+1$这个区间满足至少有一个数字满足上述性质，此时$j$需要向右移动，直到$j$到$i+1$内只有一个数字满足出现次数等于$k$。以上证明了可以使用双指针。

C++ 代码

//  codeforce每日一题  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=a;i>=b;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 2e5 + 10, M = N * 2, INF = 0x3f3f3f3f, mod = 1e9 + 7;

int n, m;

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

    cin>>n>>m;
    vector<int> w(n + 1);
    map<int,int> g;
    rep(i, 1, n) cin>>w[i];

    LL res = 0, cnt = 0;
    for(int i=1,j=0;i<=n;i++){
        g[w[i]] ++;
        if(g[w[i]]==m) cnt++;
        while(j<i){
            g[w[j + 1]] --;
            if(g[w[j + 1]]==m-1) cnt--;
            if(cnt==0){
                g[w[j + 1]]++;
                if(g[w[j + 1]] == m) cnt++;
                break;
            }
            else j++;
        }
        //  cout<<cnt<<" "<<j<<endl;
        if(cnt) res += j + 1;
    }

    cout<<res<<endl;

    return 0;
}

Java 代码

//  https://www.acwing.com/blog/content/34755/

import java.util.*;

public class Main{
    public static void solve()
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[] w = new int[n + 1];
        for(int i=1;i<=n;i++) w[i] = sc.nextInt();
        Map<Integer, Integer> g = new HashMap<Integer, Integer>();
        long res = 0, cnt = 0;
        int tmp;
        for(int i=1,j=0;i<=n;i++){
            if(g.containsKey(w[i])){
                tmp = g.get(w[i]);
                g.remove(w[i]);
                g.put(w[i], tmp + 1);
            }else g.put(w[i], 1);

            if(g.get(w[i])==m) cnt++;
            while(j<i){
                tmp = g.get(w[j + 1]);
                g.remove(w[j + 1]);
                g.put(w[j + 1], tmp - 1);
                if(g.containsKey(w[j + 1]) && g.get(w[j + 1])==m-1) cnt--;
                if(cnt==0){
                    if(g.containsKey(w[j + 1])){
                        tmp = g.get(w[j + 1]);
                        g.remove(w[j + 1]);
                        g.put(w[j + 1], tmp + 1);
                    }else g.put(w[j + 1], 1);
                    if(g.get(w[j + 1]) == m) cnt++;
                    break;
                }
                else j++;
            }
            //  cout<<cnt<<" "<<j<<endl;
            if(cnt > 0) res += j + 1;
        }
        System.out.println(res);
    }

    public static void main(String args[])
    {
        solve();
    }
}

Python 代码

#  https://www.acwing.com/blog/content/34755/

def solve():
    n, m = map(int, input().split())
    w = [int(i) for i in input().split()]
    w.insert(0, 0)

    g = {}
    res, cnt = 0, 0
    j = 0
    for i in range(1, n + 1):
        g[w[i]] = g.get(w[i], 0) + 1
        if g[w[i]] == m: cnt += 1
        while j < i:
            g[w[j + 1]] = g[w[j + 1]] - 1
            if g[w[j + 1]] == m - 1: cnt -= 1
            if cnt == 0:
                if g[w[j + 1]] == m - 1: cnt += 1
                g[w[j + 1]] = g[w[j + 1]] + 1
                break
            else: j += 1

        if cnt > 0: res += j + 1
    print(res)


def main():
    solve()

if __name__ == '__main__':
    main()

codeforce每日一题

题目链接

题目分数：1800

题目描述

输入$n(1≤n≤5000)$ 和长为 $n$ 的数组 $a(-1e9≤a[i]≤1e9)$。
定义 $s(i,i)=0, s(i,j)=a[i]+a[i+1]+…+a[j-1]$。
计算 $s(0,i)-s(i,j)+s(j,k)-s(k,n)$ 的最大值，其中 $0≤i≤j≤k≤n$。
你需要输出最大值对应的 $i,j,k$。
如果有多个满足要求的答案，输出任意一个。

样例

输入样例1

3
-1 2 3

输出样例1

0 1 3

输入样例2

4
0 0 -1 0

输出样例2

0 0 0

输入样例3

1
10000

输出样例3

1 1 1

算法

(枚举) $O(n)$

我们可以将等式化简成为$2*(s[i] - s[j] + s[k]) - s[n]$，s数组表示前缀和。则我们就先预处理一个前缀和，再维护两个前缀最大值，遍历一遍即可找出最大值。

C++ 代码

//  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
#define SZ(a) (int)a.size()

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;

int n, m;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n;
    vector<int> w(n + 1);
    rep(i, 1, n) cin>>w[i];

    vector<LL> s(n + 1, 0);
    vector<PLL> g1(n + 2, {0, 0}), g2(n + 2, {0, 0});
    rep(i, 1, n) s[i] += s[i - 1] + w[i];
    rep(i, 1, n){
        g1[i].fi = max(g1[i-1].fi, s[i]);
        if(g1[i].fi==s[i]) g1[i].se = i;
        else g1[i].se = g1[i-1].se;
    }
    g2[n + 1] = {-1e18, 0};
    per(i, 1, n)
    {
        g2[i].fi = max(g2[i+1].fi, s[i]);
        if(g2[i].fi==s[i]) g2[i].se = i;
        else g2[i].se = g2[i+1].se;
    }

    LL res = -1e18;
    vector<int> ans(3);
    rep(i, 0, n){
        LL tmp = g1[i].fi - s[i] + g2[i].fi;
        if(res<tmp){
            res = tmp;
            ans[0] = g1[i].se, ans[1] = i, ans[2] = g2[i].se;
        }
    }
    cout<<ans[0]<<" "<<ans[1]<<" "<<ans[2]<<endl;

    return 0;
}

Java 代码

//  https://www.acwing.com/blog/content/34755/

import java.util.*;

public class Main{

    public static int N = 200005, M = N * 2, INF = 0x3f3f3f3f;

    public static void solve()
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] w = new int[n + 1];
        for(int i=1;i<=n;i++) w[i] = sc.nextInt();
        long[] s = new long[n + 1];
        long[] g = new long[n + 1];
        int[] idx = new int[n + 1];
        for(int i=1;i<=n;i++) s[i] = s[i - 1] + w[i];
        for(int i=1;i<=n;i++){
            g[i] = Math.max(g[i - 1], s[i]);
            if(g[i] == s[i]) idx[i] = i;
            else idx[i] = idx[i - 1];
        }
        long res = -1000000000;
        int[] ans = new int[3];
        long S = s[n];
        int idx1 = n;
        for(int i=n;i>=0;i--)
        {
            if(s[i] > S){
                S = s[i];
                idx1 = i;
            }
            long tmp = g[i] - s[i] + S;
            if(tmp > res)
            {
                res = tmp;
                ans[0] = idx[i];ans[1] = i; ans[2] = idx1;
            }
        }
        System.out.printf("%d %d %d", ans[0], ans[1], ans[2]);
    }

    public static void main(String[] args)
    {
        solve();
    }
}

Python 代码

#  https://www.acwing.com/blog/content/34755/


def solve():
    n = int(input())
    w = [int(i) for i in input().split()]
    w.insert(0, 0)
    s = [0] * (n + 1)
    for i in range(1, n + 1): s[i] = s[i - 1] + w[i]
    g1 = [0] * (n + 1)
    idx = [0] * (n + 1)
    for i in range(1, n + 1):
        g1[i] = max(g1[i - 1], s[i])
        if g1[i] == s[i]: idx[i] = i
        else: idx[i] = idx[i - 1]
    res = -1e18
    S, idx1 = s[n], n
    for i in range(n, -1, -1):
        if S < s[i]:
            S = s[i]
            idx1 = i
        tmp = g1[i] - s[i] + S
        if tmp > res:
            res = tmp
            #  print(res)
            ans = [idx[i], i, idx1]
    print(ans[0], ans[1], ans[2])

def main():
    solve()

if __name__ == '__main__':
    main()

codeforce每日一题

题目链接

题目分数：1600

题目描述

输入 $a, b, k$，范围 $[1,1e6]$，$a≤b$。
请找到最短的 $L$，使得对于任意 $a≤x≤b-L+1$ 都满足：在 $x,x+1,…,x+L-1$ 中至少有$ k$ 个质数。
输出 $L$。如果$L$ 不存在，输出 $-1$。

样例

输入样例1

2 4 2

输出样例1

3

输入样例2

1 4 3

输出样例2

-1

算法1

(二分) $O(n*log(n))$

我们可以二分答案，每次判断的时候从前向后枚举看当前区间是否有至少k个质数。

C++ 代码

//  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 1e6 + 10, M = N * 2, INF = 0x3f3f3f3f, mod = 998244353;

int n, m, k;
int primes[N], cnt;
bool st[N];

inline void init(int n)
{
    st[1] = true;
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) primes[cnt++] = i;
        for(int j=0;i<=n/primes[j];j++)
        {
            st[i*primes[j]] = true;
            if(i%primes[j]==0) break;
        }
    }
}

inline void solve()
{
    auto check = [&](int mid)
    {
        int tmp = 0;
        for(int i=n;i<=n+mid-1;i++)
            if(!st[i]) tmp ++;
        for(int i=n,j=n+mid-1;j<=m;i++,j++)
        {
            if(tmp<k) return false;
            if(!st[i]) tmp --;
            if(!st[j+1]) tmp ++;
        }
        return true;
    };

   cin>>n>>m>>k;
   int l = 0, r = m - n + 1;
   while(l < r)
   {
       int mid = l + r >> 1;
       if(check(mid)) r = mid;
       else l = mid + 1;
   }
   if(check(r)) cout<<r<<endl;
   else cout<<-1<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    init(N - 1);

    solve();

    return 0;
}

Java 代码

//  https://www.acwing.com/blog/content/34755/

import java.util.*;

public class Main{

    public static int N = 1000005, M = N * 2, INF = 0x3f3f3f3f;

    public static void solve()
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();
        boolean[] st = new boolean[m + 10];
        int[] primes = new int[m + 10];
        int cnt = 0;
        st[1] = true;
        for(int i = 2; i <= m; i++)
        {
            if(!st[i]) primes[cnt++] = i;
            for(int j = 0; i <= m / primes[j]; j++)
            {
                st[i * primes[j]] = true;
                if(i % primes[j] == 0) break;
            }
        }
        int tmp = 0;
        for(int i = n; i <= m; i++)
            if(!st[i]) tmp++;
        if(tmp < k) System.out.println(-1);
        else{
            int l = 0, r = m - n + 1;
            while(l < r)
            {
                int mid = l + r >> 1;
                boolean flag = true;
                tmp = 0;
                for(int i=n;i<=n+mid-1;i++)
                    if(!st[i]) tmp ++;
                for(int i=n,j=n+mid-1;j<=m;i++,j++)
                {
                    if(tmp<k){
                        flag = false;
                        break;
                    }
                    if(!st[i]) tmp --;
                    if(!st[j+1]) tmp ++;
                }
                if(flag) r = mid;
                else l = mid + 1;
            }   
            System.out.println(r);
        }
    }

    public static void main(String[] args)
    {
        solve();
    }
}

Python 代码

#  https://www.acwing.com/blog/content/34755/

st = [0] * (1000011)
primes = [0] * (1000011)

def init(n:int):
    st[1] = True
    cnt = 0
    for i in range(2, n + 1):
        if st[i] == False:
            primes[cnt] = i
            cnt += 1
        j = 0
        while i <= n / primes[j]:
            st[i * primes[j]] = True
            if i % primes[j] == 0:
                break
            j += 1

def check(mid:int, n:int, m:int, k:int) -> bool:
    tmp = 0
    for i in range(n, n + mid):
        if st[i] == False: tmp += 1
    i = n
    for j in range(n + mid - 1, m + 1):
        if tmp < k: return False
        if st[i] == False: tmp -= 1 
        if st[j+1] == False: tmp += 1
        i += 1
    return True

def solve():
    n, m, k = map(int, input().split())

    init(m + 10)

    l, r = 0, m - n + 1
    while l < r:
        mid = l + r >> 1
        if check(mid, n, m, k):
            r = mid
        else:
            l = mid + 1

    if check(r, n, m, k):
        print(r)
    else:
        print(-1)

def main():
    solve()

if __name__ == '__main__':
    main()

算法2

(枚举 + 双指针) $O(n)$

我们可以用双指针维护一个区间，保证这个区间内的质数数量恰好等于k个，这样可以是为了保证最后求得的l最小。注意最后当右指针超出区间后要记得更新答案，因为这时答案至少要大于当前的区间。

C++ 代码

//  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 1e6 + 10, M = N * 2, INF = 0x3f3f3f3f, mod = 998244353;

int n, m, k;
int primes[N], cnt;
bool st[N];

inline void init(int n)
{
    st[1] = true;
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) primes[cnt++] = i;
        for(int j=0;i<=n/primes[j];j++)
        {
            st[i*primes[j]] = true;
            if(i%primes[j]==0) break;
        }
    }
}

inline void solve()
{
    cin>>n>>m>>k;

    int tmp = 0;
    for(int i=n;i<=m;i++)
        if(!st[i]) tmp++;
    if(tmp<k) cout<<-1<<endl;
    else{
        int res = 0, tmp = !st[n];
        for(int i=n,j=n+1;;i++){
            while(tmp<k && j<=m){
                if(!st[j++]) tmp++;
            }
            if(tmp<k){
                res = max(res, j - i + 1);
                break;
            }
            res = max(res, j - i);
            if(!st[i]) tmp--;
            if(j>m) break;
        }
        cout<<res<<endl;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    init(N - 1);

    solve();

    return 0;
}

Java 代码

//  https://www.acwing.com/blog/content/34755/

import java.util.*;

public class Main{

    public static int N = 200005, M = N * 2, INF = 0x3f3f3f3f;

    public static void solve()
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();
        boolean[] st = new boolean[m + 10];
        int[] primes = new int[m + 10];
        int cnt = 0;
        st[1] = true;
        for(int i = 2; i <= m; i++)
        {
            if(!st[i]) primes[cnt++] = i;
            for(int j = 0; i <= m / primes[j]; j++)
            {
                st[i * primes[j]] = true;
                if(i % primes[j] == 0) break;
            }
        }
        int tmp = 0;
        for(int i = n; i <= m; i++)
            if(!st[i]) tmp++;
        if(tmp < k) System.out.println(-1);
        else{
            int res = 0;
            if(st[n] == false) tmp = 1;
            else tmp = 0;
            for(int i=n,j=n+1;;i++){
                while(tmp<k && j<=m){
                    if(!st[j++]) tmp++;
                }
                if(tmp<k){
                    res = Math.max(res, j - i + 1);
                    break;
                }
                res = Math.max(res, j - i);
                if(!st[i]) tmp--;
                if(j>m) break;
            }
            System.out.println(res);
        }
    }

    public static void main(String[] args)
    {
        solve();
    }
}

Python 代码

#  https://www.acwing.com/blog/content/34755/

st = [0] * (1000011)
primes = [0] * (1000011)

def init(n:int):
    st[1] = True
    cnt = 0
    for i in range(2, n + 1):
        if st[i] == False:
            primes[cnt] = i
            cnt += 1
        j = 0
        while i <= n / primes[j]:
            st[i * primes[j]] = True
            if i % primes[j] == 0:
                break
            j += 1

def solve():
    n, m, k = map(int, input().split())

    init(m + 10)

    tmp = 0;
    for i in range(n, m + 1):
        if st[i] == False: tmp += 1

    if tmp < k: print(-1)
    else:
        res, tmp = 0, st[n] == False
        j = n + 1
        for i in range(n, m + 1):
            while tmp<k and j<=m:
                if st[j] == False: tmp += 1
                j += 1

            if tmp < k:
                res = max(res, j - i + 1)
                break

            res = max(res, j - i)
            if st[i] == False: tmp -= 1
            if j > m: break

        print(res)


def main():
    solve()

if __name__ == '__main__':
    main()