CodeForces Round #488 Div2 题解

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

D - Open Communication

Description

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

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

Tags

卡题意

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;
	if (aa.first==bb.first && aa.first!=bb.second && aa.second!=bb.first && aa.second!=bb.second) return aa.first;
	if (aa.first!=bb.first && aa.first==bb.second && aa.second!=bb.first && aa.second!=bb.second) return aa.first;
	if (aa.first!=bb.first && aa.first!=bb.second && aa.second==bb.first && aa.second!=bb.second) return aa.second;
	if (aa.first!=bb.first && aa.first!=bb.second && aa.second!=bb.first && aa.second==bb.second) return aa.second;
	// cout<<"NO"<<endl;
	return -1;
}

signed main(){
	n=read();m=read();
	for (int i=1;i<=n;i++){
		int x=read(),y=read();
		a[i]=make_pair(x,y);
	}
	for (int i=1;i<=m;i++){
		int x=read(),y=read();
		b[i]=make_pair(x,y);
	}

	bool tmp[15];
	for (int i=1;i<=n;i++){
		int cnt=0;
		memset(tmp,0,sizeof(tmp));
		for (int j=1;j<=m;j++){
			int now=have_same(a[i],b[j]);
			is[now]=true;tmp[now]=true;
		}
		for (int j=1;j<=9;j++) cnt+=tmp[j];
		if (cnt>1){
			cout<<-1<<endl;
			return 0;
		}
	}

	for (int i=1;i<=m;i++){
		int cnt=0;
		memset(tmp,0,sizeof(tmp));
		for (int j=1;j<=n;j++){
			int now=have_same(a[j],b[i]);
			tmp[now]=true;
		}
		for (int j=1;j<=9;j++) cnt+=tmp[j];
		if (cnt>1){
			cout<<-1<<endl;
			return 0;
		}
	}

	int all_cnt=0;
	for (int i=1;i<=9;i++) {all_cnt+=is[i];if (is[i]) ans=i;}
	if (all_cnt>1) cout<<0<<endl; else cout<<ans<<endl;
	return 0;
}

E - Careful Maneuvering

Description

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

Tags

贪心 暴力 压位存储

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];

int pop_count(int x){
	int ret=0;
	while (x) ret+=x&1,x>>=1;
	return ret;
}

signed main(){
	n=read();m=read();
	for (int i=0;i<n;i++) x[i]=read();
	for (int i=0;i<m;i++) y[i]=read();
	sort(x,x+n);sort(y,y+m);
	// for (int i=0;i<n;i++) printf("%lld ",x[i]);printf("\n");
	// for (int i=0;i<m;i++) printf("%lld ",y[i]);printf("\n");
	for (int i=0;i<n;i++){
		for (int j=0;j<m;j++){
			int mid=(x[i]+y[j])+zero;
			if ((s[mid].first&(1LL<<i))==0)  s[mid].first +=1LL<<i;
			if ((s[mid].second&(1LL<<j))==0) s[mid].second+=1LL<<j;
		}
	}
	memset(nxt,63,sizeof(nxt));
	INF=nxt[0];
	int st=INF,lst=INF;
	for (int i=-20000;i<=20000;i++) if (s[i+zero].first!=0){
		if (st==INF) st=i+zero,lst=i; else nxt[lst+zero]=i+zero,lst=i;
	}
	for (int i=st;i!=INF;i=nxt[i]){
		for (int j=st;j!=INF;j=nxt[j]){
			int num1=s[i].first  | s[j].first;
			int num2=s[i].second | s[j].second;
			// ans=max(ans,(int)__builtin_popcountll(num1)+__builtin_popcountll(num2));
			ans=max(ans,(int)pop_count(num1)+(int)pop_count(num2));
		}
	}
	printf("%lld\n",ans);
	return 0;
}

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$。

Tags

DP 二分

Analysis

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

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<int,int> tasks[maxn];

bool check(double now){
	for (int i=0;i<=n;i++) for (int j=0;j<=n;j++) for (int k=0;k<=n;k++) f[i][j][k]=INF;
	f[0][0][0]=0.0;
	for (int i=1;i<=n;i++)
	for (int j=0;j<=i;j++)
	for (int k=0;k<=i;k++) if (f[i-1][j][k]!=INF){
		double delta=(double)tasks[i].first-now*(double)tasks[i].second;
		if (tasks[i-1].first==tasks[i].first || i==1){
			f[i][j][k]=min(f[i][j][k],f[i-1][j][k]+delta);
			if (j-1>=0) f[i][j-1][k]=min(f[i][j-1][k],f[i-1][j][k]+delta);
			f[i][j][k+1]=min(f[i][j][k+1],f[i-1][j][k]);
		} else {
			if (j+k<=n) f[i][j+k][0]=min(f[i][j+k][0],f[i-1][j][k]+delta);
			if (j+k-1>=0 && j+k-1<=n) f[i][j+k-1][0]=min(f[i][j+k-1][0],f[i-1][j][k]+delta);
			if (j+k<=n) f[i][j+k][1]=min(f[i][j+k][1],f[i-1][j][k]);
		}
	}
	return f[n][0][0]<0.0;
}

bool cmp(pair<int,int> aa,pair<int,int> bb){
	return aa.first<bb.first;
}

signed main(){
	n=read();
	for (int i=1;i<=n;i++) tasks[i].first=read();
	for (int i=1;i<=n;i++) tasks[i].second=read();
	sort(tasks+1,tasks+1+n,cmp);
	double L=0.0001,R=1.0e8;
	while (L<=R){
		double mid=(L+R)/2.0;
		if (check(mid)) R=mid-eps; else ans=mid,L=mid+eps;
	}
	// printf("%.16f\n",ans);
	printf("%lld\n",(int)ceil(ans*1000.0));
	return 0;
}