当前位置：首页 > news >正文

ABC 424 D-F 题解

news 2025/9/21 19:01:16

讲个笑话：
调了 inf 年做出来半个 D
我咋这么菜
居然爆搜就能过？？（

D - 2x2 Erasing 2

算是斗胆在场上使用状压 dp 了，没分析明白多记了一维无用状态，因为重复使用了变量 i 调了 inf 年，算复杂度的时候忘了是多测，最后交上去 T 飞了，赛后把多的一维删掉再交直接过了。

开题想了半天好像没有什么类似贪心的做法，图很小，考虑状压 \(dp\)。

设 \(dp\) 状态 \(f_{i,s}\) 表示当前在第 \(i\) 行，格子状态为 \(s\)（白点为 \(0\)，黑点为 \(1\)）时需要的最小操作步骤。
转移时就枚举当前行和上一行的状态然后从上一行转移，状态的合法条件有两个：

原图中是白色的点不能在当前状态是黑色（因为题意只有把黑点变白的操作）
当前行和上一行不能出现 \(2 \times 2\) 的黑色格子（题目限制）

转移方程：

\[f_{i,s1}=\min_{s2 \in s} f_{i-1,s2} + pay(i,s1) \]

这里的 \(pay(i,s1)\) 是指第 \(i\) 行的状态为 \(s1\) 时需要改变的格点数。

初始时 \(f\) 数组都为极大值，最后的 \(ans\) 为 \(\min_{s1 \in s} f[n][s1]\)。

因为我们需要枚举行数和两种状态，时间复杂度为 \(O(TH4^W)\)。

点击查看代码

using namespace std;
const int N=1<<8;
int T;
int f[10][N];
int a[10],h,w,ans;
bool flag;
bool chk(int x,int s){if(x<=0) return true;for(int i=0;i<w;i++){if( ((a[x]>>i)&1)==0 && ((s>>i)&1)==1){return false;}}return true;
}
bool chk2(int s1,int s2){int lst=0;for(int i=0;i<w;i++){if( ((s1>>i)&1)==1 && ((s2>>i)&1)==1 ){if(lst){return false;}lst=1;}else{lst=0;}}return true;
}
int pay(int x,int s){int res=0;for(int i=0;i<w;i++){if( (((a[x]>>i)&1)==1) && (((s>>i)&1)==0) ){res++;}}return res;
}
void xpigeon(){ans=1e18;memset(f,0x3f,sizeof(f));char c;cin>>h>>w;for(int i=1;i<=h;i++){int s=0;for(int j=1;j<=w;j++){cin>>c;s<<=1;s+=(c=='.')?0:1;}a[i]=s;}for(int s=0;s<(1<<w);s++){if(chk(1,s)){f[1][s]=min(f[1][s],pay(1,s));}}for(int i=2;i<=h;i++){//当前行for(int s1=0;s1<(1<<w);s1++){if(!chk(i,s1)) continue;//上一行for(int s2=0;s2<(1<<w);s2++){if(!chk(i-1,s2)) continue;if(!chk2(s1,s2)) continue;f[i][s1]=min(f[i][s1],f[i-1][s2]+pay(i,s1));if(i==h){ans=min(ans,f[i][s1]);}}}}cout<<ans<<'\n';
}
signed main() {ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cin>>T;while(T--){xpigeon();}return 0;
}

E - Cut in Half

比赛结束前 5 分钟看了一眼这个题，感觉大根堆随便维护一下，一看 \(T,n\) 都是 \(1e5\) 的以为有什么神秘做法，结果我没看见 “The sum of \(N\) over all test cases does not exceed \(10^5\).”
直接做是对的（

使用大根堆维护相同木棍的长度和数量，每次取出最长的木棍砍一半，不够砍就能砍多少砍多少，依次找出第 \(x\) 长的木棍长度，因为木棍数量倍增，所以砍木棍操作大概最多只有 \(30\) 多次，直接做根本没问题。

点击查看代码

#define int long long
using namespace std;
int T;
int n,k,x;
void xpigeon(){priority_queue<pair<db,int>> q;rd(n,k,x);for(int i=1,a;i<=n;i++){rd(a);q.push({a,1});}while(k){auto tmp=q.top();q.pop();db v=tmp.first;int cnt=tmp.second;if(k>=cnt){k-=cnt;q.push({v/2,cnt*2});}else{q.push({v,cnt-k});q.push({v/2,k*2});k=0;}}while(!q.empty()){auto tmp=q.top();q.pop();db v=tmp.first;int cnt=tmp.second;if(x<=cnt){printf("%.9lf\n",v);return ;}else{x-=cnt;}}
}
signed main() {// ios::sync_with_stdio(false);// cin.tie(NULL);// cout.tie(NULL);rd(T);while(T--){xpigeon();}return 0;
}

F - Adding Chords

第一眼看的时候凭感觉像是线段树，但不知道怎么维护，一直在考虑区间相同颜色段个数但赛后细想发现根本不对。

用数学语言把这个相交条件抽象化一下，假设现在要连接 \(a,b\) 两点，曾经连接过了 \(c,d\) 两点。
当 \(a<c<b<d\) 或者 \(c<a<d<b\) 时，两条线段是相交的，这样看性质就很显然，当有一条线段的左端点在 \([a+1,b-1]\) 时，其右端点不能大于 \(b\)。
这个问题就可以直接用线段树来解决，维护每个左端点位置上连接到的右端点的值是多少，对于每一个操作都在线段树上查询 \([a+1,b-1]\) 区间里的最大值来判断是否与当前线段相交。
第二个条件也是同理，当有一条线段的右端点在 \([a+1,b-1]\) 时，其左端点不能小于 \(a\)，然后按照同样的方法维护每个右端点连接到的左端点的值，查询时查询最小值即可。

时间复杂度 \(O(q \log n)\)。

点击查看代码

const int N=1e6+5;
int n,q;
struct tree{int mx,mn;tree(){mx=0,mn=1e9;}tree operator + (const tree &G)const{tree res;res.mx=max(mx,G.mx);res.mn=min(mn,G.mn);return res;}
}t[N*3];
int P=1;
void update_max(int pos,int v){int x=pos+P;t[x].mx=v;for(x>>=1;x;x>>=1) t[x]=t[ls(x)]+t[rs(x)];
}
void update_min(int pos,int v){int x=pos+P;t[x].mn=v;for(x>>=1;x;x>>=1) t[x]=t[ls(x)]+t[rs(x)];
}
tree query(int l,int r){l+=P-1,r+=P+1;tree res;while(l^1^r){if(~l&1) res=res+t[l^1];if(r&1) res=res+t[r^1];l>>=1,r>>=1;}return res;
}
void xpigeon(){rd(n,q);while(P<=n+1) P<<=1;for(int i=1,a,b;i<=q;i++){rd(a,b);if(a+1<=b-1){auto tmp=query(a+1,b-1);if(tmp.mx>b || tmp.mn<a){printf("No\n");}else{printf("Yes\n");update_max(a,b);update_min(b,a);}}else{printf("Yes\n");}}
}
signed main() {xpigeon();return 0;
}