OI 笑传 #12

这次是 ABC424 423 的 DEF。

ABC424D

朴素状压即可。

code

Show me the code

#define psb push_back
#define mkp make_pair
#define ls p<<1
#define rs (p<<1)+1
#define rep(i,a,b) for( int i=(a); i<=(b); ++i)
#define per(i,a,b) for( int i=(a); i>=(b); --i)
#define rd read()
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){ll x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*f;
}
const int N=512;
vector<int> st[N];
void init(){}
string mmap[10];
int dp[10][N];
void solve(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>mmap[i];}memset(dp,0x3f,sizeof dp);for(int i=0;i<(1<<m);i++){bool isok=1;int cnt=0;for(int k=0;k<m;k++){if(mmap[1][k]=='.'&&((i>>k)&1)){isok=0;break;}if(mmap[1][k]=='#'&&!((i>>k)&1))cnt++;}if(!isok)continue;dp[1][i]=cnt;// cout<<"1 st "<<i<<' '<<cnt<<'\n';}for(int i=2;i<=n;i++){for(int st1=0;st1<(1<<m);st1++){bool isok=1;for(int k=0;k<m;k++){if(mmap[i-1][k]=='.'&&((st1>>k)&1)){isok=0;break;}}if(!isok)continue;for(int st2:st[st1]){int cnt=0;bool isok1=1;for(int k=0;k<m;k++){if(mmap[i][k]=='.'&&((st2>>k)&1)){isok1=0;break;}if(mmap[i][k]=='#'&&!((st2>>k)&1))cnt++;}if(!isok1)continue;dp[i][st2]=min(dp[i-1][st1]+cnt,dp[i][st2]);}}}int ans=0x3f3f3f3f;for(int i=0;i<(1<<m);i++){ans=min(dp[n][i],ans);}cout<<ans<<'\n';return ;
}
int main(){int T;cin>>T;for(int i=0;i<(1<<7);i++){for(int j=0;j<(1<<7);j++){bool isok=1;for(int k=1;k<7;k++){if(((i>>k)&1) && ((j>>k)&1) && ((i>>(k-1))&1) && ((j>>(k-1))&1) ){isok=0;break;}} if(!isok)continue;st[i].push_back(j);}}while(T--){// init();solve();}return 0;
}

ABC424E

初见想到了用堆模拟维护同类长度木棍集合的做法，时间复杂度应该是 \(O(n\log n^2)\)，但是竟然还会超时。

可能是堆的常数问题？

还有一种不用堆的思路是我们首先确定让集合中最长的木棍长度不超过 \(l\) 的最小操作数量是多少，继承上面维护木棍集合的做法可以二分答案。时间复杂度 \(O(n\log n^2)\)。

这样得到的 \(l\) 是一个精确的 \(l\)，也就是其中必然存在一个集合经过 \(2^k\) 次拆分后所有木棍的长度都正好是 \(l\)，且是其它所有堆中最大的，总的操作次数也小于 \(K\)。而将这些木棍再分一半之后所需要的总操作次数就

这样，剩下的那些操作一定只会对这个集合操作，直接二分拆好之后顺着找到第 \(X\) 个即可。

code

Show me the code

ABC424F

考虑把连接上的端点赋上相同的随机值。这样两个点可以连的情况就是没有相同的随机值在这根线两侧。

判重复出现可以用异或解决。于是直接树状数组维护区间异或判断即可。

code

Show me the code

ABC423D

用几个堆模拟过程即可。

code

Show me the code

ABC423E

线段树上合并区间即可，类似一个分治。

简单推下式子