Codeforces #488div.2 - 994E - Careful Maneuvering(状态压缩+暴力枚举)

news/2024/5/19 1:44:53 标签: codeforces, 枚举, 状态压缩

唉!!读错题了!(0,0)也可以。话说我是怎么读成要挖去原点的…
首先讲一下状态压缩的方法:每一位代表一架大飞船,那么长度为 60 60 的位串就代表了一组大飞船。
其次我们考虑何时飞船能被击毁:很明显当大飞船和小飞船在同一条直线上时,这两架大飞船就会被击毁。
同时,两排大飞船是对称的,这就能极方便地求出他们确定的直线在y轴上的截距。
由于数据很弱:把每一个在y轴上的点的情况用状态压缩表示出来,再 O(n2) O ( n 2 ) 枚举所有小飞船 (t1,t2) ( t 1 , t 2 ) 的位置,用 t1|t2 t 1 | t 2 就能 O(1) O ( 1 ) 求出大飞船被摧毁的数量。
下面的题解拆了点,使得 ai+bj2 a i + b j 2 一定不会是小数,也可以省去这一步。

#include <cstdio>
#include <bitset>
#include <vector>
#include <map>
using namespace std;
bitset<65> tt1[50000],tt2[50000];
int a[105],b[105];
vector<int> test;
map<int,bool> has;
int main(){
    bitset<65> *t1=tt1+25000,*t2=tt2+25000;
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int j=1;j<=m;j++){
        scanf("%d",&b[j]);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            t1[a[i]+b[j]][i]=1;
            t2[a[i]+b[j]][j]=1;
            if(!has[a[i]+b[j]]){
                has[a[i]+b[j]]=1;
                test.push_back(a[i]+b[j]);
            }
        }
    }
    int ans=0,tmp;
    //printf("%d ",test.size());
    for(int i=test.size()-1;i>=0;i--){
        //if(test[i]==0)continue;
        for(int j=test.size()-1;j>=0;j--){
            //if(test[j]==0)continue;
            tmp=(t1[test[i]]|t1[test[j]]).count()+(t2[test[i]]|t2[test[j]]).count();
            if(ans<tmp)ans=tmp;
        }
    }
    printf("%d",ans);
}

http://www.niftyadmin.cn/n/1247187.html

相关文章

ubuntu系统下安装windows并引导双系统

首先&#xff0c;感谢wenbusy&#xff0c;给了我很大的帮助&#xff0c;以下部分内容来自于该博主。 windows系统安装ubuntu很容易&#xff0c;但在ubuntu下如何安装windows构成双系统并成功引导&#xff1f;本文来详细介绍。 系统环境&#xff1a;ubuntu14.04LTS&#xff0c;安…

BUPT kamiyoru's training #1 codeforces#486div.3

A - Diverse Team 签到题就不多说了。 #include <cstdio> int find[105]; int main(){int n,k,distinc0,a;scanf("%d%d",&n,&k);for(int i1;i<n;i){scanf("%d",&a);if(!find[a]){find[a]i;distinc;}}puts(distinc>k?"YES&…

pyHeatMap:使用Python绘制热图的库

pyHeatMap是一个使用Python生成热图的库&#xff0c;基本代码是我一年多之前写的&#xff0c;最近把它从项目中抠出来做成一个独立的库并开源。(https://github.com/oldj/pyheatmap) 可以直接下载源码安装最新的版本&#xff0c;也可以通过pip或easy_install安装稳定的发布版&a…

BUPT kamiyoru's training #2 codeforces#485div.2

A - Infinity Gauntlet 签到题&#xff0c;就不多扯了。 #include <iostream> #include <string> #include <map> using namespace std; char str[10][10]{"","Power","Time","Space","Soul","Re…

android studio 如何生成自己的sdk

版本:Android stuido 2.2 很多时候我们要将自己开发一个类库打包成jar包以供他调用&#xff0c;这个jar包也叫你自己的SDK或者叫library。android studio生成jar包的方法与eclipse有所不同。在studio中library其实是module的概念。下面就详述过程。 新建一个工程名为MySDK, 然…

简单组合学(3) Polya计数定理(1)

简单组合学(3) Polya计数定理(1) 1 引言 在固定的正六边形顶点上摆放一个黑球、一个红球和四个白球的方法有多少种,读过初中的人一定能够轻而易举地得到答案,读过小学的人也能够枚举所有结果,答案是65306530种. 但是如果不固定呢&#xff1f;学过高中化学的应该有所印象,一共…

安装intel compiler and mkl library

到intel https://software.intel.com/en-us/performance-libraries 填写邮件等信息后 下载免费的安装包 https://registrationcenter.intel.com/en/products/postregistration/?sn33RM-SJ952567&EmailIDhuangwenwenlili%40126.com&Sequence2025512 下载完成后根据…

高等近世代数笔记(1) 置换与群

(Definition)设α∈Sn,且α∏i1tβi(βi∈Sn)是分解为不相交轮换的完全轮换分解:定义sgn(α)(−1)n−t.(Definition)设α∈Sn,且α∏i1tβi(βi∈Sn)是分解为不相交轮换的完全轮换分解:定义sgn(α)(−1)n−t.(Theorem)∀α,β∈Sn,sgn(αβ)sgn(α)sgn(β).(Theorem)∀α,β∈S…