题解；
第一题：
#includeusing namespace std;#define ll long longconst int M = 2e5 + 5;const ll P=1e9 + 7;ll ksm(ll a, ll b){ ll ret=1; for(;b;b>>=1,a=a*a%P) if(b&1)ret=ret*a%P; return ret;}ll fac[M], vfac[M], A[M], B[M], l[M], t[M];inline ll C(int n, int m){ return fac[n] * vfac[m] % P * vfac[n-m]%P;}int main(){ freopen("matrix.in","r",stdin); freopen("matrix.out","w",stdout); int n, a, b; scanf("%d%d%d",&n,&a,&b); fac[0]=1;vfac[0]=1; for(ll i=1;i<=(2*n);i++){ fac[i]=fac[i-1]*i%P; } vfac[n]=ksm(fac[n], P-2); for(ll i=n-1;i;i--)vfac[i]=vfac[i+1]*(i+1)%P; for(int i=1;i<=n;i++)scanf("%lld",&l[i]); for(int i=1;i<=n;i++)scanf("%lld",&t[i]); if(n==1){printf("%lld\n",t[1]);return 0;} ll t1=n-2,t2=0; ll ans=0; ll pa=1, pb=1, ap=ksm(a,n-1),bp=ksm(b,n-1); for (int i=n; i>1; i--,t1++,t2++,pa=1ll*pa*a%P,pb=1ll*pb*b%P) ans=((1ll*ans + 1ll*l[i]*ap%P*pb%P*C(t1,t2)%P)%P + 1ll*t[i]*bp%P*pa%P*C(t1,t2)%P)%P; printf("%lld\n",ans);}
第二题：dp[i][j]表示可否拆成i个p,j个q，枚举每个数拆成多少个p,q贪心取，因为dp[i][j]可行, dp[i][k](k<j)也可行；复杂度（50*2000*2000*50）
#includeusing namespace std;int a[55];struct node{ int a,b;}w[55][2005];bool dp[2][2005][2005];#define RG registerint main(){ freopen("pq.in","r",stdin); freopen("pq.out","w",stdout); int n, p, q; scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); scanf("%d%d",&p,&q); if(p < q)swap(p, q); int up1=0,up2=0; for(int i=1;i<=n;i++){ int x=0; while(a[i]>=x*p){w[i][++w[i][0].a].a=x,w[i][w[i][0].a].b=(a[i]-x*p)/q;x++;} up1+=(a[i]/p); up2+=(a[i]/q); } memset(dp, 0, sizeof(dp)); dp[0][0][0]=1; int ans=0,u=0; for(int i=1;i<=n;i++){ u^=1; memset(dp[u], 0, sizeof(dp[u])); for(RG int h=up1;h>=0;h--) for(RG int z=up2;z>=0;z--) if(dp[u^1][h][z]){ for(RG int j=1;j<=w[i][0].a;j++){ { dp[u][h+w[i][j].a][z+w[i][j].b] |= dp[u^1][h][z]; // printf("%d %d %d %d\n",i,h,z,dp[u][h][z]); } } } } int c=p+q; for(int i = up1; i >= 0; i--) for(int j = i; j <= up2; j++) if(dp[u][i][j]) ans = max(ans, i*c); printf("%d\n",ans);}
第三题：原题：
#includeusing namespace std;const int M = 5e4, ME = 2e5 + 5;#define ll long longconst ll inf = 1e9;int tot = 1, h[M];ll dis[M];bool inq[M];queue q;struct edge{ int v, nxt, w;}G[ME];void add(int u, int v, int w){G[++tot].v=v,G[tot].nxt=h[u],G[tot].w=w,h[u]=tot;}void SPFA(){ memset(inq, 0, sizeof(inq)); while(!q.empty()){ int u=q.front();q.pop();inq[u]=0; for(int i=h[u];i;i=G[i].nxt){ int v=G[i].v; if(v!=1&&dis[v]>dis[u]+G[i].w){ dis[v]=dis[u]+G[i].w; //printf("%d %d %lld\n",u,v,dis[v]); if(!inq[v])inq[v]=1,q.push(v); } } }}int read(){ int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){ if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*=f;}int main(){ freopen("graph.in","r",stdin); freopen("graph.out","w",stdout); int n = read(), m = read(); for(int i = 1; i <= m; i++){ int u = read(), v = read(), w1 = read(), w2 = read(); add(u, v, w1); add(v, u, w2); } ll ans = inf; for(int bit = 1; bit <= 18; bit++){ memset(dis, 127, sizeof(dis)); for(int i = h[1]; i; i = G[i].nxt){ int v = G[i].v; if(v & (1<<(bit-1))) q.push(v), dis[v] = min(dis[v], 1LL*G[i].w), inq[v] = 1; } SPFA(); for(int i = h[1]; i; i = G[i].nxt){ int v = G[i].v; if((v & (1<<(bit-1))) == 0) { ans = min(ans, 1LL*G[i^1].w + dis[v]); } } memset(dis, 127, sizeof(dis)); for(int i = h[1]; i; i = G[i].nxt){ int v = G[i].v; if((v & (1<<(bit-1))) == 0) q.push(v), dis[v] = min(dis[v], 1LL*G[i].w), inq[v] = 1; } SPFA(); for(int i = h[1]; i; i = G[i].nxt){ int v = G[i].v; if(v & (1<<(bit-1))){ ans = min(ans, 1LL*G[i^1].w + dis[v]); } } } printf("%lld\n", ans);}