Petya, Petya, Petr, and Palindromes
算法本质
思维
题目大意
给定长度n的数组。
定义某个奇长度数组的成本：
- 以回文对不相等的对数
输出所有长度k的子数组的成本之和。
n k <= 2e5思路推演
稍加模拟即可发现，数组奇偶下标可以分开看。
为了避免重复，我们仅遍历左端点，通常来说，右端点是右侧k/2个元素（奇偶分开处理后）。
但是首尾有所不同。
一种方法是单独处理首尾附近的点。
这其实就是模拟写法，推理写仔细点即可。
还有一种方法是整体看待。
对于每个左端点来说，其右端点是一个区间值。且题目要求保证与相同值关系很大。
我们可以用一个vector来存放相同值的下标，然后方便计算期间。
这个做法的难点在于计算区间的公式较难推理。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
void solve()
{
cin>>n>>k;
vector<vector<int>> cod0(2e5+5), cod1(2e5+5); // 奇偶分开讨论，记录每个值的下标
vector<int> a(2e5+5);
for (int i=1; i<=n; i++)
{
vector<vector<int>> &v = (i%2 ? cod1 : cod0);
int x=in();
a[i] = x;
v[x].push_back(i);
}
int ans=0;
for (int i=1; i<=n; i++) // 枚举a[i]为左端点
{
vector<vector<int>> &v = (i%2 ? cod1 : cod0);
int x=a[i];
int l = max(i, i+k-1-2*(i-1)); // l~r的范围是右端点的区间（a[]中的下标），这里的公式是重点
int r = min(i+k-1, i+2*(n-i - k/2));
if (r<l) continue;
int sum = (r-l)/2 + 1; // sum表示l~r区间值的数目，num表示这其中值为x的数目
int num = upper_bound(v[x].begin(), v[x].end(), r) - lower_bound(v[x].begin(), v[x].end(), l);
ans += sum-num;
}
cout<<ans<<endl;
return;
}Minibuses on Venus (easy version)
算法本质
思维、想象力
题目大意
给定n k mod，定义长度n的数组a[]美丽：
- 所有元素值范围
[0~k-1] - 存在
i使得$a_i ≡ \sum_{j=1}^na_j(\mod k)$
输出长度n美丽数组个数。
n <= 100
k <= 30思路推演
中等版本是需要数学板子优化
如此小的数据，实际上是对想象力的考验。
显然是dp，思考状态，重点在于如何不重复。
经过观察可发现，每个元素值v只对应一个和值sum，但是sum可能对应0~2个元素值v。
所以整体思路应该是枚举sum值，然后判断其是否有对应的元素值。
这里有两个朴素的想法：
- 先计算和为
sum值的所有方案数，再计算和为sum且没有使用对应元素值的方案数，两者相减即可 - 如果有对应相同
sum值，则称这两个元素值为一组。
设计dp[i][s1][s2][0/1]：i表示下标，s1表示当前的和值，s2表示当前方案能否使得s2为合法和值。
最后统计dp[n][s][s][1]的方案数即可。
笔者使用的是方法2，但是写崩了，一直没改回来，看cup收到启发写了方法1，更简洁简单。
代码写的是方法1，简单好理解。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
cin>>n>>k>>mod;
vector<vector<int>> dp(n+5, vector<int> (k+5)); // dp[x][y]=t表示1~x位总和位y的方案数有t
dp[0][0] = 1;
for (int i=1; i<=n; i++)
{
for (int v=0; v<k; v++)
{
for (int last=0; last<k; last++)
dp[i][(v+last)%k] += dp[i-1][last], dp[i][(v+last)%k]%=mod;
}
}
int ans=0;
for (int sum=0; sum<k; sum++)
{
vector<vector<int>> dp2(n+5, vector<int> (k+5)); // dp2[x][y]=t同上，但是不能使用sum对应的值
dp2[0][0] = 1;
int v1=-1, v2=-1; // 计算sum对应的两个值
if (sum%2==0) v1=sum/2;
if ((sum+k)%2==0) v2=(sum+k)/2;
for (int i=1; i<=n; i++)
{
for (int v=0; v<k; v++)
{
if (v==v1 || v==v2) continue;
for (int last=0; last<k; last++)
dp2[i][(v+last)%k] += dp2[i-1][last], dp2[i][(v+last)%k]%=mod;
}
}
ans += dp[n][sum] - dp2[n][sum];
ans = (ans%mod + mod) % mod;
}
cout<<ans<<endl;
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)