Codeforces Round 784 (Div. 4)
title: Codeforces Round 784 (Div. 4)
categories:
- ICPC
tags:
- null
abbrlink: 4bd1638e
date: 2024-02-25 00:00:00
Codeforces Round 784 (Div. 4)
感觉是所有cf里简单的一场了
D:题意:给一排白砖染色,每次可以选择两个相邻的数染成红蓝或蓝红,可以覆盖。多次询问,每次给出一个终态(红蓝白),问这个状态有没有可能作为终态?
Solution:快速猜猜题.首先发现white直接将状态分割成若干段,也就是染色操作显然不能跨过W,所以考虑单独考察某一段,发现无论怎么操作只要出现两种颜色怎么样都能成功,所以对每个段维护颜色种类数,每段的种类数都为2才合法。
void solve(){
cin>>n;
string str;cin>>str;str=" "+str;
bool flag=true;
set<char>s;
bool end=0;
bool st=0;
for(int i=1;i<=n;i++){
if(str[i]=='W'){
if(i==n)end=true;
if(s.size()<=1&&st)flag=false;
s.clear();
}
else {
//len++;
st=true;
s.insert(str[i]);
}
}
if(end==0&&s.size()<=1)flag=false;
if(flag)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
E:题意:给出n个二元组,查询有多少对二元组恰好有一维相同。
Solution:考虑到偏序关系,对于当前二元组,我们只考虑在我们前面的元素。考虑维护第一维,第二维,二元组的三个哈希表记录出现次数,简单的容斥考虑我们需要发现重复出现的二元组会多加2,故mp[x]+mp[y]-2*mp[str]
void solve(){
map<char,int>mp1,mp2;
map<string,int>mp;
cin>>n;int ans=0;
for(int i=1;i<=n;i++){
string s;cin>>s;
//对于完全相同子串会计算两次
ans+=mp1[s[0]]+mp2[s[1]]-mp[s]*2;
//cerr<<ans<<endl;
mp[s]++;mp1[s[0]]++;mp2[s[1]]++;
}
cout<<ans<<endl;
}
找到不相交前缀和后缀,满足前缀和=后缀和,求两段长度和最大值
Solution:考虑维护后缀和的哈希表,后缀和映射到后缀左端点,每次查询前缀和是不是在哈希表中并且查询端点有没有相交,判断合法性,维护长度之和最大值。
void solve(){
int ans=0;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
vector<int>pre(n+1,0),suf(n+2,0);
for(int i=1;i<=n;i++)pre[i]=pre[i-1]+a[i];
for(int i=n;i>=1;i--)suf[i]=suf[i+1]+a[i];
map<int,int>pr,su;
for(int i=1;i<=n;i++){
pr[pre[i]]=i;
su[suf[i]]=i;
}
for(int i=1;i<=n;i++){
if(su.count(pre[i])==0)continue;
int pos=su[pre[i]];
if(pos>i){
if(ans<i+n-pos+1){
ans=i+n-pos+1;
}
}
}
cout<<ans<<endl;
}
G:题意:给定一个网格图,有物体,障碍,空白。要求给出物体自由落体的结果图。
Solution:考虑最下面的物体落到障碍物或者最后一行(地上),我们应该从行的逆序考虑,因为只有下面的物体确定,上面的物体才能确定。对于每个物体我们直接进行暴力下行试探,看什么时候出边界或者遇到障碍物或者遇到已经确定位置的球。
void solve(){
cin>>n>>m;
vector<string>v(n+1);
for(int i=1;i<=n;i++){
string s;cin>>s;
v[i]=" "+s;
}
for(int i=n;i>=1;i--){
for(int j=1;j<=m;j++){
if(v[i][j]=='*'){
int x=i;
while(x+1<=n&&v[x+1][j]=='.')x+=1;
swap(v[i][j],v[x][j]);
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<v[i][j];
}
cout<<endl;
}
//cout<<endl;
}
H:题意:给定n个数,有k次操作的机会,每次可以给一个数int范围内的某个二进制位变为1,要求k次操作结束后,最大化数组的与和值(n个数与起来)
Solution:首先统计每一位是0的数的个数。考虑按高位贪心,如果剩余次数足以完成本次贪心,那么维护次数,更新答案。否则,就考虑下一位。
void solve(){
//cerr<<(1<<31)-1<<endl;
cin>>n;int k;cin>>k;
for(int i=1;i<=n;i++)cin>>a[i];
vector<int>v(40,0);
for(int i=1;i<=n;i++){
for(int j=30;j>=0;j--){
int u=(a[i]>>j)&1;
if(u==0)v[j]++;
}
}
int ans=0;
for(int i=30;i>=0;i--){
if(k>=v[i]){
ans|=(1<<i);
k-=v[i];
}
}
cout<<ans<<endl;
}
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog!