A.Typical Interview Problem
算法本质
思维
题目大意
使i顺序历遍[l, r]
- 如果
i%3==0则输出F（先判断） - 如果
i%5==0则输出B
现在给出一个string，判断是否存在如此的[l r]。
思路推演
模3模5，直接就想到循环节。
找最小公倍数15，可知肯定15个数字为一个循环节。
手动模拟1~15：FBFFBFFB
因为担心首尾相连的情况和考虑到string的长度，将FBFFBFFB乘3，然后用自带的find方法判断是否可行。
B.Asterisk-Minor Template
算法本质
思维、模拟
题目大意（改）
*可以表示任意长度的任意字符串（包括空字符串）。
现在给出a b两个字母组成字符串，请设计一个字符串满足以下：
- 可以使用
* - 包含a b两种情况
*的个数小于等于字符串长度的一半
可以请输出此字符串，不行则输出No。
思路推演
需要尽量找到a b相同的字母来平衡*的数目。
手动模拟一下即可发现，首尾其一字母相同即可。
其他则需要中间有2个字母连着相同。
重点在于要上手模拟一下，规律就很容易看出。
C.Maximum Set
算法本质
思维
题目大意
给定一对l r，用[l, r]范围的数字建立一个集合（数字不重复）。
若集合内数字两两为可整除关系，则称之为美丽集合（只有一个数字的集合也美丽）。
集合的数字个数为集合的长度。
找到所有美丽集合最长的集合，输出其长度，并且求出有多少个同样长度的美丽集合（%mod）。
思路推演
这类题乍一看比较唬人，都是些新鲜玩意。
实际做题的时候不要怕，都是纸老虎！
既然没怎么见过，就按照其要求先模拟一下。
要求最长和美丽，首先可以想到的就是从l出发，每次*2计算。
如此很快就可以得到最大长度。
此时思考其他同长的美丽集合。
有2个方向：
- 从
l+i出发
最远的可行地方，可以用r向下除2来获得，这里称之为l_max - 将其中的
*2改成*3 *4...
可以很容易发现，最多将其中一个*2改为*3
已知[l, l_max]都是可以通过*2来完成美丽集合的。
其中能否将*2换成*3需要判断，因为单调性，所以可以二分判断。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
//init
int l, r;
cin>>l>>r;
int len=0, x=l;
while (x<=r)
{
x*=2;
len++;
}
int ci=len-1, l_max = r;
while (ci--)
l_max/=2;
//cal
int ans=l_max-l+1; //全部都可以*2变成美丽集合
int ll=l, rr=l_max;
int res=l-1; //最后res-ll+1表示有这么多个数字可以将*2替换成*3
while (ll<=rr)
{
int mid=(ll+rr)/2, max_val=mid;
if (len-2>0) //len个数字就应该有len-1个*2，换一个*3，还有len-2个
max_val = mid*qpow(2, len-2);
max_val *= 3;
if (max_val > r) //说明不行
rr = mid-1;
else
{
res = mid;
ll = mid+1;
}
}
ans += (res-l+1) * (len-1) % mod; //加上可以替换*3变成美丽集合的
ans %= mod;
//out
cout<<len<<" "<<ans<<endl;
return;
}D.Maximum Subarray *
算法本质
思维
题目大意
给定数组a[]，你需要选择其中k个不同下标使其+val，其他下标都会-val。
完成操作后选择最大子段和，报告其最大值。
注：val可能是负值。
n <= 2e5
k <= 20思路推演
此题很容易让人想到最大子段和。
最大字段和的复杂度是O(n)，此题的k也相对小，感觉上是最大字段和的变种。
观察其中的规律，当val>0可以很明显的发现其+val的下标要在子段内。
同时将val<0情况转化为val=-val, k=n-k，方便统一思考。
发现+val有聚集的倾向，直接人为规定所有的+val都必须要贴在一起。
并且规定子段一定贴在+val的边缘
- 当
+val的长度为n-k时，其存在的可能就及其有限（k种）：
枚举所有的n-k长度的+val情况，人为设定子段贴边，用前缀和可以快速暴力出答案 - 当
+val的长度为n时
同样枚举所有的k长度的+val的情况，但是两边采用最大子段和预处理，同样nk暴力出答案。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)