A.Make A Equal to B
算法本质
思维
题目大意
给定长度都是n的01数组a[] b[]。
可以通过花钱对a[]操作，使得a[]最终等于b[]，求最少花销：
- 1元：选择某个下标
i：a[i]=1-a[i] - 1元：重新排列
a[]元素，以任何方式皆可
思路推演
一般情况，都是先将a[]中的01数目改得跟b[]一样，再重排列。
需要考虑的一点是：可能a[]改后不需要重排列。
这个逻辑相对简单，但是也可以更暴力一些。
将a[]分成2种情况：需要使用重排列、不需要使用。
然后分别计算，求小值。
B.Playing with GCD
算法本质
思维
题目大意
给定长度n的数组a[]。
对于长度为n+1的数组b[]，满足下列条件则美丽：
- 对任意
i：a[i] == gcd(b[i], b[i+1])
是否存在美丽的数组b[]。
思路推演
显然可知，最优解中：b[1]=a[1] b[n+1]=a[n]
对于b[i]来说，其最优解为：lca(a[i-1], a[i])
获得了所有最优解后，检查b[]是否美丽即可。
C1.Good Subarrays (Easy Version)
算法本质
思维、双指针（or 二分）
题目大意
对于长为m的数组b[]，其满足下列条件则是美丽的：
b[i] >= i
现在给定长度为n的数组a[]，求其美丽连续子数组个数。
思路推演
- 对于
l，如果a[r]-r >= 0-l+1则说明b[l~r]中b[r]是满足条件的（只是说这个元素满足，并不一定美丽） - 如果
a[l~r]美丽，则a[l+1~r]一定美丽
所以对于b[]是具备单调性的，可以用双指针or二分解决。s
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int a[maxn];
inline void solve()
{
//init
cin>>n;
rep(i,1,n) cin>>a[i];
//cal
int ans=0;
int r=1;
for (int l=1; l<=n; l++) //历便左端点
{
while (r<=n && a[r]-r >= -l+1) // r表示第一个不满足条件的
r++;
ans += r-l;
}
cout<<ans<<endl;
return;
}C2.Good Subarrays (Hard Version)
算法本质
思维、数据结构
题目大意
对于长为m的数组b[]，其满足下列条件则是美丽的：
b[i] >= i
现在给定长度为n的数组a[]，接下来会有q次查询，每次查询前会修改a[]中某个元素的值，然后询问a[]美丽连续子数组个数。（这意味每次查询都是独立的——修改不继承）
思路推演
此题其实不适合文字题解，结合画图讲解会清晰很多，但是懒得画
假设修改为：a[p]=x
当下标p的元素值被修改了，其影响的是p之前的贡献值，即p做右端点的区域。
进一步思考，发现a[p]值的增加和减少是两种情况，需要分开讨论。
为了方便叙述，这里定义2个词：
理论左端点：
对于右端点r，其值为val，理论上能找到的最左左端点是r+1-val，即理论左端点
对于这些左端点，r点可行，但是小于r的点不一定可行计算：
r+1-val可以直接计算可行左端点：
对于右端点r，保证整体区域可行的最左左端点。（可行左端点肯定小于）计算：
双指针找“l的最右实际可行r”时，可以顺带处理了
以下图为例，绿色部分代表对于p的理论可行的左端点，最左的绿色点称之为理论左端点。
蓝色部分代表对于p的实际可行的左端点，最左的蓝色点称之为可行左端点。
询问的计算中，贡献值会改变的左端点范围为与下列两值有关：
- 修改前的可行左端点：
pre_l - 修改后的可行左端点：
suf_l
最后计算只与可行左端点有关，但是为了更好叙述，定义了理论左端点
思路推演-a[p]值减少
值减少意味对于一部分左端点，原本可以通过p点，但是现在无法通过了——即suf_l >= pre_l。
具体的改变范围计算：
因为suf_l >= pre_l，所以修改后中间肯定不存在坏点，所以可以简单地用理论左端点约束：suf_l = max(pre_l, p+1-x)
具体改变值计算：
这些左端点，原来都有着自己的可行右端点，现在因为a[p]值的减小——a[p]成了坏点，其可行右端点都变成了p-1。
我们减去这些左端点原来的贡献值（前缀和预处理），加上之后的贡献值（等差数列）即可。
思路推演-a[p]值增加
值增加意味对于一部分左端点，原来不能通过p点，但是现在可以通过了——即suf_l <= pre_l。
具体的改变范围计算：
首先用理论左端点约束范围，之后如何保证没有坏点呢——用p-1的可行左端点！（这里有点小绕）
于是得到：suf_l = max(p-1的可行左端点， p+1-x)
具体改变值计算：
新增的这部分左端点，原来的可行右端点都是p-1，被p阻拦了，现在p点值增加，不再阻拦了。具体能跑到哪与左端点自己的值有关。
所以得想个办法维护：可行右端点2——对于l来说，允许忽略第一个碰到的坏点下，的最右右端点。
这里也存在单调性，用再开一个指针即可预处理，然后前缀和预处理。
ac核心代码
看似定义的东西很多，实际很多数组都是前缀和延申、对立数组延申
头文件、宏定义、快读模板、常见变量、常见变量等略。
int a[maxn];
int lef[maxn]; // lef[p2]=p1：[p1, p2]真实可行，且对于p2来说，p1是最左的真实可行区间
int rig[maxn]; // rig[p1]=p2：[p1, p2]真实可行，且对于p1来说，p2是最右的真实可行区间
int rig_2[maxn]; // rig_2[p1]=p2：对于p1为左端来来说，忽略rig[p1]+1的影响，的可行区间
int ctb[maxn]; // ctb[l]=y：固定左端点l时，其对答案贡献值为y（即rig[l]-l+1 = y）
int pre_ctb[maxn]; // ctb[]前缀和
int pre_more[maxn]; // 定义more[x]=rig_2[x]-rig[x]，即多出的贡献值，pre_more[]是more[]的前缀和
int get_ctb(int l, int r)
{
return pre_ctb[r] - pre_ctb[l-1];
}
int get_more(int l, int r)
{
return pre_more[r] - pre_more[l-1];
}
int best_l(int r, int val) // 下标为r的值为val，理想情况下的最左端点（中间没有坏点）
{
return r+1-val;
}
inline void solve()
{
//init
cin>>n;
rep(i,1,n) cin>>a[i];
//cal 先找到原数组的答案，后面的询问在原数组上修改答案
int r=1, r2=1;
for (int l=1; l<=n; l++) // 遍历左端点
{
while (r<=n && a[r]-r >= -l+1) // r表示第一个不满足条件的
{
lef[r] = l; // 可行左端点
r++;
}
rig[l] = r-1; // 可行右端点
ctb[l] = rig[l] - l + 1; // 左端点贡献值
pre_ctb[l] = pre_ctb[l-1] + ctb[l]; // 前缀和——左端点贡献值
r2 = max(r2, rig[l]+2); //忽略rig[l]+1的影响
r2 = min(r2, n+1);
while (r2<=n && a[r2]-r2 >= -l+1) // r2表示第2个不满足条件的
r2++;
rig_2[l] = r2-1; // 可行右端点（忽略rig[l]+1的影响）
pre_more[l] = pre_more[l-1] + rig_2[l] - rig[l]; // 前缀和——多出的贡献值
}
int ans = get_ctb(1, n); // 原数组的答案
//cal
int q;
cin>>q;
while (q--)
{
int p, x, ans_now=ans;
cin>>p>>x;
if (x < a[p]) // 即a[p]值减少了
{
int pre_l = lef[p]; // pre_l:修改前的可行左端点
int suf_l = max(lef[p], best_l(p, x)); // suf_l:修改后的可行左端点
// debug2(pre_l, suf_l)
// [lef[p] ~ l-1]这些左端点，原来的右端点都>=p，现在因为缩水变成了p-1
ans_now -= get_ctb(pre_l, suf_l-1); // 减去原来的贡献值
ans_now += (p-pre_l + p-suf_l+1) * (suf_l-pre_l) / 2; // 加上新的贡献值（等差数列s）
}
else if (x > a[p]) // 即a[p]值增加了
{
int pre_l = lef[p];
int suf_l = max(lef[p-1], best_l(p, x));
ans_now += get_more(suf_l, pre_l-1); // 加上原来的多出贡献值
}
cout<<ans_now<<endl;
}
return;
}D.Equal Binary Subsequences
算法本质
思维
题目大意
给定长度为2n的01字符串s，必须对其进行一次以下操作：
- 选择任意长度的下标组成有序列
b[]，然后对s中的这部分下标的字符，进行向右旋转一个位置
即s[b[x+1]] = s[b[x]]。
假设s=100010，可以选择b[]={1,2,5,6}，则操作后的为010001
尽量使得操作后的s可以被完全分为2个长度为n的相等子序列。
输出b[]信息、操作后s分出的其中一个子序列信息。（若不能输出-1即可）
思路推演-1
此题给了操作+满足xx条件，显然，需要我们对xx条件有一个认知，然后用操作去贴合xx条件。
cf一般情况会把操作和条件的范围卡的极限——就是刚好符合，但是这题……
正常的思路是：
- 思考满足分为2个相等子序列的01字符串最低要求
（即把规则转化为，更有规律的要求） - 操作去贴合要求
手动模拟的时候发现，01字符串分开最大的问题是：相同字符的对标。
比如1001001001这里面4个1，第一个1和谁是对标的，第二个还是第三个。
根据经验来说，这里的规律应该要一定程度的简洁，所以我们可以假设前一半的1和后一半的1对标、1和相邻的1对标。
继续模拟，得到一结论：
- 当第1个
c和第x个c对标可以分割时，其与第2~x-1中任意一个c对标一定成功 - 当第1个
c和第x个c对标不可分割时，其与第2~x-1中任意一个c对标可以成功
所以可知：
- 字符会找最近的相同字符对标
同时01字符串里的0和1都有相同的性质，于是我们优先处理第一个出现的字符，这样还可以避免前导0（前导1）的情况。
当使用了这个操作后，无法分割，则表面某个地方出了问题，需要修复。
比如对于字符串`101001101001`
前`1010`可以分割，直接丢掉，剩下：`01101001`
然后会先得到2份：
011
0
还剩下`1001`，最开始的1放入2队
011
01
剩下`001`，这个0只有放入1队，依次类推得到
01100
011
不相等，说明出了问题，出的问题就在多的那部分0上问题找到了，但是不够完全，修改的操作无地下手。（这里略述了，可以自行造一些例子试一下）
实际上，赛时就在这个地方卡住了，不明白哪一步错了
思路推演-2
这个可以算作经验主义犯的错，或者另一方面说，思考的不够完全。
这次的操作有比较特殊，不是那种常见的行为，这说明操作本身也有探索空间。
反过来思考操作，操作只能看作2种情况：
- 将某个元素从塞在前面任意位置
- 01交叉地循环换一轮位置
思考了之前的情况的话，可以较为轻松地找到一个样例，使用操作1是不可行的。（但是存在其他方法可行）
所以思考操作2的情况。
手动模拟一下，会有一个相当大的发现：我们可以将孤独的字符和其相同字符放在一起。
进一步思考就会发现，可以人为规定a[2*k]==a[2*k+1]，只需要找到不相等的对，就可以完成了。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
vector<int> v, ans;
void dfs(int p=0, char val='0') //其实可以写成循环
{
if (p>=v.size())
return;
if (s[v[p]]==val)
ans.push_back(v[p]);
else if (s[v[p]+1]==val)
ans.push_back(v[p]+1);
dfs(p+1, val=='0' ? '1':'0');
}
inline void solve()
{
//init
cin>>n>>s;
s = " " + s;
//cal 1 检查可行性
int cnt[2] = {0};
for (int i=1; i<=2*n; i++)
cnt[s[i]-'0']++;
if (cnt[0]%2 || cnt[1]%2)
{
cout<<"-1"<<endl;
return;
}
//cal 2
v.clear();
ans.clear();
for (int i=1; i<=2*n; i+=2)
{
if (s[i]!=s[i+1])
v.push_back(i); //v存放不相等的对
}
dfs();
//out
cout<<ans.size()<<" ";
for (int u:ans)
cout<<u<<" ";
cout<<endl;
for (int i=1; i<=2*n; i+=2)
cout<<i<<" ";
cout<<endl;
return;
}E.Kth Number（来自atcoder）
算法本质
思维、数学
题目大意
给n个范围[0, m]的元素。其中的0值有随机变成[1, m]中的一个数。（概率平均）
求第k大元素的期望值。（取模mod）
n,m,k：[1, 2e3]思路推演-正解
正解如何想出来的，暂时不得而知，但是做法确实巧妙，可能以后学习了数学知识可以知道吧
设某个0值随机变成了x值，则x值的期望用E(x)表示为：
i遍历[1,m]，变成i值的概率 *i值的和
等价于：（只有从1开始的平均随机期望可以这样转换）
i遍历[1,m]，大于等于i值概率之和
$E(x) = \sum_{i=1}^{m} i * p_{x=i} = \sum_{i=1}^{m} p_{x\ge i}$
所以题目的问题可以转化为a[k]>=i （排序后）的概率之和：
$ans = \sum_{i=1}^{m} p_{a_k\ge i}$
其中$p_{a_k\ge i}$的概率可以转化为：至少有n-k+1个元素>=i的概率。
具体值推理
设：
有cnt0个0值、(a+b)个已知值
对于i值来说，有a个已知值<i元素、b个已知值>=i元素
我们的目标是求得：至少有 n-k+1 个元素 >=i 的概率。
即0值中至少 n-k+1-b 个元素 >=i 的概率
（PS：如果 n-k+1-b<=0 说明百分百可行，则概率为1，若 n-k+1-b>cnt0 说明不可能满足，概率为0）
这是一个典型的二项式分布问题
p = (m-i+1)/m 一个0值>=i的概率
x = n-k+1-b 需要至少x个0值都>=i
C(cnt0, x) * p^x * (1-p)^(cnt0-x) 恰好x个0值>=i的概率
然后恰好x、x+1、……、cnt0个值>=i的概率之和ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
//init
vector<int> v;
int cnt0=0;
cin>>n>>m>>k;
for (int i=1; i<=n; i++)
{
int x;
cin>>x;
if(x==0) cnt0++;
else v.push_back(x);
}
sort(v.begin(), v.end());
//cal
int ans=0;
for (int i=1; i<=m; i++)
{
int b=v.end() - lower_bound(v.begin(), v.end(), i); //有b个已知元素 >=i
int p=(m-i+1) * qpow(m, mod-2, mod) %mod; // 一个0值>=i的概率
int q=(1-p+mod)%mod; // q=1-p
int x=n-k+1-b; //至少需要x个0值>=i
int res=0;
if (x<=0) //说明百分百成功
res=1;
else if (x>cnt0) // 说明不可能满足
res=0;
else
{
for (int y=x; y<=cnt0; y++)
res += C(cnt0, y) * qpow(p, y, mod) %mod * qpow(q, cnt0-y, mod) %mod;
res %= mod;
}
ans += res;
ans %= mod;
}
cout<<ans<<endl;
return;
}
评论 (0)