Codeforces Round 966 (Div. 3)

写在前面

赛时写的还挺快的，50分钟就A了4道题，当时排名已经到2千多了，后面就坐牢1个多小时······，E题一开始想用贪心先把猴子放在网格图的中间，后面觉得实现起来太麻烦了，直接做F题了，赛时也是用的贪心，没过，赛后想了想应该用DP的，本质上就是背包问题，当时没想到这点，DP学了还是不会用，题型还是见太少了····

A- Primary Task

思路

签到题，字符串长度为1或者2 or 字符串前两个字符不为1 0，都输出no
接着特判第三个字符是否为0，还有当长度为3时，第三个字符必须大于1
其他情况输出YES

code

void solve(){string s;cin >> s;if(s.size()==1 || s.size()==2){cout << "NO" << endl;return ;}if(s[0]!='1' || s[1]!='0'){cout << "NO" << endl;return ;} if(s.size()==3 && s[2]<='1' || s[2]=='0'){cout << "NO" << endl;return ;}cout << "YES" << endl;return ;
}

B. Seating in a Bus

思路

除了第一个人，其他人都需要判断当前座位的左右两边是否有人，用一个标记数组即可

code

int a[N],v[N];
void solve(){int n;cin >> n;for(int i=1;i<=n;++i) cin >> a[i];for(int i=1;i<=n+1;++i) v[i]=0;v[a[1]]=1;for(int i=2;i<=n;++i){int flag=0;if(v[a[i]-1]){flag=1;v[a[i]]=1;} if(v[a[i]+1]){v[a[i]]=1;flag=1;} if(flag==0){cout << "NO" << endl;return ;}}cout << "YES" << endl;return ;
}

C- Numeric String Template

思路

考点：模拟

除了第一个字符，其他字符都需要判断当前字符和数字是否一一对应
这时我们需要开两个map数组，一个map是字符判断数字，另一个map是数字判断字符
注意：数字可能为0，所以当数字为0时将0赋值成另一个值即可

code

int a[N];
void solve(){int n;cin >> n;for(int i=1;i<=n;++i) cin >> a[i];int m;cin >> m;while(m--){int flag=1;string s;cin >> s;if(s.size()!=n){cout << "NO" << endl;continue;}s=' '+s;unordered_map<char,int> m2;unordered_map<int,char> m1;if(a[1]==0) a[1]=1e10;m1[a[1]]=s[1];m2[s[1]]=a[1];for(int i=2;i<=n;++i){if(a[i]==0) a[i]=1e10;if(m1[a[i]]==0 && m2[s[i]]==0){m1[a[i]]=s[i];m2[s[i]]=a[i];}else{if(m1[a[i]] && m1[a[i]]!=s[i]){cout << "NO" << endl;flag=0;break;}if(m2[s[i]] && m2[s[i]]!=a[i]){cout << "NO" << endl;flag=0;break;}m1[a[i]]=s[i];m2[s[i]]=a[i];}}if(flag) cout << "YES" << endl;}return ;
}

D- Right Left Wrong

思路

考点：贪心+双指针

由于内层的LR不会影响外层的LR，但是外层的LR会影响内层的LR
好比LLRR，先选里面的LR，不会影响外面的LR

这时，我们就需要从外层开始遍历，l指针为0，r指针为n
每次左指针找到L，右指针找到R，就将里面的值全部加起来
在遍历之前需要先对数组进行前缀和，方便后续相加

code

int a[N],sum[N];
void solve(){int n;cin >> n;for(int i=1;i<=n;++i){cin >> a[i];sum[i]=sum[i-1]+a[i];	} string s;cin >> s;s=' '+s;int ans=0;int pos1=1,pos2=n;while(1){int k1=s.find('L',pos1);int k2=s.rfind('R',pos2);if(k1==-1 || k2==-1) break;for(int i=pos1;i<=k1;++i) s[i]='.';for(int i=k2;i<=pos2;++i) s[i]='.';ans+=sum[k2]-sum[k1-1];pos1=k1+1;pos2=k2-1;}cout << ans << endl;return ;
}

E- Photoshoot for Gorillas

思路

考点：数学思维

首先我们想让价值尽可能大，很容易想到先让数字大的放在网格中间，那么我们只需要考虑每个网格能被扫描几次即可

我们先拿列数来说，如果当前列数小于矩阵k，那么它能被扫描的次数自然也就是它的下标j，否则它能被扫描的次数就为k
这时我们就需要考虑它是否超出右边界，如果超出右边界，就需要减去超出的数量
因此，它的公式就为 $min(k,j+1)-max(j+k-m,0ll)$

行数同理，接着我们将数组从大到小排序，将他们放入进去即可

code

bool cmp(int x,int y){return x>y;
}
void solve(){int n,m,k;cin >> n >> m >> k;int w;cin >> w;vector<int> a(w),cnt;for(auto &x : a) cin >> x;for(int i=0;i<n;++i)for(int j=0;j<m;++j){int x=min(k,j+1)-max(j+k-m,0ll);int y=min(k,i+1)-max(i+k-n,0ll);cnt.push_back(x*y);}sort(a.begin(),a.end(),cmp);sort(cnt.begin(),cnt.end(),cmp);int ans=0;for(int i=0;i<w;++i){ans+=a[i]*cnt[i];}cout << ans << endl;return ;
}

F- Color Rows and Columns

思路

考点：贪心+背包DP
首先我们可以将分数看成重量，将操作数看成价值
既然是DP，我们可以开两个一维数组，一个存总体数据，一个存动态数据（由于是一维，当前状态不能影响上一层的状态，需要多开一个数组）
对于每次的长度和宽度，我们可以用贪心去考虑，每次都填入长度小的那一个
这时我们需要特判一下，当$a=1并且b=1$，那么填入这个格子，它的分数是+2的
每操作一次，我们就对当前价值和重量进行01背包的处理
由于上述可能会出现+2的情况，我们最终的分数k+1可能会比分数k的操作数更少，所以在进行DP时，它的上限为k+1
最后比较 $f[k]和f[k+1]$ 的大小即可

code

const int inf=1e9;
void solve(){int n,k;cin >> n >> k;vector<int> f(k+3,inf),g(k+3,inf);f[0]=0;for(int i=1;i<=n;++i){int a,b;cin >> a >> b; int w=0,v=0;g=f;while(w<=k && a && b){w++;if(a>b){v+=b;a--;}else if(a<b){v+=a;b--;}else{if(a==1){v+=1;w++;a--,b--;}else{v+=b;a--;}}for(int j=k+1;j>=w;--j){g[j]=min(g[j],f[j-w]+v);}}f=g;}int ans=min(f[k],f[k+1]);cout << (ans==inf? -1 : ans) << endl;return ;
}