Dashboard - CodeCraft-22 and Codeforces Round #795 (Div. 2) - Codeforces
https://codeforces.com/contest/1691
目录
A. Beat The Odds
问最少删除几个,可以让所给数组相邻的两个值的和均为偶数.
思路:
已知偶数+偶数=偶数,奇数+奇数=偶数,奇数+偶数=奇数.所以,只要剩下的都是奇数或者偶数即可.即删去所有的奇数或者偶数.
#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
void solve()
{
int x,n,ou=0,ji=0;
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&x);
if(x%2==0)
{
ou++;
}
else if(x%2==1)
{
ji++;
}
}
printf("%lld\n",min(ou,ji));
return ;
}
signed main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}B. Shoe Shuffling
有n个人,他们每个人有一双鞋.且鞋子的排列是非递减的.问是否存在一种情况,每个人得到不是自己的鞋子,且新鞋子的尺码大于或者等于旧鞋子的尺码.
思路:
只要每一种尺码的鞋子不少于两双就可以实现.把尺码相同的鞋子交换即可.做法就是把相同的鞋子分为一块,然后在这个块内进行颠倒顺序即可.
#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
using namespace std;
int arr[100005];
map<int,int>ma;
void solve()
{
ma.clear();
int n;
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&arr[i]);
ma[arr[i]]++;
}
if(n==1)
{
cout<<"-1\n";
return ;
}
for(auto x:ma)
if(x.second==1)
{
cout<<"-1\n";
return ;
}
int tot=1;
for(auto x:ma)
{
int st=tot;
for(int j=1;j<x.second;j++)
{
tot++;
cout<<tot<<" ";
}
tot++;
cout<<st<<" ";
}
cout<<"\n";
return ;
}
signed main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}C. Sum of Substrings
给你一个01串.计算贡献的方式是遍历第一位到字符串倒数第二位,计算此为和它下一位的数字组成的十进制数的和,即为贡献.每次我们可以把某一位的字符和相邻位字符交换,可交换k次,问k次交换之内,可以得到的最小贡献.
思路:其实很简单,多美居几种情况之后,就会发现,只有当最后一位或者第一位没有1,再把其他地方的1移过来才能让贡献减小.所以针对这两种情况分类讨论,求最小值即可.
#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
string s;
void solve()
{
int sum=0,n,k,st=-1,en=-1;
scanf("%lld%lld",&n,&k);
cin>>s;
for(int i=s.size()-1;i>=0;i--)
if(s[i]=='1')
{
en=i;
break;
}
for(int i=0;i<s.size();i++)
if(s[i]=='1')
{
st=i;
break;
}
for(int i=1;i<s.size();i++)
{
sum+=(s[i-1]-'0')*10+s[i]-'0';
}
if(en==-1&&st==-1)
{
cout<<sum<<"\n";
return ;
}
else if(en==st&&en!=-1)
{
if(k>=s.size()-1-en)
{
cout<<min(sum,(int)1)<<"\n";
return ;
}
else if(k>=st)
{
cout<<min(sum,(int)10)<<"\n";
return ;
}
else
{
cout<<sum<<"\n";
return ;
}
}
else
{
if(k>=s.size()-1-en&&en!=s.size()-1)
{
k-=(s.size()-1-en);
sum-=10;
}
if(k>=st&&st!=0)
{
k-=st;
sum--;
}
cout<<sum<<"\n";
return ;
}
return ;
}
signed main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}D. Max GEQ Sum
题意:题目给你一个数组,问你该数组的所有子区间是否满足该子区间的最大值大于或者等于该区间值的和.
思路:首先看题,可知我们要维护的是一个区间前缀和的最大值,最小值..针对于数组的每个值,我们去贪心的寻找到以该值最为最大值的情况下区间值的和最大的情况.因为当这个数字作为区间最大值时,只要连包含该数字的区间和的最大值都小于该数字,那么肯定成立.那么我们就枚举数组的每个值的区间来判断.
如何找到这个特殊的,以该数字作为最大值且区间和最大的情况呢.可以采用单调栈的方式,去求的每个数左边和右边第一个比它大的数字的位置这两个位置(不包含端点)存在一个区间是最大值,因为要使该数字为最大值,区间内就不能出现更大的.所以我们在该数字右边寻找在区间内的前缀和最大值,在左边寻找前缀和最小值(因为要包含这个数,所以要再亮边找).用有短的最大值减去左端的最小值,即为最大的区间的和.再将这个值与原数比较即可.
#include<map>
#include<cmath>
#include<set>
#include<stack>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
struct node
{
int l,r;
int maxx,minn;
}tr[800005];
int arr[200005],sum[200005];
int lmax[200005],rmax[200005];
void build(int node ,int l,int r)
{
tr[node].l=l,tr[node].r=r;
if(l==r)
{
tr[node].maxx=sum[l];
tr[node].minn=sum[l];
return;
}
int mid=(l+r)/2;
int L=node<<1,R=(node<<1)+1;
build(L,l,mid);
build(R,mid+1,r);
tr[node].maxx=max(tr[L].maxx,tr[R].maxx);
tr[node].minn=min(tr[L].minn,tr[R].minn);
return ;
}
int query1(int node,int l,int r)
{
if(l<=tr[node].l&&tr[node].r<=r)
return tr[node].maxx;
int mid=(tr[node].l+tr[node].r)/2;
int L=node<<1,R=(node<<1)+1;
int maxx=-1e9;
if(l<=mid)maxx=max(maxx,query1(L,l,r));
if(r>mid)maxx=max(maxx,query1(R,l,r));
return maxx;
}
int query2(int node,int l,int r)
{
if(l<=tr[node].l&&tr[node].r<=r)
return tr[node].minn;
int mid=(tr[node].l+tr[node].r)/2;
int L=node<<1,R=(node<<1)+1;
int maxx=1e18;
if(l<=mid)maxx=min(maxx,query2(L,l,r));
if(r>mid)maxx=min(maxx,query2(R,l,r));
return maxx;
}
/*
线段树维护的是前缀和的最大值和最小值
*/
stack<int>st;
void solve()
{
arr[0]=1e9+7;
int n;
scanf("%lld",&n);
arr[n+1]=1e9+7;
for(int i=1;i<=n;i++)
{
scanf("%lld",&arr[i]);
sum[i]=sum[i-1]+arr[i];
}
build(1,0,n);
while(st.size())
st.pop();
st.push(0);
for(int i=1;i<=n;i++)
{
while(arr[st.top()]<=arr[i])
st.pop();
lmax[i]=st.top();
st.push(i);
}
//向右跑,用单调栈找到每个数右边第一个大于它的数
while(st.size())
st.pop();
st.push(n+1);
for(int i=n;i>=1;i--)
{
while(arr[st.top()]<=arr[i])
st.pop();
rmax[i]=st.top();
st.push(i);
}
//向左跑,用单调栈找到每个数左边第一个大于它的数
while (st.size())
st.pop();
for(int i=1;i<=n;i++)
{
if(query1(1,i,rmax[i]-1)-query2(1,lmax[i],i-1)>arr[i])
{
去最大区间和和该数字比较进行判断
printf("NO\n");
return ;
}
}
printf("YES\n");
return ;
}
signed main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}加油!
