第一题:给出两个长度均为n的字符串A, B(只包含小写字母),求字典序介于这两个字符串之间的且长度为n的字符串有多少个, 即满足 A < X < B;
思路:直接把字符串看出是一个26进制的数据,然后相减的结果 - 1 就是答案了!
注意:26^10 超过了int的范围,所以用long long, 最后5min通过,卡崩溃了...
代码:AC
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define pii pair<int, int> #define pll pair<ll, ll> #define mp make_pair #define ios ios::sync_with_stdio(false),cin.tie(0); template <typename T> inline void read(T &x) {char ch=getchar(); int f=1; x=0; while(!isdigit(ch)){if(ch=='-')f *= -1; ch=getchar();} while(isdigit(ch)) {x = (x<<1) + (x<<3) + (ch^48); ch=getchar();} x*=f;} ll qpow(ll x, ll y) { ll a=1, b=x; while(y){if(y&0x1) a*=b; b*=b; y>>=1;} return a;} int main(void) { #ifndef ONLINE_JUDGE freopen("a.txt", "r", stdin); #endif int t, n; string stra, strb; cin >> t; while(t--) { cin >> n >> stra >> strb; if(stra >= strb) { cout << 0 << endl; continue; } int a[16] = {0}; int b[16] = {0}; for(int i = 0; i < n; ++i) { a[i] = stra[i] - 'a' + 1; b[i] = strb[i] - 'a' + 1; } int pos = 0; for(int i = 0; i < n; ++i) if(a[i] != b[i]) {pos = i; break;} ll suma = 0, sumb = 0, t = 1; for(int i = pos+1; i < n; ++i) { suma = suma * 26 + (ll)a[i]; sumb = sumb * 26 + (ll)b[i]; t *= 26; } printf("%lld\n", sumb + 1LL * t * (b[pos] - a[pos]) - suma - 1LL); } return 0; }
第二题:题目刚刚读完,最后2分钟交卷了,我也太菜了!
我感觉第二题不是那么难,有点01背包的味道,耗费忍耐值,得到对应的数量的怪!可能与阿里无缘了,不用惦记了!
全部评论
(5) 回帖