• 欢迎光临~

# Codeforces Round #799 (Div. 4) B E F G题解

### 1. B

problem B

``````#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<bitset>
#include<ctime>
#include<deque>
#include<stack>
#include<functional>
#include<sstream>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 200005
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const int mod = 1e9 + 7;
#define pi acos(-1.0)
#define pii pair<int,int>
#define eps 1e-5
#define pll pair<ll,ll>
#define lson 2*x
#define rson 2*x+1

long long  qupower(int a, int b) {
long long  ans = 1;
while (b) {
if (b & 1)ans = ans * a;
b >>= 1;
a = a * a;
}
return ans;
}

int an = 0, x = 1; char c = getchar();
while (c > '9' || c < '0') {
if (c == '-') {
x = -1;
}
c = getchar();
}
while (c >= '0'&&c <= '9') {
an = an * 10 + c - '0'; c = getchar();
}
return an * x;
}

int t;
int a[52];
map<int,int> mp;

void solve(){
ms(a); mp.clear();
int fg = 0;
for(int i=0;i<n;i++){
mp[a[i]]++;
if(mp[a[i]]>1) fg = 1;
}
if(!fg)cout<<n<<endl;
else{
int cnt1 = 0;
int cnt2 = 0;
for(auto it:mp){
if(it.second % 2)cnt1++;
else cnt2++;
}
if(cnt2%2)cnt2--;
cout<<cnt1+cnt2<<endl;
}

}

int main(){
//ios::sync_with_stdio(false);
while(t--){
solve();
}
}
``````

### 2. E

problem E

``````#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<bitset>
#include<ctime>
#include<deque>
#include<stack>
#include<functional>
#include<sstream>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 200005
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const int mod = 1e9 + 7;
#define pi acos(-1.0)
#define pii pair<int,int>
#define eps 1e-5
#define pll pair<ll,ll>
#define lson 2*x
#define rson 2*x+1

long long  qupower(int a, int b) {
long long  ans = 1;
while (b) {
if (b & 1)ans = ans * a;
b >>= 1;
a = a * a;
}
return ans;
}

int an = 0, x = 1; char c = getchar();
while (c > '9' || c < '0') {
if (c == '-') {
x = -1;
}
c = getchar();
}
while (c >= '0'&&c <= '9') {
an = an * 10 + c - '0'; c = getchar();
}
return an * x;
}

int t;
int a[200003];
int pre_sum[200003];

void solve(){
ms(a);
int sum = 0;
for(int i=1;i<=n;i++){
a[i] = read(); sum += a[i];
pre_sum[i] = pre_sum[i - 1] + a[i];
}
if(sum<s){cout<<-1<<endl;}
else if(sum==s) cout<<0<<endl;
else{
int ans = 9999999;
for(int l=1;l<n;l++){
int r = n;
int tmp = l;
int pos = -1;
while(tmp<=r){
int mid = (tmp + r) >> 1;
if(pre_sum[mid]-pre_sum[l-1]<=s){
pos = mid; tmp = mid+1;
}
else r = mid-1;
}
if(pos==-1 || pre_sum[pos]-pre_sum[l-1]!=s) continue;
//cout<<l<<" "<<pos<<endl;
ans = min(ans, n-(pos-l+1));
}
cout<<ans<<endl;
}
}

int main(){
//ios::sync_with_stdio(false);
while(t--){
solve();
}
}
``````

### 3. F

problem F

``````#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<bitset>
#include<ctime>
#include<deque>
#include<stack>
#include<functional>
#include<sstream>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 200005
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const int mod = 1e9 + 7;
#define pi acos(-1.0)
#define pii pair<int,int>
#define eps 1e-5
#define pll pair<ll,ll>
#define lson 2*x
#define rson 2*x+1

long long  qupower(int a, int b) {
long long  ans = 1;
while (b) {
if (b & 1)ans = ans * a;
b >>= 1;
a = a * a;
}
return ans;
}

int an = 0, x = 1; char c = getchar();
while (c > '9' || c < '0') {
if (c == '-') {
x = -1;
}
c = getchar();
}
while (c >= '0'&&c <= '9') {
an = an * 10 + c - '0'; c = getchar();
}
return an * x;
}

int t;
int a[200003];
map<int,int> mp;
int res[200003];

int get_last_digit(int x){
return x%10;
}

bool check(int x){
return x%10==3;
}

void solve(){
ms(a); ms(res); mp.clear();
for(int i=0;i<n;i++)a[i] = read(), a[i] = get_last_digit(a[i]);
int cnt=0;
for(int i=0;i<n;i++){
if(mp[a[i]]>3)continue;
res[cnt] = a[i];
mp[a[i]]++; cnt++;
}
int fg = 0;
for(int i=0;i<cnt;i++){
for(int j=i+1;j<cnt;j++){
for(int k=j+1;k<cnt;k++){
if(check(res[i]+res[j]+res[k])){
fg = 1;
break;
}
}
if(fg)break;
}
if(fg)break;
}
if(fg)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}

int main(){
//ios::sync_with_stdio(false);
while(t--){
solve();
}
}
``````

### 4. G

problem G

[2^0cdot a_i<2^1cdot a_{i+1}<...<2^kcdot a_{i+k} ]

[a_i<2cdot a_{i+1} ]

``````#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<bitset>
#include<ctime>
#include<deque>
#include<stack>
#include<functional>
#include<sstream>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 200005
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const int mod = 1e9 + 7;
#define pi acos(-1.0)
#define pii pair<int,int>
#define eps 1e-5
#define pll pair<ll,ll>
#define lson 2*x
#define rson 2*x+1

long long  qupower(int a, int b) {
long long  ans = 1;
while (b) {
if (b & 1)ans = ans * a;
b >>= 1;
a = a * a;
}
return ans;
}

int an = 0, x = 1; char c = getchar();
while (c > '9' || c < '0') {
if (c == '-') {
x = -1;
}
c = getchar();
}
while (c >= '0'&&c <= '9') {
an = an * 10 + c - '0'; c = getchar();
}
return an * x;
}

int t;
int n,k;
int a[200003], b[200003], sum[200003];

void solve(){
ms(a);ms(b);ms(sum);
for(int i=1;i<=n-1;i++){
if(a[i]<2*a[i+1])b[i] = 1;
}
b[n] = 1;
for(int i=1;i<n;i++)sum[i] = sum[i-1]+b[i];
int ans = 0;
for(int i=1;i<=n-k;i++){
if(sum[i+k-1]-sum[i-1]==k)ans++;
}
cout<<ans<<endl;
}

int main(){
//ios::sync_with_stdio(false);