文章目录
- 写在前面
- A- Primary Task
- B. Seating in a Bus
- C- Numeric String Template
- D- Right Left Wrong
- E- Photoshoot for Gorillas
- F- Color Rows and Columns
写在前面
赛时写的还挺快的，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
这时我们就需要考虑它是否超出右边界，如果超出右边界，就需要减去超出的数量
因此，它的公式就为
m
i
n
(
k
,
j
+
1
)
−
m
a
x
(
j
+
k
−
m
,
0
l
l
)
min(k,j+1)-max(j+k-m,0ll)
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
a=1 并且 b=1
a=1并且b=1，那么填入这个格子，它的分数是+2的
每操作一次，我们就对当前价值和重量进行01背包的处理
由于上述可能会出现+2的情况，我们最终的分数k+1可能会比分数k的操作数更少，所以在进行DP时，它的上限为k+1
最后比较
f
[
k
]
和
f
[
k
+
1
]
f[k]和f[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 ;
}