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;
}做题答题要先一定要先观察数据！！！