A.Serval and Mocha's Array
算法本质
思维
题目大意
对于一个长度>=2的数组，有好、美丽两种属性。
- 好：
数组内元素gcd之和 <= 其长度 - 美丽：
数组的所有（长度>=2的）前缀数组都是好的
给定一个数组，现在可以重新排序其元素，能否使得其美丽。
思路推演
美丽是好的延申属性。
先看好，gcd所有元素和长度比较，这具有单调性。
所以可知，如果数组的前2个元素满足好，则当前数组美丽。
即找到2个元素gcd <= 2即可。
B.Serval and Inversion Magic
算法本质
思维
题目大意
给出一个01字符串，选择某个区间内字符反转（0变1、1变0），是否能构成回文。
思路推演
回文的特定就是左右相等。
当一个字符串出现了需要操作才能变为回文，就是左右出现了不相等情况。
通常的想法是，改变一边，另外一边不动。
手动模拟找特征得知：
l r不需要跨过中间- 原字符串就是回文是可行的
对称性很强。
原字符串找其中左右两边对比，如果出现不一样的地方连续为一整块，即可构成回文，否则不可。
C.Serval and Toxel's Arrays
算法本质
思维、结构
题目大意
有一个长度为n的数组，接下来进行m次操作，每次操作改变其中一个元素的值，随后保存新生成的数组，保证每个数组不会有重合的元素。
这样就会有m+1个数组（包含最初的），让数组两两相互组合一次，组合时去重剩下的元素个数加入到ans，最后求ans
m、n <= 2e5
1 <= 元素值 <= m+n思路推演 - 1
首先，这种题一眼可知，是找到某种看题的视角（做题的数据结构），才能完成复杂度下的任务。
如果我们暴力做，就会有$O(m^2n)$的复杂度。
通常这种题的优化有2个方向：
- 常见数据结构考察
如st表、线段树、树状数组等，特点是区间运算 - 映射合并特征
比如在暴力做法下，我们是将所有数组一一对比实现的，因为每个数组其实是独特的。
但是可以找到某个共通点，将其合并在一起运算。
当然，还是可以从不同寻常的地方找到一些线索：
- 元素值<=4e5
- 每个数组的元素不会重复
从这2个条件几乎可以看出，优化做法的方向是映射合并特征，而且其单位很有可能是元素值。
思路推演 - 2
所以，元素值在所有数组中出现的次数，可能作为特征。
如果a在数组中只出现了1次，那其贡献就是m。
如果出现了2次，则可以发现其贡献本应该是2*m，但是因为这2个元素之间相互会有重复，所以是2*m-2*1/2
如果出现x次，贡献是x*m - (x-1)*x/2
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
//init
cin>>n>>m;
rep(i,1,n) cin>>ar[i];
rep(i,1,n+m) last[i]=-1, hui[i]=0;
rep(i,1,n) last[ar[i]]=0;
//cal
for (int ci=1; ci<=m; ci++)
{
int pos, val;
cin>>pos>>val;
int a=ar[pos], b=val;
ar[pos] = val;
hui[a] += ci-last[a];
last[a] = -1;
last[b] = ci;
}
for (int i=1; i<=n; i++)
hui[ar[i]] += m+1-last[ar[i]];
//cal 2
int ans = 0;
for (int val=1; val<=n+m; val++) //这里hui[val]相当于x
ans += hui[val]*m - hui[val]*(hui[val]-1)/2;
cout<<ans<<endl;
return;
}
评论 (0)