期望得分：100+100+50=250

实际得分：100+60+50=210

T2 二分 估错上界、估错复杂度

T1 立方数(cubic)

Time Limit:1000ms   Memory Limit:128MB

题目描述

LYK定义了一个数叫“立方数”，若一个数可以被写作是一个正整数的3次方，则这个数就是立方数，例如1,8,27就是最小的3个立方数。

现在给定一个数P，LYK想要知道这个数是不是立方数。

当然你有可能随机输出一些莫名其妙的东西来骗分，因此LYK有T次询问~

输入格式(cubic.in)

第一行一个数T，表示有T组数据。

接下来T行，每行一个数P。

输出格式(cubic.out)

输出T行，对于每个数如果是立方数，输出“YES”，否则输出“NO”。

输入样例

3

8

27

28

输出样例

YES

YES

NO

数据范围

对于30%的数据p<=100。

对于60%的数据p<=10^6。

对于100%的数据p<=10^18，T<=100。

预处理所有立方数，hash

//#include<set>

#include<cstdio>

#include<iostream>

using namespace std;

typedef long long LL;

//#define mod1 9000011

#define mod 3000017

//set<LL>s;

LL has[mod+];

int bit[];

void read(LL &x)

{

    x=; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

}

void insert(LL x)

{

    LL t=x; int len=,now=;

    while(t)

    {

        now+=t%*bit[len++];

        while(now>=mod) now-=mod;

        t/=;

    }

    while(has[now])

    {

        now++;

        if(now==mod) now=;

    }

    has[now]=x;

}

bool find(LL x)

{

    LL t=x; int len=,now=;

    while(t)

    {

        now+=t%*bit[len++];

        while(now>=mod) now-=mod;

        t/=;

    }

    while(has[now])

    {

        if(has[now]==x) return true;

        now++; if(now==mod) now=;

    }

    return false;

}

int main()

{

    freopen("cubic.in","r",stdin);

    freopen("cubic.out","w",stdout);

    bit[]=;

    for(int i=;i<=;i++) bit[i]=*bit[i-]%mod;

    for(int i=;i<=;i++)//    s.insert(1LL*i*i*i);

        insert(1LL*i*i*i);

    int T;

    scanf("%d",&T);

    LL x;

    while(T--)

    {

        read(x);

        //puts(s.find(x)!=s.end() ? "TES" : "NO" );

        puts(find(x) ? "YES" : "NO");

    }

}

T2 立方数2(cubicp)

Time Limit:1000ms   Memory Limit:128MB

题目描述

LYK定义了一个数叫“立方数”，若一个数可以被写作是一个正整数的3次方，则这个数就是立方数，例如1,8,27就是最小的3个立方数。

LYK还定义了一个数叫“立方差数”，若一个数可以被写作是两个立方数的差，则这个数就是“立方差数”，例如7(8-1),26(27-1),19(27-8)都是立方差数。

现在给定一个数P，LYK想要知道这个数是不是立方差数。

当然你有可能随机输出一些莫名其妙的东西，因此LYK有T次询问~

这个问题可能太难了…… 因此LYK规定P是个质数！

输入格式(cubicp.in)

第一行一个数T，表示有T组数据。

接下来T行，每行一个数P。

输出格式(cubicp.out)

输出T行，对于每个数如果是立方差数，输出“YES”，否则输出“NO”。

输入样例

5

2

3

5

7

11

输出样例

NO

NO

NO

YES

NO

数据范围

对于30%的数据p<=100。

对于60%的数据p<=10^6。

对于100%的数据p<=10^12，T<=100。

p = a^3 - b^3 = (a-b) (a^2 +ab +b^2)

因为p为素数，所以 一定是 (a-b)=1

a=b+1

后面的式子用b+1 替换 a

转化为 3*b^2 + 3*b + 1

枚举 b 即可

#include<cstdio>

using namespace std;

int main()

{

    freopen("cubicp.in","r",stdin);

    freopen("cubicp.out","w",stdout);

    int T;

    scanf("%d",&T);

    long long p,t;

    while(T--)

    {

        scanf("%I64d",&p);

        for(int i=;;++i)

        {

            t= 1LL**i*i + *i +  ;

            if(t==p) { puts("YES"); break; }

            if(t>p) { puts("NO"); break; }

        }

    }

}

猜数字(number)

Time Limit:1000ms   Memory Limit:128MB

题目描述

LYK在玩猜数字游戏。

总共有n个互不相同的正整数，LYK每次猜一段区间的最小值。形如[li,ri]这段区间的数字的最小值一定等于xi。

我们总能构造出一种方案使得LYK满意。直到…… LYK自己猜的就是矛盾的！

例如LYK猜[1,3]的最小值是2，[1,4]的最小值是3，这显然就是矛盾的。

你需要告诉LYK，它第几次猜数字开始就已经矛盾了。

输入格式(number.in)

第一行两个数n和T，表示有n个数字，LYK猜了T次。
接下来T行，每行三个数分别表示li,ri和xi。

输出格式(number.out)

输出一个数表示第几次开始出现矛盾，如果一直没出现矛盾输出T+1。

输入样例

20 4

1 10 7

5 19 7

3 12 8

1 20 1

输出样例

3

数据范围

对于50%的数据n<=8，T<=10。

对于80%的数据n<=1000，T<=1000。

对于100%的数据1<=n,T<=1000000,1<=li<=ri<=n,1<=xi<=n（但并不保证一开始的所有数都是1~n的）。

如果一个小数的区间被一个大数的区间完全覆盖

那么就发生了矛盾

二分答案

将二分范围内的区间 按猜的数 从大到小 排序

并查集维护一个位置之后第一个没有被覆盖的位置，以此判断区间是否被完全覆盖

注意 正整数互不相同

所以若猜的同一个数 有 多个互不相交的区间，也是有矛盾的

判断这个就是 左端点的最大值>右端点的最小值

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

int n;

#define N 1000001

struct node

{

    int l,r,x;

}e[N],g[N];

void read(int &x)

{

    x=; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

}

bool cmp(node p,node q)

{

    return p.x>q.x;

}

int fa[N+];

int find(int i) { return fa[i]==i ? i : fa[i]=find(fa[i]); }

bool check(int k)

{

    for(int i=;i<=k;++i) g[i]=e[i];

    sort(g+,g+k+,cmp);

    int lmin=g[].l,rmin=g[].r,lmax=g[].l,rmax=g[].r;

    for(int i=;i<=n+;++i) fa[i]=i;

    for(int i=;i<=k;++i)

    {

        if(g[i].x<g[i-].x)

        {

            if(find(lmax)>rmin) return false;

            for(int j=find(lmin);j<=rmax;++j) fa[find(j)]=find(rmax+);

            lmin=lmax=g[i].l;

            rmin=rmax=g[i].r;

        }

        else

        {

            lmin=min(lmin,g[i].l);

            lmax=max(lmax,g[i].l);

            rmin=min(rmin,g[i].r);

            rmax=max(rmax,g[i].r);

            if(lmax>rmin) return false;

        }

    }

    if(find(lmax)>rmin) return false;

    return true;

}

int main()

{

    freopen("number.in","r",stdin);

    freopen("number.out","w",stdout);

    int T;

    read(n); read(T);

    for(int i=;i<=T;++i) read(e[i].l),read(e[i].r),read(e[i].x);

    int l=,r=T,mid,ans=T+;

    while(l<=r)

    {

        mid=l+r>>;

        if(!check(mid)) ans=mid,r=mid-;

        else l=mid+;

    }

    cout<<ans;

}
#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

int n;

#define N 1000001

struct node

{

    int l,r,x;

}e[N],g[N];

void read(int &x)

{

    x=; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

}

bool cmp(node p,node q)

{

    return p.x>q.x;

}

int fa[N+];

int find(int i) { return fa[i]==i ? i : fa[i]=find(fa[i]); }

bool check(int k)

{

    for(int i=;i<=k;++i) g[i]=e[i];

    sort(g+,g+k+,cmp);

    int lmin=g[].l,rmin=g[].r,lmax=g[].l,rmax=g[].r;

    for(int i=;i<=n+;++i) fa[i]=i;

    for(int i=;i<=k;++i)

    {

        if(g[i].x<g[i-].x)

        {

            if(find(lmax)>rmin) return false;

            for(int j=find(lmin);j<=rmax;++j) fa[find(j)]=find(rmax+);

            lmin=lmax=g[i].l;

            rmin=rmax=g[i].r;

        }

        else

        {

            lmin=min(lmin,g[i].l);

            lmax=max(lmax,g[i].l);

            rmin=min(rmin,g[i].r);

            rmax=max(rmax,g[i].r);

            if(lmax>rmin) return false;

        }

    }

    if(find(lmax)>rmin) return false;

    return true;

}

int main()

{

    freopen("number.in","r",stdin);

    freopen("number.out","w",stdout);

    int T;

    read(n); read(T);

    for(int i=;i<=T;++i) read(e[i].l),read(e[i].r),read(e[i].x);

    int l=,r=T,mid,ans=T+;

    while(l<=r)

    {

        mid=l+r>>;

        if(!check(mid)) ans=mid,r=mid-;

        else l=mid+;

    }

    cout<<ans;

}

最新文章

  1. Google Authentication 机制原理
  2. chrome调试文章
  3. [Delphi编译错误]F2084 Internal Error: U2107
  4. Top Android App使用的组件 3
  5. 获利能力分析COPA的BAPI：BAPI_COPAACTUALS_POSTCOSTDATA 通过增强返回凭证号
  6. js跨越小结
  7. pragma pack（非常有用的字节对齐用法说明）
  8. javascript总结--2014-04-17
  9. 【LeetCode】116. Populating Next Right Pointers in Each Node
  10. 【zabbix系列】安装与加入host
  11. &lt;HTML&gt;页面与互联网
  12. 03-HTML的body标签（文本标签）学习
  13. Kafka笔记6（数据传递的可靠性）
  14. GC知识记录
  15. JavaWeb练习-网上名片管理系统
  16. mysql处理重复数据
  17. 基于Kubernetes集群部署skyDNS服务
  18. Electron初探
  19. vim使用技巧大全
  20. windows下vi/vim编辑器的基本操作

热门文章

  1. B-tree&amp;B+tree&amp;数据库索引原理
  2. 复利计算测试（C语言）
  3. Alpha阶段敏捷冲刺⑤
  4. 通过cmd命令安装、卸载、启动和停止Windows Service（InstallUtil.exe）
  5. yii框架 excel导出
  6. Linux进程调度策略的发展和演变（转）
  7. PGM学习之一
  8. 自定义样式，使用浏览器阅读epub格式的电子书
  9. P3701 「伪模板」主席树
  10. MT【157】至少一个小于1