Educational Codeforces Round 144 (Rated for Div. 2) (A-C)

A. Typical Interview Problem【找规律，暴力】

链接
传送门
分析
3 5 6 9 10 12 15||||||| 15 + 3 15 + 5 …………
F B F F B F FB||||||| F B
可以看出周期是8
FBFFBFFB FBFFBFFB FB
这里取10个字符，为什么两个周期不够呢？
有两种情况，如果说这个字符小于等于T的部分，我们可以有两种情况，一个是在一个周期内，横跨两个周期，前半部分在上一个周期，后半部分在下一个周期。但是如果说是10个字符有一个很叼的样例B FBFFBFFB F 横跨三个周期，故最后还要补两个字符，补一个也可以。9个字符的话两个周期也是完全够的。因为要么一个周期在前面多一个，要么一个周期在后面多一个，其他的也都是横跨两个周期就足够了。
实现

#include <bits/stdc++.h>
#define ll long long
#define ls (u << 1)
#define rs (u << 1 | 1)
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair<int, int> PII;
const int N = 5e4 + 5, p = 998244353;
string s = "FBFFBFFBFBFFBFFBF";
void solve() {int n;cin >> n;string x;cin >> x;cout << (s.find(x) == -1 ? "NO\n" : "YES\n");
}
int main(){ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while (T--) solve();return 0;
}

B. Asterisk-Minor Template【分类、模拟】

链接
传送门
分析
这题看似复杂实则简单。这里我们考虑两种情况，一颗‘’的时候，和两颗‘*’,一颗星的时候就是，首相同，尾相同的时候，注意这两个字符并不一定等长。什么时候两颗星可以解决问题，就是相邻的两个相同,在这两个字符两侧加星，其他情况都不可行，为什么呢？因为首先首位均不相同，两侧必定要有星，而且不存在相邻的两字符相同，都是单个出现的字符，倘若真的存在必定写成*x*x*x*x*x*x*单个字符都是间隔出现的，所以的数目比字符多1，如果没有的话也需要一个*，所以都不行。

#include <bits/stdc++.h>
#define ll long long
#define ls (u << 1)
#define rs (u << 1 | 1)
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair<int, int> PII;
const int N = 5e4 + 5, p = 998244353;
void solve() {string a, b;cin >> a >> b;int n = a.size(), m = b.size();if (a[0] == b[0]) {cout << "YES\n";cout << a[0] << '*' << '\n';return;}if (a[n - 1] == b[m - 1]) {cout << "YES\n";cout << '*' << a[n - 1] << '\n';return;}for (int i = 0; i + 1 < n; i++) {if (b.find(a.substr(i, 2)) != -1) {cout << "YES\n";cout << '*' << a.substr(i, 2) << '*' << '\n';return;}}cout << "NO\n";
}
int main(){ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while (T--) solve();return 0;
}

C. Maximum Set【数学】

链接
传送门
分析
这题也挺简单的，首先size可以很容易地求出来，就是取公比为2的等比数列，如何求出所以有的这样的数列？例如4 100 ,4 * 2 ， 4 * 4 …… 4 * 16 最大，如果l取5呢，最大为5 *16,我们只需看看r - min能放下多少个倍率16即可。但是这样发现只有三种，但是这里样例说有7种，说明还有其他的方法，我们可以把一个2换成三，三可以在四个位置乘3其他位置乘2，这样总共有7种了，能不能再大一点呢，不可以，保持最大值的情况下，最小的例如64，与100的倍数关系小于2，如果说再多乘一个数，必然超过r，最小的倍率的就是把一个2换成3，是1.5倍，如果再换一个3， 就是2.25倍必然超过r，如果换的不是3，是4或更大的，换一个都不行 。得到倍率后看看l能否更大即可。注意要防止除零错误。
实现

#include <bits/stdc++.h>
#define ll long long
#define ls (u << 1)
#define rs (u << 1 | 1)
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair<int, int> PII;
const int N = 5e4 + 5, p = 998244353;
void solve() {int l, r;cin >> l >> r;int x = l, cnt = 1;while (x * 2 <= r) x *= 2, cnt++;int mul = x / l;ll ans = 0;
//	cout << mul << '\n';ans += (r - x) / mul + 1;//有几种lif (mul >= 2 && x / 2 * 3 <= r) {//要防止除零错误，没有2就不能换mul = mul / 2 * 3;ans += 1ll * (cnt - 1) * ((r - l * mul) / mul + 1) % p;//每个cnt-1位置交换，有多少个l }cout << cnt << ' ' << ans % p << '\n';
}
int main(){ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while (T--) solve();return 0;
}