ZAFUACM - 23.8.5个人赛补题
A - Lucky Conversion
题意
给出两个只包含“4”和“7”的字符串,每次操作可以任选其一:
- 把“4”变成“7”或者把“7”变成“4”
- 交换两个数位置
问从第一个字符串至少经过多少次操作能变成第二个字符串
思路
遍历字符串,存储:cnt
:两个字符串有多少位上的数字不一样a4
:a 字符串中有多少个4b4
:b 字符串中有多少个4
然后看两个字符串4和7的个数是否一样:
- 如果一样就只需要靠交换顺序来变换:最少的操作数就是
cnt / 2
,因为每交换一次可以改变两个位置 - 如果不一样要先把个数调整成一样:调整的原则是,改变那些对应位置上数字不一样的,也就需要调整
abs(a4 - b4)
次,如果此时还有对应位置上数字不一样的情况,就进行内部交换,再加上(cnt - abs(a4 - b4)) / 2
次代码
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
string a, b;
cin >> a >> b;
int cnt = 0;
int a4 = 0, b4 = 0;
for (int i = 0; i < a.size(); i ++ )
{
if (a[i] != b[i]) cnt ++ ;
if (a[i] == '4') a4 ++ ;
if (b[i] == '4') b4 ++ ;
}
if (a4 == b4) cout << cnt / 2;
else
{
int ans = 0;
ans += abs(a4 - b4);
if (cnt > abs(a4 - b4)) ans += (cnt - abs(a4 - b4)) / 2;
cout << ans;
}
}B - Constanze’s Machine
原题链接
题意
机器会让所有的“m”变成“nn”,所有的“w”变成“uu”
现在给出一个字符串,判断这个字符串本来有多少种可能的样子
如果这不可能是机器输出的字符串就输出0
思路
首先判断字符串中有没有“w”或者“m”,有的话直接输出0,因为机器不可能输出这两个字母
然后找到并记录每个连续的“u”序列或者“n”序列,最后的方案数就是每一段序列的方案数的乘积
现在要解决的问题变成了每一段的方案数是多少,稍微枚举一下就能发现,这一段有几个连续的“w”或“n”,这一段的方案数就是斐波那契数列f[i]
,于是问题就解决了~
代码
|
C - Maximum Median
题意
给出一个数组和最大操作次数,每次操作可以任选一个元素加1,问经过操作后最大的中位数是多少
思路
==这!题!卡!int!==
我的思路就是首先对数组排序,之后就只用从中位数遍历后面的元素即可
观察数组发现,从中位数开始,如果当前遍历的数和比后面的数小,就可以只将当前的数加1(也能保证当前的数还是中位数),当前的数如果和后面的数一样大,就需要将后面一样大的数也一起加1(才能保证中位数也加了1)
定义的三个变量含义如下:cnt
:目前一次需要对几个数操作(才能让中位数加1)ans
:目前一共操作了多少次idx
:中位数在原基础上加了多少
遍历每个数时,中位数可以在原基础上加a[i] - a[i - 1]
次,操作次数就需要加cnt * (a[i] - a[i - 1])
次(因为每次可能要不止操作一个数),当ans
大于最大操作次数时,跳出循环即可
代码
|
D - Remove Extra One
题意
给出一个数组,如果某个元素之前的任何一个元素都比这个元素大,那就叫这个元素 record,现在要删去一个元素,让这个数组的 record 最多,问删去哪个元素
思路
赛时:八成是逆序对…看某一个元素和其他元素之间能够成多少逆序对…然后这样那样就能做了…/兴奋.jpg
赛后:???被世界欺骗
本题属于思维题和逆序对毛线关系没有,遍历一遍数组就能得到答案
遍历数组时,记录下数组从开头到目前遍历位置的最大值和次大值,再定义一个数组 $x[i]$,存储删去元素 $i$ 后,整个数组 record 数量的变化
每遍历一个元素——
- 如果这个元素比记录下来的最大值还要大,说明这个元素就是 record,删去这个元素的话,整个数组的 record 数量会减 1,因此需要进行的操作是:
x[i] --
以及更新目前的最大值与次大值 - 如果这个元素处于记录下来的最大值与次大值之间,说明这个元素是目前的次大值,只要删去目前的最大值,当前遍历的这个元素就会变成 record(也就会让整个数组的 record 数量加 1 ),因此需要进行的操作是:
x[max] ++
,以及更新目前的次大值‘’ - 如果这个元素小于目前记录的次大值,无论删去哪一个元素都不会对数组的 record 数量有影响,就不用管它
最后,在$x[N]$里找到最大的删去即可
代码
|
E - A Determined Cleanup
题意
已知$f(x)=q(x)(x+k)+p$,求出合适的$q(x)$使得多项式$f(x)$中的每一项系数都大于等于0且小于给定的k,输出$f(x)$系数
思路
设 $f(x)$ 每一项为 $a_ix^i$,$q(x)$ 每一项为 $b_ix^i$,那么可以得到以下规律:
$a_0=b_0k+p$
$a_1=b_1k+b_0$
$a_2=b_2k+b_1$
……
$a_n=b_nk+b_{n-1}$
因为多项式的最高次数为 n,所以 $b_n$ 必须为0,否组会让多项式的最高次数变成 n+1,
那么 $a_n=b_{n-1}$,所有的答案都在整数范围内取
现在关注第一个式子 $a_0=b_0k+p$,$a_0$又要小于$k$,所以可以直接得到 $a_0=p\%k$,又因为 $a_0>=0$,所以如果 $p\%k$ 是负数的话,直接在它的基础上加 k 即可
同时,因为 $0<=a_0<k$,把 $a_0$ 代入,得到 $0<=b_0k+p<k$,化简可得 $b_0=-\frac{p}{k}$,当然如果之前的 $p\%k$ 是负数的话,也要将这里的 p 加1(正负平衡)
按照这个思路一直往下做,直到找到一个 $b_i=0$ 为止(在上面说了 $b_n=0$, 所以找到一个等于0的 b 就可以默认找到答案了)
最后注意开 long long
代码
|
F - Minimal k-covering
(网络流好难 勉强理解个大概但是搞不出这题……开摆!!!