这是我的博客发布的第 100 篇文章!🎉

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