上午发挥强差人意.心态不好，编译器一直报错，心里比较慌。
t1 每一个P枚举底数 .可二分
T2 暴力30 打标60
x^3-y^3=(x-y)*(x^2+xy+y^2). x-y==1. !
p不是素数，枚举x-y=d。
T3 二分 或 枚举看是否可行难得
判定：是否有矛盾，贪心 X排 从大到小
对样例 x相同的合并
线段树，交区间没被覆盖，并区间赋值1，最小值。n logn^2
并查集操作f[i]右边空位，n logn 小于等于R
二分
50分枚举某个数
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。
思路：
如果允许的话，你可以打一个10^6的表。
不打表的话，可以预处理1~0^18以内的立方数，也就10^6个。
然后判断 所给的数P是否在这些数中。
我不得不吐槽一下，本来是这样想的，但是lower_bound（）。一直在报错，还有许多地方报错。我就蒙了，心理素质太差。!!!.
#include<iostream> #include<cstdio> #include<algorithm> #include<queue> #include<cstring> #include<vector> #include<cmath> #include<ctime> using namespace std; long long t,p,x; const int N=1e4; long long a[N+2]={1,8,27,64,125,216,343,512,729,1000,1331,1728,2197,2744,3375,4096,4913,5832,6859,8000,9261,10648,12167,13824,15625,17576,19683,21952,24389,27000,29791,32768,35937,39304,42875,46656,50653,54872,59319,64000,68921,74088,79507,85184,91125,97336,103823,110592,117649,125000,132651,140608,148877,157464,166375,175616,185193,195112,205379,216000,226981,238328,250047,262144,274625,287496,300763,314432,328509,343000,357911,373248,389017,405224,421875,438976,456533,474552,493039,512000,531441,551368,571787,592704,614125,636056,658503,681472,704969,729000,753571,778688,804357,830584,857375,884736,912673,941192,970299,1000000,1030301,1061208,1092727,1124864,1157625,1191016,1225043,1259712,1295029,1331000,1367631,1404928,1442897,1481544,1520875,1560896,1601613,1643032,1685159,1728000,1771561,1815848,1860867,1906624,1953125,2000376,2048383,2097152,2146689,2197000,2248091,2299968,2352637,2406104,2460375,2515456,2571353,2628072,2685619,2744000,2803221,2863288,2924207,2985984,3048625,3112136,3176523,3241792,3307949,3375000,3442951,3511808,3581577,3652264,3723875,3796416,3869893,3944312,4019679,4096000,4173281,4251528,4330747,4410944,4492125,4574296,4657463,4741632,4826809,4913000,5000211,5088448,5177717,5268024,5359375,5451776,5545233,5639752,5735339,5832000,5929741,6028568,6128487,6229504,6331625,6434856,6539203,6644672,6751269,6859000,6967871,7077888,7189057,7301384,7414875,7529536,7645373,7762392,7880599,8000000,8120601,8242408,8365427,8489664,8615125,8741816,8869743,8998912,9129329,9261000,9393931,9528128,9663597,9800344,9938375,10077696,10218313,10360232,10503459,10648000,10793861,10941048,11089567,11239424,11390625,11543176,11697083,11852352,12008989,12167000,12326391,12487168,12649337,12812904,12977875,13144256,13312053,13481272,13651919,13824000,13997521,14172488,14348907,14526784,14706125,14886936,15069223,15252992,15438249,15625000,15813251,16003008,16194277,16387064,16581375,16777216,16974593,17173512,17373979,17576000,17779581,17984728,18191447,18399744,18609625,18821096,19034163,19248832,19465109,19683000,19902511,20123648,20346417,20570824,20796875,21024576,21253933,21484952,21717639,21952000,22188041,22425768,22665187,22906304,23149125,23393656,23639903,23887872,24137569,24389000,24642171,24897088,25153757,25412184,25672375,25934336,26198073,26463592,26730899,27000000,27270901,27543608,27818127,28094464,28372625,28652616,28934443,29218112,29503629,29791000,30080231,30371328,30664297,30959144,31255875,31554496,31855013,32157432,32461759,32768000,33076161,33386248,33698267,34012224,34328125,34645976,34965783,35287552,35611289,35937000,36264691,36594368,36926037,37259704,37595375,37933056,38272753,38614472,38958219,39304000,39651821,40001688,40353607,40707584,41063625,41421736,41781923,42144192,42508549,42875000,43243551,43614208,43986977,44361864,44738875,45118016,45499293,45882712,46268279,46656000,47045881,47437928,47832147,48228544,48627125,49027896,49430863,49836032,50243409,50653000,51064811,51478848,51895117,52313624,52734375,53157376,53582633,54010152,54439939,54872000,55306341,55742968,56181887,56623104,57066625,57512456,57960603,58411072,58863869,59319000,59776471,60236288,60698457,61162984,61629875,62099136,62570773,63044792,63521199,64000000,64481201,64964808,65450827,65939264,66430125,66923416,67419143,67917312,68417929,68921000,69426531,69934528,70444997,70957944,71473375,71991296,72511713,73034632,73560059,74088000,74618461,75151448,75686967,76225024,76765625,77308776,77854483,78402752,78953589,79507000,80062991,80621568,81182737,81746504,82312875,82881856,83453453,84027672,84604519,85184000,85766121,86350888,86938307,87528384,88121125,88716536,89314623,89915392,90518849,91125000,91733851,92345408,92959677,93576664,94196375,94818816,95443993,96071912,96702579,97336000,97972181,98611128,99252847,99897344,100544625,101194696,101847563,102503232,103161709,103823000,104487111,105154048,105823817,106496424,107171875,107850176,108531333,109215352,109902239,110592000,111284641,111980168,112678587,113379904,114084125,114791256,115501303,116214272,116930169,117649000,118370771,119095488,119823157,120553784,121287375,122023936,122763473,123505992,124251499,125000000,125751501,126506008,127263527,128024064,128787625,129554216,130323843,131096512,131872229,132651000,133432831,134217728,135005697,135796744,136590875,137388096,138188413,138991832,139798359,140608000,141420761,142236648,143055667,143877824,144703125,145531576,146363183,147197952,148035889,148877000,149721291,150568768,151419437,152273304,153130375,153990656,154854153,155720872,156590819,157464000,158340421,159220088,160103007,160989184,161878625,162771336 ,163667323,164566592,165469149,166375000,167284151,168196608,169112377,170031464,170953875,171879616,172808693,173741112,174676879,175616000,176558481,177504328,178453547,179406144,180362125,181321496,182284263,183250432,184220009,185193000,186169411,187149248,188132517,189119224,190109375,191102976,192100033,193100552,194104539,195112000,196122941,197137368,198155287,199176704,200201625,201230056,202262003,203297472,204336469,205379000,206425071,207474688,208527857,209584584,210644875,211708736,212776173,213847192,214921799,216000000,217081801,218167208,219256227,220348864,221445125,222545016,223648543,224755712,225866529,226981000,228099131,229220928,230346397,231475544,232608375,233744896,234885113,236029032,237176659,238328000,239483061,240641848,241804367,242970624,244140625,245314376,246491883,247673152,248858189,250047000,251239591,252435968,253636137,254840104,256047875,257259456,258474853,259694072,260917119,262144000,263374721,264609288,265847707,267089984,268336125,269586136,270840023,272097792,273359449,274625000,275894451,277167808,278445077,279726264,281011375,282300416,283593393,284890312,286191179,287496000,288804781,290117528,291434247,292754944,294079625,295408296,296740963,298077632,299418309,300763000,302111711,303464448,304821217,306182024,307546875,308915776,310288733,311665752,313046839,314432000,315821241,317214568,318611987,320013504,321419125,322828856,324242703,325660672,327082769,328509000,329939371,331373888,332812557,334255384,335702375,337153536,338608873,340068392,341532099,343000000,344472101,345948408,347428927,348913664,350402625,351895816,353393243,354894912,356400829,357911000,359425431,360944128,362467097,363994344,365525875,367061696,368601813,370146232,371694959,373248000,374805361,376367048,377933067,379503424,381078125,382657176,384240583,385828352,387420489,389017000,390617891,392223168,393832837,395446904,397065375,398688256,400315553,401947272,403583419,405224000,406869021,408518488,410172407,411830784,413493625,415160936,416832723,418508992,420189749,421875000,423564751,425259008,426957777,428661064,430368875,432081216,433798093,435519512,437245479,438976000,440711081,442450728,444194947,445943744,447697125,449455096,451217663,452984832,454756609,456533000,458314011,460099648,461889917,463684824,465484375,467288576,469097433,470910952,472729139,474552000,476379541,478211768,480048687,481890304,483736625,485587656,487443403,489303872,491169069,493039000,494913671,496793088,498677257,500566184,502459875,504358336,506261573,508169592,510082399,512000000,513922401,515849608,517781627,519718464,521660125,523606616,525557943,527514112,529475129,531441000,533411731,535387328,537367797,539353144,541343375,543338496,545338513,547343432,549353259,551368000,553387661,555412248,557441767,559476224,561515625,563559976,565609283,567663552,569722789,571787000,573856191,575930368,578009537,580093704,582182875,584277056,586376253,588480472,590589719,592704000,594823321,596947688,599077107,601211584,603351125,605495736,607645423,609800192,611960049,614125000,616295051,618470208,620650477,622835864,625026375,627222016,629422793,631628712,633839779,636056000,638277381,640503928,642735647,644972544,647214625,649461896,651714363,653972032,656234909,658503000,660776311,663054848,665338617,667627624,669921875,672221376,674526133,676836152,679151439,681472000,683797841,686128968,688465387,690807104,693154125,695506456,697864103,700227072,702595369,704969000,707347971,709732288,712121957,714516984,716917375,719323136,721734273,724150792,726572699,729000000,731432701,733870808,736314327,738763264,741217625,743677416,746142643,748613312,751089429,753571000,756058031,758550528,761048497,763551944,766060875,768575296,771095213,773620632,776151559,778688000,781229961,783777448,786330467,788889024,791453125,794022776,796597983,799178752,801765089,804357000,806954491,809557568,812166237,814780504,817400375,820025856,822656953,825293672,827936019,830584000,833237621,835896888,838561807,841232384,843908625,846590536,849278123,851971392,854670349,857375000,860085351,862801408,865523177,868250664,870983875,873722816,876467493,879217912,881974079,884736000,887503681,890277128,893056347,895841344,898632125,901428696,904231063,907039232,909853209,912673000,915498611,918330048,921167317,924010424,926859375,929714176,932574833,935441352,938313739,941192000,944076141,946966168,949862087,952763904,955671625,958585256,961504803,964430272,967361669,970299000,973242271,976191488,979146657,982107784,985074875,988047936,991026973,994011992,997002999,1000000000,}; struct node{ long long p; int id; bool is; }q[110]; bool cmp(node a,node b) { return a.p<b.p;} bool cmpp(node a,node b) { return a.id<b.id;} inline long long read() { long long x = 0, f = 1; char ch = getchar(); for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1; for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0'; return x * f; } int main() { freopen("cubic.in","r",stdin); freopen("cubic.out","w",stdout); scanf("%lld",&t); for(int i=1;i<=t;i++) scanf("%lld",&q[i].p),q[i].id =i; sort(q+1,q+1+t,cmp); for(int i=1,j=1;i<=t;i++) { for(j;j<=N;j++) { if(a[j]>q[i].p) break; } if(a[j-1]==q[i].p) q[i].is=1; } sort(q+1,q+1+t,cmpp); for(int i=1;i<=t;i++) if(q[i].is) printf("YES "); else printf("NO "); return 0; }
#include<iostream> #include<cstdio> #include<algorithm> #include<queue> #include<cstring> #include<vector> #include<cmath> #include<ctime> using namespace std; const int N=1e6; long long f[N+1],x; int t,wh; int main() { freopen("cubic.in","r",stdin); freopen("cubic.out","w",stdout); for(int i=1;i<=N;i++) f[i]=1LL*i*i*i; scanf("%d",&t); for(int i=1;i<=t;i++) { scanf("%lld",&x); wh=lower_bound(f+1,f+N+1,x)-f; if(f[wh]==x) printf("YES "); else printf("NO "); } return 0; }
立方数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 <iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<map> #include<set> #include<string> using namespace std; int t; long long x; const int N=1e6+2; bool ok=0; int main() { freopen("cubicp.in","r",stdin); freopen("cubicp.out","w",stdout); scanf("%d",&t); for(int i=1;i<=t;i++) { scanf("%lld",&x); ok=0; for(int i=1;i<=N;i++) { if(3LL*i*i-3LL*i+1==x) { ok=1; break; } if(3LL*i*i-3LL*i+1>x) break; } if(ok) printf("YES "); else printf("NO "); } return 0; }
猜数字(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的）。
Hint
建议使用读入优化
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
return x * f;
a#include<iostream> #include<cstdio> #include<algorithm> #include<queue> #include<cstring> #include<vector> #include<cmath> #include<ctime> using namespace std; const int N=1000009; int f[N]; struct node{ int l,r; int x; }q[N],t[N]; int n,T; bool cmp(node a,node b) { return a.x>b.x;} int find(int x) { while(x!=f[x]) x=f[x]=f[f[x]]; return x; } bool check(int k) { for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=k;i++) t[i]=q[i]; sort(t+1,t+1+k,cmp); int lmin,lmax,rmin,rmax; lmin=lmax=t[1].l; rmax=rmin=t[1].r; for(int i=2;i<=k;i++) { if(t[i].x<t[i-1].x) { if(find(lmax)>rmin) return 1; for(int j=find(lmin);j<=rmax;j++) f[find(j)]=find(rmax+1); lmax=lmin=t[i].l; rmax=rmin=t[i].r; }else { lmax=max(lmax,t[i].l); lmin=min(lmin,t[i].l); rmin=min(rmin,t[i].r); rmax=max(rmax,t[i].r); if(lmax>rmin) return 1; } } if(find(lmax)>rmin) return 1; return 0; } int main() { // freopen("number.in","r",stdin); // freopen("number.out","w",stdout); scanf("%d%d",&n,&T); for(int i=1;i<=T;i++) scanf("%d%d%d",&q[i].l ,&q[i].r,&q[i].x); int L,R,mid; L=1,R=T+1; while(L<=R) { mid=(L+R)>>1; if(check(mid)) R=mid-1; else L=mid+1; } for(int i=R-1;i<=L+1;i++) if(check(i)) { printf("%d",i); return 0; } return 0; }