2022/2/6
2022/2/6
[P3381 【模板】最小费用最大流]( P3381 [模板]最小费用最大流 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) )
学习整理一下，(SPFA求费用流的模板)
const int qs=1e5;
const ll mod=998244353;
const ll inf=0x3f3f3f3f;
int n,m,s,t;
int p,head[qs],nxt[qs],to[qs],val[qs],dis[qs];
void add(int fx,int tx,int dx,int cx){
to[p]=tx;
dis[p]=dx;
nxt[p]=head[fx];
val[p]=cx;
head[fx]=p++;
}
void ist(int u,int v,int w,int c){
add(u,v,w,c);
add(v,u,0,-c);
}
int inq[qs],d[qs],pre[qs];
bool spfa(){
for(int i=0;i<=n;++i){
inq[i]=0;d[i]=inf,pre[i]=-1;
}
d[s]=0;inq[s]=1;
queue q; q.push(s);
while(q.si){
int u=q.front(); q.pop();
inq[u]=0;
for(int i=head[u];i!=-1;i=nxt[i]){
if(dis[i]){//spfa是以费用val求最短路的，但流量不能忽略
int v=to[i];
if(d[u]+val[i] [ 多彩的树 ]( 多彩的树 (nowcoder.com) )
状压+dfs
k<=10,枚举所有可能出现的颜色状态 i。
在图中搜索 状态i 出现的所有连通块的大小，其中一块连通块大小为n，产生的贡献是\(n*(n+1)/2\)。
考虑到颜色多的情况会多算颜色少的情况，比如 1011 多算的情况有 ： 1010 1001 1000 0011 0010 0001 这6种，计算的时候要减去。
//找到比状态i小的且与状态i 1 的位置对应的下一个状态（学到了
for(int j=i&(i-1);j;j=(j-1)&i)
参考代码
#include
#define ll long long
#define pii pair
#define si size()
#define fi first
#define se second
#define pb push_back
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}
const int qs=1e5;
const ll mod=1e9+7;
const ll inf=0x3f3f3f3f;
ll n,k,a[qs],f[qs],u[qs],pw[107];
vector v[qs];
ll dfs(int x,int sta){
if(u[x]) return 0; u[x]=1;
if((a[x]&sta) == 0) return 0;
ll ret=1;
for(int i=0;i>=1;
}
return ret;
}
int main(){
n=read(),k=read();
for(int i=1;i<=n;++i){
a[i]=read();
a[i]=(1<<(a[i]-1));
}
int x,y;
for(int i=1;i [ D. Range and Partition ]( Problem - D - Codeforces (Unofficial mirror site, accelerated for Chinese users) )
二分+暴力枚举
二分区间长度，判断一块区间[x,y]是否合法，需要在这段区间数的数量 num 减去 不在这段区间的数量 n-num 要 >=k
即 \(num-(n-num)>=k\)。
参考代码
#include
#define ll long long
#define pii pair
#define si size()
#define fi first
#define se second
#define pb push_back
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}
const int qs=2e5+7;
const ll mod=1e9+7;
const ll inf=0x3f3f3f3f;
int n,k,T,a[qs],b[qs];
vector< pii > ans;
int ck(int x){
for(int i=1;i+x-1<=n;++i){
if((b[i+x-1]-b[i-1])*2-n>=k) return i;
}
return 0;
}
int main(){
T=read();
while(T--){
n=read(),k=read();
ans.clear();
for(int i=1;i<=n;++i) b[i]=0;
for(int i=1;i<=n;++i) a[i]=read(),b[a[i]]++;
for(int i=1;i<=n;++i) b[i]+=b[i-1];
int l=1,r=n,ret=0,len=0;
while(l<=r){
int md=(l+r)/2;
int sta=ck(md);
// cout<<"l="<=l) {
ret++;
if(ret>0){
ans.pb({last+1,i});
ret=0;
last=i;
cnt++;
}
}
else ret--;
}
ans.pb({last+1,n});
cout<