CQOI2016

orz hhw posted @ 2016年4月12日 07:21 in 做题记录 with tags 解题报告 bzoj CQOI 做题记录 , 2283 阅读

听说要450+分才能进队。。感觉作为ZJ选手在CQ根本进不了队啊。。2道板子题1道原题1道语文题,要我考最少跪两道。。

T1 不同的最小割

和ZJOI2011最小割几乎一样,不同的最小割个数为$n-1$,分治后求得,时间复杂度$O(n*maxflow)$似乎人人都闭眼打分治最小割,作为拉原题选手好方啊

#include<bits/stdc++.h>
#define CL(a) memset(a,0,sizeof(a))
#define N 855
#define M 333333
using namespace std;bool v[N];
int n,m,o,i,j,x,y,z,u,p,S,T,Q,fl,tot,L,R,a[N],A[N][N],d[N],fir[N],pre[N],nb[N],la[M],va[M],ne[M],cur[N],q[N],V[N*N];
void ins(int x,int y,int z){
    la[++tot]=y;ne[tot]=fir[x];va[tot]=z;fir[x]=tot;
    la[++tot]=x;ne[tot]=fir[y];va[tot]=0;fir[y]=tot;
}
void dfs(int x){v[x]=1;for(int i=fir[x];i;i=ne[i])if(va[i]&&!v[la[i]])dfs(la[i]);}
void fz(int l,int r){
	if(l==r)return;u=S=a[l];T=a[r];CL(nb);CL(d);CL(pre);CL(v);fl=0;
	for(i=2;i<=tot;i+=4)va[i+2]=va[i]=(va[i]+va[i+1]+va[i+2]+va[i+3])/2,va[i+1]=va[i+3]=0;
	memcpy(cur,fir,sizeof(fir));
    for(nb[0]=n;d[S]<n;){
        if(u==T){
            for(p=1e9,i=S;i!=T;i=la[cur[i]])if(va[cur[i]]<p)p=va[cur[u=i]];
            for(fl+=p,i=S;i!=T;i=la[cur[i]])va[cur[i]]-=p,va[cur[i]^1]+=p;
        }
        for(i=cur[u];i;i=ne[i])if(va[i]&&d[la[i]]+1==d[u])break;
        if(i)cur[u]=i,pre[la[i]]=u,u=la[i];else{
            if(0==--nb[d[u]])break;
            for(i=cur[u]=fir[u],p=n;i;i=ne[i])if(d[la[i]]<p&&va[i])p=d[la[i]];
            ++nb[d[u]=p+1];if(u!=S)u=pre[u];
        }
    }dfs(S);L=l,R=r;
    for(i=1;i<=n;i++)if(v[i])for(j=1;j<=n;j++)if(!v[j])A[i][j]=A[j][i]=min(A[i][j],fl);
    for(i=l;i<=r;i++)if(v[a[i]])q[L++]=a[i];else q[R--]=a[i];
    for(i=l;i<=r;i++)a[i]=q[i];fz(l,L-1);fz(R+1,r);
}
int main(){
	for(scanf("%d%d",&n,&m),i=tot=1;i<=n;i++)a[i]=i;
	for(memset(A,63,sizeof A);m--;ins(x,y,z),ins(y,x,z))scanf("%d%d%d",&x,&y,&z);
	fz(1,n);for(i=1;i<=n;i++)for(j=i+1;j<=n;j++)V[++o]=A[i][j];
	sort(V+1,V+o+1);printf("%d",unique(V+1,V+o+1)-V-1);
}

T2 K远点对

考虑先用K-D树求出距离每个点最远的点,最远的点对很好求得,次远的点对选次大的也是对的,但从第三远开始会不对。
但是发现可能不对的答案只会出现在最远的$K$对点中,于是找出最远的$K$对点暴力枚举判断即可。时间复杂度$O(n\sqrt{N}+k^2lgk)$。
考虑一个小优化,距每个点最远的点一定在凸包上,于是可以只把凸包上的点建K-D树,每个点进去查,时间复杂度最坏是$O(nlgn+n*\sqrt{S}+k^2lgk)$,$S$为凸包点数。在int内很难弄出很多的凸包点数(最多为short),所以加了这个小优化在考场上也一定可以A题的。
#include<bits/stdc++.h>
#define N 100010
#define Mx(a,b)(a<b?a=b:a)
#define Mi(a,b)(a>b?a=b:a)
#define inf 2147483647ll*2147483647
using namespace std;typedef long long LL;LL A,E[N];int n,k,i,j,t,e,o,O,rt,q[N];
struct W{int x,y;LL z;}p[N];bool cp(W a,W b){return a.z>b.z;}
struct P{int l,r,d[2],mi[2],mx[2];}T[N];bool cmp(P a,P b){return a.d[O]<b.d[O]||a.d[O]==b.d[O]&&a.d[O^1]<b.d[O^1];}
LL S(int x){return 1ll*x*x;}LL D(int a,int b){return S(T[a].d[0]-T[b].d[0])+S(T[a].d[1]-T[b].d[1]);}
LL md(P k){return S(max(max(T[i].d[0]-k.mi[0],k.mx[0]-T[i].d[0]),0))+S(max(max(T[i].d[1]-k.mi[1],k.mx[1]-T[i].d[1]),0));}
int bt(int l,int r,int o){
    O=o;int k=l+r>>1,i,u;nth_element(T+l+1,T+k+1,T+r+1,cmp);for(i=0;i<2;i++)T[k].mi[i]=T[k].mx[i]=T[k].d[i];
    if(l<k)for(u=T[k].l=bt(l,k-1,o^1),i=0;i<2;i++)Mi(T[k].mi[i],T[u].mi[i]),Mx(T[k].mx[i],T[u].mx[i]);
    if(k<r)for(u=T[k].r=bt(k+1,r,o^1),i=0;i<2;i++)Mi(T[k].mi[i],T[u].mi[i]),Mx(T[k].mx[i],T[u].mx[i]);
    return k;
}
void qu(int k){
	LL d=D(k,i),dl=-inf,dr=-inf;
	if(d>A)A=d,o=k;if(T[k].l)dl=md(T[T[k].l]);if(T[k].r)dr=md(T[T[k].r]);
	if(dl>dr){if(dl>A)qu(T[k].l);if(dr>A)qu(T[k].r);}else{if(dr>A)qu(T[k].r);if(dl>A)qu(T[k].l);}
}
int main(){
	for(scanf("%d%d",&n,&k),i=1;i<=n;i++)scanf("%d%d",&T[i].d[0],&T[i].d[1]);
	for(rt=bt(1,n,0),i=1;i<=n;i++)A=o=0,qu(rt),p[i]=W{i,o,A};
	for(sort(p+1,p+n+1,cp),i=1;i<=min(k*2,n);i++)q[++t]=p[i].x,q[++t]=p[i].y;
	for(sort(q+1,q+t+1),o=unique(q+1,q+t+1)-q-1,i=1;i<=o;i++)for(j=i+1;j<=o;j++)E[++e]=D(q[i],q[j]);
	sort(E+1,E+e+1);printf("%lld",E[e-k+1]);
}

T3 手机号码4

数位DP,$f[i][x][y][A][B][C][D]$表示第$i$位,前一个数是$x$,前第二个数是$y$,是否出现连续三个,是否出现$4$,是否出现$8$,是否比当前数大的方案数。使用记忆化搜索可以无脑转移。

#include<bits/stdc++.h>
#define CL(a) memset(a,0,sizeof a)
typedef long long LL;int i,j,t,q[22];LL V,L,R,f[13][10][10][2][2][2][3];bool v[13][10][10][2][2][2][3];
LL dp(int k,int x,int y,int A,int B,int C,int D){
	if(k==1)return x&&A&&!(B&&C)&&!D;
	if(v[k][x][y][A][B][C][D])return f[k][x][y][A][B][C][D];v[k][x][y][A][B][C][D]=1;
	for(int i=0;i<10;i++)f[k][x][y][A][B][C][D]+=dp(k-1,i,x,A|(i==x&&x==y),B|(i==4),C|(i==8),D?i>=q[13-k]:i>q[13-k]);
	return f[k][x][y][A][B][C][D];
}
LL G(LL x){
	if(x<1e10)x=1e10,V=-1;else V=0;for(t=0;x;x/=10)q[++t]=x%10;CL(f);CL(v);
	for(i=0;i<10;i++)V+=dp(11,i,i^1,0,i==4,i==8,i>q[1]);return V;
}
int main(){scanf("%lld%lld",&L,&R);printf("%lld",G(R)-G(L-1));}

T4 密钥破解

通过泼辣的肉求出r后可以通过扩欧轻易求出$d$,通过快速幂轻易求出$n$,为了水一发经验抄了发泼辣的肉。。为什么别人泼辣的肉都这么短。。拉板选手表示十分羞愧

#include<bits/stdc++.h>
typedef long long LL;int i,t;LL e,c,n,d,y,R,q[8];
LL mul(LL a,LL b,LL p){LL v=0;for(;b;a=(a+a)%p,b>>=1)if(b&1)v=(v+a)%p;return v;}
LL pw(LL a,LL b,LL p){LL v=1;for(a%=p;b;a=mul(a,a,p),b>>=1)if(b&1)v=mul(v,a,p);return v;}
void ex(LL a,LL b,LL&x,LL&y){if(!b){x=1;y=0;return;}ex(b,a%b,y,x);y-=a/b*x;}
LL G(LL a,LL b){if(!a)return 1;if(a<0)return G(-a,b);LL t;for(;b;)t=a%b,a=b,b=t;return a;}
bool ck(LL a,LL n,LL x,LL t){
	LL V=pw(a,x,n),la=V,i;
	for(i=1;i<=t;la=V,i++)if(V=mul(V,V,n),V==1&&la!=1&&la!=n-1)return 1;
	return V!=1;
}
bool mr(LL n){
	if(n<2)return 0;if(n==2)return 1;if(n%2==0)return 0;LL x=n-1,t=0,i;for(;x%2==0;x>>=1)t++;
	for(i=20;i;i--)if(ck(rand()%(n-1)+1,n,x,t))return 0;return 1;
}
LL pr(LL x,LL c){
    LL i=1,k=2,x0=rand()%x,y=x0,d;
    for(;i++;){
        x0=(mul(x0,x0,x)+c)%x;d=G(y-x0,x);
        if(d!=1&&d!=x)return d;if(y==x0)return x;
        if(i==k)y=x0,k+=k;
    }
}
void ff(LL n){
	if(mr(n)){q[++t]=n;return;}
	LL p=n;for(;p>=n;)p=pr(p,rand()%(n-1)+1);
	ff(p);ff(n/p);
}
int main(){
	srand(23333);scanf("%lld%lld%lld",&e,&n,&c);ff(n);
	R=(q[1]-1)*(q[2]-1);ex(e,R,d,y);if(d<0)d+=R;printf("%lld %lld",d,pw(c,d,n));
}

T5 路由表

直接把所有点加到Tire里,由于没有重复,于是可以每次暴力得到询问Tire链上每个点出现的时间,然后单调扫一遍判断就可以了,时间复杂度$O(32n)$。读了半小时题TAT

#include<bits/stdc++.h>
#define N 1111111
using namespace std;typedef unsigned int U;char s[9];int Q,A,B,C,D,L,R,u,o,t,i,id,di,q[33],c[N][26],V[N];U x;
char ch;void G(int&x){for(ch=getchar();ch<'0'||ch>'9';ch=getchar());for(x=0;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';}
int main(){
	for(scanf("%d",&Q);Q--;)
		if(scanf("%s",s),s[0]=='A'){
			G(A);G(B);G(C);G(D);G(L);x=(U)A*16777216+B*65536+C*256+D;
			for(u=0,i=31;i>=32-L;u=c[u][o],i--)if(!c[u][o=x>>i&1])c[u][o]=++id;V[u]=++di;
		}else{
			G(A);G(B);G(C);G(D);G(L);G(R);x=(U)A*16777216+B*65536+C*256+D;
			for(u=t=0,i=31;~i;i--){
				if(V[u=c[u][o=x>>i&1]]&&V[u]<=R){for(;t&&q[t]>V[u];t--);q[++t]=V[u];
				}if(!u)break;
			}printf("%d\n",lower_bound(q+1,q+t+1,L)-q+t+1);
		}
}

T6 仿光滑数

预处理求出每个质数的每个指数是否合法,把它们的最大值都加到堆中,然后把堆中元素取出时分裂。
考虑用堆存放一个四元组$(V,x,y,z)$表示值为$V$,还能用$x$次,当前最大能除以第$y$个质数,最大的质数是$z$。
那么初始时,加入$(p_i^w,w-1,i-1,i)$。取出分裂$(V,x,y,z)$时,枚举$i$,分裂为$(\frac{V}{p[z]}*p[i],x-1,i,z)$。
对数抵消,时间复杂度$O(128k)$。
#include<bits/stdc++.h>
using namespace std;typedef long long LL;LL n,o;int k,i,j,t,p[66];bool f[133];struct P{LL V;int x,y,z;bool operator<(P a)const{return a.V>V;}}w;priority_queue<P>Q;
int main(){
	for(scanf("%lld%d",&n,&k),i=2;i<128;i++){if(!f[i])p[++t]=i;for(j=i;j<128;j+=i)f[j]=1;}
	for(i=1;i<=t;i++)for(o=1,j=0;o*p[i]<=n;Q.push(P{o,j,i-1,i}))o*=p[i],j++;
	for(;k--;)if(w=Q.top(),Q.pop(),w.x-1)for(i=w.y;i;i--)Q.push(P{w.V/p[w.z]*p[i],w.x-1,i,w.z});
	printf("%lld",w.V);
}

 

 

 

 

Avatar_small
JDC Result rajshahi 说:
2022年8月28日 12:21

Bangladesh Education Board DPE has conducted the class 8th grade of Junior School Certificate Exam and Junior Dakhil Certificate Exam on 1st to 15th November 2022 at all centers in division wise under Ministry of Primary and Mass Education (MOPME), and the class 8th grade terminal examination tests are successfully conducted for all eligible JSC/JDC students for the academic year of 2022. JDC Result rajshahi The Bangladesh government Minister of Secondary Education is going to announce the JSC Result 2022 in student wise for division students in education board wise, and the result documents will be submitted to the Prime Minister of the country after then the result with mark sheet will be announced to public to check the individual result.


登录 *


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