jiry_2's Blog

最近有幸膜到了贵省的题目，感觉非常神奇，就来更一发博客骗访问量。

好吧主要是最近找不到什么有趣的整套省选题来骗访问量了，要么就是懒得写要么就是觉得题目太逗逼。但是访问量还是要骗的是吧..正好HEOI的题出来了..就花了一天多的时间写了一下，似乎现在网上还没有什么系统的题解？那真是喜闻乐见。

【D1T1】兔子与樱花

挺简单题，这种数据范围显然只能贪心了，[tex]dp_i[/tex]表示以[tex]i[/tex]为根的子树按照最优策略删除第[tex]i[/tex]个点上连的大小是多少，然后处理每一个节点的时候就把它的孩子的大小[tex]dp[/tex]值从小到大排序然后能取就取，不能取就累加答案。至于正确性没有仔细去想，感觉还是挺显然的？

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int dp[2100000],ans,p[2100000],len,n,m,w[2100000],d[2100000],A[2100000];
struct bian{
	int next,point;
}b[2100000];
void add(int k1,int k2){
	b[++len]=(bian){p[k1],k2}; p[k1]=len;
}
void treedp(int k){
	for (int i=p[k];i;i=b[i].next){
		int j=b[i].point; treedp(j);
	}
	len=0; dp[k]=w[k]+d[k];
	for (int i=p[k];i;i=b[i].next){
		int j=b[i].point; A[++len]=dp[j]-1;
	}
	sort(A+1,A+len+1);
	for (int i=1;i<=len;i++)
		if (dp[k]+A[i]>m) {ans-=len-i+1; break;} else dp[k]+=A[i];
}
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&w[i]);
	for (int i=1;i<=n;i++){
		scanf("%d",&d[i]);
		for (int j=1;j<=d[i];j++){
			int k1; scanf("%d",&k1); add(i,k1+1);
		}
	}
	ans=n-1; treedp(1); 
	cout<<ans<<endl;
	return 0;
}

【D1T2】公约数数列

BZ上暴力可以AC...首先可以发现gcd的值最多只有[tex]\log a_0[/tex]个，可以枚举gcd的值，然后要做的就是后缀xor一个值，询问一个区间内权值等于给定值的下标最小值，这个可以用分块来解决，每一块保持权值大小有序。而维护gcd相同段用线段树实现，每一次在线段树上二分得到一段。复杂度似乎是[tex]O(m\log^2 n \log a_0+m\sqrt{n\log^2n \log a_0})[/tex]，跑的还是要比暴力快那么一点点的..

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int gcd(int k1,int k2){
	if (k2==0) return k1; return gcd(k2,k1%k2);
}
int num[410000],x[110000],n,m,len,size=900,R[1000],tot,w[1000],y[110000],a[110000],where[110000];
char ch[20];
struct atom{
	int r,w;
}A[100];
void buildtree(int k1,int k2,int k3){
	if (k2==k3){num[k1]=x[k2]; return;}
	int mid=k2+k3>>1; buildtree(k1*2,k2,mid); buildtree(k1*2+1,mid+1,k3);
	num[k1]=gcd(num[k1*2],num[k1*2+1]);
}
int find(int k1,int k2,int k3,int k4,int aim){
	if (k2==k3){
		int k5=gcd(num[k1],k4);
		if (k5>=aim) return k2; else return k2-1;
	}
	int mid=k2+k3>>1; int k5=gcd(k4,num[k1*2]);
	if (k5>=aim) return find(k1*2+1,mid+1,k3,k5,aim); else return find(k1*2,k2,mid,k4,aim);
}
void change(int k1,int k2,int k3,int k4,int k5){
	if (k2==k3){num[k1]=k5; return;}
	int mid=k2+k3>>1;
	if (mid>=k4) change(k1*2,k2,mid,k4,k5); else change(k1*2+1,mid+1,k3,k4,k5);
	num[k1]=gcd(num[k1*2],num[k1*2+1]);
}
void rebuild(){
	tot=0;
	while (A[tot].r!=n){
		tot++; A[tot].w=gcd(A[tot-1].w,x[A[tot-1].r+1]);
		A[tot].r=find(1,1,n,0,A[tot].w);
	}
}
int compare(int k1,int k2){
	return y[k1]<y[k2]||(y[k1]==y[k2]&&k1<k2);
}
int find2(int l,int r,long long k3){
	int ans=0; r++;
	while (l<r){
		int mid=l+r>>1;
		if (y[a[mid]]>=k3){
			r=mid; ans=mid;
		} else l=mid+1;
	}
	if (ans&&y[a[ans]]!=k3) ans=0;
	return a[ans];
}
int find(int k1,int k2,long long k3){
	if (k3>=(1ll<<32)) return 0;
	int l=where[k1-1],r=where[k2+1]; 
	if (l>=r){
		long long now=k3^w[where[k1]];
		for (int i=k1;i<=k2;i++) if (y[i]==now) return i;
		return 0;
	}
	long long now=k3^w[l];
	for (int i=k1;i<=R[l];i++) if (y[i]==now) return i;
	for (int i=l+1;i<r;i++){
		int k1=find2(R[i-1]+1,R[i],k3^w[i]); if (k1) return k1;
	}
	now=k3^w[r];
	for (int i=R[r-1]+1;i<=k2;i++) 	if (y[i]==now) return i;
	return 0;
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&x[i]);
	buildtree(1,1,n); rebuild();
	scanf("%d",&m); len=0;
	while (R[len]!=n) R[++len]=min(R[len-1]+size,n);
	memset(w,0x00,sizeof w);
	for (int i=1;i<=n;i++) y[i]=y[i-1]^x[i];
	for (int i=1;i<=n;i++) a[i]=i;
	for (int i=1;i<=len;i++) sort(a+R[i-1]+1,a+R[i]+1,compare);
	for (int i=1;i<=len;i++)
		for (int j=R[i-1]+1;j<=R[i];j++) where[j]=i;
	where[n+1]=len+1;
	for (;m;m--){
		scanf("%s",ch+1);
		if (ch[1]=='M'){
			int k1,k2; scanf("%d%d",&k1,&k2); k1++;
			change(1,1,n,k1,k2); int k3=where[k1-1],k4=k2^x[k1];
			for (int i=k3+1;i<=len;i++) w[i]^=k4;
			for (int i=k1;i<=R[k3];i++) y[i]^=k4;
			sort(a+R[k3-1]+1,a+R[k3]+1,compare); x[k1]=k2;
			rebuild();
		} else {
			long long k1; scanf("%lld",&k1); int flag=0;
			for (int i=1;i<=tot;i++)
				if (k1%A[i].w==0){
					int k2=find(A[i-1].r+1,A[i].r,k1/A[i].w);
					if (k2){
						printf("%d\n",k2-1); flag=1; break;
					}
				}
			if (flag==0) printf("no\n");
		}
	}
	return 0;
}

【D1T3】定价

送分的题，注意不要写残就好了...枚举后面删除的以及未删除的最后一位是否为5，然后判断是否存在这样的数，如果存在求出最小值就好了。

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int t,l,r,ans,now;
long long find(long long k1,long long k2){
	long long k3=(l/k2)*k2+k1;
	while (k3<l) k3+=k2; return k3;
}
int cal(int k){
	int len=0;
	while (k%10==0) k/=10;
	if (k%10==5) len--;
	while (k){k/=10; len+=2;}
	return len;
}
void update(int k){
	int k1=cal(k);
	if (k1<now||(k1==now&&k<ans)){
		ans=k; now=k1;
	}
}
int main(){
	scanf("%d",&t);
	for (;t;t--){
		scanf("%d%d",&l,&r); ans=l,now=cal(l);
		for (long long i=1;i<=r;i*=10){
			long long k1=find(0,i*10); if (k1<=r) update(k1);
			k1=find(i*5,i*10); if (k1<=r) update(k1);
		}
		cout<<ans<<endl;
	}
	return 0;
}

【D2T1】小L的白日梦

这题我再网上找不到题解..但是为了访问量我也是只好硬上了...我的算法建立在以下假设之上：

1.一定存在最优解每一天不高兴的概率是单调不增的。

2.一定存在最优解它选取的项目是所有项目按照不高兴的概率排序后的前缀一段加上后缀一段。

3.每一次选取的项目种类只有三种可能的情况：选了1个，全部选完，其他。且处于第三种状态的至多一个。

不要问我是怎么知道这三个假设的..我连最基本的假设1都不会证明..这些全部都是在各种暴力求证之后得到了..这A的实在是6的不行..

知道了这些假设就很简单了..假设第三种状态的是取在后缀中的，那么枚举选取前缀最右端的位置，后缀最左端的位置单调不增，扫一下就好了，反过来也是一样。

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int t,n,m,len,pd[10];
struct atom{
	long double w;
	int num;
	void scan(){
		char ch[20]; scanf("%s",ch+1); int k1=0,k2=0,len=strlen(ch+1);
		int now=1;
		for (now=1;ch[now]!='/';now++) k1=k1*10+ch[now]-'0';
		now++;
		for (;now<=len;now++) k2=k2*10+ch[now]-'0';
		w=(double)k1/(double)k2; scanf("%d",&num);
	}
}A[110000],B[310000];
long double x[110000],ans,y[10];
int compare(atom k1,atom k2){
	return k1.w>k2.w;
}
int main(){
	scanf("%d",&t);
	for (;t;t--){
		scanf("%d%d",&n,&m);
		for (int i=1;i<=n;i++) A[i].scan();  ans=1e18;
		int len=0;
		for (int i=1;i<=n;i++) if (A[i].num) A[++len]=A[i]; n=len;
		sort(A+1,A+n+1,compare); len=0;
		for (int i=1;i<=n;i++){
			B[++len]=(atom){A[i].w,1}; A[i].num--;
			if (A[i].num){
				if (A[i].num>1) B[++len]=(atom){A[i].w,A[i].num-1};
				B[++len]=(atom){A[i].w,1};
			}
		}
		n=len;
		long double ans=1e18,k1=0; int now=1; long long rem=m; 
		B[0].w=1; B[n+1].w=0;
		for (int i=n;i;i--){
			k1+=(B[i].num-1)*B[i].w*(1-B[i].w)+(1-B[i].w)*B[i+1].w; rem-=B[i].num;
		}
		for (int i=1;i<=n;i++){
			rem-=B[i].num;
			while (now<=n&&rem<=0){
				rem+=B[now].num; k1-=(B[now].num-1)*B[now].w*(1-B[now].w)+(1-B[now].w)*B[now+1].w; now++;
			}
			if (rem<=0) break;
			k1+=(B[i].num-1)*B[i].w*(1-B[i].w)+(1-B[i-1].w)*B[i].w;
			ans=min(ans,k1+(rem-1)*B[now-1].w*(1-B[now-1].w)+(1-B[now-1].w)*B[now].w+(1-B[i].w)*B[now-1].w);
		}
		rem=m; k1=0;
		for (int i=1;i<=n;i++){
			int k2=0; if (B[i].num<=rem) k2=B[i].num; else k2=rem;
			if (k2==0) break; rem-=k2; k1+=(k2-1)*(1-B[i].w)*B[i].w+(1-B[i-1].w)*B[i].w;
		}
		ans=min(ans,k1);
		for (int i=1;i<=n;i++) if (n-i+1<=i) swap(B[i],B[n-i+1]);
		for (int i=1;i<=n;i++) B[i].w=1-B[i].w;
		k1=0; now=0; rem=m; 
		for (int i=n;i;i--){
			k1+=(B[i].num-1)*B[i].w*(1-B[i].w)+(1-B[i].w)*B[i+1].w; rem-=B[i].num;
		}
		for (int i=1;i<=n;i++){
			rem-=B[i].num;
			while (now<=n&&rem<=0){
				rem+=B[now].num; k1-=(B[now].num-1)*B[now].w*(1-B[now].w)+(1-B[now].w)*B[now+1].w; now++;
			}
			if (rem<=0) break;
			k1+=(B[i].num-1)*B[i].w*(1-B[i].w)+(1-B[i-1].w)*B[i].w;
			ans=min(ans,k1+(rem-1)*B[now-1].w*(1-B[now-1].w)+(1-B[now-1].w)*B[now].w+(1-B[i].w)*B[now-1].w);
		}
		rem=m; k1=0;
		for (int i=1;i<=n;i++){
			int k2=0; if (B[i].num>=rem) k2=B[i].num; else k2=rem;
			if (k2==0) break; rem-=k2; k1+=(k2-1)*(1-B[i].w)*B[i].w+(1-B[i-1].w)*B[i].w;
		}
		ans=min(ans,k1);
		printf("%.6lf\n",(double)fabs(ans));
	}
	return 0;
}
	

【D2T2】小Z的房间

生成树计数...基尔霍夫矩阵直接上就好了。

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int mo=1000000000;
struct atom{
    int x,y;
};
atom operator - (const atom k1,const atom k2){
    return (atom){(k1.x-k2.x+mo)%mo,(k1.y-k2.y+mo)%mo};
}
atom operator * (const atom k1,const int k2){
    return (atom){1ll*k1.x*k2%mo,1ll*k1.y*k2%mo};
}
int x[100][100],pd[20][20],n,gox[4]={1,0,-1,0},goy[4]={0,1,0,-1},m;
char ch[100];
int gauss(int n){
    int pd=1; n--;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++) x[i][j]=(x[i][j]+mo)%mo;
    for (int i=1;i<=n;i++){
        int r=0;
        for (int j=i;j<=n;j++) if (x[j][i]){r=j; break;}
        for (int j=1;j<=n;j++) swap(x[i][j],x[r][j]);
        if (r!=i) pd=-pd;
        for (int j=i+1;j<=n;j++){
            int k1=x[i][i],k2=x[j][i];
            atom xx=(atom){1,0},y=(atom){0,1};
            while (k2){
                int k4=k1/k2;
                atom z=y; y=xx-y*k4; xx=z;
                k4=k2; k2=k1%k2; k1=k4; pd=-pd;
            }
            for (int k=1;k<=n;k++){
                int k3=x[i][k],k4=x[j][k];
                x[i][k]=(1ll*xx.x*k3+1ll*xx.y*k4)%mo;
                x[j][k]=(1ll*y.x*k3+1ll*y.y*k4)%mo;
            }
        }
    }
    for (int i=1;i<=n;i++) pd=1ll*pd*x[i][i]%mo;
    return (pd+mo)%mo;
}
int main(){
	scanf("%d%d",&n,&m); int len=0;
	for (int i=1;i<=n;i++){
		scanf("%s",ch+1);
		for (int j=1;j<=m;j++) if (ch[j]=='.') pd[i][j]=++len;
	}
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			if (pd[i][j])
				for (int k=0;k<4;k++){
					int k1=i+gox[k],k2=j+goy[k];
					if (pd[k1][k2]){
						x[pd[i][j]][pd[i][j]]++; x[pd[i][j]][pd[k1][k2]]=-1;
					}
				}
	cout<<gauss(len)<<endl;
	return 0;
}

【D2T3】最短不公共子串

字符串DP题四合一也是挺服气的。第一问直接求出两串后缀两两之间的LCP就可以得到答案了。第二问枚举A串中的起始点，然后往后取，B串贪心的取最近的和当前串匹配，不能匹配则更新答案。第三问建出B串的后缀自动机，令[tex]dp_{i,j}[/tex]表示A串中终止位置为[tex]i[/tex]匹配到自动机中的第[tex]j[/tex]个点的最短长度，然后递推就好了。第四问和第三问类似，令[tex]dp_{i,j}[/tex]表示A串中终止位置为[tex]i[/tex]，B串为[tex]j[/tex]的最短长度，更新时注意B串仍然要按照贪心策略选取而不能任意选取。复杂度都是[tex]O(n^2)[/tex]

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int A[2100],B[2100],n,m,dp[2100][2100],go[2100][26],a[26],f[4100];
char ch[2100];
struct tree{
    int go[27],father,val,w;
}t[4100];
int len,pre;
void insert(int now){
    int p=pre,np=++len; t[np].val=t[p].val+1; t[np].w=1;
    for (;p&&t[p].go[now]==0;p=t[p].father) t[p].go[now]=np;
    if (p==0) {
        t[np].father=1; pre=np; return;
    }
    int q=t[p].go[now];
    if (t[q].val==t[p].val+1){
        t[np].father=q; pre=np; return;
    }
    int nq=++len; memcpy(t[nq].go,t[q].go,sizeof t[q].go); t[nq].father=t[q].father;
    t[nq].val=t[p].val+1; t[q].father=nq; t[np].father=nq;
    for (;p&&t[p].go[now]==q;p=t[p].father) t[p].go[now]=nq;
    pre=np;
}
int main(){
	scanf("%s",ch+1); n=strlen(ch+1);
	for (int i=1;i<=n;i++) A[i]=ch[i]-'a';
	scanf("%s",ch+1); m=strlen(ch+1);
	for (int i=1;i<=m;i++) B[i]=ch[i]-'a';
	memset(dp,0x00,sizeof dp);
	for (int i=0;i<26;i++) a[i]=n+1;
	for (int i=m;i>=0;i--){
		for (int j=0;j<26;j++) go[i][j]=a[j];
		a[B[i]]=i;
	}
	for (int i=n;i;i--)
		for (int j=m;j;j--)
			if (A[i]==B[j]) dp[i][j]=dp[i+1][j+1]+1;
	int ans=n+1;
	for (int i=1;i<=n;i++){
		int num=0;
		for (int j=1;j<=m;j++) num=max(num,dp[i][j]);
		if (num!=n-i+1) ans=min(ans,num+1);
	}
	if (ans==n+1) cout<<-1<<endl; else cout<<ans<<endl;
	ans=n+1;
	for (int i=1;i<=n;i++){
		int now=0;
		for (int j=i;j<=n;j++){
			now=go[now][A[j]];
			if (now>n){
				ans=min(ans,j-i+1); break;
			}
		}
	}
	if (ans==n+1) cout<<-1<<endl; else cout<<ans<<endl;
	len=1; ans=n+1; pre=1;
	for (int i=1;i<=m;i++) insert(B[i]);
	memset(f,0x3f,sizeof f); f[1]=0;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=len;j++){
			int k1=t[j].go[A[i]];
			if (k1==0) ans=min(ans,f[j]+1); else f[k1]=min(f[k1],f[j]+1);
		}
	if (ans==n+1) cout<<-1<<endl; else cout<<ans<<endl;
	ans=n+1;
	memset(f,0x3f,sizeof f); f[0]=0;
	for (int i=1;i<=n;i++)
		for (int j=m;j>=0;j--){
			int k1=go[j][A[i]];
			if (k1>n) ans=min(ans,f[j]+1); else f[k1]=min(f[k1],f[j]+1);
		}
	if (ans==n+1) cout<<-1<<endl; else cout<<ans<<endl;
}