LOJ2557. 「CTSC2018」组合数问题

时间：2023-03-09 03:10:58
LOJ2557. 「CTSC2018」组合数问题

LOJ2557. 「CTSC2018」组合数问题

这道题是我第一道自己做完的题答题。考场上面我只拿了41分，完全没有经验。现在才发现其实掌握了大概的思路还是不难。

首先模拟退火，通过了1，2，6，9，10五个测试点。

#include<bits/stdc++.h>

using namespace std;

#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)

#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)

typedef long long ll;

template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}

template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}

inline int read(){

	int x;

	char c;

	int f=1;

	while((c=getchar())!='-' && (c>'9' || c<'0'));

	if(c=='-') f=-1,c=getchar();

	x=c^'0';

	while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');

	return x*f;

}

inline ll readll(){

	ll x;

	char c;

	int f=1;

	while((c=getchar())!='-' && (c>'9' || c<'0'));

	if(c=='-') f=-1,c=getchar();

	x=c^'0';

	while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');

	return x*f;

}

const int maxn=100000+10;

const double delt=0.98;

int a[maxn],n,m,k;

int Wanted;

inline double Possible(){ return rand()*1.0/RAND_MAX; }

inline int getans(){

	freopen("placement8.out","w",stdout);

	REP(i,1,n) printf("%d%c",a[i],i==iend?'\n':' ');

	fclose(stdout);

	system("./simulator placement8.in placement8.out");

	freopen("res.txt","r",stdin);

	int res=read();

	fclose(stdin);

	if(res<=Wanted) exit(0);

	return res;

}

int main(){

	srand(time(0));

	freopen("placement8.ans","r",stdin);

	REP(i,1,10) Wanted=read();

	fclose(stdin);

	freopen("placement8.in","r",stdin);

	n=read(),m=read(),k=read();

	m=k;

	fclose(stdin);

	int Now;

	//cerr << Possible() << endl; return 0;

	REP(i,1,n) a[i]=rand()%m+1;

	while(1){

		double T=100;

		Now=getans();

		while(T>=1e-6){

			int x=rand()%n+1,y=rand()%m+1,z=a[x];

			a[x]=y;

			int res=getans();

			if(res<Now||(Possible()<exp((-fabs(res-Now))/T))) Now=res;

			else a[x] = z;

			T*=delt;

		}

		REP(i,1,1e5) {

			int x=rand()%n+1,y=rand()%m+1,z=a[x];

			a[x]=y;

			int res=getans();

			if(res<Now) Now=res; else a[x]=z;

		}

	}

	return 0;

}

观察第三个测试点，发现只有三台TPU，且依赖数为0，最后答案为106，可以直接dp求出最优解。

#include<bits/stdc++.h>

using namespace std;

#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)

#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)

typedef long long ll;

template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}

template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}

inline int read(){

	int x;

	char c;

	int f=1;

	while((c=getchar())!='-' && (c>'9' || c<'0'));

	if(c=='-') f=-1,c=getchar();

	x=c^'0';

	while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');

	return x*f;

}

inline ll readll(){

	ll x;

	char c;

	int f=1;

	while((c=getchar())!='-' && (c>'9' || c<'0'));

	if(c=='-') f=-1,c=getchar();

	x=c^'0';

	while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');

	return x*f;

}

const int maxn=100+10,inf=0x3f3f3f3f;

int dp[maxn][maxn][maxn],pre[maxn][maxn][maxn];

int t[maxn][maxn];

void dfs(int n,int i,int j){

	if(!n) return;

	if(pre[n][i][j]==1) dfs(n-1,i-t[n][1],j);

	else if(pre[n][i][j]==2) dfs(n-1,i,j-t[n][2]);

	else dfs(n-1,i,j);

	printf("%d ",pre[n][i][j]);

}

int main(){

#ifndef ONLINE_JUDGE

	freopen("placement3.in","r",stdin);

	freopen("placement3.out","w",stdout);

#endif

	int n=read(),m=read();

	m=read(),read();

	REP(i,1,n) REP(j,1,m) t[i][j]=read();

	m=106;

	memset(dp,inf,sizeof(dp));

	dp[0][0][0]=0;

	REP(i,1,n)

		REP(A,0,m) REP(B,0,m) REP(C,0,m) if(dp[i-1][A][B]!=inf){

			if(A+t[i][1]<=m)

				if(chkmin(dp[i][A+t[i][1]][B],dp[i-1][A][B])) pre[i][A+t[i][1]][B]=1;

			if(B+t[i][2]<=m)

				if(chkmin(dp[i][A][B+t[i][2]],dp[i-1][A][B])) pre[i][A][B+t[i][2]]=2;

			if(chkmin(dp[i][A][B],dp[i-1][A][B]+t[i][3])) pre[i][A][B]=3;

		}

	REP(i,0,m) REP(j,0,m) if(dp[n][i][j]<=m){

		dfs(n,i,j);

		return 0;

	}

	return 0;

}

观察第四个测试点，发现依赖条件构成了三条链，则我们可以对每条链dp出最优值即可。

#include<bits/stdc++.h>

using namespace std;

#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)

#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)

typedef long long ll;

template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}

template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}

inline int read(){

	int x;

	char c;

	int f=1;

	while((c=getchar())!='-' && (c>'9' || c<'0'));

	if(c=='-') f=-1,c=getchar();

	x=c^'0';

	while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');

	return x*f;

}

inline ll readll(){

	ll x;

	char c;

	int f=1;

	while((c=getchar())!='-' && (c>'9' || c<'0'));

	if(c=='-') f=-1,c=getchar();

	x=c^'0';

	while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');

	return x*f;

}

const int maxn=400+10,inf=0x3f3f3f3f;

int f[maxn][maxn],pre[maxn][maxn];

int l[maxn],r[maxn],tmp;

int t[maxn][maxn],W[maxn][maxn],cnt;

void dfs(int i,int j){

	if(pre[i][j]) dfs(i-1,pre[i][j]);

	printf("%d ",j);

	++cnt;

}

int main(){

#ifndef ONLINE_JUDGE

	freopen("placement4.in","r",stdin);

	freopen("placement4.out","w",stdout);

#endif

	int n=read(),m=read(),K=read();read();

	int lst=1;

	l[++tmp]=1;

	while(m--){

		int x=read(),y=read();

		if(x!=lst){

			r[tmp]=lst;

			l[++tmp]=x;

		}

		lst=y;

	}

	r[tmp]=lst;

	REP(i,1,n) REP(j,1,K) t[i][j]=read();

	REP(i,1,K) REP(j,1,K) W[i][j]=read();

	memset(f,inf,sizeof(f));

	REP(T,1,tmp){

		REP(i,1,K) f[l[T]][i]=t[l[T]][i];

		REP(i,l[T]+1,r[T]) REP(j,1,K) REP(k,1,K) if(chkmin(f[i][j],f[i-1][k]+W[k][j]+t[i][j])) pre[i][j]=k;

		int Min=inf,num;

		REP(i,1,K) if(chkmin(Min,f[r[T]][i])) num=i;

		dfs(r[T],num);

	}

	putchar('\n');

	return 0;

}

观察第5个测试点，每个点只会向它之后5个点以内连边，我们就只需要记录向前5个点的状态dp即可。

#include<bits/stdc++.h>

using namespace std;

#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)

#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)

typedef long long ll;

template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}

template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}

inline int read(){

	int x;

	char c;

	int f=1;

	while((c=getchar())!='-' && (c>'9' || c<'0'));

	if(c=='-') f=-1,c=getchar();

	x=c^'0';

	while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');

	return x*f;

}

inline ll readll(){

	ll x;

	char c;

	int f=1;

	while((c=getchar())!='-' && (c>'9' || c<'0'));

	if(c=='-') f=-1,c=getchar();

	x=c^'0';

	while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');

	return x*f;

}

const int maxn=500+5,inf=0x3f3f3f3f;

int a[maxn][maxn];

int dp[maxn][5][5][5][5][5],pre[maxn][5][5][5][5][5];

int t[maxn][maxn],W[maxn][maxn];

void find_pre(int n,int A,int B,int C,int D,int E){

	if(!n) return;

	find_pre(n-1,B,C,D,E,pre[n][A][B][C][D][E]);

	printf("%d ",A+1);

}

int main(){

#ifndef ONLINE_JUDGE

	freopen("placement5.in","r",stdin);

	freopen("placement5.out","w",stdout);

#endif

	int n=read(),m=read(),K=read();read();

	while(m--){

		int x=read(),y=read();

		a[y][y-x]=1;

	}

	REP(i,1,n) REP(j,0,4) t[i][j]=read();

	REP(i,0,4) REP(j,0,4) W[i][j]=read();

	m=K;

	memset(dp,inf,sizeof(dp));

	REP(A,0,4) REP(B,0,4) REP(C,0,4) REP(D,0,4) REP(E,0,4) dp[0][A][B][C][D][E]=0;

	REP(i,1,n) REP(A,0,4) REP(B,0,4) REP(C,0,4) REP(D,0,4) REP(E,0,4) if(dp[i-1][A][B][C][D][E]<inf)

		REP(x,0,4){

			int res=t[i][x];

			if(a[i][1]) res+=W[A][x];

			if(a[i][2]) res+=W[B][x];

			if(a[i][3]) res+=W[C][x];

			if(a[i][4]) res+=W[D][x];

			if(a[i][5]) res+=W[E][x];

			if(chkmin(dp[i][x][A][B][C][D],dp[i-1][A][B][C][D][E]+res)) pre[i][x][A][B][C][D]=E;

		}

	REP(A,0,4) REP(B,0,4) REP(C,0,4) REP(D,0,4) REP(E,0,4) if(dp[n][A][B][C][D][E]<=300063) find_pre(n,A,B,C,D,E);

	return 0;

}

观察第7个测试点，发现没有运行时间很大，相当于把点和TPU进行二分图匹配。由于我们已经知道最后的答案，我们直接把边权小于等于答案的连边即可。

#include<bits/stdc++.h>

using namespace std;

#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)

#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)

typedef long long ll;

template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}

template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}

inline int read(){

	int x;

	char c;

	int f=1;

	while((c=getchar())!='-' && (c>'9' || c<'0'));

	if(c=='-') f=-1,c=getchar();

	x=c^'0';

	while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');

	return x*f;

}

inline ll readll(){

	ll x;

	char c;

	int f=1;

	while((c=getchar())!='-' && (c>'9' || c<'0'));

	if(c=='-') f=-1,c=getchar();

	x=c^'0';

	while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');

	return x*f;

}

const int maxn=600+10;

int a[maxn][maxn],n,K,vis[maxn],ma[maxn];

int p[maxn];

int dfs(int x){

	if(vis[x]) return 0;

	vis[x]=1;

	REP(i,1,K) if(a[x][i])

		if(!ma[i] || dfs(ma[i])){

			ma[i]=x;

			return 1;

		}

	return 0;

}

int main(){

#ifndef ONLINE_JUDGE

	freopen("placement7.in","r",stdin);

	freopen("placement7.out","w",stdout);

#endif

	n=read();read(),K=read();read();

	REP(i,1,n) REP(j,1,K){

		int x=read();

		if(x<=1014) a[i][j]=1;

	}

	REP(i,1,n){

		memset(vis,0,sizeof(vis));

		dfs(i);

	}

	REP(i,1,K) p[ma[i]]=i;

	REP(i,1,n) printf("%d%c",p[i],i==iend?'\n':' ');

	return 0;

}

观察第8个测试点，发现为一个分层图，且两两之间传输的权值很小，对于每一层做二分权值做二分图匹配即可。

#include<bits/stdc++.h>

using namespace std;

#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)

#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)

typedef long long ll;

template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}

template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}

inline int read(){

	int x;

	char c;

	int f=1;

	while((c=getchar())!='-' && (c>'9' || c<'0'));

	if(c=='-') f=-1,c=getchar();

	x=c^'0';

	while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');

	return x*f;

}

inline ll readll(){

	ll x;

	char c;

	int f=1;

	while((c=getchar())!='-' && (c>'9' || c<'0'));

	if(c=='-') f=-1,c=getchar();

	x=c^'0';

	while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');

	return x*f;

}

const int maxn=600+10,inf=0x3f3f3f3f;

int a[maxn][maxn],t[maxn][maxn],W[maxn][maxn],co[maxn];

int n,m,K,l[maxn],Nw,r[maxn],tmp,vis[maxn],ma[maxn],p[maxn];

int dfs(int x){

	if(vis[x]) return 0;

	vis[x]=1;

	REP(i,1,K) if(a[x][i]){

		if(!ma[i] || dfs(ma[i])){

			ma[i]=x;

			return 1;

		}

	}

	return 0;

}

inline bool check(int x){

	memset(ma,0,sizeof(ma));

	memset(a,0,sizeof(a));

	int res=0;

	REP(i,l[Nw],r[Nw]) REP(j,1,K)

		if(t[i][j]<=x) a[i][j]=1;

		else a[i][j]=0;

	REP(i,l[Nw],r[Nw]){

		memset(vis,0,sizeof(vis));

		res+=dfs(i);

	}

	return res==(r[Nw]-l[Nw]+1);

}

int main(){

#ifndef ONLINE_JUDGE

	freopen("placement8.in","r",stdin);

	freopen("placement8.out","w",stdout);

#endif

	n=read(),m=read(),K=read();read();

	co[1]=1;

	while(m--){

		int x=read(),y=read();

		if(!co[y]) co[y]=co[x]+1;

		if(!co[x]) co[x]=co[y]-1;

	}

	for(int i=1,j;i<=n;i=j+1){

		j=i;

		while(j<=n && co[j+1]==co[i]) ++j;

		l[++tmp]=i,r[tmp]=j;

	}

	REP(i,1,n) REP(j,1,K) t[i][j]=read();

	int sum=0;

	REP(i,1,tmp){

		Nw=i;

		int L=1,R=10000;

		while(L<=R){

			int Mid=(L+R)>>1;

			if(check(Mid)) R=Mid-1;

			else L=Mid+1;

		}

		check(R+1);

		memset(p,0,sizeof(p));

		REP(j,1,K) if(ma[j]){

//			if(p[ma[j]]) cerr<<p[ma[j]]<<' '<<j<<endl;

			p[ma[j]]=j;

			++sum;

		}

		REP(j,l[i],r[i]){

//			if(!p[j]) cerr<<j<<endl;

			printf("%d ",p[j]);

		}

	}

//	cerr<<sum<<' '<<n<<endl;

	return 0;

}

做题答题要先一定要先观察数据！！！

相关文章