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()

codeforce每日一题链接

题目链接

题目分数：1500

题目描述

输入 $n(3≤n≤3e5 且 n\%3=0)$ 和长为 $n$ 的字符串$ s$，只包含$ 012$。
你需要修改 $s$ 中的字符，使得 $012$ 的数量都等于 $n/3$。
修改次数应当尽量少。
输出修改后的字典序最小的字符串。

样例

输入样例1

3
121

输出样例1

021

输入样例2

6
000000

输出样例2

001122

输入样例3

6
211200

输出样例3

211200

输入样例4

6
120110

输出样例4

120120

算法

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

先填2，从后向前枚举，如果当前是1且1有多余的，就替换，否则替换0。再填0，从前向后枚举，如果当前是2并且2多余，就替换，否则替换1。再填1，如果0多余就从后向前填，如果2多余就从前向后填。

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 = 2e5+10, M = N * 2, INF = 0x3f3f3f3f;

int n, m;

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

    cin>>n;
    string str;
    cin>>str;
    int a = n/3, b = n/3, c = n/3;
    for(auto u : str)
        if(u=='0') a--;
        else if(u=='1') b--;
        else c--;
    per(i, 0, n-1)
        if(c>0)
            if(str[i]=='1' && b < 0) c--, b++, str[i] = '2';
            else if(str[i]=='0' && a < 0) c--, a++, str[i] = '2';
    rep(i, 0, n-1)
        if(a>0)
            if(str[i]=='2' && c < 0) a--, c++, str[i] = '0';
            else if(str[i]=='1' && b < 0) a--, b++, str[i] = '0';
    rep(i, 0, n-1)
        if(str[i]=='2' && c < 0) b--, c++, str[i] = '1';
    per(i, 0, n-1)
        if(str[i]=='0' && a < 0) b--, a++, str[i] = '1';

    cout<<str<<endl;

    return 0;
}

codeforce每日一题链接

题目链接

题目分数：1900

题目描述

给你$n$个数对，保证$l[i]<=r[i]<l[i+1]-1$，你从$0$开始，有三种操作，第一种是想向右移动$1$，第二种是按下上色的按钮，第三种是松开上色的按钮。注意，你只能在$l[i]$到$r[i]$的范围内上色。请问怎样用最少的操作给$k$个位置上色。

样例

输入样例1

4
2 3
1 3
1 4
4 20
10 13 16 19
11 14 17 20
2 3
1 3
1 10
2 4
99 999999999
100 1000000000

输出样例1

8
-1
7
1000000004

算法

(贪心) $O(n)$

这道题重点在于长度为1的区间能不能直接选，答案是不能直接选，因为选了之后可能会亏了。这个在样例1的第3组就可以看出来。因为要上色就一定要操作两次，而为区间长度为1不如为下一个较长的区间上色，当然前提是我们要能选到下一个区间。那代码怎么写呢，我们可以动态维护长度为1的区间有多少个，比较长度大于等于2的区间总和和m的大小，维护最小值。

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 = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;

int n, m;

inline void solve()
{
    cin>>n>>m;
    vector<PII> w(n);
    rep(i, 0, n-1) cin>>w[i].fi;
    rep(i, 0, n-1) cin>>w[i].se;

    int k = 0, cnt = 0;
    LL res = 3e9;
    rep(i, 0, n-1)
    {
        if(w[i].se-w[i].fi+1>1) k += w[i].se - w[i].fi + 1;
        else cnt ++;

        if(k < m){
            if(k + cnt >= m)
            {
                res = min(res, (LL)w[i].se + 2 * (i - cnt + 1 + m - k));
            }
        }else{
            res = min(res, (LL)w[i].se + m - k + 2 * (i - cnt + 1));
            break;
        }
    }

    if(res == 3e9) res = -1;
    cout<<res<<endl;
}

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

    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }

    return 0;
}

codeforce每日一题链接

题目描述

题意太长，可以看原题。

样例

输入样例1

2
1 2 3 4

输出样例1

0

输入样例2

2
1 3 4 2

输出样例2

1

输入样例3

1
-1 -1

输出样例3

2

算法

(枚举) $O(n*log(n))$

我们每次只考虑后面n/2个队伍填到哪个位置，因为后面的队伍是一定要和前面n/2个队伍匹配的，所以我们找出后面n/2支队伍有哪些没有填，如果发现后面的队伍和后面的队伍打了，直接输出0就好了。将找出来的队伍以全排列的形式乘入答案中。然后再找出哪些位置有空缺的，如果发现当前位置是有空缺的，那么被分配到当前韦德队伍还挑选位置，所以答案乘上这个位置空缺的位置次数，填上后将这个位置的次数减1。

C++ 代码 (参考的jiangly的代码)

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

#include<bits/stdc++.h>

#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 = 2e6+10, M = N * 2, INF = 0x3f3f3f3f, mod = 998244353;

int n, m;
LL f[N];

void init()
{
    f[0] = 1;
    for(int i=1;i<=n;i++) f[i] = f[i-1] * i % mod;
}

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

    cin>>n;
    n = 1 << n;
    init();
    vector<int> a(n, -1);
    vector<int> s(n, 1);

    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        if(x != -1){
            x--;
            a[x] = i;
            s[i] = 0;
        }
    }

    LL res = 1;
    while(n > 1)
    {
        vector<bool> st(n/2, 0);
        vector<int> g(n/2, 0);
        for(int i=0;i<n/2;i++) g[i] = s[i*2] + s[i*2+1];
        for(int i=0;i<n;i++){
            if(a[i]!=-1) a[i] /= 2;
        }
        LL ans = n / 2;
        for(int i=n/2;i<n;i++){
            if(a[i] != -1){
                if(st[a[i]]){
                    cout<<0<<endl;
                    return 0;
                }
                st[a[i]] = true;
                ans --;
            }
        }

        res = res * f[ans] % mod;
        for(int i=0;i<n/2;i++){
            if(!st[i]){
                res = res * (g[i]--) % mod;
            }
        }
        a.resize(n/2);
        s = g;
        n/=2;
    }

    cout<<res<<endl;

    return 0;
}

codeforce每日一题链接

题目描述

给定一个长度为n的数组和k，请选出k个数字，顺序与原数组的顺序一致。将它分成前后两部分，使得两部分的最大值最小。

样例

输入样例1

6
5 4
1 10 1 1 1
5 3
1 20 5 15 3
5 3
1 20 3 15 5
10 6
10 8 20 14 3 8 6 4 16 11
10 5
9 9 2 13 15 19 4 9 13 12
1 1
1

输出样例1

2
6
5
21
18
1

算法

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

答案是有范围的，所以我们可以二分答案。我们在判断mid是否可行时，$left[i]$数组表示，从0到i在选择的数字不超过mid的情况下，最多能选择多少数字，right就表示从右选择，从i到n-1在选择的数字不超过mid的情况下，最多能选择多少数字。然后我们可以枚举分界点，如果两边最多能选取的数字数量大于k的话，返回true。

C++ 代码

#include<bits/stdc++.h>

#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;

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

int n, m;

bool check(LL mid, vector<int> w)
{
    vector<int> left(n+1, 0);
    vector<int> right(n+1, 0);
    priority_queue<int> heap1;
    LL sum = 0;
    for(int i=0;i<n;i++)
    {
        heap1.push(w[i]);
        sum += w[i];
        while(sum>mid && heap1.size()){
            sum -= heap1.top();
            heap1.pop();
        }
        left[i]=heap1.size();
    }
    sum = 0;
    priority_queue<int> heap2;
    for(int i=n-1;~i;i--)
    {
        sum += w[i];
        heap2.push(w[i]);
        while(sum>mid && heap2.size())
        {
            sum -= heap2.top();
            heap2.pop();
        }
        right[i] = heap2.size();
    }

    int res = 0;
    for(int i=-1;i<n;i++){
        if(i==-1) res = max(res, right[i+1]);
        else if(i==n-1) res=max(res, left[i]);
        else res=max(res, left[i]+right[i+1]);
    }
    return res >= m;
}

void solve()
{
    cin>>n>>m;
    vector<int> w(n+1, 0);
    for(int i=0;i<n;i++) cin>>w[i];
    LL l=0,r=3e14;
    while(l<r)
    {
        LL mid=l+r>>1;
        if(check(mid, w)) r=mid;
        else l=mid+1;
    }
    cout<<r<<endl;
}

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

    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }

    return 0;
}

5.26 Educational Codeforces Round 149 (Rated for Div. 2)

codeforce每日一题汇总链接

Educational Codeforces Round 149 (Rated for Div. 2)

A. Grasshopper on a Line

题解链接

B. Comparison String

题解链接

C. Best Binary String

题解链接

D. Bracket Coloring

题解链接

E. Playoff Fixing

题解链接

F. Editorial for Two

题解链接

codeforce每日一题链接

题目描述

给你一个字符串，每个字符不是$’<’$，就是$’>’$。有一个数组$a$，$s[i]$为$’<’$表示a[i] < a[i+1]，$s[i]$为$’>’$表示$a[i]>a[i+1]$，请返回$a$的最小代价。数组的代价是数组中不同元素的数量。

样例

输入样例1

4
4
<<>>
4
>><<
5
>>>>>
7
<><><><

输出样例1

3
3
6
2

算法

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

找出最大连续的’<’或者’>’的长度，答案就是最大长度加1。

C++ 代码

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

#include<bits/stdc++.h>

#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 = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;

int n, m;

inline void solve()
{
    cin>>n;
    string str;
    cin>>str;
    int res = 0;
    for(int i=0;i<n;i++){
        int j = i;
        while(j<n && str[j]==str[i]) j++;
        res = max(res, j - i);
        i = j - 1;
    }

    cout<<res + 1<<endl;
}

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

    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }

    return 0;
}