2015-6-9&2015-6-12练习题解题报告
2015-06-09解题报告
T1:
歪解:给出同一平面上n个不同点的坐标,求用这些点能构成的正方形数,n<=2000,坐标绝对值<=100
蒟蒻用了求长方体的方法、、枚举对角线,如果交于一点特判、、理论复杂度n^3,但是由于坐标绝对值较小,还是能过
#include<cstdio> #include<algorithm> #include<iostream> #define N 2222 using namespace std; int n,i,j,top,ans,x[N],y[N]; struct EG{int len,x,y,x1,x2,y1,y2;}eg[N*N]; bool cmp(EG a,EG b){return a.len<b.len||(a.len==b.len&&a.x<b.x)||(a.len==b.len&&a.x==b.x&&a.y<b.y);} int main(){ scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]); for(i=1;i<n;i++) for(j=i+1;j<=n;j++){ eg[++top].len=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]); eg[top].x1=x[i];eg[top].x2=x[j]; eg[top].y1=y[i];eg[top].y2=y[j]; eg[top].x=x[i]+x[j];eg[top].y=y[i]+y[j]; } sort(eg+1,eg+top+1,cmp); for(i=top;i;i--) for(j=i-1;j&&eg[i].len==eg[j].len&&eg[i].x==eg[j].x&&eg[i].y==eg[j].y;j--) if((eg[i].x1-eg[j].x1)*(eg[i].x1-eg[j].x1)+(eg[i].y1-eg[j].y1)*(eg[i].y1-eg[j].y1)==(eg[i].x1-eg[j].x2)*(eg[i].x1-eg[j].x2)+(eg[i].y1-eg[j].y2)*(eg[i].y1-eg[j].y2))ans++; printf("%d",ans); }
正解:枚举对角,判断另外两个点是否存在
T2:输入正整数n和k,求字典序第k小的波浪排列,如果字典序第k小的波浪排列不存在,则输出-1,n<=200,k<=10^100
#include<cstdio> #define N 222 long long n,x,i,j,k,last,now,sum,p,dp[N][N][2],da[N]; bool vis[N],ff; void go(long long x){ printf("%lld ",x);now=(x>last);last=x;vis[x]=1; for(long long i=1;i<x;i++)da[i]--; } int main(){ scanf("%lld%lld",&n,&p); dp[n][0][0]=dp[n][0][1]=1; for(x=n-1;x;x--) for(i=0;i<=n-x;i++){ for(k=0;i+1+k<=n-x;k++){ dp[x][i+1+k][1]+=dp[x+1][i][0]; if(dp[x][i+1+k][1]>p)dp[x][i+1+k][1]=p+1; } for(k=0;k<=i;k++){ dp[x][i-k][0]+=dp[x+1][i][1]; if(dp[x][i-k][0]>p)dp[x][i-k][0]=p+1; } } for(i=1;i<=n;i++)sum+=dp[1][n-i][0]+dp[1][n-i][1]; if(p>sum){puts("-1");return 0;} for(i=1;i<=n;i++)da[i]=n-i; for(i=1;i<=n;i++){ for(j=1;j<=n;j++)if(!vis[j])if(i==1)if(p>dp[i][da[j]][0]+dp[i][da[j]][1])p-=dp[i][da[j]][0]+dp[i][da[j]][1];else break; else if(((j<last)&&now)||(j>last&&(!now))||(i==2))if(p>dp[i][da[j]][j<last])p-=dp[i][da[j]][j<last];else break; go(j); } }
最后几个点好像爆掉了、、难道要高精度?
正解:膜HZH大爷,时间复杂度n^2,代码还超短,达成了20行AK的誓言
#include<cstdio> int n,g[210],i,j,pre,t,s,use[210]; long long k,f[210][210]; int main(){ scanf("%d%lld",&n,&k);f[0][0]=1; for(i=1;i<=n;i++) for(j=i;j>=1;j--){ f[i][j]=f[i-1][i-j]+f[i][j+1]; if(f[i][j]>k)f[i][j]=k+1; } for(i=1;i<=n&&k>f[n][i]+f[n][n-i+1];i++)k-=f[n][i]+f[n][n-i+1]; if(i>n){puts("-1");return 0;}printf("%d ",i); if(f[n][n-i+1]<k)k-=f[n][n-i+1],pre=1;use[i]=1; for(j=n-1;j>=1;j--,pre^=1){ if(pre)for(t=i;k>f[j][j-t+1];t++)k-=f[j][j-t+1]; else for(t=1;k>f[j][t];t++)k-=f[j][t]; i=t;for(s=1;t;s++)t-=!use[s];s--; printf("%d ",s);use[s]=1; } }
#include<cstdio> #include<cstring> #include<iostream> #define N 202 #define rad 10 using namespace std; int n,x,i,j,k,last,now,ml,da[N]; struct data{short v[1444],l;}dp[N][N][2],sum,p,mav; bool vis[N];char s[233333]; void print(data a){for(int i=a.l;i;i--)printf("%d",a.v[i]);} data operator+(data a,data b){ a.l=max(a.l,b.l); for(int i=1;i<=a.l;i++){ a.v[i]=a.v[i]+b.v[i]; if(a.v[i]>=rad){ a.v[i]-=rad; a.v[i+1]++; } } if(a.v[a.l+1]>0)a.l++; return a; } data operator-(data a,data b){ for(int i=1;i<=a.l;i++){ a.v[i]-=b.v[i]; if(a.v[i]<0){ a.v[i]+=rad; a.v[i+1]--; } } while(a.l>1&&!a.v[a.l])a.l--; return a; } bool operator>(data a,data b){ if(a.l>b.l)return 1; if(a.l<b.l)return 0; for(ml=a.l;ml;ml--){ if(a.v[ml]>b.v[ml])return 1; if(a.v[ml]<b.v[ml])return 0; } return 0; } void go(int x){ printf("%d ",x);now=(x>last);last=x;vis[x]=1; for(int i=1;i<x;i++)da[i]--; } int main(){ scanf("%d%s",&n,s); for(i=1;i<=n;i++)for(j=0;j<=n;j++)dp[i][j][0].l=dp[i][j][1].l=1; p.l=strlen(s);for(i=0;i<p.l;i++)p.v[p.l-i]=s[i]-'0'; dp[n][0][0].v[1]=dp[n][0][1].v[1]=sum.l=1; mav=p+dp[n][0][0]; for(x=n-1;x;x--){ for(i=1;i<=n-x;i++){ dp[x][i][1]=dp[x][i-1][1]+dp[x+1][i-1][0]; if(dp[x][i][1]>mav)dp[x][i][1]=mav; } for(i=n-x-1;i>=0;i--){ dp[x][i][0]=dp[x][i+1][0]+dp[x+1][i][1]; if(dp[x][i][0]>mav)dp[x][i][0]=mav; } } for(i=1;i<=n;i++)sum=sum+(dp[1][n-i][0]+dp[1][n-i][1]); if(p>sum){puts("-1");return 0;} for(i=1;i<=n;i++)da[i]=n-i; for(i=1;i<=n;i++){ for(j=1;j<=n;j++)if(!vis[j])if(i==1)if(p>(dp[i][da[j]][0]+dp[i][da[j]][1]))p=p-(dp[i][da[j]][0]+dp[i][da[j]][1]);else break; else if(((j<last)&&now)||(j>last&&(!now))||(i==2))if(p>dp[i][da[j]][j<last])p=p-dp[i][da[j]][j<last];else break; go(j); } }
#include<cstdio> #include<iostream> #define M 1111111 int n,T,i,p,tot,root,ans,now,next[M],val[M],son[M][2],father[M]; int merge(int x,int y){ if(!x||!y)return x+y; if(val[x]<val[y])std::swap(x,y); son[x][1]=merge(son[x][1],y); std::swap(son[x][0],son[x][1]); return x; } int main(){ scanf("%d%d",&n,&T); for(i=1;i<=n;i++){ scanf("%d",&val[++tot]); root=merge(root,tot); while(getchar()!='\n')scanf("%d",&val[next[tot]=++tot]); } T=T-n+1; while(T--){ ans+=val[root];now=next[root]; root=merge(son[root][0],son[root][1]); if(now)root=merge(root,now); } printf("%d",ans); }
正解:话说似乎直接排序就行了、、、
T4:
#include<cstdio> #include<algorithm> using namespace std; int n,m,i,p,q,sum,now,father[2222]; struct EG{int x,y,z;}eg[11111]; bool cmp(EG a,EG b){return a.z>b.z;} int find(int x){if(father[x]!=x)father[x]=find(father[x]);return father[x];} int main(){ scanf("%d%d",&n,&m); for(i=1;i<=m;i++)scanf("%d%d%d",&eg[i].x,&eg[i].y,&eg[i].z),sum+=eg[i].z; for(i=1;i<=n;i++)father[i]=i; sort(eg+1,eg+m+1,cmp); for(i=1;i<=m;i++){ p=find(eg[i].x);q=find(eg[i].y); if(p!=q){ father[p]=q; sum-=eg[i].z; if(++now==n-1)break; } } printf("%d",sum); }
附录:T19的K值
55786858466342809234785453980306038971889478457617651597514421774251036162639964364960096661231736335046991626196524442613166317193680068609984590647004291324163849026558255909509230681678221355018301652772942753585628964489612784368253896576559263466404376223674811205355506963428130498285741093749819801561178884514009634470839082073977135403110174283996750715605629926658577935322212957449262000443869361508076446568794246921027839365385608324781694642792782329540721473642215887165211773458121141379077709207575092222610059068792751054597863294289497746784288167093817994740623414821451290485939794733303472913097005731802066824475883702215043424456468243815700662787621305028311749077404583454916407455151662513319111955049804878309464653770672710739245598540965881998010663909442787039134330518459606908040302268050546052025271304196293904318684693037820266326695844542877443983930724398293969821922214982363097186213333762715423883275592658593706191974706261446136139809059215282455922494028573238507633998109234815357365697826366582512806720430559305410439602926105265679302646958990664865630790549536804284568886314958653955196829091011332953915854295116346036928040504917481675533903546309916326209634426285439453495130636586430993479668295897162301700214258719413155979809598373217616880004653201988024414459940801424423061387363304366068966735318474237057315607660981688005949573913085787362305022010210502831059784813174453307473910380388661997534563235214265205813120597061561068976935838549459278034002935864346358799943890766225271797244142758419438087191732004418542259179690392622400069463785759436867336642082102316437756410140022390268781136716786580409005277044181685458875443753897801669078184511369296263164951222864783175538324742329970712553727636797819834043445160448967434886342205819719361711870490038755333975396555409156877209772296033705478229193185182302773935733377872399182714324657868421671448313944700289731994539714502837559081775597438684247400302856720150942568590349750581510221925518274006404927527427686291798648129113420096927432292418501534637302416483439020094426842239717450724605055800099686100990211861132795675134741299866803799251371970811375079961532298218897785905444428423316472059039283598692126093986213570614913865229274347019372463113122523777036126238997398810607811458310005748739224314657976936259717729769471838726897838696283036566527013337938686623456870683008980016750181870599590951399224470285017121137064063450306241696128353595292307954399750174977629121794559969986328369490670527176713485524262081521921933033433938338068069189912862941776295620686707506351282718797759563000938828496050293375190456242755429252150709465761436406028363783560407307168717927555878972777655774980718790054292170048445545665351635105832999667639186733438204799951103815129636217250829101169021018302927749057953116462944654992827943173372231592776075854380952068595291329190488773663917678603654180334151147181052407946396548932363969329793071119012643812349916077589459061548607142747138976780557172991757479410998607477873997432457613114424875036818693884412870936919263640054543403293647557333320508207767737783739288505203961476813315067242709810934135999415651067876741343353809700111612385667728798658073358902002545641960891045594471997408860429161750664992227889534659405447466108168976283997846525004364818000233215897054961086131762115144759275870230584823399823350481142825862371859519207819221018411334430433054085810966802072878016051421603575301633849426752381106206927689524766534772121444350388765993097727352870178668088469987850892256249625073555055286796992998869490466928234127870928150154834523889853650439315689810216375466126481235294690174561951791034041203244879655896439134453051967288739110896101383216381609871145078870877887252405973926084780357272932355962211309571007945607859646061137841183064961086694137161110208529369744558118570952525139873175448171896379707431109521971681298702874793635356591168108604971714061558349532960325811124345231204052946714799011131528633200687345695061474887550903565084772279662257207930498297907217459133131556087433212887047576018013151406583411885537578912875363522319423225528458927496255936774944133061525167252698120377633004290493694693517757899241174271039865304426456562380537394498901095932272134765175878646419961065135980669762494829903532083615117546893539890685246850717157537666534596294546506925589024122257464460991932301589999523031884913292713489664040922367893346695776805399220836937515977571077449727213955831227594746899744638158276950930499550632724390493482536182674216558147985969875200932779514524701698845541215687225429301291587901378203196768849311264609012745248736919449272779273844549927342430123482293195705272164815261233349525428183772541121943785983800754689102542103507871054200211628302293398418720448078292059971379728480869094369891676735756076138873552408421077948530190866107359467194195530060250040510455597441527985336863088139694370731162862477669323173521757168218698506559222234199882423194285106146664578397794586156451169635638354168733968384307598594301798722305209044223424592961481095313347249847593548931374442165201830247271177721267787609667885584193725131844409498042006895816890884054738605734964745610480566997630503551307329956804099027392492665353336444116638774451774095798397395166659425239172205870324859437600493261700613657951954215686659579511011323586525494645884178125286114169167208934139114567093185612712922918963615494896110309914010565319693228532225891122302327713215571934853864521867830472608316326901768540482405179787219938281692973772381432591987452358773775409578350764151093982334154782708827779124644529993011384079978096437531063262268172103682283532800102553166209372087191977317562099796868463994380447746694139637404215227509180580681971969191035227523812464195053583698369774324885111859934260666961844090762823389102094556907100091178337803526052843864197510743602467590775530548288026915838886246607984851586002060116433433708509160319336646990961104879040670428146617053866513480292052464218522538789879475578423319798933716270407046015444298938073849857418842234030565954082736195812174643609207428936441556093162772258537130351842391710357572934480913143371841978678190110379111585913780806853593269251347786394661613001353808345598733541148154434422213202579735408550503342557987674986253628437716835042166532749611042455153317700004789251097103174252436759909179053558208019289761647929506720895459831203772118251929014960907919510454580677644697474010631033633965970834805298998332099326226075995642168703853691896409615421508224340876049956230684388873057286196823301903829374190932534560212900618497521343380205397763778993770098308315623675175395781867658620148836499240066077427538977429447253578464902308181750505324290302357977680191354689031335866537937801434723266221734804427310571295501851908339726574429937971598749454921902718288073440992168276917730293826778064150953491530566848950466902922764697589202176149814576511377731352374242141102198802468314277862511472181173313025373866273471926519566134887050196884279773346830038964641037891606192171660009566718602335481595954627968179484476526856720830122321540794560168211782181907706000297118572640853966420734819888103081587179053241958846044657922238675716154373709830380481667546930714330608502464958321029294354318744383590634886768616864605075334044273207343304262325301671311659190413446562077039670833098911652810975086308192339530339994298932988396532115586972165842255928502686396615612298306026868825980873408749082690351085080726019168558562142586374736017550652942134265906957461842185976952436168587730856231174245255204306008543974248220631657452751255882826748628376533664079838465674103230044805865182519802756171533333863387705396360174731681866452676181209894251161132517849833304410735928425334271060410664181264877593218551794511873117545120793259559590690785819104838510800500509340334291645173445879431205611380530125563931826928868862288842252926466592892483375633831290262512105047813270516842290122585492761098385017799435869236149469175948008686268274702005857214242051762916719834409572142306244132456790966136286264270131992637287574459773808179301769717783323839438601572853060810986544355847453428026016475512523622549375225147536278942137022596891192898794579404513552864328374145374531358483258342372278096408219759252211394374540437099649517506175763781132742592994411081933357558411817709520548586690218848668572766189959038950260492452055182193365324435473012180241830666488936683254739717541600799459000034320786469888526236311258064136713692179954165924786100498643741180579558769475563306434982127707856643221655487491276342056130064006625955978479502901103815505031837963560943464802612509589209045851041586481311643008650211151773071640177549800186189239580079229666232016814027918859841669396390725173422805611346688469274068107977528124568279812852306654636376740490461597754251254941754572773645560619827508610957128962086288731968626775323124414803211752163383515099408756443594562752282518697437457403353357820285535795102722495477074692418712227669456370884667319641419708358147315547372730
2015-06-12解题报告
T1:
数据范围:n<=50000,0<k<=10
题解:首先n^2k DP比较好想
#include<cstdio> #include<cstring> #include<algorithm> #define N 55555 #define MOD 100007 using namespace std; int n,m,i,j,k,ans,sum,c[N][2],dp[N][12][2]; struct EG{int x,y;}eg[N]; bool cmp(EG a,EG b){return a.x<b.x;} bool cmp2(EG a,EG b){return a.y<b.y;} int lowbit(int x){return x&(-x);} void insert(int lx,int x,int key){for(;x<=n;x+=lowbit(x))c[x][lx]=(c[x][lx]+key)%MOD;} int query(int lx,int x){ sum=0;for(;x;x-=lowbit(x))sum=(sum+c[x][lx])%MOD; return sum; } int main(){ scanf("%d%d",&n,&m); for(i=1;i<=n;i++)scanf("%d%d",&eg[i].x,&eg[i].y); sort(eg+1,eg+n+1,cmp); for(i=1;i<=n;i++)eg[i].x=i; sort(eg+1,eg+n+1,cmp2); for(i=1;i<=n;i++)eg[i].y=i; sort(eg+1,eg+n+1,cmp); for(i=1;i<=n;i++)dp[i][0][0]=dp[i][0][1]=1; for(k=1;k<=m;k++){ memset(c,0,sizeof(c)); for(i=1;i<=n;i++){ dp[i][k][0]=(query(0,n)-query(0,eg[i].y)+MOD)%MOD; dp[i][k][1]=query(1,eg[i].y); insert(0,eg[i].y,dp[i][k][0]+dp[i][k-1][1]); insert(1,eg[i].y,dp[i][k][1]+dp[i][k-1][0]); } } for(i=1;i<=n;i++)ans=(ans+dp[i][m][0]+dp[i][m][1])%MOD; printf("%d\n",ans); }
T2
首先比较好想到从高到低排序后按位处理
从高到低,对于每一位把0的归为一类,把1的归为一类,00的放到一起和11的放到一起都能得到较小的解,而把01放到一起会得到一个大的解
但如果直接搜索会发现很难实现,当把01放到一起后下一步无法处理
于是考虑用一个堆,用now表示处理到第i位,l1和r1表示一个区间,l2和r2表示另一个区间,val表示处理到的代价,这样就可以处理01放到一起的情况了
一开始now=30,l1=l2=1,r1=r2=n,val=0,每次拿出val最小的,如果val相同拿出now最小的,可以保证先出的解是更优的解
然后拿出后处理l1到r1和l2到r2区间第now位数的情况,如果第now位数都是0或1,就不用加代价,否则加(1<<now)代价
当now为-1时,如果L1=L2且R1=R2,表示这段区间都是同一个数,可以取(R1-L1+1)*(R1-L1)>>1次
否则表示这段区间不是同一个数,可以取(R1-L1+1)*(R2-L2+1)次,如果取到k次就退出
#include<cstdio> #include<algorithm> #define M 5555555 using namespace std; int n,k,tmp,top,i,j,tail,root,x,p,L1,L2,R1,R2,u1,u2,va,t,nv,a[M],val[M],now[M],son[M][2],l1[M],l2[M],r1[M],r2[M],stv[M],stn[M]; int merge(int x,int y){ if(!x||!y)return x+y; if(val[x]>val[y])t=x,x=y,y=t; son[x][1]=merge(son[x][1],y); t=son[x][0];son[x][0]=son[x][1];son[x][1]=t; return x; } void insert(int tmp,int L1,int R1,int L2,int R2,int va){ if(R1<L1||R2<L2)return; now[++tail]=tmp;val[tail]=va; l1[tail]=L1;r1[tail]=R1;l2[tail]=L2;r2[tail]=R2; root=merge(root,tail); } int main(){ scanf("%d%d",&n,&k); for(i=1;i<=n;i++)scanf("%d",&a[i]); sort(a+1,a+n+1); insert(30,1,n,1,n,0); while(k){ x=root;tmp=now[x];va=val[x]; root=merge(son[root][0],son[root][1]); L1=l1[x];L2=l2[x];R1=r1[x];R2=r2[x]; if(tmp==-1){ if(L1==L2&&R1==R2)p=(R1-L1+1)*(R1-L1)>>1; else p=(R1-L1+1)*(R2-L2+1); if(k>p)k-=p,stv[++top]=va,stn[top]=p; else stv[++top]=va,stn[top]=k,k=0; }else{ nv=1<<tmp; u1=R1+1;for(i=L1;i<=R1;i++)if(a[i]&nv){u1=i;break;} u2=R2+1;for(i=L2;i<=R2;i++)if(a[i]&nv){u2=i;break;} insert(tmp-1,L1,u1-1,L2,u2-1,va); insert(tmp-1,u1,R1,u2,R2,va); insert(tmp-1,L1,u1-1,u2,R2,va+(1<<tmp)); if(L1!=L2||R1!=R2)insert(tmp-1,u1,R1,L2,u2-1,va+(1<<tmp)); } } for(i=1;i<=top;i++)for(j=1;j<=stn[i];j++)printf("%d ",stv[i]); }
HZH的解法,似乎是正解,比我的歪解跑得快
#include<cstdio> #include<algorithm> using namespace std; long long tot,x; int pre,ux,uy,f,i,k,l[2],qx[2][100010],qy[2][100010],an[500010],len; int n,K,np,a[100010],cur,sum[3000010],s[2][3000010],ans,KK,lab[3000010]; void dfs(int x,int cur,int v,int t) { if(t<0) { for(int i=1;i<=sum[cur];i++) an[++len]=v; if(!v)len--;return; }if(s[x>>t&1][cur]&&v<ans) dfs(x,s[x>>t&1][cur],v,t-1); if(s[!(x>>t&1)][cur]&&(v|1<<t)<ans) dfs(x,s[!(x>>t&1)][cur],v|1<<t,t-1); } int main() { scanf("%d%d",&n,&K); KK=K;np=1; for(i=1;i<=n;i++) { scanf("%d",&a[i]); for(k=30,cur=1;k>=0;k--) { if(!s[a[i]>>k&1][cur]) s[a[i]>>k&1][cur]=++np,lab[np]=a[i]; cur=s[a[i]>>k&1][cur]; sum[cur]++; } }l[pre=1]=1;qx[pre][1]=1;qy[pre][1]=1; for(k=30;k>=0;k--) { tot=0; for(i=1;i<=l[pre];i++) { ux=qx[pre][i];uy=qy[pre][i]; x=1ll*sum[s[0][ux]]*sum[s[0][uy]]+1ll*sum[s[1][ux]]*sum[s[1][uy]]; if(ux==uy)x=(x-sum[s[0][ux]]-sum[s[1][uy]])/2;tot+=x; }if(tot>=K)f=0;else K-=tot,ans|=1<<k,f=1; l[pre^1]=0; for(i=1;i<=l[pre];i++) { ux=qx[pre][i];uy=qy[pre][i]; if(sum[s[0][ux]]&&sum[s[f][uy]]) { qx[pre^1][++l[pre^1]]=s[0][ux]; qy[pre^1][l[pre^1]]=s[f][uy]; } if(sum[s[1][ux]]&&sum[s[!f][uy]]&&(ux!=uy||(!f))) { qx[pre^1][++l[pre^1]]=s[1][ux]; qy[pre^1][l[pre^1]]=s[!f][uy]; } }pre^=1; }for(i=1;i<=n;i++) dfs(a[i],1,0,30); sort(an+1,an+len+1); for(i=1;i<=len;i+=2) printf("%d ",an[i]); for(i=(len>>1)+1;i<=KK;i++) printf("%d%c",ans,i==KK?'\n':' '); }
2题都是1A,爽
T3:
第1-4个点:n<=8直接手算
第5-8个点:所有点都在两条线上,非常好处理
第9-10个点:n=100,乱弄弄,争取搞几分
2015年6月10日 15:46
膜李泊神