比赛地址:https://ac.nowcoder.com/acm/contest/11232
A:
首先,si+i%26与si+i的结果相同,下面的变量i自动变为i%26
分以下4种情况讨论:
① i为奇数,si+i 不超过z
直接把i加上去即可
② i为奇数,si+i 超过z
超过z,需要把超过的部分从a开始算,因为i取模之后小于26,所以超过的部分从a开始加时,不会超过z
③ i为偶数, si-i 不小于a
直接把i减上去即可
④ i为偶数, si-i小于a
小于a,需要把小于的部分从z开始减
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
string s;
cin>>s;
for(int i=1;i<=n;i++)
{
int x;
if(i%2==1)
{
if(s[i-1]+i%26>'z')
{
x='a'+(s[i-1]+i%26-'z')-1;
}
else
{
x=s[i-1]+i%26;
}
}
else
{
if(s[i-1]-i%26<'a')
{
x='z'-('a'-(s[i-1]-i%26))+1;
}
else
{
x=s[i-1]-i%26;
}
}
s[i-1]=x;
}
cout<<s<<endl;
return 0;
}B和C:
因为B题和C题只有输出上的不同,所以一起讲,在比赛的时候,看见这种题,最好先做C题,这样B题把输出删掉就行,而如果先做B题,用了不太方便改输出的方法,就可能会少了一题的分,这也是做题的一种策略吧
用一个二维vector记录下每种字符出现的位置,这里有一个优化,连续的相同字符只需要计算一次,因为选出来的字符串是单调严格递增的,所以不可能存在连续的相同字符
接下来只需要枚举,枚举字符串第一个字符是什么,第二个字符是什么,利用STL中的upper_bound函数,返回某个字符出现位置第一个大于指定位置的答案,这可以很方便地求出答案
程序中的check1函数为将字符转为数字编码,check2函数为将数字编码转为字符,接下来给出这两题的代码:
//B
#include<bits/stdc++.h>
using namespace std;
int ans=0;
int check1(char x)
{
if(x>='0'&&x<='9') return x-'0';
return x-'A'+10;
}
char check2(int x)
{
if(x>=0&&x<=9) return (char)(x+'0');
return (char)(x-10+'A');
}
string s;
vector<int> a[16];
int dfs(int x,int wei,string s2)
{
for(int i=x;i<=15;i++)
{
auto it=upper_bound(a[i].begin(),a[i].end(),wei);
if(it!=a[i].end())
{
ans++;
dfs(i+1,*it,s2+check2(i));
}
}
return 0;
}
int main()
{
cin>>s;
for(int i=0;i<s.size();i++)
{
a[check1(s[i])].push_back(i);
}
dfs(0,-1,"");
cout<<ans<<endl;
return 0;
}//C
#include<bits/stdc++.h>
using namespace std;
int check1(char x)
{
if(x>='0'&&x<='9') return x-'0';
return x-'A'+10;
}
char check2(int x)
{
if(x>=0&&x<=9) return (char)(x+'0');
return (char)(x-10+'A');
}
string s;
vector<int> a[16];
int dfs(int x,int wei,string s2)
{
for(int i=x;i<=15;i++)
{
auto it=upper_bound(a[i].begin(),a[i].end(),wei);
if(it!=a[i].end())
{
cout<<s2<<check2(i);
printf("\n");
dfs(i+1,*it,s2+check2(i));
}
}
return 0;
}
int main()
{
cin>>s;
for(int i=0;i<s.size();i++)
{
a[check1(s[i])].push_back(i);
}
dfs(0,-1,"");
return 0;
}
京公网安备 11010502036488号