# CodeForces Round #488 Div2 题解

2019 年 3 月 19 日 08:12

## D - Open Communication

### Tags

卡题意

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

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(){
for (int i=1;i<=n;i++){
a[i]=make_pair(x,y);
}
for (int i=1;i<=m;i++){
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

### Tags

贪心 暴力 压位存储

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

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(){
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

### Tags

DP 二分

### Code

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

#define int long long
using namespace std;

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] 一样的

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){
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(){
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;
}