===== A =====
**题意:**有n个字符串,给定相邻两个字符串的公共前缀长度,输出这n个字符串的一种可能情况
**题解:**第一个字符串全部是a,下一个字符串生成时在公共前缀长度之外的字符进行修改即可。
#include
using namespace std;
int main(){
int t = 0;
cin>>t;
int a[200];
while(t--){
int n;
cin>>n;
for (int i = 0; i < n; ++i) {
cin>>a[i];
}
char s[200][60] = {};
for (int i = 0; i < 50; ++i) {
s[0][i] = 'a';
}
cout<
===== B1 & B2 =====
** 题意 ** 需要从海滩游到海岛上,给定初始时波浪高度等于0时的水深分布,波浪高度在0-k-0-k之间连续变动,已知最深能够游的水深D,求是否可以游到小岛
** 题解 ** 设波浪高度为k-0-k,维护到达位置i时,可能的波浪时间范围[l, r]。位置i+1时,波浪的范围为[l+1, r+1]和 [k - (D - d[i]), k + (D - d[i])]的交,如果长度为0则不可游到。特别的,如果D大于d[i]+k则时间范围为[0,2k-1],即整个长度
特别要注意D - d[i]小于0的情况。这里pretest没有测结果B2 System test的时候WA了
#include
using namespace std;
int d[300005];
int main(){
int t = 0;
cin>>t;
while(t--){
int n, k, l;
cin>>n>>k>>l;
for (int i = 1; i <= n; ++i) {
cin>>d[i];
}
int t1 = 0, t2 = 2*k-1;
bool ok = true;
for (int i = 1; i <= n; ++i) {
if(l - d[i] >= k){
t1 = 0, t2 = 2*k-1;
}
else{
if(l < d[i]){
ok = false;break;
}
int tt1 = k - (l - d[i]);
int tt2 = k + (l - d[i]);
t1++, t2++;
if(tt2 < t1 || tt1 > t2) {
ok = false;
break;
}
t1 = max(tt1, t1);
t2 = min(tt2, t2);
}
}
cout<<(ok ? "Yes" : "No")<
===== C =====
** 题意 ** 给定AB两个a-t组成的字符串,每次可以将A字符串的一种字符改成另一种比其大的字符。求将A字符串改为B字符串的最小步数。如果不存在解输出-1
** 题解 ** 可以等效为建立一个字符构成的有向图。从t至a遍历字符,如果a-c需要连边而存在b-c的边,则选择连a-b的边。
#include
using namespace std;
int main() {
int t = 0;
cin >> t;
while (t--) {
int n;
cin >> n;
string a, b;
cin >> a >> b;
bool ok = true;
for (int i = 0; i < n; ++i) {
if (a[i] > b[i]) {
ok = false;
break;
}
}
if (!ok) {
cout << -1 << endl;
continue;
}
set to[22] = {};
int toa[22][22] = {};
bool have[22] = {};
for (int i = 0; i < n; ++i) {
if (a[i] != b[i]) {
to[a[i] - 'a'].insert(b[i] - 'a');
toa[a[i] - 'a'][b[i] - 'a'] = 1;
}
}
int cnt = 0;
bool passed[22];
for (int i = 19; i >= 0; --i) {
if (to[i].empty())continue;
bool hh = false;
for (int j = 19; j > i; j--) {
bool ha = false;
for (int k : to[j]) {
if (toa[i][k]) {
ha = true;
break;
}
}
if (toa[i][j]) {
ha = true;
}
if (ha) {
to[i].insert(j);
for (int k : to[j]) {
to[i].insert(k);
toa[i][k] = 0;
}
toa[i][j] = 1;
to[i].insert(j);
hh = true;
}
}
for (int j = 0; j < 20; ++j) {
cnt += toa[i][j];
}
}
cout << (cnt) << endl;
}
}