120. 防线

作者:神秘网友 发布时间:2021-01-25 19:04:56

120. 防线

原题链接:120. 防线

达达学习数学竞赛的时候受尽了同仁们的鄙视,终于有一天......受尽屈辱的达达黑化成为了黑暗英雄怪兽达达。

就如同中二漫画的情节一样,怪兽达达打算毁掉这个世界。

数学竞赛界的精英 lqr 打算阻止怪兽达达的阴谋,于是她集合了一支由数学竞赛选手组成的超级行动队。

由于队员们个个都智商超群,很快,行动队便来到了怪兽达达的黑暗城堡的下方。

但是,同样强大的怪兽达达在城堡周围布置了一条“不可越过”的坚固防线。

防线由很多防具组成,这些防具分成了 N 组。

我们可以认为防线是一维的,那么每一组防具都分布在防线的某一段上,并且同一组防具是等距离排列的。

也就是说,我们可以用三个整数 S, E 和 D 来描述一组防具,即这一组防具布置在防线的 S,S + D,S + 2D,…,S + KD(K∈ Z,S + KD≤E,S + (K + 1)D>E)位置上。

黑化的怪兽达达设计的防线极其精良。如果防线的某个位置有偶数个防具,那么这个位置就是毫无破绽的(包括这个位置一个防具也没有的情况,因为 0 也是偶数)。

只有有奇数个防具的位置有破绽,但是整条防线上也最多只有一个位置有奇数个防具。

作为行动队的队长,lqr 要找到防线的破绽以策划下一步的行动。

但是,由于防具的数量太多,她实在是不能看出哪里有破绽。作为 lqr 可以信任的学弟学妹们,你们要帮助她解决这个问题。

输入格式

输入文件的第一行是一个整数 T,表示有 T 组互相独立的测试数据。

每组数据的第一行是一个整数 N。

之后 N 行,每行三个整数 Si,Ei,Di,代表第 i 组防具的三个参数,数据用空格隔开。

输出格式

对于每组测试数据,如果防线没有破绽,即所有的位置都有偶数个防具,输出一行 "There's no weakness."(不包含引号) 。

否则在一行内输出两个空格分隔的整数 P 和 C,表示在位置 P 有 C 个防具。当然 C 应该是一个奇数。

数据范围

防具总数不多于108,

Si≤Ei,

1≤T≤5,

N≤200000,

0≤Si,Ei,Di≤231?1

输入样例:

3
2
1 10 1
2 10 1
2
1 10 1 
1 10 1 
4
1 10 1 
4 4 1 
1 5 1 
6 10 1

输出样例:

1 1
There's no weakness.
4 3

解题思路

前缀和+二分判定

这道题目的数据范围,相信很容易就看出来是二分,那么如何二分呢二分什么呢这个需要分析题目,分析完后,我们大致可以确定,这道题是要二分坐标。

确定了要二分坐标后,我们接着看,二分判定什么,首先呢二分判定,自然是要看这道题目的条件,而这道题目的条件非常的明确,就是要我们找出这个奇数点。

现在我们就是要找这个奇数点,但是这个奇数点最多只有一个,而且左右都是偶数,也就是说如果我们直接二分的话,是无法确定左右边界的。

那我们怎么做呢首先我们可以想到这道题目,一定要用到奇偶性质,不然的话肯定无法做,然后我们可以这么思考,有什么好的方法,可以让mid左边的都是错误的,右边的都是正确的,也就是右边的数都要是偶数,左边的数都要是奇数,那么我们就可以想到前缀和这个很好的算法。

前缀和想到了,那么这个空间范围是不允许我们开231-1的数组的,那么这里就有一个非常巧妙的数学方法,计算x点前面的所有防具。

样例代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=201000;
ll l,r,mid,n;
struct node
{
    ll s,e,d;
} a[N];
int judge(ll x)
{
    ll ans=0;
    for(int i=1;i<=n;i++)
        if(a[i].s<=x) 
            ans+=(min(x,a[i].e)-a[i].s)/a[i].d+1;
    return ans;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for (int i=1;i<=n;i++)
            cin>>a[i].s>>a[i].e>>a[i].d;
        l=0,r=(1ll<<31)-1;//l边界为0
        while(l<r)
        {
            ll mid=l+r>>1;
            if (!(judge(mid) & 1))
                l=mid+1;
            else
                r=mid;
        }
        int ans=judge(r)-judge(r-1);
        if (ans)
            cout<<l<<" "<<ans<<endl;
        else
            puts("There's no weakness.");
    }
}

120. 防线 相关文章

  1. HDU 3660 树形DP

    原题地址 题意 Alice与Bob在一棵树的树根一同出游,两人从Bob开始轮换选择道路一直走到树叶,Alice会尽可能使走过的总长最小,而Bob相反。不过他们都不能让总长落到[l, r]之外 现在给出这棵树和l,r,要求我们判断最终走过的总长落到[l, r]内,如果能,则输

  2. 明天补

    明天补 原题链接:https://codeforces.com/problemset/problem/1426/F 题目大意:给定一个n长的字符串,字符串由‘a‘,‘b,‘c‘,‘?‘组成,其中‘?‘可以任意转化为abc中一个字符,问在所有的情况下,总共有多少‘abc‘子序列(不要求连续)? 思路: htt

  3. 高斯消元解线性方程组

    高斯消元解线性方程组 原题链接:https://www.acwing.com/activity/content/11 敲代码的注意事项: 1.for循环中的”++”和”- -“符号要应情况而选择,否则及容易打错,进而出现一些非常难找到的bug 2.doule和int的类型需要注意,例如输入输出过程,和定义过程 3.r

  4. win10解压安装mysql 报错 MSVCR120.dll文件的问题

    win10解压安装mysql 报错 MSVCR120.dll文件的问题 在安装mysql 5.7 过程中报错,执行这个 mysqld -install出现报错 解决: msvcp、msvcr、vcomp140.dll属于VC++2015版 msvcp、msvcr、vcomp120.dll属于VC++2013版 msvcp、msvcr、vcomp110.dll属于VC++2012版 msv

  5. 如何花“一点点小钱”突破华为云CCE服务的“防线”

    如何花“一点点小钱”突破华为云CCE服务的“防线” 摘要: 有没有方法绕开CCE的限制,自由的调用K8s的API呢?有还便宜,2.4元/集群/天。 申明:所有的一切都是为了使得华为云可以更好,而不是为了diss它。 通过华为云购买多个K8s集群,又想使用原生K8s接口调

  6. 金九银十,大厂面试题100道整理(原题 + 精讲 1.2万字)(一)

    金九银十,大厂面试题100道整理(原题 + 精讲 1.2万字)(一) 戳蓝字 前端优选 关注我们哦 ! 大家喜欢的可以给笔者点个赞,花费了很长时间整理,这些面试题更适合中级前端,和需要进阶的高级前端的小伙伴,查缺补漏,为金九银十保驾护航 . 问题一:Meta标签常用

  7. 如何解决由于找不到msvcp120.dll无法继续执行代码的问题

    解决方法是:首先下载vcredist;然后选择合适的版本安装;接着重新打开一个CMD;最后切换到mysql的目录下即可。 今天安装mysql的时候遇到了一个bug,如下图所示: 这是因为没有安装如下软件导致的,点击如下链接,下载vcredist. 下载 vcredist 地址: https:

  8. 规划题解

    规划题解 原题链接: https://www.luogu.com.cn/problem/P1642 题目 题解 首先看题, 求∑ai∑bi\frac{\sum a_i} { \sum b_i}∑bi?∑ai??的最大值不禁让人联想到0/1分数规划, 然后再看, 这一张图是一棵树, 然后又要选择刚好n - m个节点, 这不就是一个有依

  9. 三角形最小路径和

    三角形最小路径和 题目链接 120. 三角形最小路径和 解题过程 我觉得这道题已经可以当作如何优化动态规划的经典例题了,首先从路径上采用的是从上到下的方式,我是用了我自己能想出来的方法,也就是二维数组去解决的,接下来进行优化,将O(n2)的空间复杂度降低

  10. 虚拟机win10上MySQL安装并遇上MSVCP120.dll丢失

    虚拟机win10上MySQL安装并遇上MSVCP120.dll丢失 Mysql安装 1.准备:mysql-5.7.18-winx64安装包 2.解压、配置环境 3.在mysql-5.7.18-winx64添加my.ini文件,修改文件中的映射 4.在mysql-5.7.18-winx64下添加data文件 5.管理员身份打开cmd 问题1MSVCP120.dll丢失

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2020, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词