首页 > 其他分享 >P8666 [蓝桥杯 2018 省 A] 三体攻击

P8666 [蓝桥杯 2018 省 A] 三体攻击

时间：2024-02-10 13:44:04浏览次数：30  
标签：xytok int 三体 蓝桥 2018 push now LL op

这道题好像数据有问题？有些题解也会WA

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#define For(i, j, n) for (int i = j; i <= n; ++i)
using namespace std;

const int N = 1e6 + 10;
typedef long long LL;
typedef pair<LL, int> PLI;

int A, B, C, m, num, now, opidx[N]; // now记录当前是第几次操作,opidx记录每个点的最后一次操作处于第几次
vector<PLI> ops[N]; // 记录操作序列
LL nhp[N];

int xytok(int x, int y, int z)
{
    return max(0,((x - 1) * B + (y - 1)) * C + z); 
}

void op_push(int k, int h)
{
    //printf("op push : %d, %d\n", k, h);
    if(ops[k].empty())
    {
        ops[k].push_back({(LL)h, now});
        opidx[k] = now;
        return ;
    }
    if(opidx[k] != now)
    {
       ops[k].push_back({(LL)h, now});
    }
    else
    {
        ops[k].back().first += (LL)h;
    }
    opidx[k] = now;
    //nhp[k] += (LL)h;
}

void Operate(int x1,int y1, int z1, int x2, int y2, int z2, int h)
{
    op_push(xytok(x1, y1, z1), h);
    op_push(xytok(x2 + 1, y1, z1), -h);
    op_push(xytok(x1, y1, z2 + 1), -h);
    op_push(xytok(x2 + 1, y1, z2 + 1), h);

    op_push(xytok(x1, y2 + 1, z1), -h);
    op_push(xytok(x2 + 1, y2 + 1, z1), h);
    op_push(xytok(x1, y2 + 1, z2 + 1), h);
    op_push(xytok(x2 + 1, y2 + 1, z2 + 1), -h);
}

void add(LL h[], int x, int y, int z)
{
    h[xytok(x, y, z)] += h[xytok(x - 1, y, z)] + h[xytok(x, y - 1, z)] + h[xytok(x, y, z - 1)] 
                  - h[xytok(x, y - 1, z - 1)] - h[xytok(x - 1, y, z - 1)] - h[xytok(x - 1, y - 1, z)]
                  + h[xytok(x - 1, y - 1, z - 1)];
}

int find(vector<PLI> &v, int x)
{
    int l = 0, r = v.size() - 1;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(v[mid].second <= x) l = mid;
        else r = mid - 1;
    }
    return l;
}

bool check(int x)
{
    for(int i = 1; i <= num; i++)
    {
        int pos = find(ops[i], x);
        nhp[i] = ops[i][pos].first;
    }
    /*for(int i = 1; i <= num; i++)
        printf("%d ", nhp[i]);
    puts("");*/
    for(int i = 1, cnt = 1; i <= A; i++)
        for(int j = 1; j <= B; j++)
            for(int k = 1; k <= C; k++, cnt++)
            {
                add(nhp, i, j, k);
                if(nhp[cnt] < 0ll)
                {
                    //printf("destroyed at (%d, %d, %d, %d)\n", i, j, k, x);
                    return 1;
                }
            }
    return 0;
}

int search()
{
    int l = 1, r = m;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main()
{
    int tmp;
    scanf("%d%d%d%d", &A, &B, &C, &m);
    for (int i = 1; i <= A; i++)
        for (int j = 1; j <= B; j++)
            for (int k = 1; k <= C; k++, num++)
            {
                scanf("%d", &tmp);
                // 把初始化也看成一次操作，就不需要特判了
                Operate(i, j, k, i, j, k, tmp);
            }
    now++;
    int x1, y1, z1, x2, y2, z2, h;
    for (int i = 1; i <= m; i++, now++)
    {
        scanf("%d%d%d%d%d%d%d", &x1, &x2, &y1, &y2, &z1, &z2, &h);
        Operate(x1, y1, z1, x2, y2, z2, -h);
    }
    /*printf("size:\n");
    for(int i = 1; i <= num; i++)
        printf("%d ", ops[i].size());
    puts("");*/
    for(int i = 1; i <= num; i++)
            for(int j = 1; j < ops[i].size(); j++)
                ops[i][j].first += ops[i][j - 1].first;
    /*check(2);
    for(int i = 1; i <= num; i++)
        printf("%lld ", nhp[i]);
    puts("");
    exit(0);*/
    printf("%d\n", search());
    return 0;
}
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#define For(i, j, n) for (int i = j; i <= n; ++i)
using namespace std;

const int N = 1e6 + 10;
typedef long long LL;
typedef pair<LL, int> PLI;

int A, B, C, m, num, now, opidx[N]; // now记录当前是第几次操作,opidx记录每个点的最后一次操作处于第几次
vector<PLI> ops[N]; // 记录操作序列
LL nhp[N];

int xytok(int x, int y, int z)
{
    return max(0,((x - 1) * B + (y - 1)) * C + z); 
}

void op_push(int k, int h)
{
    //printf("op push : %d, %d\n", k, h);
    if(ops[k].empty())
    {
        ops[k].push_back({(LL)h, now});
        opidx[k] = now;
        return ;
    }
    if(opidx[k] != now)
    {
       ops[k].push_back({(LL)h, now});
    }
    else
    {
        ops[k].back().first += (LL)h;
    }
    opidx[k] = now;
    //nhp[k] += (LL)h;
}

void Operate(int x1,int y1, int z1, int x2, int y2, int z2, int h)
{
    op_push(xytok(x1, y1, z1), h);
    op_push(xytok(x2 + 1, y1, z1), -h);
    op_push(xytok(x1, y1, z2 + 1), -h);
    op_push(xytok(x2 + 1, y1, z2 + 1), h);

    op_push(xytok(x1, y2 + 1, z1), -h);
    op_push(xytok(x2 + 1, y2 + 1, z1), h);
    op_push(xytok(x1, y2 + 1, z2 + 1), h);
    op_push(xytok(x2 + 1, y2 + 1, z2 + 1), -h);
}

void add(LL h[], int x, int y, int z)
{
    h[xytok(x, y, z)] += h[xytok(x - 1, y, z)] + h[xytok(x, y - 1, z)] + h[xytok(x, y, z - 1)] 
                  - h[xytok(x, y - 1, z - 1)] - h[xytok(x - 1, y, z - 1)] - h[xytok(x - 1, y - 1, z)]
                  + h[xytok(x - 1, y - 1, z - 1)];
}

int find(vector<PLI> &v, int x)
{
    int l = 0, r = v.size() - 1;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(v[mid].second <= x) l = mid;
        else r = mid - 1;
    }
    return l;
}

bool check(int x)
{
    for(int i = 1; i <= num; i++)
    {
        int pos = find(ops[i], x);
        nhp[i] = ops[i][pos].first;
    }
    /*for(int i = 1; i <= num; i++)
        printf("%d ", nhp[i]);
    puts("");*/
    for(int i = 1, cnt = 1; i <= A; i++)
        for(int j = 1; j <= B; j++)
            for(int k = 1; k <= C; k++, cnt++)
            {
                add(nhp, i, j, k);
                if(nhp[cnt] < 0ll)
                {
                    //printf("destroyed at (%d, %d, %d, %d)\n", i, j, k, x);
                    return 1;
                }
            }
    return 0;
}

int search()
{
    int l = 1, r = m;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main()
{
    int tmp;
    scanf("%d%d%d%d", &A, &B, &C, &m);
    for (int i = 1; i <= A; i++)
        for (int j = 1; j <= B; j++)
            for (int k = 1; k <= C; k++, num++)
            {
                scanf("%d", &tmp);
                // 把初始化也看成一次操作，就不需要特判了
                Operate(i, j, k, i, j, k, tmp);
            }
    now++;
    int x1, y1, z1, x2, y2, z2, h;
    for (int i = 1; i <= m; i++, now++)
    {
        scanf("%d%d%d%d%d%d%d", &x1, &x2, &y1, &y2, &z1, &z2, &h);
        Operate(x1, y1, z1, x2, y2, z2, -h);
    }
    /*printf("size:\n");
    for(int i = 1; i <= num; i++)
        printf("%d ", ops[i].size());
    puts("");*/
    for(int i = 1; i <= num; i++)
            for(int j = 1; j < ops[i].size(); j++)
                ops[i][j].first += ops[i][j - 1].first;
    /*check(2);
    for(int i = 1; i <= num; i++)
        printf("%lld ", nhp[i]);
    puts("");
    exit(0);*/
    printf("%d\n", search());
    return 0;
}

三维差分+二分答案

标签：xytok,int,三体,蓝桥,2018,push,now,LL,op
From： https://www.cnblogs.com/smartljy/p/18012855

相关文章

  • 蓝桥杯考纲
    第十五届蓝桥杯大赛（软件赛）C&C++和Java组竞赛规则及说明.pdf（1）int能到10的9次方longlong能到10的19次方（2）（3）k=10^3Kilo（千）M=10^6Mega（百万）G=10^9Giga（十亿）T=10^12Tera（兆）P=10^15Peta（千兆）E=10^18Exa（百京）B=10^21Bronto（十垓）1TB=1024GB1GB=1024MB1MB=1024KB1KB=1024By......
  • 2.6 蓝桥杯练习5题
    2.6蓝桥杯练习5题1.[P3951NOIP2017提高组]小凯的疑惑/[蓝桥杯2013省]买不到的数目题意：小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的......
  • 2.5 蓝桥杯练习4题
    2.5蓝桥杯练习4题昨天忘记写题解啦，今天补上。1.[P8687蓝桥杯2019省A]糖果题意：糖果店的老板一共有\(M\)种口味的糖果出售。为了方便描述，我们将\(M\)种口味编号\(1\)∼\(M\)。小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果，而是\(K\)颗一包整包......
  • [BUUCTF 2018]Online Tool
    [BUUCTF2018]OnlineTool打开环境后显示如下的代码<?phpif(isset($_SERVER['HTTP_X_FORWARDED_FOR'])){$_SERVER['REMOTE_ADDR']=$_SERVER['HTTP_X_FORWARDED_FOR'];}if(!isset($_GET['host'])){highlight_file(__FILE......
  • 靶场搭建----phpstudy2018安装及注意问题
    安装官网下载:https://www.xp.cn/download.html新人推荐2018版本phpstudy介绍系统服务------开机自启非服务模式------开机不自启搭建好环境,此时服务器与客户端同时存在服务器:phpstudy所在的目录客户端:除phpstudy所在目录外的都是客户端调整phpstud......
  • pycharm 2018.2+ 激活码
    I2A0QUY8VU-eyJsaWNlbnNlSWQiOiJJMkEwUVVZOFZVIiwibGljZW5zZWVOYW1lIjoiVU5JVkVSU0lEQURFIEVTVEFEVUFMIERFIENBTVBJTkFTIiwiYXNzaWduZWVOYW1lIjoiVGFvYmFv77yaSkVU5YWo5a625qG25r+AIOa0u+W3peS9nOWupCAgcmVuIHpodW4gZGlhbiBtaW5n77yBIiwiYXNzaWduZWVFbWFpbCI6IlJvYmJ5X1dlbmln......
  • 2. 4 蓝桥练习5题
    2.4蓝桥练习5题今天写的几个题都挺有意思的，码量不大，主要是思维。藕还得多练QAQ1.[P8669蓝桥杯2018省B]乘积最大题意：给定\(N\)个整数\(A_1,A_2,\cdots,A_N\)。请你从中选出\(K\)个数，使其乘积最大。请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以......
  • 2.3 蓝桥杯练习3题
    2.3蓝桥杯练习3题1.[P9241蓝桥杯2023省B]飞机降落题意：\(N\)架飞机准备降落到某个只有一条跑道的机场。其中第\(i\)架飞机在\(T_{i}\)时刻到达机场上空，到达时它的剩余油料还可以继续盘旋\(D_{i}\)个单位时间，即它最早可以于\(T_{i}\)时刻开始降落，最晩可以于\(T_{i......
  • 2.1 蓝桥杯练习5题
    2.1蓝桥杯练习5题1.[P8623蓝桥杯2015省B]移动距离题意：X星球居民小区的楼房全是一样的，并且按矩阵样式排列。其楼房的编号为$1,2,3,\cdots$。当排满一行时，从下一行相邻的楼往反方向排号。比如：当小区排号宽度为\(6\)时，开始情形如下：12345612111098......
  • 洛谷 P8687 [蓝桥杯 2019 省 A] 糖果
    题意有\(m\)种口味，每次\(k\)颗一袋出售，给你\(n\)包均为\(k\)颗的糖果，求最少买几袋可以吃到所有口味的糖果。思路暴力对\(n\)包糖果做组合。如果找到其中一种包含了所有口味，将所有满足的方案取糖果包数最小即可。时间复杂度\(\mathcal{O(2^n)}\)。正解考虑状......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99