qbxt 考前集训 Day1

立方数(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。

 思路：依题意模拟，注意精度，注意精度，注意精度！

 转换为long long防止被卡精度的方法：(long long)(something+eps)

 eps为一个非常小的值（1e-6~1e-11）

正解直接1-1e6枚举判断，少了精度问题。

#include<cstdio>
#include<cmath>
using namespace std;
long long t,n;
double res;
long long chk;
const double cube=0.33333333333333333333333333333333333333333333333333333;
const double eps=1e-7;
int main()
{
    freopen("cubic.in","r",stdin);
    freopen("cubic.out","w",stdout);
    scanf("%I64d",&t);
    for(int i=0;i<t;i++)
    {
        scanf("%I64d",&n);
        res=pow(n,cube)+eps;//防止被卡精度
        chk=res;
        if(pow(chk,3)==n)printf("YES
");
        else printf("NO
");
    }
    fclose(stdin);
    fclose(stdout);
    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。

 思路：立方差公式的运用。

 立方差公式：

 egin{equation*}a^3-b^3=(a-b)(a^2+ab+b^2)end{equation*}

因为是素数，所以可以设$a-b=1$，容易得到$a=b+1$，带回原式，得到$(b+1)^2+[(b+1) imes b]+b^2$，化简即可得到$3 imes x^2-3 imes x+1$。

观察这个式子具有单调性，所以可以二分。当然枚举也行。

code

#include <algorithm>
#include <cstdio>
typedef long long LL;
LL cubeps[1000005];
int main() {
  freopen("cubicp.in", "r", stdin);
  freopen("cubicp.out", "w", stdout);
    for (LL i = 1; i <= 1000000; ++i)
    cubeps[i - 1] = 3 * i * i + 3 * i + 1;
  int T;
  LL n;
  scanf("%d", &T);
  while (T--) {
    scanf("%I64d", &n);
    puts(*std::lower_bound(cubeps, cubeps + 1000000, n) == n ? "YES" : "NO");
  }
  return 0;
}

#include<cstdlib>
#include<cstdio>
#include<ctime>
#include<set>
using namespace std;
long long table[]={7,19,37,61,127,271,331,397,547,631,919,1657,1801,1951,2269,2437,2791,3169,3571,4219,4447,5167,5419,6211,7057,7351,8269,9241,10267,11719,12097,13267,13669,16651,19441,19927,22447,23497,24571,25117,26227,27361,33391,35317,42841,45757,47251,49537,50311,55897,59221,60919,65269,70687,73477,74419,75367,81181,82171,87211,88237,89269,92401,96661,102121,103231,104347,110017,112327,114661,115837,126691,129169,131671,135469,140617,144541,145861,151201,155269,163567,169219,170647,176419,180811,189757,200467,202021,213067,231019,234361,241117,246247,251431,260191,263737,267307,276337,279991,283669,285517,292969,296731,298621,310087,329677,333667,337681,347821,351919,360187,368551,372769,374887,377011,383419,387721,398581,407377,423001,436627,452797,459817,476407,478801,493291,522919,527941,553411,574219,584767,590077,592741,595411,603457,608851,611557,619711,627919,650071,658477,666937,689761,692641,698419,707131,733591,742519,760537,769627,772669,784897,791047,812761,825301,837937,847477,863497,879667,886177,895987,909151,915769,925741,929077,932419,939121,952597,972991,976411,986707,990151,997057,1021417,1024921,1035469,1074607,1085407,1110817,1114471,1125469,1155061,1177507,1181269,1215397,1253887,1281187,1285111,1324681,1328671,1372957,1409731,1422097,1426231,1442827,1451161,1480519,1484737,1527247,1570357,1579051,1600891,1605277,1609669,1618471,1653919,1662841,1667311,1703287,1725967,1748797,1757971,1846321,1855747,1888927,1956169,1980469,1995121,2009827,2024587,2034457,2044351,2069191,2079169,2099197,2129419,2139541,2149687,2185387,2200777,2221381,2226547,2262877,2273311,2294251,2310019,2331127,2368297,2389669,2421907,2427301,2448937,2459791,2465227,2541961,2564101,2603077,2619871,2625481,2636719,2653621,2676241,2738941,2773447,2784997,2813977,2843107,2860657,2866519,2907721,2925469,2949217,2967091,3045169,3069397,3148801,3161107,3179611,3216781,3247921,3310651,3329587,3348577,3418669,3425077,3437911,3470101,3483019,3489487,3515419,3580669,3593791,3600361,3653137,3692971,3733021,3813769,3834091,3854467,3984769,4019419,4033321,4075171,4117237,4131307,4194919,4202017,4216231,4266169,4294837,4302019,4352461,4366927,4476187,4483519,4505551,4527637,4571971,4579381,4586797,4609081,4623967,4683751,4759021,4819669,4834891,4850137,4873051,4896019,4972969,5034961,5081707,5089519,5105161,5144371,5247019,5270851,5310691,5358697,5382781,5390821,5447269,5455357,5471551,5495887,5536567,5569219,5618377,5626591,5676001,5684257,5709061,5725627,5733919,5825527,5842261,5859019,5884201,5917861,5993947,6002431,6019417,6036427,6053461,6061987,6138991,6147577,6156169,6259741,6303151,6329269,6337987,6364177,6381667,6504769,6549019,6575641,6664771,6673717,6709561,6727519,6763507,6790561,6799591,6817669,6862969,6881131,6899317,6963157,7045669,7054867,7073281,7091719,7156441,7174987,7184269,7221457,7333597,7399411,7446601,7512919,7541431,7550947,7569997,7608169,7646437,7684801,7732891,7771471,7810147,7819831,7907257,8083567,8142769,8192269,8331667,8391769,8401807,8421901,8462161,8715961,8787697,8818531,8901019,8921701,9004669,9067147,9077581,9119377,9266419,9287521,9308647,9372169,9382777,9404011,9446551,9510541,9521227,9531919,9564031,9585469,9639169,9660691,9779491,9812017,9888121,9931741,9975457,10052191,10118197,10173367,10195477,10206541,10250857,10273051,10295269,10317511,10350919,10406719,10608841,10710631,10756027,10790137,10835701,11007421,11088019,11111101,11203669,11226871,11284981,11331577,11354911,11366587,11389957,11413351,11448487,11613169,11695951,11731519,11767141,11826631,11850469,11886271,11982007,11994001,12066091,12186721,12332269,12417571,12441997,12478681,12490921,12503167,12527677,12625957,12650587,12675241,12761719,12873337,12997927,13010419,13060447,13274137,13349971,13362631,13451419,13464127,13489561,13502287,13578769,13642669,13848157,14003281,14094169,14133211,14172307,14263741,14276827,14368597,14447491,14487019,14619169,14712031,14765227,14805187,14818519,14871907,14952169,14965567,15086419,15140287,15180751,15465511,15533701,15711697,15863101,15876901,15918337,16015231,16042969,16237807,16293691,16307677,16447867,16560451,16631011,16645141,16730047,16744219,16758397,16800967,16829377,16843591,16986061,17143471,17287201,17330437,17359291,17388169,17489431,17590987,17605519,17736577,17897419,17912077,17956087,17970769,18044269,18147421,18206497,18280477,18310111,18428887,18458641,18637669,18667591,18742501,18847627,18877717,18953047,18983221,19013419,19104157,19149607,19210291,19225477,19271071,19316719,19423441,19469269,19576411,19683847,19868707,19945987,20007919,20023417,20054431,20116531,20272201,20334637,20350261,20412817,20459797,20491147,20506831,20522521,20727037,20742811,20837581,20932567,20948419,20996011,21075451,21107269,21123187,21155041,21298681,21378691,21619621,21667969,21716371,21732517,21780991,21910519,21975427,22072969,22089247,22121821,22170727,22203361,22252357,22301407,22366891,22399669,22580377,22646269,22745287,22761811,22778341,22827967,22927381,23060269,23110201,23277031,23410927,23478019,23511601,23578837,23646169,23933401,24035191,24052177,24239419,24358951,24393157,24461641,24478777,24598897,24719311,24771007,24840019,24943717,24961021,24995647,25012969,25134391,25151761,25238701,25256107,25273519,25430497,25447969,25500421,25605487,25675651,25745911,25816267,25886719,26010241,26134057,26240419,26364781,26382571,26471611,26542951,26560801,26614387,26793397,26847217,27063037,27099091,27135169,27171271,27297817,27515437,27569977,27697447,27880057,27934957,27953269,28210267,28247077,28283911,28320769,28394557,28505419,28542421,28635031,28653571,28709227,28764937,28783519,28802107,28969669,29025631,29193841,29325007,29381311,29456467,29494081,29644777,29682511,29701387,29720269,29776951,29909419,30023197,30213307,30384919,30557017,30710401,30768019,30844927,31172857,31192201,31599811,31658257,31775311,31853467,31970881,32068891,32108137,32127769,32147407,32403247,32521669,32541427,32620519,32759161,32937847,32957731,32977621,33156901,33236737,33516919,33577111,33657451,33717769,33778141,33818419,33959581,33999967,34020169,34202257,34445797,34669801,34792291,34812727,34853617,35202151,35243269,35511121,35573077,35676457,35738557,35779987,35800711,35883667,35945947,36008281,36550771,36697519,36760501,36823537,37097317,37266301,37690441,37839457,37988767,38010121,38031481,38288269,38438461,38481427,38524417,38696617,38826019,38912407,38934019,39389257,39606967,39672397,39737881,39803419,40109977,40131919,40219747,40527901,40572019,40616161,40682419,40748731,40881517,41036707,41281171,41370247,41459419,41504041,41682769,41749891,41839471,41906719,41996467,42153757,42311341,42333877,42446647,42536971,42559567,42627391,42695269,42853861,43126417,43194691,43240237,43285807,43445491,43765741,43834519,43903351,44064169,44087167,44225281,44363611,44455951,44479051,44803081,44872669,44942311,44965537,45035251,45058501,45174841,45291331,45431317,45665107,45711937,45782227,45852571,45922969,45946447,46087441,46511719,46535347,46748269,46819351,46843057,47151781,47199367,47533141,47868091,48084037,48204217,48324547,48348631,48420919,48445027,48493261,48662269,48686437,48831571,49098211,49365577,49462981,49511719,49560481,49633669,49878019,49902487,49975927,50073931,50147497,50245669,50565391,50886127,50985019,51108769,51257467,51282271,51331897,51580387,51630157,51804541,51929281,51954247,52029181,52229269,52279351,52304401,52404661,52655731,52680871,52731169,52806661,52932601,52983019,53008237,53159671,53184931,53336617,53640637,53818381,53996419,54047341,54098287,54174751,54455581,54506719,54865357,54942361,54993727,55225171,55302427,55431307,55586161,55948327,56052019,56259691,56337667,56441719,56519821,56780551,56806657,56885011,56937277,57068047,57146581,57408751,57671521,57882169,57961261,58040407,58093201,58172437,58278169,58516417,58595941,58781707,58887991,58967767,59074219,59394151,59527711,59634667,59661421,59768497,59822071,59929291,59956111,60090301,60466831,60952669,61060897,61142131,61521937,61630669,61712281,61739497,61984711,62011987,62093851,62121151,62285077,62367121,62394481,62421847,62503981,62558767,62586169,62695837,62805601,62997919,63080431,63135469,63190531,63273169,63438607,63659527,63853147,63908521,64213507,64324591,64491397,64519219,64686277,64993111,65328667,65384677,65412691,65524807,65580901,65665087,65721241,65777419,65805517,65889847,66171337,66199519,66255901,66396961,66509917,66792727,66991051,67047769,67303297,67473919,67559311,67673251,67958521,67987081,68588227,68789197,68961691,68990461,69076807,69278491,69480469,69596017,69711661,69885307,70117171,70465687,70611157,70727641,70785919,70873381,70931719,70990081,71223769,71282251,71340757,71633647,71692297,71956519,72044701,72250669,72368497,72427447,72840769,73077481,73166347,73255267,73344241,73581769,73670941,73998367,74087791,74177269,74236951,74326519,74625469,74655397,75015001,75045007,75075019,75165091,75225169,75586141,76219921,76280419,76401487,76522651,76643911,76825981,76917097,77373487,77464927,77556421,77770117,77892361,77984107,78014701,78198391,78412969,78566419,78689287,78843007,79305067,79428511,79521157,79644769,79985197,80171191,80419519,80574919,80730469,81042019,81166807,81479197,81510469,81604321,81886201,81917551,82011637,82357081,82388521,82482877,82766269,82797787,83113297,83208067,83366137,83429407,83492701,83714419,83904697,83999917,84126961,84317707,84891241,84923161,85114807,85210711,85242691,85338667,85498747,85723111,85915657,85947769,86108419,86333581,86397967,86494591,86623507,86688001,86946217,87043147,87463801,87625861,88210519,88308151,88960411,89418421,89516719,89549497,89779111,90239221,90436771,90667519,90832519,90931591,91361527,91593451,91726111,91858867,91991719,92058181,92224441,92557411,92991169,93158269,93358987,93392461,93626947,93727531,93828169,93962437,94096801,94197637,94399471,94534147,94702627,95107591,95175169,95411881,95479567,95581141,95818357,95852269,95954041,95987977,96225697,96327667,96463711,96599851,96667957,96770161,97179517,97795171,98241019,98275357,98447137,98515891,98756719,98928919,98997841,99480967,99722971,99792169,99896011,100381321,100450747,100554931,100624417,100693927,100798237,101007019,101181169,101285731,101425231,101529919,101634661,101774401,101844307,102089167,102229219,102264247,102755269,102966067,103001221,103106719,103247467,103882021,104200027,104447701,104943931,104979421,105299101,105726097,106046911,106368211,106439677,106475419,106833169,106940611,107191519,107299141,107335027,107442721,107802091,107838061,107982001,108342271,108378331,108450469,108703141,108847657,109136977,109390447,109499167,109644211,109716769,109753057,109970911,110079919,110152621,110261719,110516491,110625769,110662207,111099931,111172969,111758137,111868027,112051297,112124647,112418287,112528501,112638769,112969897,113190919,113412157,113449051,113559769,113744419,114077167,114225211,114262237,114336307,114521587,114781231,114966871,115227019,115264207,115375807,115524691,116345269,116569567,116719219,116831521,116868967,117056287,117206251,117356311,117393841,117468919,117656719,117919891,118108051,118296361,118447117,118635697,118786669,118937737,119088901,119315827,119353669,119429371,119770327,119884087,120149737,120377671,120415681,120643867,120758041,121291567,121558771,121902751,122247217,122285521,122400469,122553817,122630527,123360469,123899707,123976837,124053991,124131169,124285597,124324219,124710769,125214181,125408071,125485669,125757451,126185131,126418717,126691507,126730501,127159831,127237969,127394317,127433419,127589887,127668157,127707301,128334421,128609269,128963077,129041767,129159847,129317371,129356767,129435577,129474991,130066921,130185469,130739407,130818637,131175469,131930377,131970169,132129397,132527887,133046821,133686901,133767019,133887241,133967419,134208097,134609707,135011917,135455041,135495361,135777769,136222147,136464841,136505311,136626757,136748257,137031967,137072521,137194219,137275381,137437777,137559637,138169747,138414169,138495691,138577237,138740401,139067017,139639519,139721401,140008177,140172181,140746951,141075919,141199381,141281719,141487669,141611311,141776251,141858757,142065127,142312969,142767907,143057791,143347969,143638441,143679961,143970769,144095491,144553267,144636577,145053487,145638169,145679977,145805437,145847269,145930951,146014657,146140261,146224027,147273127,147399271,147778027,147862261,147904387,148030801,148283791,148325977,148452571,148579219,148748167,148874941,149382577,149467267,149636719,149933491,150060769,150103207,150442927,150655447,150697969,151038361,151166107,151421761,151634971,151762969,151891021,152061841,152318251,152361007,152660467,152960221,153260269,153431857,153517687,153732367,153861247,154592587,154894231,154937347,155023597,155196169,155325661,155800927,155973931,156060469,156103747,156233617,156363541,156580201,156840391,157013971,157187647,157361419,157448341,157578769,157796269,158362471,158406067,158493277,158536891,158711407,158886019,159017041,159410431,159497917,159629191,160023337,160330231,160505731,161648821,161780977,161869111,161957269,162221887,162575047,162840169,162884377,162972811,163105507,163194001,163415341,163592521,163725469,164080261,164257801,164346607,164657617,164702071,164746531,164879947,165013417,165146941,165592411,166395769,166842919,167021947,167335477,167514769,167694157,168187969,168412669,168592537,168772501,169358047,169448221,169583527,169764019,169989769,170396497,170532181,170713177,170848987,170939557,170984851,171030151,171166087,171574219,171619597,171801169,172210057,172255519,172391941,172619431,173211607,173530891,173667817,173804797,173987521,174307519,174810967,175085881,175406887,175728187,176049781,176371669,176417677,176693851,176785957,177062419,177385231,177569827,177893101,178077961,178864687,179189137,179467471,179606719,179653147,179931841,179978311,180024787,180769219,180815797,180908971,181095391,181142011,181328551,181421857,181468519,181982197,182122417,182309461,182449807,182543401,182918017,183433741,183527587,183574519,183621457,183856237,184185181,184279219,184891051,185032387,185268067,186070501,186212287,186590647,187253701,187585669,187728031,187822969,188012917,188060419,188155441,188345557,188488207,189249919,189392911,189869941,190490977,190538791,190586611,190682269,190730107,191256721,191592217,191688127,191928007,192504331,192552397,192937141,193081519,193418611,193755997,194190211,194431651,194914981,195108481,195398911,195544207,195641101,196222969,196320031,196611361,196757107,196902907,197000137,197291971,197632717,198120007,198363877,198461467,198705547,199145269,199291951,199732321,199879219,200909017,201007231,201105469,201203731,201252871,201695401,201744601,201892237,202286197,202384747,202434031,202483321,202828519,204212251,204311269,204558919,204856297,205005067,205153891,205600687,205700041,206047969,206197171,206545519,206794519,206993827,207143371,207592327,207991807,208341667,208491697,208641781,209192551,209393011,210045169,210246037,210296269,210798919,211503637,211554019,211906861,212058169,212562919,212714461,212916601,212967151,213068269,213118837,213472981,214131457,214384987,214638667,214740181,214841719,215044867,215095669,215705761,215756641,215960221,216163897,216316717,216418627,216673507,216826507,217183717,217336897,217387969,217694527,218410669,218615497,218922919,219384457,219538411,220257577,220360411,220823461,220977919,221183947,221338531,221854201,222009019,222267169,222939061,222990787,223611967,224182141,224234011,224389657,224804977,225792901,225897019,226001161,226157419,226209517,226261621,226365847,226417969,227148307,227252737,227357191,227618431,228350701,228455407,228612511,228717277,228769669,228979297,229503787,229661251,229871287,230081419,230186521,230239081,230396797,230554567,230922907,230975551,232399207,232504837,233139121,233192017,233774269,234251197,235472221,235578547,235791271,235950877,236483287,237122971,237283027,237656701,237870361,237977227,238030669,238244497,238404931,238940101,239154337,239475871,239743981,239851267,240602941,240817921,241032997,242595169,243243061,243621397,244054141,244378951,244812367,244974997,245137681,245408941,245571769,245734651,246386719,246495481,247094101,247475419,247529917,247693447,248238937,248457301,248785027,248948971,249058297,249222331,249605287,249714757,249824251,250098091,250591381,252679519,252844741,252899827,253230469,253285597,253671661,253782019,253947601,254058019,254721031,255108187,255329551,255384907,256271419,256382341,256548769,256770757,257048377,257548471,257715277,257826511,258327361,258438727,258494419,259386307,259442101,259776991,260671087,261398671,261622747,261846919,261959041,262351657,262576141,262913047,262969219,263306377,263756257,264319147,264375469,264882637,264939019,265277437,265390291,265559617,265898431,266463601,266689837,267085981,267142597,267482419,267879151,268332919,268843867,270151831,270322669,270550537,270721501,270949537,271291771,271520047,271634221,272148301,272662867,272948947,273521557,273636151,273693457,273922741,274094767,274496371,274553767,274725991,275530417,275645431,275933071,276278437,276681637,276912169,277085131,277719787,278124037,278470771,279512269,279917821,280381669,280613737,280787851,281020087,282008161,282240901,282997969,283639357,283814407,284164669,284223067,284573581,284690467,285041269,285275257,285392287,286857187,286915861,287679169,287973019,288267019,288737731,288796597,288914347,289385587,290329219,291215269,291274387,291688381,291806719,292813561,293050717,293347297,293525317,293703391,293762761,294178519,294297361,294475669,294594571,295368019,295546651,295963669,296798587,297097057,297276211,297455419,297634681,297873781,298112977,298292437,298891027,299310397,299910007};
set<long long> s;
long long t,n;
bool preprocessed;
inline void preprocess()
{
    for(int i=0;i<sizeof(table)/sizeof(long long);i++)
        s.insert(table[i]);
    preprocessed=true;
}
inline void test(long long n)
{
    if(preprocessed==false)preprocess();
    if(s.count(n)==1)printf("YES
");
    else printf("NO
");
}
int main()
{
    srand(time(NULL));
    freopen("cubicp.in","r",stdin);
    freopen("cubicp.out","w",stdout);
    for(int i=0;i<1964;i++)
        s.insert(table[i]);
    scanf("%d",&t);
    for(int i=0;i<t;i++)
    {
        scanf("%I64d",&n);
        if(n<=299910007)test(n);
        else printf(rand()%2?"YES
":"NO
");
    }
    fclose(stdin);
    fclose(stdout);
    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;

}

思路：打了个暴力，但是只有20.

正解：二分答案，用并查集维护集合的关系。

正确性证明：

两个猜测的最小值如果相同的话那么这个最小值一定在这两个线段的交上

否则，一定在这两个线段的交集关于全集的补集上

当产生冲突的时候一定是权值小的一次猜测被几条比他权值大的猜测完全覆盖，

那么我们可以二分第几次不满足要求，用并查集维护线段的覆盖。

时间复杂度$O(nlog n imes alpha (n))$.

#include <cstdio>
#include <iostream>
#include <algorithm>
#define N 1000011
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y))
using namespace std;
int n, q, ans;
int f[N];

struct node
{
    int x, y, z;
}p[N], t[N];

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;
}

inline bool cmp(node x, node y)
{
    return x.z > y.z;
}

inline int find(int x)
{
    return x == f[x] ? x : f[x] = find(f[x]);
}

inline bool check(int k)
{
    int i, j, x, y, lmin, lmax, rmin, rmax;
    for(i = 1; i <= n + 1; i++) f[i] = i;
    for(i = 1; i <= k; i++) t[i] = p[i];
    std::sort(t + 1, t + k + 1, cmp);
    lmin = lmax = t[1].x;
    rmin = rmax = t[1].y;
    for(i = 2; i <= k; i++)
    {
        if(t[i].z < t[i - 1].z)
        {
            if(find(lmax) > rmin) return 1;
            for(j = find(lmin); j <= rmax; j++)
                f[find(j)] = find(rmax + 1);
            lmin = lmax = t[i].x;
            rmin = rmax = t[i].y;
        }
        else
        {
            lmin = min(lmin, t[i].x);
            lmax = max(lmax, t[i].x);
            rmin = min(rmin, t[i].y);
            rmax = max(rmax, t[i].y);
            if(lmax > rmin) return 1;
        }
    }
//    cout<<find(1)<<endl;
    if(find(lmax) > rmin) return 1;
    return 0;
}

int main()
{
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    int i, x, y, mid;
    n = read();
    q = read();
    for(i = 1; i <= q; i++)
        p[i].x = read(), p[i].y = read(), p[i].z = read();
    x = 1, y = q;
    //cout<<check(2)<<endl;
    //return 0;
    ans = q + 1;
    while(x <= y)
    {
        mid = (x + y) >> 1;
        if(check(mid)) ans = mid, y = mid - 1;
        else x = mid + 1;
    }
    printf("%d
", ans);
    return 0;
}

水题(water)

Time Limit:1000ms   Memory Limit:128MB

题目描述

LYK出了道水题。

这个水题是这样的：有两副牌，每副牌都有n张。

对于第一副牌的每张牌长和宽分别是xi和yi。对于第二副牌的每张牌长和宽分别是aj和bj。第一副牌的第i张牌能覆盖第二副牌的第j张牌当且仅当xi>=aj并且yi>=bj。（注意牌不能翻转）当然一张牌只能去覆盖最多一张牌，而不能覆盖好多张。

LYK想让两副牌的各n张一一对应叠起来。它想知道第二副牌最多有几张能被第一副牌所覆盖。

输入格式(water.in)

    第一行一个数n。

    接下来n行，每行两个数xi,yi。

    接下来n行，每行两个数aj,bj。

输出格式(water.out)

输出一个数表示答案。

输入样例

3

2 3

5 7

6 8

4 1

2 5

3 4

输出样例

2

数据范围

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

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

对于100%的数据1<=n<=100000，1<=xi,yi,aj,bj<=10^9。

思路：

50pts n! 枚举。

80pts 网络流二分图匹配。

80pts 贪心。

普通贪心？考虑A_1=(x[i],y[i]); B_1(x[i],1), B_2(1,y[i])的情况，此时二者都优。

对x[i]进行排序，每次遇到B类牌，将y值插入进某个数据结构中。遇到A类牌，找这个数据结构中y值尽可能大且不超过这张牌的y值。数组实现，n^2暴力维护。

100pts 考虑这个数据结构的操作。

1. 插入一个数
2. 删除不超过y最大的数

         =>  平衡树、权值线段树+离散化、multiset

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
int n;
multiset <int> s;
struct node {int x,y;} a[100005],b[100005];
int cmp(node i,node j) {return i.x<j.x;}
int main()
{
    freopen("water.in","r",stdin);
    freopen("water.out","w",stdout);
    int T;
    T=1;
    while(T--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++) scanf("%d%d",&a[i].x,&a[i].y);
        for(int i=0;i<n;i++) scanf("%d%d",&b[i].x,&b[i].y);
        sort(a,a+n,cmp);
        sort(b,b+n,cmp);
        s.clear();
        int k=0,ans=0;
        for(int i=0;i<n;i++)
        {
            while(a[i].x>=b[k].x&&k<n)
            {
                 s.insert(b[k].y);
                 k++;
            }
            if(s.empty())continue;
            multiset<int>::iterator it=s.upper_bound(a[i].y);
            if (it==s.begin()) continue; it--;
            ans++; s.erase(it);
        }
        printf("%d
",ans);
    }
    return 0;
}

梦境(dream)

Time Limit:1000ms   Memory Limit:128MB

题目描述

LYK做了一个梦。

这个梦是这样的，LYK是一个财主，有一个仆人在为LYK打工。

不幸的是，又到了月末，到了给仆人发工资的时间。但这个仆人很奇怪，它可能想要至少x块钱，并且当LYK凑不出恰好x块钱时，它不会找零钱给LYK。

LYK知道这个x一定是1~n之间的正整数。当然抠门的LYK只想付给它的仆人恰好x块钱。但LYK只有若干的金币，每个金币都价值一定数量的钱（注意任意两枚金币所代表的钱一定是不同的，且这个钱的个数一定是正整数。LYK想带最少的金币，使得对于任意x，都能恰好拼出这么多钱。并且LYK想知道有多少携带金币的方案总数。

具体可以看样例。

输入格式(dream.in)

    第一行一个数n，如题意所示。

输出格式(dream.out)

输出两个数，第一个数表示LYK至少携带的金币个数，第二数表示方案总数。

输入样例

6

输出样例

3 2

样例解释

LYK需要至少带3枚金币，有两种方案，分别是{1,2,3}，{1,2,4}来恰好得到任意的1~n之间的x。

输入样例2

10

输出样例2

4 8

数据范围

对于30%的数据n<=10。

对于60%的数据n<=100。

对于100%的数据n<=1000。

思路：

DP/搜索

第一问：打表找规律即可

第二问：直接搜索或者DP。

dfs(Max,Sum,S)//Max金币最大值，Sum所有金币的和，S金币的数量。
{
    if(S==X)
    if(Sum>=n)
        ans++;
    return;
    for(int i=Max+1;i<=Sum+1;i++)
        dfs(i,Sum+I,S+1);
}

DP？直接转化dfs。

优化：前缀和优化（$nlog ^3 n$ -> $nlog ^2 n$ ）

剪枝：if(dp[i][j][k])/*do something*/

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
int n,sum,ans,dp[1005][1005],DP[1005][1005],i,j,k,l;
int main()
{
    freopen("dream.in","r",stdin);
    freopen("dream.out","w",stdout);
    scanf("%d",&n);
    sum=int(log(n)/log(2)+0.000000001)+1;
    dp[1][1]=1;
    for (i=1; i<sum; i++)
    {
        for (j=1; j<=n; j++)
          for (k=1; k<=n; k++)
            if (dp[j][k])
              for (l=k+1; l<=j+1; l++)
                DP[min(n,j+l)][l]+=dp[j][k];
        for (j=1; j<=n; j++) for (k=1; k<=n; k++) {dp[j][k]=DP[j][k];DP[j][k]=0;}
    }
    for (j=1; j<=n; j++) ans+=dp[n][j];
    cout<<sum<<' '<<ans;
    return 0;
}

动态规划(dp)

Time Limit:1000ms   Memory Limit:128MB

题目描述

LYK在学习dp，有一天它看到了一道关于dp的题目。

这个题目是这个样子的：一开始有n个数，一段区间的价值为这段区间相同的数的对数。我们想把这n个数切成恰好k段区间。之后这n个数的价值为这k段区间的价值和。我们想让最终这n个数的价值和尽可能少。

例如6个数1,1,2,2,3,3要切成3段，一个好方法是切成[1],[1,2],[2,3,3]，这样只有第三个区间有1的价值。因此这6个数的价值为1。

LYK并不会做，丢给了你。

输入格式(dp.in)

    第一行两个数n,k。

    接下来一行n个数ai表示这n个数。

输出格式(dp.out)

一个数表示答案。

输入样例

10 2

1 2 1 2 1 2 1 2 1 2

输出样例

8

数据范围

对于30%的数据n<=10。

对于60%的数据n<=1000。

对于100%的数据1<=n<=100000,1<=k<=min(n,20),1<=ai<=n。

其中有30%的数据满足ai完全相同均匀分布在所有数据中。

题解：

对于最后30%，尽量切成长度相同的区间。

前30%，$2^n$暴力枚举出现的位置。

∑ 50pts

70pts:

dp[i][j] 1~i 切了i刀的最优解。

dp[i][j]=min{dp[k][j-1]+sum(k+1,i)}

k从大到小枚举，每次枚举时更新这个sum。

时间复杂度：  $20 imes n^2$

100pts:

固定j，随着i的增大，k不会减少。

1D1D动态规划优化。

分治求DP。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=100010;
typedef long long LL;
int c[N],a[N];
LL f[N],g[N];
int p,q,n,k;
LL tot;
void move(int l,int r)  // [p,q]之前的区间
{
    while (l<p) p--,tot+=c[a[p]],c[a[p]]++;
    while (r>q) q++,tot+=c[a[q]],c[a[q]]++;
    while (p<l) c[a[p]]--,tot-=c[a[p]],p++;
    while (r<q) c[a[q]]--,tot-=c[a[q]],q--;
}
void work(int l,int r,int fl,int fr)
//需要求dp[fl] ~ dp[fr]  最优解一定从l~r中的某一个转移过来
{
    if (fl>fr) return;
    int mid=(fl+fr)>>1,mi;
    LL mx=1LL<<60;
    for (int i=l;i<=r;i++)
    if (i<mid)
    {
        move(i+1,mid); -> tot=sum(i+1,mid);
        if (f[i]+tot<mx) mx=f[i]+tot,mi=i;
    }
    g[mid]=mx;
    work(l,mi,fl,mid-1);
    work(mi,r,mid+1,fr);
}
int main()
{
    freopen("dp.in","r",stdin);
    freopen("dp.out","w",stdout);
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    f[0]=0;
    for (int i=1;i<=n;i++) f[i]=1LL<<60;
    while (k--)
    {
        p=1,q=0,tot=0;
        for (int i=1;i<=n;i++) c[i]=0;
        work(0,n-1,1,n);
        for (int i=0;i<=n;i++) f[i]=g[i],g[i]=0;
    }
    cout<<f[n];
    return 0;
}

总结：

上午发挥还行。180

下午随着题目难度提高，爆零了。

不会的重要算法：二分与贪心。

还是要学会打暴力啊，NOIp暴力分还是很多的。