2017-10-28-morning-清北模拟赛
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。
二分是否存在使p为立方数的数
#include <cstdio> #define LL long long
inline void read(LL &x)
{
x=; register char ch=getchar();
for(; ch>''||ch<''; ) ch=getchar();
for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';
}
LL L,R,Mid,tot; int Presist()
{
// freopen("1.txt","r",stdin);
freopen("cubic.in","r",stdin);
freopen("cubic.out","w",stdout);
LL t; read(t);
for(LL p; t--; )
{
read(p);bool flag=;
for(L=,R=1e6+; L<=R; )
{
Mid=L+R>>;
tot=Mid*Mid*Mid;
if(tot==p)
{
flag=;
break;
}
else if(tot<p) L=Mid+;
else if(tot>p) R=Mid-;
}
if(flag) puts("YES");
else puts("NO");
}
return ;
} int Aptal=Presist();
int main(int argc,char**argv){;}
AC
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。
#include <cstdio> #define LL long long
inline void read(LL &x)
{
x=; register char ch=getchar();
for(; ch>''||ch<''; ) ch=getchar();
for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';
}
LL L,R,Mid,l,r,mid,tmp,x,y; inline int check(LL oo)
{
LL ret=;
for(l=,r=1e4+; l<=r; )
{
mid=l+r>>;
x=mid*mid*mid;
if(x==oo) return ;
else if(oo>x) l=mid+,ret=;
else if(oo<x) r=mid-,ret=-;
}
return ret;
} int Presist()
{
// freopen("1.txt","r",stdin);
// freopen("cubicp.in","r",stdin);
// freopen("cubicp.out","w",stdout);
LL t; read(t);
for(LL p; t--; )
{
read(p);bool flag=;
for(L=,R=1e4+; L<=R; )
{
Mid=L+R>>;
y=Mid*Mid*Mid;
tmp=check(y-p);
if(tmp==)
{
flag=;
break;
}
else if(tmp>) R=Mid-;
else if(tmp<) L=Mid+;
}
if(flag) puts("YES");
else puts("NO");
}
return ;
} int Aptal=Presist();
int main(int argc,char**argv){;}
考试的逗比二分
p=x^3-y^3=(x-y)*(x^2+x*y+y^2)，因为p为素数，
所以x-y=1，所以x=y+1,可以枚举y，检验是否存在p
#include <cstdio> #define LL long long
inline void read(LL &x)
{
x=; register char ch=getchar();
for(; ch>''||ch<''; ) ch=getchar();
for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';
} int Presist()
{
// freopen("cubicp.in","r",stdin);
freopen("cubicp.out","w",stdout);
LL t,tmp; read(t);
for(LL p; t--; )
{
read(p);bool flag=;
for(int y=; y<=1e6+; ++y)
{
tmp=3ll*y*y+3ll*y+;
if(tmp==p) { flag=;break; }
else if(tmp>p) break;
}
if(flag) puts("YES");
else puts("NO");
}
return ;
} int Aptal=Presist();
int main(int argc,char**argv){;}
AC
T3 猜数字(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的）。
二分不可行的最早次数，从大到小枚举x，
对于一段区间，如果被>x的数覆盖过，则不可行，
判断比xi大的区间的并集是否完全覆盖当前区间，xi相等时，更新区间的交
可以用并查集，将确定最小值的区间放到一个并查集里，
#include <algorithm>
#include <cstdio> #define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b) inline void read(int &x)
{
x=; register char ch=getchar();
for(; ch>''||ch<''; ) ch=getchar();
for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';
}
const int N();
int n,q;
struct Node {
int l,r,x;
bool operator < (const Node&a)const
{
return x>a.x;
}
}g[N],tmp[N]; int L,R,Mid,ans;
int fa[N],lmin,lmax,rmin,rmax;
int find(int x)
{
return fa[x]==x ?x :fa[x]=find(fa[x]);
}
inline bool check(int t)
{
for(int i=; i<=n+; ++i) fa[i]=i;
for(int i=; i<=t; ++i) tmp[i]=g[i];
std:: sort(tmp+,tmp+t+);
lmin=lmax=tmp[].l, rmin=rmax=tmp[].r;
for(int i=,j,k; i<=t; ++i)
{
if(tmp[i].x<tmp[i-].x)
{
if(find(lmax)>rmin) return ;
j=find(lmin), k=find(rmax+);
for(; j<=rmax; ++j) fa[find(j)]=k;
lmax=lmin=tmp[i].l;
rmax=rmin=tmp[i].r;
}
else
{
lmin=min(lmin,tmp[i].l);
lmax=max(lmax,tmp[i].l);
rmin=min(rmin,tmp[i].r);
rmax=max(rmax,tmp[i].r);
if(lmax>rmin) return ;
}
}
return find(lmax)>rmin;
} int Presist()
{
freopen("number.in","r",stdin);
freopen("number.out","w",stdout); read(n),read(q);
for(int i=; i<=q; ++i)
read(g[i].l),read(g[i].r),read(g[i].x);
for(R=n; L<=R; )
{
Mid=L+R>>;
if(check(Mid))
{
ans=Mid;
R=Mid-;
}
else L=Mid+;
}
printf("%d\n",ans);
return ;
} int Aptal=Presist();
int main(int argc,char**argv){;}
AC
最新文章
- Qt:Drag-Drop操作在QGraphicsView及Model/View框架下的实现
- 问题：Virtual Box如何复制镜像
- [转]搞ACM的你伤不起(转自Roba大神)
- UIApplication sharedApplication详细解释-IOS
- object-c学习笔记
- matlab mat文件读取和调用
- framework 安装出错 1603
- The Kernel Newbie Corner: Kernel Debugging Using proc "Sequence" Files--Part 1
- Windows重新建立图标缓存
- 剑指OFFER之合并有序链表（九度OJ1519）
- JDK和Jython安装
- JS中undefined与null的区别
- c#一个简单的实例告诉你，多继承还可以这么来
- 使用TypeScript开发ReactNative应用的简单示例
- 返回变量的类型VarType函数
- celery概述
- MySQL系列：数据表基本操作（2）
- ubuntu 忽略文件的50unattended升级问题
- 步步为营-63-Asp.net-get与post
- MongoDB 创建索引及其他