文章目录
这是我的博客发布的第 100 篇文章！:tada:
D - Open Communication
Description
有两个玩家，给出分别 n 和 m 个数对，，所有数字都 ，并且一个数对里的数字不相同，不会有重复的数对。现在有一个“共享数字”，这个数字在 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 艘飞船位于 ，另外有 m 艘飞船位于 ，现在需要让你确定两个点 和 ，每艘宇宙飞船同时向两个点发射激光，射中其他飞船即摧毁，需要使得最后能摧毁的宇宙飞船数量尽量多。输出最多被摧毁的飞船数量。。
Tags
贪心 暴力 压位存储
Analysis
注意到 n 和 m 最大 60，那么完全可以对于左边和右边能被炸掉的小飞机压位存储一下。直接暴力枚举，对于左右一对小飞机，累计于把它们一次性轰掉的点放置位置，这样会形成 n×m 个点，那么最后再 枚举点即可。
需要注意的坑：有飞船坐标重复情况，压位的时候需要判断某一位为 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 个任务，每个任务需要计算机 的功率，并且要启用 个处理器。你有足够的无限处理器计算机，每台计算机可以执行 1 个或 2 个任务，但是第二个任务的功率不能超过第一个任务。你需要安排一下，使得最后所有计算机的第一个任务平均功率最小。“平均功率”定义为：功率总和除以处理器总和。输出平均功率乘以 1000 向上取整。。
Tags
DP 二分
Analysis
这题就是 0/1 分数规划的变形题，同样是选出 m 个物品使得 尽量小。不同之处在于需要考虑第二个任务，这个直接排序即可解决： 先从小到大排序，可以定义 F[i][j] 表示前 i 个任务剩余 j 个未处理（这 j 个任务可以被接下来的计算机“认领”为第二个任务，既然 为升序）。
但是又会出现一个问题：有很多 是相同的。第一个任务功率必须严格大于第二个，不能相同。可以改一下这个 DP 定义：F[i][j][k] 表示前 i 个任务，剩余 j 个和 不一样的和 k 个和 一样的。状态转移很容易得到。
注意向上取整（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;
}