比赛地址: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; }