CodeForces Round #488 Div2 题解

This blog post is only available in Simplified Chinse.

这是我的博客发布的第 100 篇文章！:tada:

D - Open Communication

Description

有两个玩家，给出分别 n 和 m 个数对， $1\leq n,m\leq 12$ ，所有数字都 $\in [0,9]$ ，并且一个数对里的数字不相同，不会有重复的数对。现在有一个“共享数字”，这个数字在 A 玩家的数对里和 B 玩家的数对里都至少出现一次。如果你可以推断出这个数字，输出这个数字；如果你无法推断出这个数字，但是你确信两个玩家都知道这个数字，输出 0；如果连玩家也不知道，输出 -1。

（题意难以解释，建议参考原题样例：Link）

Analysis

其实是个非常简单的题，两两枚举数对，如果发现 A 中某一个数对与 B 中多个数对都有恰好一个相同的数字就是 -1，如果每次枚举到 A 中一个数对，B 中与其有相同数字的都只有一个，则可以确定双方知道，输出 0；如果总是同一个数字，则确定这个数字。

Code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

const int maxn=20;
int n,m,ans=1;
pair <int,int> a[maxn],b[maxn];
bool is[15];

inline int read(){
	int ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}

inline int have_same(pair<int,int> aa, pair<int,int> bb){
	// cout<<aa.first<<","<<aa.second<<"  "<<bb.first<<","<<bb.second<<endl;
	 (aa.first==bb.first && aa.first!=bb.second && aa.second!=bb.first && aa.second!=bb.second)  aa.first;
	 (aa.first!=bb.first && aa.first==bb.second && aa.second!=bb.first && aa.second!=bb.second)  aa.first;
	 (aa.first!=bb.first && aa.first!=bb.second && aa.second==bb.first && aa.second!=bb.second)  aa.second;
	 (aa.first!=bb.first && aa.first!=bb.second && aa.second!=bb.first && aa.second==bb.second)  aa.second;
	
	 ;
}

{
	n=();m=();
	 ( i=;i<=n;i++){
		 x=(),y=();
		a[i]=(x,y);
	}
	 ( i=;i<=m;i++){
		 x=(),y=();
		b[i]=(x,y);
	}

	 tmp[];
	 ( i=;i<=n;i++){
		 cnt=;
		(tmp,,(tmp));
		 ( j=;j<=m;j++){
			 now=(a[i],b[j]);
			is[now]=;tmp[now]=;
		}
		 ( j=;j<=;j++) cnt+=tmp[j];
		 (cnt>){
			cout<<<<endl;
			 ;
		}
	}

	 ( i=;i<=m;i++){
		 cnt=;
		(tmp,,(tmp));
		 ( j=;j<=n;j++){
			 now=(a[j],b[i]);
			tmp[now]=;
		}
		 ( j=;j<=;j++) cnt+=tmp[j];
		 (cnt>){
			cout<<<<endl;
			 ;
		}
	}

	 all_cnt=;
	 ( i=;i<=;i++) {all_cnt+=is[i]; (is[i]) ans=i;}
	 (all_cnt>) cout<<<<endl;  cout<<ans<<endl;
	 ;
}

E - Careful Maneuvering

Description

一个平面上有 n 艘飞船位于 $(-100,y_{1,i})$ ，另外有 m 艘飞船位于 $(100,y_{2,i})$ ，现在需要让你确定两个点和，每艘宇宙飞船同时向两个点发射激光，射中其他飞船即摧毁，需要使得最后能摧毁的宇宙飞船数量尽量多。输出最多被摧毁的飞船数量。。

Analysis

注意到 n 和 m 最大 60，那么完全可以对于左边和右边能被炸掉的小飞机压位存储一下。直接暴力枚举，对于左右一对小飞机，累计于把它们一次性轰掉的点放置位置，这样会形成 n×m 个点，那么最后再 $\Theta(n^2)$ 枚举点即可。
需要注意的坑：有飞船坐标重复情况，压位的时候需要判断某一位为 0 再累计！否则很容易爆出去……

Code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
#define int long long

const int maxn=65;
const int maxx=40005,zero=20001;

inline int read(){
	int ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}

int n,m,INF;
int x[maxn],y[maxn];
int ans=0;

pair<int,int> s[maxx]; // mid 扩展两倍
int nxt[maxx];

{
	 ret=;
	 (x) ret+=x&,x>>=;
	 ret;
}

{
	n=();m=();
	 ( i=;i<n;i++) x[i]=();
	 ( i=;i<m;i++) y[i]=();
	(x,x+n);(y,y+m);
	
	
	 ( i=;i<n;i++){
		 ( j=;j<m;j++){
			 mid=(x[i]+y[j])+zero;
			 ((s[mid].first&(<<i))==)  s[mid].first +=<<i;
			 ((s[mid].second&(<<j))==) s[mid].second+=<<j;
		}
	}
	(nxt,,(nxt));
	INF=nxt[];
	 st=INF,lst=INF;
	 ( i=;i<=;i++)  (s[i+zero].first!=){
		 (st==INF) st=i+zero,lst=i;  nxt[lst+zero]=i+zero,lst=i;
	}
	 ( i=st;i!=INF;i=nxt[i]){
		 ( j=st;j!=INF;j=nxt[j]){
			 num1=s[i].first  | s[j].first;
			 num2=s[i].second | s[j].second;
			
			ans=(ans,()(num1)+()(num2));
		}
	}
	(,ans);
	 ;
}

F - Compute Power

Description

有 n 个任务，每个任务需要计算机 $a_i$ 的功率，并且要启用 $b_i$ 个处理器。你有足够的无限处理器计算机，每台计算机可以执行 1 个或 2 个任务，但是第二个任务的功率不能超过第一个任务。你需要安排一下，使得最后所有计算机的第一个任务平均功率最小。“平均功率”定义为：功率总和除以处理器总和。输出平均功率乘以 1000 向上取整。 $1\leq n\leq 50, 1\leq a_i\leq 10^8, 1\leq b_i\leq 100$ 。

Analysis

这题就是 0/1 分数规划的变形题，同样是选出 m 个物品使得 $\frac {\sum a_i} {\sum b_i}$ 尽量小。不同之处在于需要考虑第二个任务，这个直接排序即可解决：先从小到大排序，可以定义表示前 i 个任务剩余 j 个未处理（这 j 个任务可以被接下来的计算机“认领”为第二个任务，既然为升序）。但是又会出现一个问题：有很多是相同的。第一个任务功率必须严格大于第二个，不能相同。可以改一下这个 DP 定义：表示前 i 个任务，剩余 j 个和不一样的和 k 个和一样的。状态转移很容易得到。注意向上取整（C++ 函数是）……

Code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>

#define int long long
using namespace std;

inline int read(){
	int ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}

const int maxn=55;
const double eps=1e-5,INF=1.0e9;
int n;
double ans=-1.0;
double f[maxn][maxn][maxn];

//f[i][j][k]: 前 i 个任务，剩余 j 个和 a[i] 不一样的和 k 个和 a[i] 一样的

pair<,> tasks[maxn];

{
	 ( i=;i<=n;i++)  ( j=;j<=n;j++)  ( k=;k<=n;k++) f[i][j][k]=INF;
	f[][][]=;
	 ( i=;i<=n;i++)
	 ( j=;j<=i;j++)
	 ( k=;k<=i;k++)  (f[i][j][k]!=INF){
		 delta=()tasks[i].first-now*()tasks[i].second;
		 (tasks[i].first==tasks[i].first || i==){
			f[i][j][k]=(f[i][j][k],f[i][j][k]+delta);
			 (j>=) f[i][j][k]=(f[i][j][k],f[i][j][k]+delta);
			f[i][j][k]=(f[i][j][k],f[i][j][k]);
		}  {
			 (j+k<=n) f[i][j+k][]=(f[i][j+k][],f[i][j][k]+delta);
			 (j+k>= && j+k<=n) f[i][j+k][]=(f[i][j+k][],f[i][j][k]+delta);
			 (j+k<=n) f[i][j+k][]=(f[i][j+k][],f[i][j][k]);
		}
	}
	 f[n][][]<;
}

{
	 aa.first<bb.first;
}

{
	n=();
	 ( i=;i<=n;i++) tasks[i].first=();
	 ( i=;i<=n;i++) tasks[i].second=();
	(tasks,tasks+n,cmp);
	 L=,R=;
	 (L<=R){
		 mid=(L+R)/;
		 ((mid)) R=mid-eps;  ans=mid,L=mid+eps;
	}
	
	(,()(ans*));
	 ;
}

3/19/2019

CodeForces Round #488 Div2 题解

D - Open Communication

Description

Tags

Analysis

Code

E - Careful Maneuvering

Description

Tags

Analysis

Code

F - Compute Power

Description

Tags

Analysis

Code

Post a New Comment