对Niko的崇拜并不能使我顺利做出G2题😢
A. Codeforces Checking
注意别漏字母就行.
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define lowbit(x) ((x)&-(x))
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
char c;
cin>>c;
if(c=='c'||c=='o'||c=='d'||c=='e'||c=='f'||c=='r'||c=='s')
cout<<"YES"<<'\n';
else
cout<<"NO"<<'\n';
}
return 0;
}B. Following Directions
把题意翻译一下即可.
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define lowbit(x) ((x)&-(x))
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
string s;
cin>>s;
int x=0,y=0;
bool flag=false;
for(int i=0;i<n;i++)
{
if(s[i]=='L')
x--;
else if(s[i]=='R')
x++;
else if(s[i]=='U')
y++;
else if(s[i]=='D')
y--;
if(x==1&&y==1)
{
cout<<"YES"<<'\n';
flag=true;
break;
}
}
if(!flag)
cout<<"NO"<<'\n';
}
return 0;
}C. Prepend and Append
明显操作可以回溯回去.
只需从最终的二进制串往回推，推到不能动了就是最短初始串.
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define lowbit(x) ((x)&-(x))
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
string s;
cin>>s;
int len=s.length();
int i=0,j=len-1;
while(i<=j)
{
if((s[i]=='0'&&s[j]=='1')||(s[i]=='1'&&s[j]=='0'))
len-=2;
else
break;
i++,j--;
}
cout<<len<<'\n';
}
return 0;
}D. Distinct Split
需要注意的是分成的两个子串各自连续，所以不能直接
先遍历一遍原字符串获得每个字母出现次数，用map记录.
注意到如果字符串
所以两个子串是原子串的一个划分时是更优的.
只需要枚举中间断点的位置，有
断点向右移动时，同时更新左右子串的
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define lowbit(x) ((x)&-(x))
map<char,int>mp,mp1;
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
string s;
cin>>s;
mp.clear(),mp1.clear();
for(int i=0;i<s.length();i++)
{
mp[s[i]]++;
}
int ans=0;
for(int i=0;i<s.length();i++)
{
mp1[s[i]]++;
mp[s[i]]--;
int an=0;
for(auto it=mp.begin();it!=mp.end();it++)
an+=min(1,it->second);
for(auto it=mp1.begin();it!=mp1.end();it++)
an+=min(1,it->second);
ans=max(an,ans);
}
cout<<ans<<'\n';
}
return 0;
}E. Negatives and Positives
将相邻两个数置为相反数的操作可以做无数次，可以想到将两个数拓展为一串数，都进行一遍题中的操作，那么这一串数的中间的数都改变了两次符号(相当于没变号)，只有两端变号.
操作可以等效为在
题目要求将
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define lowbit(x) ((x)&-(x))
const int N=2e5+5;
int a[N];
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
int m=1e9+5;
int cnt=0;
ll sum=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum+=labs(a[i]);
m=min(m,abs(a[i]));
if(a[i]<0)
cnt++;
}
if(cnt%2==0)
cout<<sum<<'\n';
else
cout<<sum-2*m<<'\n';
}
return 0;
}F. Range Update Point Query
发现并不需要每操作一次就将
用差分替代区间修改可以大大提高效率.
同时还有时不时的查询(求前缀和)，所以可以用树状数组存储
因为求数位和收敛很快，所以对
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lowbit(x) ((x)&-(x))
const int N=2e5+5;
int a[N];
int dif[N];
void update(int x,int d,int n)
{
while(x<=n)
{
dif[x]+=d;
x+=lowbit(x);
}
}
int sum(int x)
{
int ans=0;
while(x>0)
{
ans+=dif[x];
x-=lowbit(x);
}
return ans;
}
int getnum(int x)
{
int ans=0;
while(x)
{
ans+=x%10;
x/=10;
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
int n,q;
cin>>n>>q;
memset(dif,0,sizeof(dif));
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=q;i++)
{
int op;
cin>>op;
if(op==1)
{
int l,r;
cin>>l>>r;
update(l,1,n);
update(r+1,-1,n);
}
else if(op==2)
{
int x;
cin>>x;
int lazy=sum(x);
int ans=a[x];
while(lazy--)
{
ans=getnum(ans);
if(ans<10)
break;
}
cout<<ans<<'\n';
}
}
}
return 0;
}G1. Teleporters (Easy Version)
可以发现最优的方法下人不会在数轴上闲逛，都是从0坐标直奔目的地然后传送回0坐标.
所以只需要更新权值之后排个序，计算一下元素和即可.
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define lowbit(x) ((x)&-(x))
const int N=2e5+5;
priority_queue<int,vector<int>,greater<int>> s;
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
int n,c;
cin>>n>>c;
while(!s.empty())
s.pop();
int a;
for(int i=1;i<=n;i++)
{
cin>>a;
s.push(a+i);
}
int ans=0;
int cnt=0;
while(!s.empty()&&ans+s.top()<=c)
{
ans+=s.top();
s.pop();
cnt++;
}
cout<<cnt<<'\n';
}
return 0;
}G2. Teleporters (Hard Version)
留坑.
一开始以为成环后跟G1一样，后来发现第一步只能从0开始没有对称性.
解决了第一步似乎就可以了？
看了题解，仿着题解码了一份代码.
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define lowbit(x) ((x)&-(x))
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
int n,c;
cin>>n>>c;
vector<pair<ll,ll>> a;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
a.push_back({x+min(i,n+1-i),x+i});
}
sort(a.begin(),a.end());
vector<ll> pref;
pref.push_back(0);
for(int i=0;i<n;i++)
{
pref.push_back(pref.back()+a[i].first);
}
int ans=0;
for(int i=0;i<n;i++)
{
int new_c=c-a[i].second;
int l=0,r=n;
int mx=0;
while(l<=r)
{
int mid=l+r>>1;
ll price=pref[mid];
int now=mid+1;
if(mid>i)
{
price-=a[i].first;
now--;
}
if(price<=new_c)
{
mx=max(now,mx);
l=mid+1;
}
else
r=mid-1;
}
ans=max(ans,mx);
}
cout<<ans<<'\n';
}
return 0;
}