A.Consecutive Sum
算法本质
思维
题目大意
给长度n的数组a[]，下标对于k同余的元素为同一组，同一组的元素可以任意调换位置。
任意次操作后，选择长度为k的连续子数组，输出最大化其元素和。
思路推演
显然是每个组出一个元素，每组出最大的元素即可。
B.Rule of League
算法本质
思维
题目大意
一队列原有n个人，id1~n顺序占位（1号占队头）。头的两个人会决斗，输掉的人出队，赢家仍站在队头。比赛进行n-1次直到最后剩下一个人。
给定n x y，规定同一个id的人只允许赢x或y场决斗，检测是否存在如此情景，若存在输出每场胜者id，反之输出-1。
思路推演
手动模拟一下会发现，对于第一场比赛，1号胜利则2号直接出局——2号赢0场。
所以x y中必须有一个等于0、一个大于0（n>1的情况下）。
设x=0
假设第一场1号必输，则2号连赢y场后必须输掉比赛，换2+y上场连赢y场，以此类推，n-1必须能整除y。
即得到答案。
C.Parity Shuffle Sorting
算法本质
思维
题目大意
给长度n的数组a[]，最多进行n次以下操作：
- 选择一对
l r，如果a[l]+a[r]为奇数，则a[r]=a[l]；反之a[l]=a[r]
使得a[]单调不减。
输出操作的l r。
思路推演
既然跟奇偶性有关，则考虑一下4种情况。
若两者都是奇数或者偶数，其操作后两者奇偶性不变。
这下我们就通过奇偶性来分成两条线，这两条线可以分别处理，思考如何整合到一起。
此时就需要思考，奇数+偶数的情况，会a[r]=a[l]。
所以若a[1]是奇数，则我们将所以的奇数向最右的奇数看齐，然后再将所有的偶数向a[1]看齐。
D2.Zero-One (Hard Version)
算法本质
思维、dp
题目大意（改）
有长度n的01字符串，有2种操作方式，将其变成一个全0字符串：
- x元：选择两个相邻字符反转
- y元：选择两个不相邻字符反转
最小化成本。（或者输出-1）
n:[1, 5e3]思路推演
显然，奇数个1会导致失败。
显然操作2更为灵活，如果x>=y的情况下，有且仅有2个连续1相邻的这种情况，可能用操作1，否则都会使用操作2。
于是可以单独讨论x>=y的情况，这部分比较简单不详述。
实际上easy版本也提醒了我们：单独讨论x>=y的情况到了这个地步，要么贪心、要么dp。（也有可能是没见过的神奇数据结构、图论之类的）
贪心的话，思考一段时间，发现找不到角度贪，所以思考一下dp。
显然dp应该用二维区间dp。
思考一会就发现：对于l r
int val_ll = dp[l][l+1] + dp[l+2][r]; // 左边2个+右边
int val_rr = dp[l][r-2] + dp[r-1][r]; // 左边+右边2个
int val_lr = dp[l+1][r-1] + y; // 左右各给1个
dp[l][r] = min(val_ll, min(val_rr, val_lr));即得，思路很顺。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int dp[maxn][maxn];
inline void solve()
{
//init
int x, y;
string s1, s2;
vector<int> v;
cin>>n>>x>>y>>s1>>s2;
s1 = " " + s1;
s2 = " " + s2;
s = s1;
for (int i=1; i<=n; i++)
{
if (s1[i] == s2[i])
s[i] = '0';
else
{
s[i] = '1';
v.push_back(i);
}
}
//cal 特殊情况判断
int ans;
if (v.size()%2==1)
{
cout<<-1<<endl;
return;
}
if (x>=y)
{
if (v.size()==2 && v[0]+1==v[1])
ans = min(x, 2*y);
else
ans = v.size()/2*y;
cout<<ans<<endl;
return;
}
//cal 2
n = v.size();
for (int i=1; i<=n-1; i++)
dp[i][i+1] = min(x*(v[i]-v[i-1]), y); // 注意v是零下标
for (int len=4; len<=n; len+=2)
{
for (int l=1, r=len; r<=n; l++, r++)
{
int val_ll = dp[l][l+1] + dp[l+2][r]; // 左边2个+右边
int val_rr = dp[l][r-2] + dp[r-1][r]; // 左边+右边2个
int val_lr = dp[l+1][r-1] + y; // 左右各给1个
dp[l][r] = min(val_ll, min(val_rr, val_lr));
}
}
ans = dp[1][n];
cout<<ans<<endl;
return;
}
评论 (0)