模拟题 day3
出题人: liu_runda
题目名称 摆渡 摆车 背包
源程序文件名 boat.cpp ju.cpp pack.cpp
输入文件名 boat.in ju.in pack.in
输出文件名 boat.out ju.out pack.out
每个测试点时限 1s 1s 1s
内存限制 512MB 512MB 512MB
测试点数目 10 10 10
每个测试点分值 10 10 10
是否打开O2 优化 是 是 是
在windows 下用lemon 进行测试.
摆渡(boat)
【题目描述】
民国时期,在湘西有一位老人摆渡为生.
水道不复杂,也不简单,有n 个渡口,m 条河流连接不同的渡口.每条河流都可以双向通
行,用时也相同.
摆渡的收费是很特别的.
基本费用是按照路程来算.如果总路程为L,就会收取基本费用L.
附加费用是按照经过的渡口的凶险程度来计算,而且只考虑经过的渡口(包括出发的
渡口和终点的渡口)中凶险程度最大的渡口.如果经过的渡口中凶险程度最大为M,就会
收取附加费用M
收取的总费用为L+M.
现在有q 次摆渡,给出每次的起点和终点,问每次摆渡的最少收费是多少.
【输入格式】
第一行三个整数n,m,q
接下来一行n 个数字,依次表示n 个渡口的凶险程度v
接下来m 行,每行三个数字a,b,w 表示渡口a,b 之间有一条长度为w 的河道.
接下来q 行,每行两个数字u,v 表示一次摆渡的起点和终点
【输出格式】
q 行,每行一个整数表示最少的收费.
【样例输入】
5 5 2
1 2 3 4 5
1 2 1
2 3 2
3 4 3
4 5 4
5 1 5
4 1
2 5
【样例输出】
10
11
【数据范围】
第1,2,3 个测试点,所有渡口的凶险程度相同
第4,5,6 个测试点,所有渡口的凶险程度从1 到n 单调不下降
所有数据,n<=300,m<=40000,1<=a,b,u,v<=n,u!=v,a!=b,1<=w<=109.同一对渡口之间可
能连有多条河道.
摆车(ju)
【题目描述】
liu_runda 从前很喜欢下象棋.象棋中的车是很厉害的棋子,如果一个车和另外一个棋
子位于同一行或者同一列,而两个棋子之间又没有其他棋子,车就可以攻击到那个棋子.
现在liu_runda 有一个n 行m 列的棋盘,上面有一些地方摆上了不是车的棋子.他想
知道,怎样才能在棋盘上尽量多地放置车,并使得它们互相之间不攻击?也就是说,怎样才
能选择若干个格子放置车,使得同一行/同一列放置车的位置之间都隔有其他棋子?
【输入格式】
第一行,三个数字n,m,q,分别表示行数,列数和已经摆放的不是车的棋子数目
接下来q 行,每行两个数字a,b,表示a 行b 列放置了一个不是车的棋子.保证这q 个
位置各不相同.
【输出格式】
一行一个整数,表示棋盘上最多能放车的个数.
【样例输入】
3 3 1
2 2
【样例输出】
4
【数据范围】
第1 个测试点,n=1
第2 个测试点,q=0
第3,4,5 个测试点,n*m<=16
对所有的测试点,n<=50,m<=50,q<=1000
背包(pack)
【题目描述】
给出n 个物品,每个物品有重量w[i]和价值v[i]两种属性.
现在要求选出重量不超过m 的物品,使得物品的价值之和最大.
【输入格式】
第一行两个整数n,m 表示物品个数和重量的限制
接下来n 行第i 行两个整数w[i]和v[i],表示第i 种物品的重量和价值
【输出格式】
一行一个整数表示能够获得的最大价值
【样例输入】
3 5
4 5
2 4
3 4
【样例输出】
8
【数据范围】
第1,2,3 个测试点,n<=20,m<=109,w[i]<=109,v[i]<=109
第4,5,6,7 个测试点,n<=500,m<=500,w[i]<=109,v[i]<=109
第8,9,10 个测试点,n<=500,m<=109,w[i]<=109,v[i]<=10
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 //#include<queue> 7 //#include<set> 8 #include<bitset> 9 #include<cassert> 10 #include<vector> 11 #define INF (1LL<<60) 12 #define re register 13 #define Ii inline int 14 #define Il inline long long 15 #define Iv inline void 16 #define Ib inline bool 17 #define Id inline double 18 #define ll long long 19 #define Fill(a,b) memset(a,b,sizeof(a)) 20 #define R(a,b,c) for(register int a=b;a<=c;++a) 21 #define nR(a,b,c) for(register int a=b;a>=c;--a) 22 #define Min(a,b) ((a)<(b)?(a):(b)) 23 #define Max(a,b) ((a)>(b)?(a):(b)) 24 #define Cmin(a,b) ((a)=(a)<(b)?(a):(b)) 25 #define Cmax(a,b) ((a)=(a)>(b)?(a):(b)) 26 #define abs(a) ((a)>0?(a):-(a)) 27 #define D_e(x) printf("&__ %d __& ",x) 28 #define D_e_Line printf("----------------- ") 29 #define Pause system("pause"); 30 const int N=305; 31 using namespace std; 32 Ii read(){ 33 int s=0,f=1;char c; 34 for(c=getchar();c>'9'||c<'0';c=getchar())if(c=='-')f=-1; 35 while(c>='0'&&c<='9')s=s*10+(c^'0'),c=getchar(); 36 return s*f; 37 } 38 Iv print(ll x){ 39 if(x<0)putchar('-'),x=-x; 40 if(x>9)print(x/10); 41 putchar(x%10^'0'); 42 } 43 int hurt[N],seq[N]; 44 ll dis[N][N],ans[N][N]; 45 Ib cmp(const int &a,const int &b){ 46 return hurt[a]<hurt[b]; 47 } 48 int main(){ 49 freopen("boat.in","r",stdin),freopen("boat.out","w",stdout); 50 int n=read(),m=read(),T=read(); 51 R(i,1,n) 52 hurt[i]=read(); 53 R(i,1,n)seq[i]=i; 54 sort(seq+1,seq+n+1,cmp); 55 R(i,1,n) 56 R(j,1,n) 57 if(i!=j) 58 ans[i][j]=dis[i][j]=INF; 59 R(i,1,m){ 60 int u=read(),v=read(),w=read(); 61 Cmin(dis[u][v],w), 62 dis[v][u]=dis[u][v]; 63 } 64 R(p,1,n){ 65 int k=seq[p]; 66 R(i,1,n) 67 if(i!=k) 68 R(j,1,n) 69 if(i!=j&&j!=k) 70 Cmin(dis[i][j],dis[i][k]+dis[k][j]); 71 R(i,1,n) 72 R(j,1,n) 73 if(i!=j) 74 Cmin(ans[i][j],dis[i][j]+Max(Max(hurt[i],hurt[j]),hurt[k])); 75 } 76 while(T--) 77 print(ans[read()][read()]),putchar(' '); 78 return 0; 79 }
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 //#include<queue> 7 //#include<set> 8 #include<bitset> 9 #include<cassert> 10 #include<vector> 11 #define INF (1ll<<60) 12 #define re register 13 #define Ii inline int 14 #define Il inline long long 15 #define Iv inline void 16 #define Ib inline bool 17 #define Id inline double 18 #define ll long long 19 #define Fill(a,b) memset(a,b,sizeof(a)) 20 #define R(a,b,c) for(register int a=b;a<=c;++a) 21 #define nR(a,b,c) for(register int a=b;a>=c;--a) 22 #define Min(a,b) ((a)<(b)?(a):(b)) 23 #define Max(a,b) ((a)>(b)?(a):(b)) 24 #define Cmin(a,b) ((a)=(a)<(b)?(a):(b)) 25 #define Cmax(a,b) ((a)=(a)>(b)?(a):(b)) 26 #define abs(a) ((a)>0?(a):-(a)) 27 #define D_e(x) printf("&__ %d __& ",x) 28 #define D_e_Line printf("----------------- ") 29 #define Pause system("pause"); 30 const int N=505; 31 using namespace std; 32 Ii read(){ 33 int s=0,f=1;char c; 34 for(c=getchar();c>'9'||c<'0';c=getchar())if(c=='-')f=-1; 35 while(c>='0'&&c<='9')s=s*10+(c^'0'),c=getchar(); 36 return s*f; 37 } 38 Iv print(ll x){ 39 if(x<0)putchar('-'),x=-x; 40 if(x>9)print(x/10); 41 putchar(x%10^'0'); 42 } 43 int a[N][N],b[N][N],tot,head[N*N<<1],tim,vis[N*N<<1],match[N*N<<1]; 44 vector<int>V[N<<1]; 45 Ib Hungary(int u){ 46 for(vector<int>::iterator v=V[u].begin();v!=V[u].end();++v) 47 if(vis[*v]!=tim){ 48 vis[*v]=tim; 49 if(!match[*v]||Hungary(match[*v])){ 50 match[*v]=u;return 1; 51 } 52 } 53 return 0; 54 } 55 int mp[N][N]; 56 int main(){ 57 //freopen("ju.in","r",stdin),freopen("ju.out","w",stdout); 58 int n=read(),m=read(),K=read(); 59 R(i,1,K)mp[read()][read()]=1; 60 R(i,1,n)mp[i][0]=mp[i][m+1]=1; 61 R(i,1,m)mp[0][i]=mp[n+1][i]=1; 62 R(i,1,n) 63 R(j,1,m) 64 if(!mp[i][j]) 65 tot+=(mp[i][j-1]), 66 a[i][j]=tot; 67 int tot2=tot; 68 R(j,1,m) 69 R(i,1,n) 70 if(!mp[i][j]) 71 tot2+=(mp[i-1][j]), 72 b[i][j]=tot2; 73 R(i,1,n) 74 R(j,1,m) 75 if(!mp[i][j]) 76 V[a[i][j]].push_back(b[i][j]); 77 //V[b[i][j]].push_back(a[i][j]); 78 int ans=0; 79 R(i,1,tot) 80 vis[i]=++tim, 81 ans+=(Hungary(i));//ans+=(!match[i]&&Hungary(i)); 82 print(ans); 83 return 0; 84 }
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 //#include<queue> 7 //#include<set> 8 #include<bitset> 9 #include<cassert> 10 #include<vector> 11 #define INF (1ll<<60) 12 #define re register 13 #define Ii inline int 14 #define Il inline long long 15 #define Iv inline void 16 #define Ib inline bool 17 #define Id inline double 18 #define ll long long 19 #define Fill(a,b) memset(a,b,sizeof(a)) 20 #define R(a,b,c) for(register int a=b;a<=c;++a) 21 #define nR(a,b,c) for(register int a=b;a>=c;--a) 22 #define Min(a,b) ((a)<(b)?(a):(b)) 23 #define Max(a,b) ((a)>(b)?(a):(b)) 24 #define Cmin(a,b) ((a)=(a)<(b)?(a):(b)) 25 #define Cmax(a,b) ((a)=(a)>(b)?(a):(b)) 26 #define abs(a) ((a)>0?(a):-(a)) 27 #define D_e(x) printf("&__ %d __& ",x) 28 #define D_e_Line printf("----------------- ") 29 #define Pause system("pause"); 30 const int N=205; 31 using namespace std; 32 Ii read(){ 33 int s=0,f=1;char c; 34 for(c=getchar();c>'9'||c<'0';c=getchar())if(c=='-')f=-1; 35 while(c>='0'&&c<='9')s=s*10+(c^'0'),c=getchar(); 36 return s*f; 37 } 38 Iv print(ll x){ 39 if(x<0)putchar('-'),x=-x; 40 if(x>9)print(x/10); 41 putchar(x%10^'0'); 42 } 43 int n,m,c[505],w[505]; 44 ll sumc[1<<20],sumw[1<<20]; 45 Iv work1(){ 46 R(i,0,n-1) 47 sumc[1<<i]=c[i+1], 48 sumw[1<<i]=w[i+1]; 49 ll ans=0; 50 R(i,0,(1<<20)-1){ 51 int lowbit=i&(-i); 52 sumc[i]=sumc[lowbit]+sumc[i^lowbit], 53 sumw[i]=sumw[lowbit]+sumw[i^lowbit]; 54 if(sumc[i]<=m&&sumw[i]>ans)ans=sumw[i]; 55 } 56 print(ans), 57 exit(0); 58 } 59 ll f[5005]; 60 Iv work2(){ 61 R(i,0,m) 62 f[i]=0; 63 R(i,1,n) 64 nR(j,m,c[i]) 65 if(f[j-c[i]]+w[i]>f[j]) 66 f[j]=f[j-c[i]]+w[i]; 67 print(f[m]), 68 exit(0); 69 } 70 Iv work3(){ 71 int sum=0; 72 R(i,1,n)sum+=w[i]; 73 R(i,1,sum)f[i]=INF; 74 R(i,1,n) 75 nR(j,sum,w[i]) 76 if(f[j-w[i]]+c[i]<f[j]) 77 f[j]=f[j-w[i]]+c[i]; 78 int ans=0; 79 while(f[ans+1]<=m)++ans; 80 print(ans), 81 exit(0); 82 } 83 int main(){ 84 //R(i,0,100) 85 // printf("%d-> %d, %d ",i,i&-i,i^(i&-i)); 86 freopen("pack.in","r",stdin),freopen("pack.out","w",stdout); 87 n=read(),m=read(); 88 R(i,1,n) 89 c[i]=read(),w[i]=read(); 90 if(n<=20)work1(); 91 if(m<=500)work2(); 92 work3(); 93 return 0; 94 }