Codeforces Round 799 (Div. 4)
目录
A. Marathon
B. All Distinct
C. Where’s the Bishop?
D. The Clock
E. Binary Deque
F. 3SUM
G. 2^Sort
H. Gambling
A. Marathon
直接模拟
void solve()
{int ans=0;for(int i=1;i<=4;i++) {cin>>a[i];if(i>1&&a[i]>a[1]) ans++;}cout<<ans<<endl;return ;
}B. All Distinct
把重复的数删除然后判断是不是删的偶数个不是就再减去一个即可
void solve()
{cin>>n;vector<int> a;for(int i=1;i<=n;i++){int x; cin>>x;a.push_back(x);}sort(a.begin(),a.end());a.erase(unique(a.begin(),a.end()),a.end());int now=n-a.size();cout<<(now%2==0 ? a.size() : a.size()-1)<<endl;return ;
}C. Where’s the Bishop?
简单的八皇后行列的性质,也就是副对角线的是行列之和相等,主对角线是差值相等需要加上n防止越界,接着谁所在的行列之和最大谁就是king
char a[M][M];
int d[M],ud[M];
void solve()
{n=m=8;memset(d,0,sizeof d);memset(ud,0,sizeof ud);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];if(a[i][j]=='#'){d[i+j]++;ud[8-i+j]++;}}}int x=0,y=0,ma=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(d[i+j]+ud[8-i+j]>ma){ma=d[i+j]+ud[8-i+j];x=i,y=j;}}}cout<<x<<" "<<y<<endl;return ;D. The Clock
简单模拟即可,我们发现这一类题目都是数据范围很小 我们可以先装为总的分钟再来变化即可用mp记录是否出现过
map<PII,int> mp;
void solve()
{string s; cin>>s>>m;h=(s[0]-'0')*10+s[1]-'0';n=(s[3]-'0')*10+s[4]-'0';mp.clear();int hh=m/60,mm=m-hh*60;int ans=0;while(1){if(mp[{h,n}]) break;mp[{h,n}]++;string x,y;int xx=h,yy=n;while(xx){x+=xx%10+'0';xx/=10;}while(yy){y+=yy%10+'0';yy/=10;}if(h<10) x+='0';if(n<10) y+='0';reverse(x.begin(),x.end());if(x==y) ans++;h+=hh,n+=mm;if(n>=60) n-=60,h++;if(h>=24) h-=24;}cout<<ans<<endl;return ;
}E. Binary Deque
简单性质使用 要删除的最少也就是留下的最多我们可以考虑使用双指针,如果后面多了一定要删去前面的
void solve()
{cin>>n>>m;int sum=0;for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];if(sum<m) cout<<-1<<endl;else{sum=0;int ans=0;for(int i=1,j=1;i<=n;i++){sum+=a[i];while(sum>m){sum-=a[j];j++;}if(sum==m) ans=max(ans,i-j+1);}cout<<n-ans<<endl;}return ;
}F. 3SUM
考虑到我们只需要看最后一个位置所以我们只需要把每一个数的最后一位取出来即可然后直接
暴力即可
int a[10];
void solve()
{cin>>n;memset(a,0,sizeof a);for(int i=1;i<=n;i++){int x; cin>>x;a[x%10]++;}for(int i=0;i<=9;i++){for(int j=0;j<=9;j++){for(int k=0;k<=9;k++){if(i==j&&j==k&&a[i]<3) continue;if(i==j&&a[i]<2) continue;if(i==k&&a[i]<2) continue;if(j==k&&a[j]<2) continue;if(!a[i]||!a[j]||!a[k]) continue;if((i+j+k)%10==3){cout<<"YES"<<endl;return ;}}}}cout<<"NO"<<endl;return ;
}G. 2^Sort
我们发现变化的其实之后后面一个数多乘以2了后面也是一样的就判断 是否满足即可如果不满足重新开始,双指针算法
int a[N];
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];int ans=0,len=1;for(int i=2;i<=n;i++){if(a[i]*2>a[i-1]) len++;else{if(len>m) ans+=len-m;len=1;}} if(len>m) ans+=len-m;cout<<ans<<endl;return ;
}H. Gambling
我们发现其实只需要对每一个数来判断即可我们也就是求一个数的区间的数量减去其他数的数量,
我们可以把这个数看成1,其它的数就是-1来计算贡献来维护一个前缀最小的即可
void solve()
{cin>>n;map<int,set<PII>> mp;int res=0,a=0,l=0,r=0;for(int i=1;i<=n;i++){int x; cin>>x;int sum=2*mp[x].size()-i;mp[x].insert({sum-1,i});// auto it=*mp[x].begin();if(sum-it.first>res){res=sum-it.first;a=x;l=it.second;r=i;}}cout<<a<<" "<<l<<" "<<r<<endl;
}