A.Matching
算法本质
思维
题目大意
给定由数组和?组成的字符串，?可以变为任意数字字符，输出其能表示的不存在前导0的数字个数。
思路推演
显然?在第一位就有9种可能，其他位置有10种可能。
但是需要考虑自带前导0的字符串，这种字符串的答案为0。
B.Sort the Subarray
算法本质
思维
题目大意
给定长度为n的数组a[] b[]，其中b[]是由a[]对自身某个区间元素升序排序后的结果。（保证a[] b[]有所不同）
输出长度最大的区间l r。
思路推演
显然，未排序的地方元素一定相同，排序的区域不一定相同。
且元素不相同的地方一定属于排序区域。
所以通过对比元素是否相同，确定最小的排序区域。
对于在排序区域，但是位置不变的元素，左边的为最小值，右边的为最大值。
按照这个规律扩展即可。
C.Tear It Apart
算法本质
思维
题目大意
给定由小写字母组成的字符串s，进行尽可能少的以下操作，使得s变成由单一字符组成
- 选择任意互不相邻的下标，删除下标元素，剩余字符按序重连
输出最小化的操作次数。
思路推演
显然，最后的可能情况为26字母中的某个。
假设剩下的字符传为c，则需要删除c之间的所有字符，发现十分简单，即其log2函数（向上取整）。
同时，不删除任何c显然是最优解。
D.Black Cells
算法本质
思维
题目大意
在一行无限长的方格地图上，存在n个不相连的区间。
你操控一只画笔，想要涂（已知）k个格子，但仅能在区间中涂写，并且遵守以下规则：
- 每个回合只能选择选择一个操作：右移一格、笔尖下放、笔尖提起
- 当完成一次笔尖下方、笔尖提起后，画笔在中间所在的方格会被涂色（意思是最后必须笔尖提起）
输出最小化回合数。
思路推演
显然，这题的矛盾点在于，如果我们考虑少走路，就尽可能地用前面的的区间。
但是如果前面的区域比较小，则我们的下放、提起所损耗比较多。
我们定性分析一下：对于一个长度x的区间
- 若取
收益为x，成本为x+2 - 若不取
收益为0，成本为x
如果我们想在后面捞x收益回来的话，至少需要x的成本
所以可知，若x>=2，则这个区间一定是要取的。
对于x=1的区间，则存在取或不取2种可能。
于是我们枚举最后走到的区间。
前面大于1的区间都必取，先加起来，变量名pre
- 若pre>k
则continue - 若pre<=k
先用当前区间补一下，若不够补再用之前的1区间补。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int l[maxn], r[maxn];
inline void solve()
{
//init
cin>>n>>k;
rep(i,1,n) cin>>l[i];
rep(i,1,n) cin>>r[i];
//cal
int ans=1e18;
int sum=0, sum2=0, cnt2=0; // sum表示前面区间的总和，sum2表示前面区间>1的总和，cnt2表示前面区间>1的个数
for (int i=1; i<=n; i++)
{
sum += r[i]-l[i]+1;
if (sum >= k) // 当前存在解决方案
{
if (sum2 > k) // 说明当前+之后的方案都不是最优方案
break;
int cha = k-sum2; // 还差的格子数
int bu = min(cha, r[i]-l[i]+1); // 当前区间尽可能补格子数
int pos = l[i] + bu - 1; // 最后停留下来的位置
int res = pos + (cnt2 + 1 + cha-bu)*2; // 计算这个方案的成本
ans = min(ans, res);
}
// 善后
if (r[i]-l[i]+1 > 1)
sum2 += r[i]-l[i]+1, cnt2++;
}
if (ans==1e18)
ans=-1;
cout<<ans<<endl;
return;
}E.Rearrange Brackets
算法本质
思维
题目大意
题意稍微难懂，细心阅读
称括号字符串为规则的，当满足以下条件：
- 其可分割为若干子序列，每个子序列都是
()
定义规则括号字符串的属性成本值：
- 可以进行任意次以下操作：选择两个相邻的字符组成的
()，删去他们，成本为右边括号字符数。
多次操作的成本之和的最小值，为成本值
现给定规则括号字符串s和整数k，可以进行k次以下操作，得到一个新的规则括号字符串。
- 任意调整某个字符位置（即半个括号）
输出最小化得到的规则括号字符串的成本值。
思路推演
成本值是这题的关键属性，我们先模拟一下，如何求解一个括号字符串的成本值。
其最优解显然是从右边开始，有点类似剥洋葱——但是从内部剥开。
随后允许调整单个字符，再模拟找最优解。
这个也非常显然，（调整单个字符的）最优解为把最大洋葱的外皮剥开。
思路和代码相当简单，完全不符合2100的题目难度。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
//init
cin>>k>>s;
stack<int> st;
vector<int> v;
for (int i=0; i<s.length(); i++)
{
if (s[i]=='(')
st.push(i);
else
{
int l=st.top();
int r=i; // 找到对应的括号对
st.pop();
v.push_back((r-l-1)/2); // 每个括号对对成本的贡献值
}
}
sort(v.begin(), v.end());
k = min(k, (int)v.size());
int ans = accumulate(v.begin(), v.end()-k, 0ll); // 丢掉最后k个最大值
cout<<ans<<endl;
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)