CF1907总结
A.Rook
题面翻译
给出车在国际象棋棋盘中的位置，输出其可到达的坐标（不必在意顺序）。
车可以横着或竖着走任意格数。
分析
题意明了，输出车所在行和列所有格子的序号（除车所在位置外）。
code
#include <bits/stdc++.h>
using namespace std;
int t;
void solve()
{
string x;
cin>>x;
int a=x[0];
int b=x[1]-'0';
for(int i=1;i<=8;i++) if(i!=b) cout<<(char)a<<i<<"\n";
for(int i='a';i<='h';i++) if(a!=i) cout<<(char)i<<b<<"\n";
}
int main ()
{
cin>>t;
while(t--) solve();
return 0;
}
B.YetnotherrokenKeoard
题面翻译
Polycarp 的笔记本键盘坏了。
现在，当他按下 'b' 键时，它的行为类似于退格键：删除已输入字符串中最后一个小写字母。如果已输入字符串中没有小写字母，则完全忽略该按键。
类似地，当他按下 'B' 键时，它删除已输入字符串中最后一个大写字母。如果已输入字符串中没有大写字母，则完全忽略该按键。
给定一个按键序列，输出处理所有按键后的结果。
分析
用两个栈分别存下大写和小写字母的位置，每次删除时若栈非空则取对应栈顶位置删除。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int n,m,t,i1[N],i2[N];
char a[N];
string s;
void solve()
{
cin>>s;
n=s.size();
int t1=0,t2=0;
for(int i=0;i<n;i++)
{
a[i]=0;
int x=s[i];
if(x=='b')
{
if(t1)
{
a[i1[t1--]]=0;
}
}
else if(x=='B')
{
if(t2)
{
a[i2[t2--]]=0;
}
}
else
{
if(x>='a'&&x<='z') i1[++t1]=i;
if(x>='A'&&x<='Z') i2[++t2]=i;
a[i]=x;
}
}
for(int i=0;i<n;i++) if(a[i]!=0) cout<<a[i];
cout<<"\n";
}
int main ()
{
cin>>t;
while(t--) solve();
return 0;
}
C.Removal of Unattractive Pairs
题面翻译
有一个长为 \(n\) 的字符串，每次可以删除相邻两个不同的字符，问删除若干次最终可能的最短长度
分析
这让我想到一种类似的题，只不过是把题目和解法反过来。
已知小写字母组成的长度为 \(n\) 的字符串，求个数超过 \(n/2\) 的小写字母，保证至多至少有一个，\(1<n<1e8\)。
- 直接排序，取最中间的那个数，复杂度为 \(O(nlogn)\)。
- 用一个桶统计个数，再找出满足的那个，复杂度为 \(O(n)\)。
还能不能更快呢？于是聪明的你一定能想到每次读入后删掉两个不同的字母，没错，删掉两个不同的字母后，永远不会影响我们要求的答案。用我们要求的答案来和其他字母相删，最后一定有剩余。这样就能做到更快的线性复杂度求出答案了。
接下来回到这道题，考虑删除难想，不如考虑不删除的情况：
- 字符串为空。
- 只剩下一个字符。
那就好了，相邻的限制已经无所谓了，我们可以知道最短的长度就是让数量最多的字母与其他字母互删，得到剩下的数量 \(num\)，还要注意 \(n\) 如果是奇数的话一定会剩下一个，最后答案就是 \(max(num,n&1)\)。
code
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,t,a[N];
string s;
void solve()
{
cin>>n>>s;
for(int i=0;i<n;i++) a[s[i]-'a']++;
int ma=0;
for(int i=0;i<26;i++) ma=max(ma,a[i]),a[i]=0;
cout<<max(n&1,ma*2-n)<<"\n";
}
int main ()
{
cin>>t;
while(t--) solve();
return 0;
}
D.Jumping Through Segments
题面翻译
数轴上有 \(n\) 条线段，第 \(i\) 条线段的范围是 \([l_i,r_i]\)。
开始时在原点，每次可以跳至多 \(k\) 的距离，但是在第 \(i\) 次跳跃后一定要站在第 \(i\) 条线段上。
求出最小的 \(k\) 使得你可以跳到第 \(n\) 条线段上。
分析
求最小的 k 值，已知上界和下界，不难看出可以用二分答案，重点思考如何进行判断。
考虑每一步可以到达的区间，第一步可到达 \([-k,k]\) 如果和第二段没有交集，那肯定不满足要求，如果有交集说明下一步要从这交集开始跳，于是范围就变为 \([l-k,r+k]\)。于是我们只需要一直求交集判断下一步是否有交集直到最后。
总复杂度为 \(O(nlogk)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,m,t,a[N],b[N];
int check(int k)
{
int l=0,r=0;
for(int i=1;i<=n;i++)
{
l-=k,r+=k;
if(l>b[i]||r<a[i]) return 1;
l=max(l,a[i]),r=min(r,b[i]);
}
return 0;
}
void solve()
{
cin>>n;
int l=0,r=1,mid;
for(int i=1;i<=n;i++) cin>>a[i]>>b[i],r=max(r,b[i]);
while(l<r)
{
mid=(l+r)>>1;
if(check(mid)) l=mid+1;
else r=mid;
}
cout<<l<<"\n";
}
int main ()
{
cin>>t;
while(t--) solve();
return 0;
}
E.Good Triples
题面翻译
给定一个整数 \(n\)，我们称三元组 \((a,b,c)\) 是“好的”，当且仅当 \(a+b+c=n\) 并且 \(digsum(a)+digsum(b)+digsum(c)=digsum(n)\)。这里的 \(digsum(x)\) 指的是 \(x\) 各个数位之和。
并且三元组的顺序也很重要。例如 \((4,12,10)\) 和 \((10,12,4)\) 不是相同的三元组。
求不同三元组的数量。
分析
容易看出，如果没有进位，则一定能满足条件，如果产生进位，则 \(digsum(a)+digsum(b)+digsum(c)>digsum(n)\)。所以每一位分开来考虑，计算贡献。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,m,t,a[N];
void solve()
{
string s;
cin>>s;
n=s.size();
ll ans=1;
for(int i=0;i<n;i++) ans*=a[s[i]-'0'];
cout<<ans<<"\n";
}
int main ()
{
a[0]=1;
for(int i=1;i<=9;i++) a[i]=a[i-1]+i+1;
cin>>t;
while(t--) solve();
return 0;
}