太久没打CF了，再加上有一段时间没用C++写程序。这把复建局
A. Cipher Shifer
题面
由题意可知只需要从头到尾遍历字符串，去掉最近的两个相同字母之间的部分即可。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
int n;
string s;
cin>>n>>s;
int cnt=0;
char ch=s[0];
for(int i=0;i<n;i++)
{
if(s[i]==ch)
cnt++;
if(cnt==2)
{
cout<<s[i];
if(i<n-1)
ch=s[i+1];
cnt=0;
}
}
cout<<'\n';
}
return 0;
}B. Binary Cafe
题面
因为每个点心的价格都是二的幂，所以不同点心的选取组合就是一个二进制串。由二进制串的表示唯一性可以知道只需要算出最大的二进制串是什么就行。
而最大的二进制串就是可以花出去的最多的钱。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
ll n,k;
cin>>n>>k;
if(k>log2(n+1))
cout<<n+1<<'\n';
else
{
ll x=1;
while(k--)
x*=2;
cout<<min(n+1,x)<<'\n';
}
}
return 0;
}C. Ski Resort
题面
首先可以肯定的是需要找出所有的连续的温度适宜天气，记录每一段的长度。
这些段中长度不足k的肯定不能出行，只需要计算长度大于等于k的段的出行方法的和。
需要注意的是，安排出行的日期必须是连续的(一开始没注意到这一点，问题被转化成组合数求和，TLE卡了很久😥)。
设段的长度为
所以总的方法数即为
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll a[N];
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
ll n,k,q;
cin>>n>>k>>q;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]>q)
a[i]=0;
else
a[i]=1;
}
vector<int>vc;
int cnt=0;
for(int i=1;i<=n;i++)
{
if(a[i]==1)
{
if(i<n)
cnt++;
else
vc.push_back(++cnt);
}
else
{
vc.push_back(cnt);
cnt=0;
}
}
ll ans=0;
for(auto it:vc)
{
if(it>=k)
ans+=(it-k+2)*(it-k+1)/2;
}
cout<<ans<<'\n';
}
return 0;
}D. Wooden Toy Festival
题面
题面意思即为在数轴上选取三个点，使得以这三个点画相同半径的圆包住所有点所需的半径最小。
(一开始理解错题意卡了好久🤡)
可以发现直接求出点或半径不容易，但是验证一个方案很简单。
所以可以用二分，对半径二分，每次验证半径能否将点集覆盖。验证可以从最左边开始，加两个半径之后找比这个数还大的第一个数，然后再加两个半径，再比较。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll a[N];
int n;
bool judge(int x)
{
int y=a[1]+2*x;
int pos=upper_bound(a+1,a+1+n,y)-a;
if(pos>=n)
return true;
y=a[pos]+2*x;
pos=upper_bound(a+1,a+1+n,y)-a;
if(pos>=n)
return true;
y=a[pos]+2*x;
if(y>=a[n])
return true;
return false;
}
ll ceil(ll x,ll n)
{
if(x%n==0)
return x/n;
else
return x/n+1;
}
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+1+n);
ll left=0,right=ceil(a[n]-a[1],3);
ll res=-1;
while(left<right)
{
ll mid=(left+right)>>1;
if(judge(mid))
{
right=mid;
res=mid;
}
else
left=mid+1;
}
if(res==-1)
cout<<right<<'\n';
else
cout<<res<<'\n';
}
return 0;
}E. Character Blocking
题面
就是一个模拟，当时没时间写了。
ACTLE代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int tim[N];
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
memset(tim,0,sizeof(tim));
string s1,s2;
cin>>s1>>s2;
int t,q;
cin>>t>>q;
for(int i=1;i<=q;i++)
{
int op;
cin>>op;
if(op==1)
{
int pos;
cin>>pos;
if(tim[pos-1]<i)
tim[pos-1]=i+t-1;
else
tim[pos-1]+=t-1;
}
else if(op==2)
{
int x_1,pos1,x_2,pos2;
cin>>x_1>>pos1>>x_2>>pos2;
/*if(tim[pos1-1]>=i||tim[pos2-1]>=i)
continue;
else
{*/
if(x_1==1&&x_2==1)
swap(s1[pos1-1],s1[pos2-1]);
else if(x_1==2&&x_2==2)
swap(s2[pos1-1],s2[pos2-1]);
else
{
if(x_1==2)
swap(pos1,pos2);
swap(s1[pos1-1],s2[pos2-1]);
}
//}
}
else if(op==3)
{
bool flag=true;
for(int j=0;j<s1.length();j++)
{
if(tim[j]>=i)
continue;
else
{
if(s1[j]!=s2[j])
{
flag=false;
break;
}
}
}
if(flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}
}
return 0;
}