2015-6-9&2015-6-12练习题解题报告

orz hhw posted @ 2015年6月09日 20:34 in 做题记录 with tags 做题记录 , 2265 阅读

 

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

歪解:dp[p][i][j][k]表示在第p位,有i个数比当前数大,j个数比当前数小,上一个数比当前数大(k=1)或比当前数小(k=0)的排列数
dp[n][0][0][0]=dp[n][0][0][1]=1
dp[x][i][j][0]-->dp[x-1][i+1+k][j-k][1](0<=k<=j)
dp[x][i][j][1]-->dp[x-1][i-k][j+1+k][0](0<=k<=i)
其实[j]这一维可以消掉的、、
然后再按顺序处理就可以了,时间复杂对n^3
第一位是dp[1][i][0]+dp[1][i][1]
从第二位开始要注意往后的方向
从第三位开始还要注意前面的方向
#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;
	}
}
正解:、、要再用前缀和维护一下,由于我写了dp递推式,没有看到这个显然的性质
dp[x][i][0]=Σdp[x+1][k][1](0<=k<=i)
dp[x][i][1]=Σdp[x+1][k][0](i<k<=j)
然后复杂度就是n^2了
这样推比较易懂,HZH大爷的解法蒟蒻还是不太理解、、
高精度未压位版本(95分):
#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);
    }
}
第19个点的K值实在太大了,放到word中三页,根本没法存、、
 
T3:
n<=100000,n<=t<=1000000
歪解:将每个摊位最贵的加入到堆中,可以取t-n+1次,每次取时将最大值弹出,并将取得店铺的下一个商品加入到堆中
由于我蒟蒻,已经不会写堆了,于是写了个可并堆,应该比写堆短
#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:

歪解:n<=1000,m<=10000
首先看数据范围,很像最小生成树,n^2是prim算法,mlogm是Kruskal算法,都能过
于是考虑集合F应该是该图最大生成树的补图,对拍一下,证明这是对的
正解:题目要求其实是最后剩下N颗树,没有环,于是只要让着N颗树的值尽可能大,代价就会尽量小
#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比较好想

i表示选到第i个数,k表示折线有k部分,0表示从上边下来,1表示从下面上去
dp[i][0][0]=dp[i][0][1]=1
dp[i][k][0]=Σdp[j][k][0]+dp[j][k-1][1](a[i]<a[j])
dp[i][k][1]=Σdp[j][k][1]+dp[j][k-1][0](a[i]>a[j])
然后每次用树状数组维护一下dp[i][k][0]+dp[i][k-1][1]和dp[i][k][1]+dp[i][k-1][0]的值,就可以在O(n logn k)的复杂度内出解
#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,乱弄弄,争取搞几分

  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter