2026 HDU春季联赛第六场 个人补题记录
1006
想了一半，没想到优先队列那部分。
令 \(dp_{i, \ j}\) 为节点 \(i\) 到 \(j\) 的最短合法括号路径的长度。初始化 \(dp_{i, \ i}= 0\)。
对于题目中两条规则，有递推式：
- “包裹式拓展”：对应第一种拓展，令 \(x \to u\) 有一条边权为
(的边，\(y \to v\) 有一条边权为)的边，则有：
- “连接式拓展”：对应第二种拓展，即 \(dp_{u,x}\) 和 \(dp_{x,v}\) 均存在，则
如上，两个点应该如何枚举？可以利用一种类似Dijsktra的方式，维护一个优先队列，储存 \([x, \ y, \ dp_{x,y}]\)，以 \(dp_{x,y}\) 为关键词排序。
CF Global Round 18CProblem - 1615C - Codeforces
少考虑一种情况。
考虑初始的字符串 \(a\) 中的 \(1\) 的个数。如果为 \(0\) 且不与 \(b\) 相等显然输出 -1。设初始为 \(1\) 的个数为 \(x\)。
接下来枚举操作。依据题意，第一次操作前有 \(n-x\) 个 \(0\)，则操作后的 \(1\) 的个数为操作前 \(0\) 的个数加上被选定的那个 \(1\) 保留，可得到 \(n-x+1\) 个 \(1\)。对于第二次操作，可以有类似的操作，得到 \(n-(n-x+1)+1 = x\) 个 \(1\)。经过上述操作，我们发现经过两次任意位置下的合法操作之后，\(1\) 的个数不变。经过推广，可以发现偶数次下的合法操作都不会改变 \(1\) 的个数。
那么可以分情况讨论，令 \(a\) 中初始的 \(1\) 的个数为 \(cnt_a\)，令 \(b\) 中初始的 \(1\) 的个数为 \(cnt_b\)：
- \(cnt_a = cnt_b\)，此时可进行偶数次操作。假设我们有两个位置错了，一个是 \(a_i=1, b_i=0\)，另一个是 \(a_j=0, b_j=1\)。首先选择选择 \(a_i\)（它是 \(1\)），保留它不变，其他全翻转。此时 \(a_j\) 从 \(0\) 变成了 \(1\)。选择刚才变出来的 \(a_j\)（它现在是 \(1\)），保留它不变，其他全翻转。经过这 2 步，\(a_i\) 变成了 \(0\)，\(a_j\) 变成了 \(1\)。原来的错位被修复了，而其他位置被翻转了两次，仍然与原字符串相等。假设有 \(k\) 个 \(1 \to 0\) 的错位，和 \(k\) 个 \(0 \to 1\) 的错位。那么总的不匹配位置数 \(diff = 2k\)。 因为每修复一对（2个错位）需要 2 次操作，所以修复 \(k\) 对需要 \(2k\) 次操作。所以此时答案为 \(\sum (a_i \neq b_i )\) 。
- \(n-cnt_a+1 = cnt_b\)，此时进行奇数次操作。这种情况下，最终的状态其实是 \(a\) 经过一次全翻转（除了某个选中的 \(1\)）后，再通过偶数次操作变成 \(b\)。操作奇数次后，原本相同的位会变不同，原本不同的位会变相同。以上述方法同样递推可得此时答案为 \(\sum (a_i = b_i )\) 。
对以上两种情况判断答案是否合法，如果均无法满足仍然需要输出-1。
const int mxn = 200010;
void LonelyLunar_solve(){
int n;
cin>>n;
string a,b;cin>>a>>b;
if(a==b){
cout<<"0"<<endl;
return;
}
bool vis =0;
int cnta = 0;
int cntb = 0;
for(char c : a){
if(c=='1'){
vis=1;
cnta++;
}
}
if(vis==0){
cout<<"-1"<<endl;
return;
}
for(char c : b){
if(c=='1'){
vis=1;
cntb++;
}
}
int res = 2e9;
if(cnta==cntb){
int dif = 0;
for(int i = 0;i < n; i++){
if(a[i]!=b[i]) dif++;
}
if(dif%2==0)res = min(res,dif);
}
if(cntb==n-cnta+1){
int same = 0;
for(int i = 0;i < n; i++){
if(a[i]==b[i]) same++;
}
if(same%2==1)res = min(res,same);
}
if(res!=2e9)cout<<res<<endl;
else cout<<"-1"<<endl;
}
CR374DProblem - 721D - Codeforces
好题，就是为什么数组开小了不报RE，对着调了十分钟没发现/ll
判断所有数字的符号，显然乘积是负数的时候最优，令数组中负数的个数为 \(c\)，当 \(c\) 为偶数的时候，枚举绝对值最小的那个数，令其正好变成异号，设其操作次数为 \(s\)。若 \(s \geq k\)，则只能将其变成最小，别的无能为力，此时直接输出。重点关注 \(s < k\) 的情况。
此时确保最终乘积为负数后，问题转化为：如何分配剩下的 \(k\) 次操作，使得所有元素绝对值的乘积最大？我们可以举一个例子，例如周长相同的矩形，长宽越接近面积越大，要想使乘积变大，应当优先增加绝对值最小的元素的绝对值，此时可以用一个优先队列维护 \([id, \ val]\)，队列里存绝对值，在原数组上进行修改，然后就做完了。
实现非常朴素。
AC Submission
CR1043EProblem - E - Codeforces
本题的正解思路还是很简单的。
显然第一步需要将两个数组降序排序。那样就转化成了分别在两个数组中取一个可以为空的前缀，因为当前两个数组都是单调的，所以考虑两个前缀的最后一个值对答案的贡献。假设取排序后的 \(a\) 数组下标为 \(l\)，那么 \(b\) 数组与其对比的下标应该为 \(b-l+1\)。即答案可以取到最后一个 \(a_{l}>b_{z-l+1}\) 的合法下标。因为下标取贡献可以是单调的，所以以上判断都可以用二分解决。
那么我是哪里卡住的呢？我在快速写完下面的代码之后喜提 wa on test 2：
const int mxn = 200010;
int n,m,q;
int a[mxn],b[mxn];
int prea[mxn],preb[mxn];
void LonelyLunar_solve(){
cin>>n>>m>>q;
for(int i = 1;i <= n; i++) cin>>a[i];
for(int i = 1;i <= m; i++) cin>>b[i];
sort(a+1,a+n+1,greater<>());
sort(b+1,b+m+1,greater<>());
for(int i = 1;i <= n; i++){
prea[i] = a[i]+prea[i-1];
}
for(int i = 1;i <= m; i++){
preb[i]=preb[i-1]+b[i];
}
while(q--){
int x,y,z;
cin>>x>>y>>z;
int l = max(0ll,z-y);
int r = min(z,x);
int tres = l;
while(l<=r){
int mid = (l+r)>>1;
if(mid==0||a[mid]>b[z-mid+1]){
tres = mid;
l = mid+1;
}else r = mid-1;
}
cout<<prea[tres]+preb[z-tres]<<endl;
}
}
那么以上代码哪里有问题呢？
多测清空！
\(a\) 数组和 \(b\) 数组在上述代码中是没有多测清空的，如果前一个测试用例数组长度很大，而下一个测试用例又较小的话，在二分 a[mid]>b[z-mid+1] 查询的时候就会受到上一组数据的污染。
于是需要在程序最后清空原数组：
for(int i = 1;i <= n; i++) a[i] = 0;
for(int i = 1;i <= m; i++) b[i] = 0;
思路实现不困难。
ABC454EE - LRUD Moving
网格图路径问题。
在网格中，每次往上下左右走一步，行号或者列号会且只会改变 \(1\)。这就像一个国际象棋棋盘。如果你站在黑格子上，不管你怎么走（不走对角线），下一步必然踏入白格子；从白格子走一步，必然踏入黑格子。这促使我们需要考虑奇偶性。
如果走过奇数个格子，路径一定是“黑-白-黑-...-黑”，头尾颜色相同，走过的黑格子多一个。而走过偶数个格子时路径一定是“黑-白-黑-白”，头尾路径不同，且走过的黑白格子数量一定相同。
我们发现给定的网格图是一个 \(N \times N\) 的图，且必须经过所有的除一个障碍点之外的所有点，起终点全部固定。也就是说我们需要走 \(N \times N -1\) 个点。
- \(N \times N\) 是奇数，那么 \(N \times N -1\) 为偶数，起终点奇偶性必然不同，与原题题意矛盾，故此时一定无解。
- \(N \times N\) 是偶数，那么 \(N \times N -1\) 为奇数，为了保持起终点奇偶性一致的属性（此时，奇偶性同为偶数），中间不经过的点一定为奇数。也就是说 \(a+b\) 必须为偶数，反之无解。
剩下的就是实现过程。
int n,a,b;
string res = "";
void cal(int r1,int r2,int c1,int c2){
if(r2==r1+1&&c2==c1+1){
if(a==r1&&b==c1+1){
res+="DR";
}
else if(a==r1+1&&b==c1){
res+="RD";
}
return;
}
if(a>r1+1){
res.append(c2-c1,'R');
res+="D";
res.append(c2-c1,'L');
res+="D";
cal(r1+2, r2, c1, c2);
return;
}
if(a<r2-1){
cal(r1, r2-2, c1, c2);
res+="D";
res.append(c2-c1,'L');
res+="D";
res.append(c2-c1,'R');
return;
}
if(b>c1+1){
res.append(r2-r1,'D');
res+="R";
res.append(r2-r1,'U');
res+="R";
cal(r1, r2, c1+2, c2);
return;
}
if(b<c2-1){
cal(r1, r2, c1, c2-2);
res+="R";
res.append(r2-r1,'U');
res+="R";
res.append(r2-r1,'D');
return;
}
}
void LonelyLunar_solve(){
cin>>n>>a>>b;
res="";
res.reserve(n*n);
if(n%2==1||(n%2==0&&(a+b)%2==0)){
ctn;
return;
}
cty;
cal(1, n, 1, n);
cout<<res<<endl;
}
CF edu173CProblem - 2043C - Codeforces
需要找到一个数学性质：对于只包含1/-1的数组，所有子数组的和必然构成一个连续的整数区间。因为题目保证至多一个元素不为1或-1，可以将数组按照特殊元素一分为二，分别计算左右两边数组的可达区间，以及跨过中间特殊元素的子区间的可达区间。复杂度 \(O(n)\)。
AC Submission
HDU5309Gorgeous Sequence - HDU 5306 - Virtual Judge
吉司机线段树例题。
本题对于第一个操作 \(min(a_i, \ t) \to a_i\) 无法用一个统一的区间 \(Tag\) 进行处置，吉司机线段树的思路是：既然不能统一打标记，那就向下递归，直到区间内的数字满足某种“一致性”再打标记。为了保证不退化成 \(O(N^2)\) 的暴力，我们需要找到一种“势能”（比如区间内不同数字的种数、或者最大值与次大值的差距），证明这种向下的暴力递归是有限的，总的时间复杂度是可分摊的。
对于一个区间，我们的诉求是在 \(O(1)\) 的时间里将1操作完成，我们需要维护区间里最大值，次大值及最大值个数，并对区间进行如下判断：
- \(x \geq mx\)，说明区间完全不受操作的影响，直接剪枝。
- \(cmx<x<mx\) ，区间只影响最大值，可以 \(O(1)\) 修改。
- \(x<cmx\)，无法 \(O(1)\) 修改，继续深搜。
AC Submission