华中农业大学第五届程序设计大赛

（ACM）动态规划 （ACM）数学----fib数列 （ACM）数学----矩阵快速幂

contest

A. Little Red Riding Hood（dp）

题意

题解

• 简单dp。
• d[i]表示i一定取的最大收益。
• 维护一个前缀最大值，转移就可以做到o1了。

代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define de(x) cout << #x << "=" << x << endl
const int N=100005;
int a[N];
ll Max[N],dp[N];
int main() {
    int T;scanf("%d",&T);
    int ca=0;
    while(T--) {
        ///init
        memset(Max,0,sizeof(Max));
        memset(dp,0,sizeof(dp));
        ///read
        int n,k;scanf("%d%d",&n,&k);
        for(int i=1;i<=n;++i) scanf("%d",a+i);
        ///solve
        for(int i=1;i<=n;++i) {
            int pre=i-k-1;
            pre=max(0,pre);
            dp[i]=Max[pre]+a[i];
            Max[i]=max(Max[i-1],dp[i]);
        }
        ///print
        cout<<Max[n]<<endl;
    }
    return 0;
}

C. Friends（dp思想）

题意

题解

• dp思想。
• 对于每个点，与它距离小等于6的值可能在它的子树，也可能不在（但是可以看成在它的父亲的子树）
• 因此处理出所有点子树中符合条件的值(on)，每次询问时的答案是子树+父亲的子树-重复的。

代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define de(x) cout << #x << "=" << x << endl
const int N=100005;
vector<int> G[N];
int fa[N],son[N][7],ans[N];
void dfs1(int u,int pre) {
    ///
    fa[u]=pre;
    son[u][0]=1;
    ///
    int sz=G[u].size();
    for(int i=0;i<sz;++i) {
        int v=G[u][i];
        if(v==pre) continue;
        ///
        dfs1(v,u);
        for(int j=1;j<=6;++j) son[u][j]+=son[v][j-1];
    }
}
void dfs2(int u) {
    for(int i=1;i<=6;++i) ans[u]+=son[u][i];
    int pre=u,now=u;
    for(int i=1;i<=6;++i) {
        now=pre;
        pre=fa[pre];
        if(!pre) break;
        for(int j=0;j<=6-i;++j) {
            ans[u]+=son[pre][j];
            if(j) ans[u]-=son[now][j-1];
        }
    }
}
int main() {
    int T;scanf("%d",&T);
    int ca=0;
    while(T--) {
        printf("Case #%d:\n",++ca);
        ///init
        for(int i=0;i<N;++i) G[i].clear();
        memset(son,0,sizeof(son));
        memset(ans,0,sizeof(ans));
        ///read
        int n;scanf("%d",&n);
        for(int i=1;i<n;++i) {
            int u,v;scanf("%d%d",&u,&v);
            G[u].pb(v);
            G[v].pb(u);
        }
        ///solve
        dfs1(1,0);
        for(int i=1;i<=n;++i) dfs2(i);
        ///print
        for(int i=1;i<=n;++i) printf("%d\n",ans[i]);
    }
    return 0;
}

D. GCD（fib数列+矩阵快速幂）

题意

题解

• fib数列的性质。
• sum(f[i])+1=f[n+2]
• gcd(f[n],f[m])=f[gcd(n,m)]
• 求fib用矩阵快速幂

代码

#include<cstdio>
#include<cstring>
int n,m,p;
int gcd(int a,int b) {
    if(b==0) return a;
    return gcd(b,a%b);
}
struct Mat {
    int mat[3][3];
    Mat() {memset(mat,0,sizeof(mat));}
    Mat operator * (Mat B) {
        Mat C;
        for(int i=1;i<=2;++i) {
            for(int j=1;j<=2;++j) {
                for(int k=1;k<=2;++k) {
                    C.mat[i][j]=(C.mat[i][j]+1ll*mat[i][k]*B.mat[k][j]%p)%p;
                }
            }
        }
        return C;
    }
};
Mat powmul(Mat A,int k) {
    Mat B;
    B.mat[1][1]=B.mat[2][2]=1;
    while(k) {
        if(k&1) B=B*A;
        A=A*A;
        k>>=1;
    }
    return B;
}
int main() {
    int T;scanf("%d",&T);
    while(T--) {
        ///
        scanf("%d%d%d",&n,&m,&p);
        ///get d
        int d=gcd(n+2,m+2);
        ///get fib[d]
        Mat A;
        A.mat[1][1]=A.mat[1][2]=A.mat[2][1]=1;
        A=powmul(A,d);
        printf("%d\n",A.mat[1][2]);
    }
    return 0;
}