#144 EDU2
A:
题目:
现在给出一个只含 FB 字符串,问你是不是从 1 开始 N 的,构成的字符串的连续子串。
如果当前从 1 开始枚举的数字 x, x 能整除 3 输出一个 F, 能整除 5 输出B , 同时整除按顺序输出。
思路:
每 3 输出 F 每 5输出B, 每 15 输出 FB, 所以只需要先构造出 1- 100, 然后暴力匹配就行
代码
void solved()
{
cin >> n;
string s;
cin >> s;
string now;
for(int i = 1; i <= 100; i++)
{
if(i % 3 == 0) now += 'F';
if(i % 5 == 0) now += 'B';
}
for(int i = 0; i < now.size() - s.size(); i++)
{
int k = i;
bool flag = true;
for(int j = 0; j < s.size(); j++)
{
if(s[j] != now[k++])
{
flag = false;
break;
}
}
if(flag)
{
cout << "YES" << endl;
return;
}
}
cout << "NO" << endl;
}
B
略
思路:
因为 * 的个数不大于 字母的个数, 所以如果有连续两个字母的子串,那么一左一右一个*
如果只有一个字母,必须保证在 开头或者结尾。
代码
void solved()
{
map<string, int> has;
string a, b;
cin >> a >> b;
for(int i = 0; i < a.size() - 1; i++)
{
string s;
s += a[i], s += a[i + 1];
has[s]++;
}
for(int i = 0; i < b.size() - 1; i++)
{
string s;
s += b[i], s += b[i + 1];
if(has[s])
{
cout << "YES" << endl;
cout << "*" << s << "*" << endl;
return;
}
}
if(b[0] == a[0])
{
cout << "YES" << endl;
cout << b[0] << "*" << endl;
return;
}
if(b[b.size() - 1] == a[a.size() - 1])
{
cout << "YES" << endl;
cout << "*" << b[b.size() - 1] << endl;
return;
}
cout << "NO" << endl;
}
C
题目:
现在给出一个范围 L- R, 问你最多元素的集合,使得集合内的元素都能互相整除。问你最多元素的集合有多少种
思路:
肯定先考虑最小的边界 l, 然后不断 * 2,得到新的数字,这是使集合内元素都能互相整除的最优解。
有多少种,我们考虑可能出现 * 3,但是不可能 * 4,否则就可以转化为两个 * 2 * 2
所以考虑 *3 替换在第几个位置上变成 3
代码
void solved()
{
cin >> l >> r;
int res = 0;
int mx = 0;
int now = l;
int cnt = 0;
for(int i = 1; i <= 20; i++)
{
now *= 2;
if(now > r) break;
cnt++;
}
cout << cnt + 1 << " ";
res += (r / p2[cnt] - l + 1) % MOD;
res %= MOD;
if(r * 2 / p2[cnt] / 3 >= l)
res += cnt * (r * 2 / p2[cnt] / 3 - l + 1) % MOD;
res %= MOD;
cout << res << endl;
}