C++奥赛一本通刷题记录(递推)

C++奥赛一本通刷题记录(递推)

2017.11.8 By gwj1139177410

  1. 斐波那契数列 openjudge1760

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    #include<iostream>
    using namespace std;
    const int maxn=1000010, mod=1000;
    int f[maxn];
    int main(){
    f[1] = f[2] = 1;
    for(int i = 3; i <= maxn; i++)
    f[i] = (f[i-1]+f[i-2])%mod;//bugs
    int t; cin>>t;
    while(t--){
    int n; cin>>n;
    cout<<f[n]<<"\n";
    }
    return 0;
    }
  2. pell数列 noioj1071&openjudge1788

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    #include<iostream>
    using namespace std;
    const int maxn = 1000000+10,mod=32767;
    int f[maxn];
    int main(){
    f[1]=1; f[2]=2;
    int k = maxn;
    for(int i = 3; i <= k; i++)f[i]=(2*f[i-1]+f[i-2])%mod;//bugs
    int n; cin>>n;
    while(n--){
    cin>>k;
    cout<<f[k]<<"\n";
    }
    return 0;
    }
  3. 上台阶 openjudge3525

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    //f[i]表示走i阶台阶的走法数目
    //因为每次只能走一阶或者两阶,所以由f[i-1]和f[i-2]相加转移而来
    #include<iostream>
    using namespace std;
    const int maxn = 110;
    int f[maxn], n;
    int main(){
    f[1] = 1; f[2] = 2; f[3] = 4;
    for(int i = 4; i < maxn; i++)f[i] = f[i-1]+f[i-2]+f[i-3];
    while(cin>>n && n)cout<<f[n]<<"\n";
    return 0;
    }
  4. 流感传染 openjudge6262

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    //BFS模板
    #include<iostream>
    #include<queue>
    using namespace std;
    const int maxn = 110;
    char a[maxn][maxn];
    int n, m, cnt;
    int vis[maxn][maxn];
    struct node{
    int x, y, step;
    node(int x,int y, int step){
    this->x = x;
    this->y = y;
    this->step = step;
    };
    };
    const int dx[] = {0,-1,0,1};
    const int dy[] = {1,0,-1,0};
    queue<node>q;
    void bfs(){
    while(q.size()) {
    node t = q.front(); q.pop();
    for(int i = 0; i < 4; i++){
    int nx = t.x+dx[i], ny = t.y+dy[i], st = t.step+1;
    if(st == m){
    cout<<cnt<<"\n";
    return ;
    }
    if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&a[nx][ny]!='#'&&!vis[nx][ny]){
    q.push(node(nx,ny,st));
    vis[nx][ny] = 1;
    cnt++;
    }
    }
    }
    cout<<cnt<<"\n";//bugs
    return ;
    }
    int main(){
    cin>>n; cin.get(); //datain bugs
    for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
    a[i][j]=getchar();
    if(a[i][j]=='@'){
    q.push(node(i,j,0));
    vis[i][j] = 1;
    cnt++;
    }
    }
    getchar();
    }
    cin>>m; cin.get();
    bfs();
    return 0;
    }
  5. 放苹果 openjudge666&POJ1664&luogu2386

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    //f[i][j]表示i个苹果j个盘子的放法数目
    //j>i时,去掉空盘不影响结果; j<=i时,对盘子是否空着分类讨论;*
    #include<iostream>
    using namespace std;
    const int maxn = 11;
    int f[maxn][maxn];
    int main(){
    for(int i = 0; i < maxn; i++)f[0][i]=f[i][1]=1;
    for(int i = 1; i < maxn; i++)//pojbugs
    for(int j = 2; j < maxn; j++)
    f[i][j] = j>i?f[i][i]:f[i][j-1]+f[i-j][j];//所有盘子又有苹果时每个盘子都去掉一个苹果不影响结果
    int t; cin>>t;
    while(t--){
    int n, m;
    cin>>n>>m;
    cout<<f[n][m]<<"\n";
    }
    return 0;
    }
  6. 吃糖果 openjudge1944

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    //f[i]表示名名吃i块巧克力的方案数, f[0]=f[1]=1;
    #include<iostream>
    using namespace std;
    int f[30];
    int main(){
    int n; cin>>n;
    f[0] = f[1] = 1;
    for(int i = 2; i <= n; i++)
    f[i%2]=f[(i-1)%2]+f[(i-2)%2];
    cout<<f[n%2];
    return 0;
    }
  7. 移动路线 openjudge2781

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    //f[i][j]表示从(m,1)到(i,j)的不同路线数目
    #include<iostream>
    using namespace std;
    const int maxn = 30;
    int f[maxn][maxn];
    int main(){
    int m, n; cin>>m>>n;
    f[m][0] = 1;
    for(int i = m; i >= 1; i--)
    for(int j = 1; j <= n; j++)
    f[i][j] = f[i+1][j]+f[i][j-1];
    cout<<f[1][n];
    return 0;
    }
  8. 判断整除 openjudge3531

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    //f[i][j]表示用前i个数计算能得到余数j*
    #include<iostream>
    using namespace std;
    const int maxn = 10010, maxk = 110;
    int a[maxn], f[maxn][maxk];
    int main(){
    int n, k; cin>>n>>k;
    for(int i = 1; i <= n; i++)cin>>a[i],a[i]%=k;
    f[1][a[1]] = 1;
    for(int i = 2; i <= n; i++)
    for(int j = 0; j < k; j++)
    if(f[i-1][j])f[i][(j+a[i])%k]=f[i][(j-a[i]+k)%k]=1;
    if(f[n][0])cout<<"YES\n";else cout<<"NO\n";
    return 0;
    }
  9. 踩方格 openjudge4982

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    //l[i],r[i],u[i]分别表示最后一步向左向右向上走到第i格*
    #include<iostream>
    using namespace std;
    const int maxn = 30;
    int l[maxn], r[maxn], u[maxn];
    int main(){
    int n; cin>>n;
    l[1] = r[1] = u[1] = 1;
    for(int i = 2; i <= n; i++){
    l[i] = l[i-1]+u[i-1];
    r[i] = r[i-1]+u[i-1];
    u[i] = l[i-1]+r[i-1]+u[i-1];
    }
    cout<<l[n]+r[n]+u[n]<<"\n";
    return 0;
    }
  10. 山区建小学 openjudge7624

    //f[i][j]表示1..i中建j个小学的最小距离和.(这里的j可以看成是最后一所学校管辖区的终点)
    //f[i][j]=min(f[i][j],f[k][j-1]+s[k+1][i]),j-1<=k<i;
    #include<iostream>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    const int maxn = 510;
    int a[maxn],dis[maxn][maxn],s[maxn][maxn],f[maxn][maxn];
    //s[管辖区起点][管辖区终点]=这片辖区内建一个学校,区内村庄到学校的最小距离和
    //一个结论:因为i..j中选一个点使所有点到这个点的总距离最小,这个点一定在中点位置(反证法,左移右移时)
    int dist(int l, int r){
       int m = (l+r)/2, sum = 0;
       for(int i = l; i <= r; i++)sum += dis[i][m];
       return sum;
    }
    int main(){
       int m, n;
       cin>>m>>n;
       for(int i = 2; i <= m; i++)cin>>a[i],a[i]+=a[i-1];
       //初始化两两距离
       for(int i = 1; i <= m; i++)
           for(int j = 1; j <= m; j++)
               dis[i][j] = i==j?0:abs(a[j]-a[i]);
       //计算一个管辖从i到j村庄的学校到这些村庄的距离和
       for(int i = 1; i <= m; i++)
           for(int j = 1; j <= m; j++)
               s[i][j] = dist(i,j);
       //初始化
       for(int i = 1; i <= m; i++)
           for(int j = 1; j <= m; j++)
               f[i][j] = i==j?0:0xfffff;
       for(int i = 1; i <= m; i++)f[i][1] = s[1][i];//只建一所学校
       //DP
       for(int i = 2; i <= m; i++)//村庄
           for(int j = 2; j <= min(i,n); j++)//学校
               for(int k = j-1; k < i; k++)//枚举已有的(最后一所)学校管辖的范围(终点)
                   if(i!=j)f[i][j] = min(f[i][j],f[k][j-1]+s[k+1][i]);
       cout<<f[m][n];
       return 0;
    }