Codeforces Round 951 (Div. 2)

A – Guess the Maximum

直接暴力枚举

a

i

,

a

i

+

1

a_i,a_{i+1}

ai​,ai+1​找最小的最大值
答案即为最小的最大值-1

code:

#include
#define endl '
'
#define fast() ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define F first
#define S second
#define lowbit(x) ((x) & (-x))
#define _ int _T; cin >> _T; while(_T --) 
#define int long long
#define no cout << "NO" << endl
#define yes cout << "YES" << endl
using namespace std;
typedef pair<int, int> PII;
typedef pair<char,int> PCI;
const int N = 3e5 + 7;
const int mod = 998244353;
int n,m,k;
int a[N],b[N];
//PII p[N];
void solve(){
cin >> n;
for(int i = 0;i < n;i ++) cin >> a[i];
int mx = 1e18;
for(int i = 0;i < n - 1;i ++){
mx = min(mx,max(a[i],a[i + 1]));
}
cout << mx - 1 << endl;
}
signed main(){
fast();
_
solve();
return 0;
} 

B – XOR Sequences

序列长度无限 所以从最低位到最高位按位枚举 答案为小于最先不同的位数的所有值 即

(

1

<

<

i

)

(1<<i)

(1<<i) 高位总会有

⨁

\bigoplus

⨁后使其相等的值

code:

#include
#define endl '
'
#define fast() ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define F first
#define S second
#define lowbit(x) ((x) & (-x))
#define _ int _T; cin >> _T; while(_T --) 
#define int long long
#define no cout << "NO" << endl
#define yes cout << "YES" << endl
using namespace std;
typedef pair<int, int> PII;
typedef pair<char,int> PCI;
const int N = 3e5 + 7;
const int mod = 998244353;
int n,m,k;
int a[N],b[N];
//PII p[N];
void solve(){
cin >> n >> m;
for(int i = 0;i < 32;i ++){
int cnt1 = (n >> i) & 1;
int cnt2 = (m >> i) & 1;
if(cnt1 != cnt2){
cout << ((int)1 << i) << endl;
return;
}
}  
}
signed main(){
fast();
_
solve();
return 0;
} 

C – Earning on Bets

假设每一位放的硬币数为

a

i

a_i

ai​ 那么总共就会放

s

u

m

=

∑

i

=

1

n

a

i

sum = \sum\limits_{i = 1}^n{a_i}

sum=i=1∑n​ai​个硬币
然后我们我们知道获胜会得到

a

i

∗

k

i

a_i*k_i

ai​∗ki​金币 并且

s

u

m

<

a

i

∗

k

i

sum < a_i*k_i

sum<ai​∗ki​
即

s

u

m

k

i

sum \over k_i

ki​sum​ <

a

i

a_i

ai​
并且有

∑

i

=

1

n

s

u

m

k

i

<

∑

i

=

1

n

a

i

\sum\limits_{i = 1}^n{sum \over k_i} < \sum\limits_{i = 1}^n{a_i}

i=1∑n​ki​sum​<i=1∑n​ai​
即

∑

i

=

1

n

s

u

m

k

i

<

s

u

m

\sum\limits_{i = 1}^n{sum \over k_i} < sum

i=1∑n​ki​sum​<sum
那么有

∑

i

=

1

n

1

k

i

<

1

\sum\limits_{i = 1}^n{1 \over k_i} < 1

i=1∑n​ki​1​<1
那么我们可以令

s

u

m

=

l

c

m

(

k

1

,

k

2

,

k

3

,

.

.

.

,

k

n

)

sum = lcm(k_1,k_2,k_3,…,k_n)

sum=lcm(k1​,k2​,k3​,…,kn​)
这样

s

u

m

∗

k

i

sum * k_i

sum∗ki​可以不剩余并且可以

s

u

m

k

i

sum \over k_i

ki​sum​的分给每个位置的

a

i

a_i

ai​
即有

∑

i

=

1

n

s

u

m

k

i

<

s

u

m

\sum\limits_{i = 1}^n{sum \over k_i} < sum

i=1∑n​ki​sum​<sum 满足此式子即说明有一个解
解为每个位置分

s

u

m

k

i

sum \over k_i

ki​sum​

code:

#include
#define endl '
'
#define fast() ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define F first
#define S second
#define lowbit(x) ((x) & (-x))
#define _ int _T; cin >> _T; while(_T --) 
#define int long long
#define no cout << "NO" << endl
#define yes cout << "YES" << endl
using namespace std;
typedef pair<int, int> PII;
typedef pair<char,int> PCI;
const int N = 3e5 + 7;
const int mod = 998244353;
int n,m,k;
int a[N],b[N];
//PII p[N];
void solve(){
cin >> n;
int lcm = 1;
for(int i = 0;i < n;i ++){
cin >> a[i];
lcm = (a[i] * lcm) / __gcd(a[i],lcm);
}  
int sum = 0;
for(int i = 0;i < n;i ++) sum += lcm / a[i];
if(sum >= lcm){
cout << -1 << endl;
return;
}
for(int i = 0;i < n;i ++) cout << lcm / a[i] << " ";
cout << endl;
}
signed main(){
fast();
_
solve();
return 0;
} 

D – Fixing a Binary String

直接从头开始遍历并且记录连续的0或1的个数
如果遍历过程中个数大于k了 那么就有两种切割情况：

• 直接从刚大于时的位置前切开
• 看末尾的连续序列长度是否小于k 如果小于k并且

  s

  i

  =

  =

  s

  n

  s_i == s_n

  si​==sn​那就说明此处可以拼接上去 就从此序列开始位置+ (k – 末尾的连续序列长度 – 1)处切割

然后看这两种切割方式是否可以达成连续k个0或1交替出现即可
如果遍历过程中个数小于k了 ：

• 那么就在此前切割

code:

#include
#define endl '
'
#define fast() ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define F first
#define S second
#define lowbit(x) ((x) & (-x))
#define _ int _T; cin >> _T; while(_T --) 
#define int long long
#define no cout << "NO" << endl
#define yes cout << "YES" << endl
using namespace std;
typedef pair<int, int> PII;
typedef pair<char,int> PCI;
const int N = 3e5 + 7;
const int mod = 998244353;
int n,m,k;
int a[N],b[N];
//PII p[N];
int flag;
void check(string ans){
int len = 1;
for(int i = 1;i < n;i ++){
if(ans[i] == ans[i - 1]){
len ++;
if(len > k){
flag = 1;
break;
}
} else{
if(len != k){
flag = 1;
break;
}
len = 1;
}
}    
}
void solve(){
cin >> n >> k;
string s; cin >> s;
int pos = -1,cnt = 1;
int pos2 = -1;
int st = 0;
int mx = 1;
for(int i = n - 2;i >= 0;i --){
if(s[i] != s[i + 1]){
break;
} else{
mx ++;
}
}
for(int i = 1;i < n;i ++){
if(s[i] == s[i - 1]){
cnt ++;
if(cnt > k){
pos = i - 1;
if(s[i] == s[n - 1]){
if(mx >= k) pos2 = -1;
else if(i - st >= k - mx) pos2 = st + k - mx - 1;
}
break;
}
} else{
if(cnt != k){
pos = i - 1;
break;
}
st = i;
cnt = 1;
}
}
if(pos == -1){
cout << n << endl;
return;
}
string s1 = s.substr(0,pos + 1);
string s2 = s.substr(pos + 1);
reverse(s1.begin(),s1.end());
string ans = s2 + s1;
flag = 0;
check(ans);
if(!flag){
cout << pos + 1 << endl;
return;
}
if(pos2 == -1){
cout << -1 << endl;
return;
}
s1 = s.substr(0,pos2 + 1);
s2 = s.substr(pos2 + 1);
reverse(s1.begin(),s1.end());
ans = s2 + s1;
flag = 0;
check(ans);
if(!flag){
cout << pos2 + 1 << endl;
return;
}
cout << -1 << endl;
}
signed main(){
fast();
_
solve();
return 0;
}