A.New Palindrome
算法本质
思维
题目大意
给定回文字符串s，是否可以通过对其重排列组合出一个新的回文字符串。
思路推演
焦点在于“新的”，对于回文我们只需要镜像移动即可。
当s的某一半回文（不含中间字符）非单一字符组成，则可行，反之不可行。
B.Maximum Sum
算法本质
思维
题目大意
给定n个数，需要执行k次操作，每次操作为下面的一种：
- 删除2个最小数
- 删除1个最大数
输出最大化剩余数的和。（保证2k < n）
思路推演
排列数，显然我们是删除左边2x个数和右边y个数，其中x+y = k。
我们只需要暴力枚举x y即可，这需要一点前缀和优化。
C.Contrast Value
算法本质
思维
题目大意
给定长度n的数组a[]，定义其对比值：
- 遍历
i = 2~n，求和abs(a[i] - a[i-1])
找到一个满足下列条件的数组b[]：
b[]为a[]的子序列a[] b[]的对比值相等
输出最小化b[]的长度。
思路推演
又要是子序列，又要对比值相等。显然，只有连续上升的时候才可以省去中间部分元素。
同时存在前后相等的情况，所以我们可以定义状态：上升、平缓、下降。
状态转换间使得答案++。（具体算法比较简单繁琐，这里略过）
D2.Red-Blue Operations (Hard Version)
算法本质
思维
题目大意
给定长度n的数组a[]，然后会进行q次独立询问，每次询问会给出一个k值。
每次询问的规则如下：
- 初始元素都是红色的，接下来需要进行
k回合：
第i回合需要选择一个元素，若元素为红色，则+i且变为蓝色；反之则-i变为红色。
输出最大化k回合后的最小值。
n q <= 2e5
元素大小 <= 1e9思路推演 - 抽象题意
这个规则给的比较奇怪，我们对其模拟抽象出数学含义。
容易观察到的是，对于某个元素，我们至多给其值+k，即只变一次颜色，（对于单个元素）多次颜色变换的收益小于一次变换。
所以很容易想到的是，如果k <= n，那我们肯定让元素至多变色一次，即都做加法，再细细琢磨：大的值给较小元素加是最优解。
接着思考k > n情况：
通过几轮模拟可知，我们将k-n+1 ~ k用于做加法，剩余的值两两合并为-1做减法（如果k-n为奇数，做再拿一个做加法的值过来合并-1），这是显然的最优解。
这个结论是很直观的，也可以数学证明，但是需要用中间值替换，比较繁琐。
无法理解的话，结合这句话（对于单个元素）多次颜色变换的收益小于一次变换再思考一下。
到此，我们就抽象出其背后数学含义：
先排序a[]
k <= n
将1~k作加法，每个元素至多加一次，最优解为a[1]+k a[2]+k-1 …… a[i]+k-i+1 ... a[k]+1
ans即其中的最小值k > n
将k-n+1 ~ k或者k-n+2 ~ k作加法，剩余的元素两两合并成-1作减法
ans即其中的最小值
思路推演 - 最优解
在抽象出基本题意之后，思考如何解题。
对于每次询问来说，我们的均摊复杂度只有log级别的，怎么才能找到其最小值呢。
k <= n：
这个情况相对简单，我们可以将数组简单分为前k个和后n-k个。
因为后n-k的最小值一定是a[k+1]
求解前k个元素的最小值，观察其加法，值是有规律的。
所以我们可以维护数组b[] b[i]=a[i]-i+1。b[i]+k可以用来表示a[i]+k-i+1的值，从而预处理时就看出谁是最小值。
k > n：
我们同样借助b[]来O(1)找到最小值，随后需要先用-1打平差距，若打平后还存在-1则可以用除法O(1)计算最小值。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int a[maxn], b[maxn], pre_min[maxn];
inline void solve()
{
//init
cin>>n>>m;
rep(i,1,n) cin>>a[i];
sort(a+1, a+n+1);
for (int i=1; i<=n; i++)
b[i] = a[i] - i + 1;
int sumb = accumulate(b+1, b+n+1, 0ll);
//预处理
pre_min[0] = 1e18; // pre_min[x]表示b[1~x]的最小值
for (int i=1; i<=n; i++)
pre_min[i] = min(pre_min[i-1], b[i]);
while (m--)
{
int x, ans;
cin>>x;
if (x<n)
ans = min(pre_min[x]+x, a[x+1]); // 前半段的最小值和后半段的最小值
else if ((x-n)%2==0)
{
int num = (x-n)/2; // -1的个数
int xiao = pre_min[n]+x; // 目前最小值
int wast = sumb + x*n - xiao*n; // 打平的花费
num -= wast; // 打平之后的个数
if (num > 0) // 打平后还剩，则继续打
xiao -= (num + n-1) / n;
ans = xiao;
}
else
{
int num = (x-n+1)/2; // -1的个数
int xiao = min(pre_min[n-1]+x, a[n]); // 哪部分小用什么
int wast = sumb-b[n]+a[n] + x*(n-1) - xiao*n; // 打平的花费
num -= wast; // 打平之后的个数
if (num > 0) // 打平后还剩，则继续打
xiao -= (num + n-1) / n;
ans = xiao;
}
cout<<ans<<" ";
}
cout<<endl;
return;
}E.Combinatorics Problem
算法本质
思维
题目大意
给定n a[1] x y m k。
这里存在数组a[] b[] c[]，数组的定义如下：
a[i] = (a[i-1]*x + y) % mb[i] = 求和j:1~i C(i-j+1, k) * a[j]b[i] %= 998244353c[i] = b[i] * i（注意这里不取模）
输出c[]元素的异或和。
n <= 1e7
k <= 5思路推演
1e7显然这是一个O(n)的做法。
最朴素的思路就是O(n)求得c[]再作计算答案。
思考是否有其他取巧的方法，但是因为c[i] = b[i]*i最后这个*i明显打破了二进制可能存在的规律。所以大概率是不存在取巧方法的。
于是先思考一下朴素做法。
a[]可以看作已知，重点在b[]的计算。b[]这种组合数多项式，很容易让人想起组合数公式：C(a, b) = C(a-1, b) + C(a-1, b-1)。
简单尝试后就可以发现，b[i]和b[i-1]有着关联，但是单凭一维b[]无法搞定。
于是我们给b[]扩展一维，多的维度用来表示k值。（即原来的b[i]=b[i][k]）
则可得到转移公式：b[i][j] = b[i-1][j] + b[i-1][j-1] + C(1, J)*a[i]。
这是一个简单的二维dp，我们先处理好边界条件即可dp得出b[]，最后求出答案。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int a[maxn], b[maxn][7];
inline void solve()
{
//init
int x, y;
cin>>n>>a[1]>>x>>y>>m>>k;
for (int i=2; i<=n; i++)
a[i] = (a[i-1]*x + y) % m;
int pre=0;
for (int i=1; i<=n; i++) // 预处理得到b[][0]
{
pre += a[i];
pre %= mod;
b[i][0] = pre;
}
for (int i=1; i<=n; i++)
{
for (int j=1; j<=k; j++)
b[i][j] = b[i-1][j]+b[i-1][j-1] + a[i]*(j==1), b[i][j]%=mod;
}
int ans=0;
for (int i=1; i<=n; i++)
ans ^= b[i][k]*i;
cout<<ans<<endl;
return;
}
评论 (0)