jiry_2's Blog

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

其实去北京之前就开始做HAOI的题了，但是因为在北京一直都在浪，所以也就没有时间把这个坑填完。回到杭州之后总算可以开始写题了，就来更一下博客骗访问量吧，虽然早已错过了骗访问量的最佳时机了233。

【T1】T1

按照以前的格式写名字感觉好醉啊...直接大力DP，把贡献分每一条边考虑，然后就是一个貌似[tex]O(n^3)[/tex]但是是[tex]O(n^2)[/tex]的做法。

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
struct bian{
    int next,point,w;
}b[4100];
long long dp[2100][2100],A[2001];
int n,k,p[2100],len,size[2100];
void ade(int k1,int k2,int k3){
    b[++len]=(bian){p[k1],k2,k3}; p[k1]=len;
}
void add(int k1,int k2,int k3){
    ade(k1,k2,k3); ade(k2,k1,k3);
}
void dfs(int k1,int k2){
    int num=0; size[k1]=1;
    for (int i=2;i<=n;i++) dp[k1][i]=-1e18;
    dp[0][0]=0; dp[0][1]=0;
    for (int i=p[k1];i;i=b[i].next){
        int j=b[i].point;
        if (j==k2) continue;
        dfs(j,k1); 
        for (int k3=0;k3<=n;k3++) A[k3]=-1e18;
        for (int k3=0;k3<=size[k1];k3++)
            for (int k4=0;k4<=size[j];k4++){
                int k5=k4*(k-k4)+(size[j]-k4)*((n-k)-(size[j]-k4));
                A[k3+k4]=max(A[k3+k4],dp[k1][k3]+dp[j][k4]+1ll*b[i].w*k5);
            }
        size[k1]+=size[j];
        for (int k3=0;k3<=size[k1];k3++) dp[k1][k3]=A[k3];
    }
}
int main(){
    scanf("%d%d",&n,&k);
    for (int i=1;i<n;i++){
        int k1,k2,k3; scanf("%d%d%d",&k1,&k2,&k3);
        add(k1,k2,k3);
    }
    dfs(1,0); cout<<dp[1][k]<<endl;
    return 0;
}

【T2】T2

先dfs序，第一个操作就变成了区间加，而第二个操作相当于给子树内的所有节点[tex]i[/tex]加上[tex]a(d_i-d_x+1)[/tex]，把这个式子拆开就可以变成区间加以及区间加上每一个位置的权值的若干倍，第三个操作时单点询问，直接两个树状数组就好了。

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
struct bian{
    int next,point;
}b[210000];
int p[110000],n,m,len,dfs[110000],r[110000],sign,d[110000],x[110000];
long long A[110000],a[110000];
void ade(int k1,int k2){
    b[++len]=(bian){p[k1],k2}; p[k1]=len;
}
void add(int k1,int k2){
    ade(k1,k2); ade(k2,k1);
}
void dfs1(int k1,int k2){
    dfs[k1]=++sign; d[k1]=d[k2]+1;
    for (int i=p[k1];i;i=b[i].next){
        int j=b[i].point;
        if (j!=k2) dfs1(j,k1);
    }
    r[k1]=sign;
}
void addin(long long *A,int k1,long long k2){
    for (;k1<=n;k1+=k1&(-k1)) A[k1]+=k2;
}
long long find(long long *A,int k1){
    long long ans=0; for (;k1;k1-=k1&(-k1)) ans+=A[k1]; return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&x[i]);
    for (int i=1;i<n;i++){
        int k1,k2; scanf("%d%d",&k1,&k2); add(k1,k2);
    }
    sign=0; dfs1(1,0);
    for (int i=1;i<=n;i++){addin(A,dfs[i],x[i]); addin(A,r[i]+1,-x[i]);}
    for (;m;m--){
        int k1,k2,k3; scanf("%d",&k1);
        if (k1==3){
            scanf("%d",&k2); printf("%lld\n",find(A,dfs[k2])+1ll*d[k2]*find(a,dfs[k2]));
        } else if (k1==2){
            scanf("%d%d",&k2,&k3); addin(a,dfs[k2],k3); addin(a,r[k2]+1,-k3); addin(A,dfs[k2],-1ll*(d[k2]-1)*k3);
            addin(A,r[k2]+1,1ll*(d[k2]-1)*k3);
        } else if (k1==1){
            scanf("%d%d",&k2,&k3); addin(A,dfs[k2],k3); addin(A,r[k2]+1,-k3);
        }
    }
    return 0;
}

【T3】T3

论博弈渣渣的自我修养...根本不会做这题，然后就去看题解..每一个位置是独立的，只要计算每一个位置的sg函数就好了，可以发现只要[tex]\lfloor \frac{n}{i} \rfloor=\lfloor \frac{n}{j} \rfloor[/tex]，[tex]i[/tex]和[tex]j[/tex]的sg函数就是相同的，于是就可以把需要计算的规模变成[tex]O(n^\frac{1}{2})[/tex]，然后用之前做莫比乌斯函数题目的技巧做这题就行了..复杂度是什么我也分析不出来，反正跑的挺快的。

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int A[100000],lim,n,w[100000],pd[100000],next,len;
int find(int k){
	if (k<=lim) return k;
	int l=lim+1,r=len+1,ans=0;
	while (l<r){
		int mid=l+r>>1;
		if (A[mid]<=k){
			ans=mid; l=mid+1;
		} else r=mid;
	}
	return ans;
}
int main(){
	scanf("%d",&n); next=0;
	for (int i=1;i<=n;i=next+1){
		next=n/(n/i); A[++len]=(n/i);
	}
	for (int i=1;i<=len;i++) if (len-i+1<=i) swap(A[i],A[len-i+1]);
	lim=1;
	while (lim<=n&&A[lim]==lim) lim++; lim--;
	for (int now=1;now<=len;now++){
		int pre=0;
		for (int i=2;i<=A[now];i=next+1){
			int k1=A[now]/i; next=A[now]/k1; k1=find(k1);
			pd[pre^w[k1]]=now;
			if (k1!=i) pd[pre]=now;
			if ((next-i+1)&1) pre^=w[k1];
		}
		for (int i=1;;i++) if (pd[i]!=now){w[now]=i; break;}	
	}
	int t; scanf("%d",&t);
	for (;t;t--){
		int k1; scanf("%d",&k1); int ans=0;
		for (;k1;k1--){
			int k2; scanf("%d",&k2); ans^=w[find(n/k2)];
		}
		if (ans==0) cout<<"No"<<endl; else cout<<"Yes"<<endl;
	}
	return 0;
}

【T4】Set

VFK的论文题..定义集合函数之间的乘法为或卷积，然后可以发现答案就是[tex][x^{2^n-1}]-\frac{1}{1-w}[/tex]，然后就用前缀和（莫比乌斯变换？）直接算就好了。

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
double A[1<<20];
int n;
int main(){
    scanf("%d",&n);
    for (int i=0;i<(1<<n);i++) scanf("%lf",&A[i]);
    for (int i=1;i<=n;i++)
        for (int j=0;j<(1<<n);j++)
            if (j&(1<<i-1)) A[j]+=A[j-(1<<i-1)];
    for (int i=0;i<(1<<n);i++) if (A[i]>=1-1e-8){if (i!=(1<<n)-1){cout<<"INF"<<endl; return 0;}A[i]=0;} else A[i]=-(1/(1-A[i]));
    for (int i=1;i<=n;i++)
        for (int j=0;j<(1<<n);j++)
            if (j&(1<<i-1)) A[j]-=A[j-(1<<i-1)];
    printf("%.10lf\n",A[(1<<n)-1]);
    return 0;
}

【T5】Str

感觉是挺老的idea？把矩阵当成DP的值来进行DP。这儿就预处理转移矩阵[tex]A[/tex]的所有[tex]A^{10^ij}[/tex]，然后暴力转移就好了。

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
struct atom{
    int x[5][5];
}A,B,num[510][10],zero,dp[510];
int mo=998244353,x[600],n,m;
char ch[600];
atom operator * (atom k1,atom k2){
    memset(B.x,0x00,sizeof B.x);
    for (int i=0;i<m;i++)
        for (int j=0;j<m;j++)
            for (int k=0;k<m;k++) B.x[i][j]=(B.x[i][j]+1ll*k1.x[i][k]*k2.x[k][j])%mo;
    return B;
}
atom operator + (atom k1,atom k2){
    memset(B.x,0x00,sizeof B.x);
    for (int i=0;i<m;i++)
        for (int j=0;j<m;j++)
            B.x[i][j]=(k1.x[i][j]+k2.x[i][j])%mo;
    return B;
}
atom get(atom k1){
    atom k3=k1;
    for (int i=1;i<=9;i++) k3=k3*k1;
    return k3;
}
int main(){
    scanf("%s",ch+1); n=strlen(ch+1); scanf("%d",&m);
    for (int i=0;i<m;i++) zero.x[i][i]=1;
    for (int i=1;i<=n;i++) x[i]=ch[i]-'0';
    for (int i=0;i<m;i++) A.x[i][0]=1;
    for (int i=1;i<m;i++) A.x[i-1][i]=1;
    for (int i=1;i<=n;i++){
        num[i][0]=zero;
        for (int j=1;j<10;j++) num[i][j]=num[i][j-1]*A;
        A=get(A);
    }
    dp[0]=zero;
    for (int i=1;i<=n;i++){
        A=zero;
        for (int j=i;j;j--){
            A=num[i-j+1][x[j]]*A;
            dp[i]=dp[i]+dp[j-1]*A;
        }
    }
    cout<<dp[n].x[0][0]<<endl;
    return 0;
}