2022/2/22

2022/2/22

明七暗七_牛客竞赛动态规划专题班数位dp练习 (nowcoder.com)

二分+数位dp

二分区间右端点 r

用数位dp求出 r 与 m 之间有多少个合法数字

参考代码

#include<bits/stdc++.h>
#define ll  long long
#define pii pair<long long , long long >
#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 ll mod=20020219;
const ll inf=0x3f3f3f3f;
const int qs=1e6+7;
 
ll n,m,f[20][10],bit[20],len;

ll dfs(int pos,ll num,ll lim){
	if(!pos) 	return num%7!=0;	
	if(!lim && f[pos][num]) return f[pos][num];
	ll ans=0;
	int up=lim ? bit[pos] : 9;
	for(int i=0;i<=up;++i){
		if(i==7) continue;
		
		ans+=dfs(pos-1,(num*10+i)%7,lim&&i==up);
	}
	if(!lim) f[pos][num]=ans;
	return ans;
}

ll solve(ll x){
	if(x<0) return 0;
	len=0;
	while(x){
		bit[++len]=x%10;
		x/=10;
	}
	return dfs(len,0,1);
}

int ck(ll x){
	ll p=solve(x)-solve(m);
	p=x-m-p;
	return p>=n;
}

int main(){
	
	m=read(),n=read();	
    ll ans,l,r;
	l=m-1,r=1e16;
    while(l<=r){
    	ll md=(l+r)/2;
    	if(ck(md)) ans=md,r=md-1;
    	else l=md+1;
	}
    cout<<ans<<"\n";
    return 0;
}

CQOI2016 手机号码_数位dp练习 (nowcoder.com)

数位dp

\(f[pos][ppre][pre][is4][is8][fg]\)表示当前位置pos,前一位是pre,前前一位是ppre,是否有4或8,是否有贡献

参考代码

#include<bits/stdc++.h>
#define ll  long long
#define pii pair<long long , long long >
#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 ll mod=20020219;
const ll inf=0x3f3f3f3f;
const int qs=1e6+7;

ll f[13][13][13][2][2][2],n,m,bit[13],len;

ll dfs(ll pos,ll pre,ll ppre,ll fg,ll is4,ll is8,ll lim){
	if(is4&&is8) return 0;
	if(!pos) return fg;
	if(!lim && f[pos][ppre][pre][is4][is8][fg]) return f[pos][ppre][pre][is4][is8][fg];
	ll up=lim ? bit[pos] : 9;
	ll ans=0;
	for(int i=0;i<=up;++i){
		ll p=fg;
		if(i==pre&&ppre==pre) p=1;
		ans+=dfs(pos-1,i,pre,p,is4||i==4,is8||i==8,lim&&i==up);
	}
	if(!lim) f[pos][ppre][pre][is4][is8][fg]=ans;
	return ans;
}

ll solve(ll x){
	if(x<0) return 0;
	len=0;
	memset(f,0,sizeof(f));
	while(x){
		bit[++len]=x%10;
		x/=10;
	}
	ll ans=0;
	for(int i=1;i<=bit[len];++i){
		ans+=dfs(len-1,i,0,0,i==4,i==8,i==bit[len]);
	}
	return ans;
}

int main(){
	n=read(),m=read();
	ll ans=solve(m)-solve(n-1); 
	cout<<ans<<"\n";
    return 0;
}

\(f[pos][pre][cnt][sta][fg]\) 表示当前位pos,前一位为pre,有连续cnt个,4和8的状态为sta,是否已经产生贡献fg。

参考代码

#include<bits/stdc++.h>
#define ll  long long
#define pii pair<long long , long long >
#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 ll mod=20020219;
const ll inf=0x3f3f3f3f;
const int qs=1e6+7;

ll f[13][13][13][5][2],n,m,bit[13],len;

ll dfs(ll pos,ll pre,ll cnt,ll sta,ll fg,ll lim){
	if(sta==3) return 0;
	if(!pos) {
		return fg;	
	}
	if(!lim && f[pos][pre][cnt][sta][fg]) return f[pos][pre][cnt][sta][fg];
	ll up=lim ? bit[pos] : 9;
	ll ans=0;
	for(int i=0;i<=up;++i){
		ll ft=sta;
		if(i==4){
			if(!sta) sta=1;
			else if(sta==2) sta=3;
		}
		if(i==8){
			if(!sta) sta=2;
			else if(sta==1) sta=3;
		}
		ll p=(i==pre) ? cnt+1 : 1;
		p=min(p,3ll);
		ans+=dfs(pos-1,i,p,sta,fg||p==3,lim&&i==up);
		sta=ft;
	}
	if(!lim) f[pos][pre][cnt][sta][fg]=ans;
	return ans;
}

ll solve(ll x){
	if(x<0) return 0;
	len=0;
	while(x){
		bit[++len]=x%10;
		x/=10;
	}
	ll ans=0;
	for(int i=1;i<=bit[len];++i){
		ll sta=0;
		if(i==4) sta=1;
		if(i==8) sta=2;
		ans+=dfs(len-1,i,1,sta,0,i==bit[len]);
	}
	return ans;
}

int main(){
	n=read(),m=read();
	ll ans=solve(m)-solve(n-1); 
	cout<<ans<<"\n";
    return 0;
}

ps:找了三个小时bug,写了好多组数据,终于找到了问题,之前记忆化数组f没有记录fg那一维,但也感觉没毛病,后来想了想,不记录fg那一维,会导致pos前已经有贡献的加到之前没有贡献的,贡献会增多。

[网络流24题]运输问题 (nowcoder.com)

费用流(最小费用流&最大费用流)

最大费用流就是最小费用流中每个流的费用取相反数,最后结果再取相反数

建模方法:

  1. s向每个仓库连{c,0}的边
  2. 每个仓库向每个商店连{inf,w}的边
  3. 每个商店向t连{c,0}的边

去相反数跑两边最小费用流即可

参考代码

#include<bits/stdc++.h>
#define ll  long long
#define pii pair<long long , long long >
#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 ll mod=20020219;
const ll inf=0x3f3f3f3f;
const int qs=1e6+7;

int n,m,s,t; 
int p,head[qs],nxt[qs],to[qs],val[qs],dis[qs];
int a[107],b[107],c[107][107];
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);
}

void build_map(int ff){
	memset(head,-1,sizeof(head));
	s=0,t=n+m+1;  p=0;
	for(int i=1;i<=n;++i){
		ist(s,i,a[i],0);
	}
	for(int i=1;i<=m;++i){
		ist(n+i,t,b[i],0);
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			ist(i,n+j,inf,c[i][j]*ff);
		}
	}
}

int inq[qs],d[qs],pre[qs];

bool spfa(){
	for(int i=0;i<=n+m+3;++i){
		inq[i]=0;d[i]=inf,pre[i]=-1;
	}
	d[s]=0;inq[s]=1;
	queue<int> 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]<d[v]){
					d[v]=d[u]+val[i];
					pre[v]=i;
					if(!inq[v]){
						q.push(v);
						inq[v]=1;
					}
				}
			}
		}
	}
	return pre[t]!=-1;
}

ll costflow(){//计算最小费用最大流 
	ll ret=0,ans=0;
	while(spfa()){
		int flow=inf;
		for(int i=t;i!=s;i=to[pre[i]^1]){
			//计算当前增广路的最小流量 
			flow=min(dis[pre[i]],flow);
		}
		ans+=flow;
		for(int i=t;i!=s;i=to[pre[i]^1]){
			dis[pre[i]]-=flow;
			dis[pre[i]^1]+=flow;
			ret+=val[pre[i]]*flow;
		}
	}
	return ret;
}

int main(){
	n=read(),m=read();
	for(int i=1;i<=n;++i) a[i]=read();
	for(int i=1;i<=m;++i) b[i]=read();
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j) c[i][j] = read();
	}
	build_map(1);
	ll ans;
	ans=costflow(); cout<<ans<<"\n";
	
	build_map(-1);
	ans=costflow()*-1; cout<<ans<<"\n";
	
    return 0;
}

上一篇:工具代码


下一篇:体验jQuery