$\href{https://www.acwing.com/blog/content/34755/}{codeforce 每日一题}$

1.9万

h.john
tonngw

.拾光.

Ascension
Jiangly_fan
Reminiscence

k_415
Snowing
AC不了怎么办

5小时前

### 题目描述

#### 样例

##### 输入样例1
2 4 2

##### 输出样例1
3

##### 输入样例2
1 4 3

##### 输出样例2
-1


### 算法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

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

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


17小时前

19小时前
AcWing【AC之星】教育优惠计划！https://www.acwing.com/user/security/school_verify/ac_stars/ 我的邀请码是：SSXPJ

### 题目描述

#### 样例

##### 输入样例1
3
121

##### 输出样例1
021

##### 输入样例2
6
000000

##### 输出样例2
001122

##### 输入样例3
6
211200

##### 输出样例3
211200

##### 输入样例4
6
120110

##### 输出样例4
120120


### 算法

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


### 题目描述

#### 样例

##### 输入样例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


### 算法

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


### 题目描述

#### 样例

##### 输入样例1
2
1 2 3 4

##### 输出样例1
0

##### 输入样例2
2
1 3 4 2

##### 输出样例2
1

##### 输入样例3
1
-1 -1

##### 输出样例3
2


### 算法

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


### 题目描述

#### 样例

##### 输入样例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


### 算法

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


### 题目描述

#### 样例

##### 输入样例1
4
4
<<>>
4
>><<
5
>>>>>
7
<><><><

##### 输出样例1
3
3
6
2


### 算法

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