A.Bestie
算法本质
思维
题目大意
给定长度n的数组a[]，经过一下付费操作，使得最后所有元素的gcd运算为1：
- n-x+1元：使
a[x] = gcd(a[x], x)
输出最小化花费。
思路推演
这个花费，意味靠右元素操作更好。
另外，相邻的2个自然数gcd值为1，所以可以保证，对n-1和n元素操作后，全部gcd值都为1。
所以只有3种情况：
- 对
n操作 - 对
n-1操作 - 两者都操作
B.Ugu
算法本质
思维
题目大意
给定01字符串s，需要进行多次以下操作，使得s不递减：
- 选择下标
i，取反[i,n]的字符
最小化操作次数。
思路推演
直接暴力从左往右推，记录一下取反次数，得到当前字符即可。
C2.Sheikh (Hard Version)
算法本质
思维
题目大意
给定长度n的数组a[]。
对于数组a[]的[l, r]区间，定义：
- 元素和：
sum(l,r) = a[l] + a[l+1] + ... + a[r] - 异或和：
xor(l,r) = a[l] ^ a[l+1] ^ ... ^ a[r] - 魅力值：
f(l,r) = sum(l,r)-xor(l,r)
接下来跟有q次询问，每次询问会给出L R，需要你找到一对l r满足：（条件先后存在优先级）
L <= l <= r <= R- 最大化魅力值
- 最小化
r-l
n <= 2e5
q = n思路推演
显而易见的是（或者手动模拟一下），当一个区间新加入一个元素时，魅力值可能不变 or 增加（单调性）。
所以f(L,R)一定是最大值。
注：因为a[]元素不改变，所以可以预处理，O(1)做到对区间魅力值的查询。我们的目标就是减少左右两边的元素，同时保持魅力值不变。
通过魅力值的单调性可知：
- 若丢弃某个元素会导致魅力值下降，则这个元素一定不可丢弃
理想情况，肯定是先丢左边的、再丢右边的。
实际上，模拟一下也很快发现，左边元素是否丢弃，会影响右边元素是否可以丢弃。
例如1 2 4 3可以变成1 2 4或者4 3。
此时就有一个显然的暴力做法：
枚举l，r的位置用二分找出，单次询问复杂度nlog，可以应付简单版本
显然，还缺一个特性来优化算法，而此题用到了异或，大概率是从异或上找个特性。
异或的特性基本都要从二进制形式去找，结合刚才模拟的情况，可以发现：
- 若某个元素，其二进制下为1的位，剩下的元素都无交集，即可以去除同时魅力值不减
这样的话，最多有30个元素可以去掉。
所以我们可以放心的枚举l，只要遇到枚举时降低了魅力值就break即可。
但是这道题有0的存在，0百分百可以去掉的，但是如果手动O(n)去掉则复杂度会超的。
预处理一个数组，可以O(1)找到下个不为0的元素下标即可。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int a[maxn];
int pre_sum[maxn];
int pre_xor[maxn];
int to[maxn]; // to[i]：[i~n]中最左端的不为0值的下标
int f(int l, int r) // 区间魅力值
{
return pre_sum[r]-pre_sum[l-1] - (pre_xor[r]^pre_xor[l-1]);
}
inline void solve()
{
//init
int q;
cin>>n>>q;
rep(i,1,n) cin>>a[i];
rep(i,1,n) pre_sum[i]=pre_sum[i-1]+a[i];
rep(i,1,n) pre_xor[i]=pre_xor[i-1]^a[i];
to[n+1] = n+1;
for (int i=n; i>=1; i--) // 维护to[]
{
if (a[i]!=0)
to[i]=i;
else
to[i] = to[i+1];
}
//cal
while (q--)
{
int L, R;
cin>>L>>R;
int ans_l=L, ans_r=R; // ans_r-ans_l最小
int zhi=f(L, R); // 魅力值
int l=L;
while (l<=R && f(l, R)==zhi) //枚举r（最多枚举30个不为0的r
{
int z=l, y=R; //二分r
int r=y;
while (z<=y)
{
int mid=(z+y)/2;
if (f(l, mid)==zhi)
{
r=mid;
y=mid-1;
}
else
z=mid+1;
}
if (r-l < ans_r-ans_l) //更新答案
{
ans_l=l;
ans_r=r;
}
l = to[l+1]; //更新l
}
cout<<ans_l<<" "<<ans_r<<endl;
}
return;
}D1.Balance (Easy version)
D2.Balance (Hard version)
算法本质
思维
题目大意
初始有一个空的集合，接下来有q次操作，每次操作为以下某种情况：
+ x：添加x到集合中- x：从集合中删去x（Easy版本不存在- x操作）? k：查找不存在集合中、%k为0、最小正数
q：[1, 2e5]
x k：[1, 1e18]思路推演-D1（Easy版本）
如果就模拟题目的描述，用set存放x，每次查询的复杂度是q/k，如果查询的k都是较小数，则时间不可行。
检查一下，很轻易地就发现了重复计算的部分，加上不会删除元素，所以每次查询时，保存一下上次查询进度，下次继承即可。
思路推演-D2（Hard版本）
Hard版本引入了删除操作，沿用之前的思路的话，问题是如果集合已有2 4 6 8 10 ...，现在删除元素8，不仅对k=2的查询有影响，还对k=4、k=8等查询有影响。我们之前的查询进度将会作废。
假设称k 2*k 3*k ...的形式为k链条。
x的最大值为1e18，所以其最多因数的个数也相当大
即可以对许多链条造成影响
不过因为q最大2e5
所以最多对2e5条链条造成影响
继续看能否优化一下
手动模拟一下，当x影响的最多链条数 与 集合内元素个数开方 相关整理一下思路：
当查询k时，我们同D1一样，维护k链条的最值
当删除x时，找到有x值的链条，然后给他们打上缺失x的标记
当增加x时，找到有x值的链条，清除缺失x的标记
还需要维护链条是否存在x值，这里放在查询时建立链条中使用ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
set<int> vis; // 表示集合中的数
map<int, int> lian; // lian[x]表示x链条的最值
map<int, set<int>> que; // que[x]表示x链条缺失的值（用set是为了快速找出最小的值）
map<int, vector<int>> change; // change[x]表示存在x值的链条集合
inline void solve()
{
//init
int q;
cin>>q;
while (q--)
{
char op;
int x;
cin>>op>>x;
if (op=='+')
{
vis.insert(x); // 集合添加x
for (int u:change[x]) // u链条需要删除缺值x
que[u].erase(x);
}
else if (op=='-')
{
vis.erase(x); // 集合删除x
for (int u:change[x]) // u链条需要添加缺值x
que[u].insert(x);
}
else if (op=='?')
{
if (lian.count(x)==0) // 还没有建链条
lian[x] = 0; // 初始化链条
if (que[x].size()) // 存在缺失的值
{
cout<<*que[x].begin()<<endl; // 输出最小的缺失值
continue;
}
// 没有缺值则输出链条不可达值
while (vis.count(lian[x]+x)) // 维护链条
{
lian[x]+=x;
change[lian[x]].push_back(x); // 记录x链条存在lian[x]值
}
cout<<lian[x]+x<<endl; // 输出链条不可达值
}
}
return;
}
评论 (0)