头像

qsmy_41




离线:3分钟前



qsmy_41
23小时前
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n, a[N], f[N];

int main() {
    cin>>n;
    for (int i=1; i<=n; i++) cin>>a[i];
    for (int i=1; i<=n; i++) {
        f[i]=1;
        for (int j=1; j<i; j++) {
            if (a[i]>a[j]) f[i]=max(f[i], f[j]+1);
        }
    }
    int m=0;
    for (int i=1; i<=n; i++) m=max(m, f[i]);
    cout<<m;
    return 0;
}



qsmy_41
1天前

题目描述

分形,具有以非整数维形式充填空间的形态特征。

通常被定义为“一个粗糙或零碎的几何形状,可以分成数个部分,且每一部分都(至少近似地)是整体缩小后的形状”,即具有自相似的性质。

现在,定义“盒子分形”如下:

一级盒子分形:

   X

二级盒子分形:

   X X
    X
   X X

如果用B(n - 1)代表第n-1级盒子分形,那么第n级盒子分形即为:

  B(n - 1)        B(n - 1)

          B(n - 1)

  B(n - 1)        B(n - 1)

你的任务是绘制一个n级的盒子分形。

输入格式

输入包含几个测试用例。

输入的每一行包含一个不大于7的正整数n,代表要输出的盒子分形的等级。

输入的最后一行为-1,代表输入结束。

输出格式

对于每个测试用例,使用“X”符号输出对应等级的盒子分形。

请注意’X’是一个大写字母。

每个测试用例后输出一个独立一行的短划线。

输入样例:

1
2
3
4
-1

输出样例

X
-
X X
 X
X X
-
X X   X X
 X     X
X X   X X
   X X
    X
   X X
X X   X X
 X     X
X X   X X
-
X X   X X         X X   X X
 X     X           X     X
X X   X X         X X   X X
   X X               X X
    X                 X
   X X               X X
X X   X X         X X   X X
 X     X           X     X
X X   X X         X X   X X
         X X   X X
          X     X
         X X   X X
            X X
             X
            X X
         X X   X X
          X     X
         X X   X X
X X   X X         X X   X X
 X     X           X     X
X X   X X         X X   X X
   X X               X X
    X                 X
   X X               X X
X X   X X         X X   X X
 X     X           X     X
X X   X X         X X   X X
-

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=750;

bool a[N][N];

void copy(int x1, int y1, int x2, int y2, int dim) {
    for (int i1=x1, i2=x2; i1<x1+dim; i1++, i2++)
        for (int j1=y1, j2=y2; j1<y1+dim; j1++, j2++) 
            a[i2][j2]=a[i1][j1];
}


void construct(int x) {
    int i=2*x+1, dim=x;
    copy(1,1,i,1,dim), copy(1,1,1,i,dim), copy(1,1,i,i,dim), copy(1,1,x+1,x+1,dim);
}


int main() {
    int n;
    a[1][1]=true;
    for (int i=1; i<7; i++) construct(pow(3, i-1));
    while (cin>>n, n!=-1) {
        for (int i=1; i<=pow(3, n-1); i++, cout<<'\n') 
            for (int j=1; j<=pow(3, n-1); j++)
                cout<<(a[i][j]?'X':' ');
        cout<<"-\n";
    }

    return 0;
}


活动打卡代码 AcWing 754. 平方矩阵 II

qsmy_41
1天前
#include <bits/stdc++.h>
using namespace std;
const int N=110;

int main() {
    int n;
    while (cin>>n, n) {
        for (int i=1; i<=n; i++, cout<<'\n')
            for (int j=1; j<=n; j++) {
                int x=abs(i-j);
                cout<<x+1<<' ';
            }
        cout<<'\n';
    }
    return 0;
}


活动打卡代码 AcWing 1341. 十三号星期五

qsmy_41
1天前
#include <bits/stdc++.h>
using namespace std;
const int N=410;
const int M[]={31,28,31,30,31,30,31,31,30,31,30,31};
int res[7];

int main() {
    int n;
    cin>>n;
    int cnt=-1;
    for (int i=1900; i<1900+n; i++) {
        for (int j=0; j<12; j++) {
            res[(cnt+13)%7]++;
            cnt=(cnt+M[j])%7;
            if (j==1 && (i%4==0 && i%100 || i%400==0)) cnt++;
        }
    }
    for (int i=5, j=0; j<7; i=(i+1)%7, j++) cout<<res[i]<<' ';
    return 0;
}


活动打卡代码 AcWing 898. 数字三角形

qsmy_41
1天前
#include <bits/stdc++.h>
using namespace std;
const int N=510;
int n, a[N][N];

int main() {
    cin>>n;
    for (int i=1; i<=n; i++) for (int j=1; j<=i; j++) cin>>a[i][j];

    for (int i=n-1; i; i--) for (int j=i; j; j--) a[i][j]+=max(a[i+1][j], a[i+1][j+1]);
    cout<<a[1][1];
    return 0;
}



qsmy_41
1天前

题目描述

有 $N$ 组物品和一个容量是 $V$ 的背包。

每组物品有若干个,同一组内的物品最多只能选一个。
每件物品的体积是 $v_{ij}$,价值是 $w_{ij}$,其中 $i$ 是组号,$j$ 是组内编号。

求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。

输出最大价值。

输入格式

第一行有两个整数 $N$,$V$,用空格隔开,分别表示物品组数和背包容量。

接下来有 $N$ 组数据:

每组数据第一行有一个整数 $S_i$,表示第 $i$ 个物品组的物品数量;
每组数据接下来有 $S_i$ 行,每行有两个整数 $v_{ij}$,$w_{ij}$,用空格隔开,分别表示第 $i$ 个物品组的第 $j$ 个物品的体积和价值;

输出格式

输出一个整数,表示最大价值。

数据范围

$0<N,V≤100$,
$0<Si≤100$,
$0<v_{ij},w_{ij}≤100$,

输入样例

3 5
2
1 2
2 4
1
3 4
1
4 5

输出样例:

8

思路

状态可以用f[i][j][k],表示选到第i个组,体积小于等于j,选择第i组里的第k个物品。

由此f[i][j][k]可以这么算:
1. 不在当前这组选, 即f[i-1][j][s[i-1]]
2. 选第i组里面的k之前的物品,即f[i][j][k-1]
3. 选当前第i组里面的第k个物品,即f[i-1][j-v[i][k]][s[i-1]]+w[i][k]

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=110;
int n, V, v[N][N], w[N][N], s[N], f[N][N][N];

int main() {
    cin>>n>>V;
    for (int i=1; i<=n; i++) {
        cin>>s[i];
        for (int j=1; j<=s[i]; j++) cin>>v[i][j]>>w[i][j];
    }
    for (int i=1; i<=n; i++) for (int j=1; j<=V; j++) for (int k=1; k<=s[i]; k++) {
        f[i][j][k]=max(f[i-1][j][s[i-1]], f[i][j][k-1]);
        if (j>=v[i][k]) f[i][j][k]=max(f[i][j][k], f[i-1][j-v[i][k]][s[i-1]]+w[i][k]);
    }
    cout<<f[n][V][s[n]];
    return 0;
}


活动打卡代码 AcWing 9. 分组背包问题

qsmy_41
1天前
#include <bits/stdc++.h>
using namespace std;
const int N=110;
int n, V, v[N][N], w[N][N], s[N], f[N][N][N];

int main() {
    cin>>n>>V;
    for (int i=1; i<=n; i++) {
        cin>>s[i];
        for (int j=1; j<=s[i]; j++) cin>>v[i][j]>>w[i][j];
    }
    for (int i=1; i<=n; i++) for (int j=1; j<=V; j++) for (int k=1; k<=s[i]; k++) {
        f[i][j][k]=max(f[i-1][j][s[i-1]], f[i][j][k-1]);
        if (j>=v[i][k]) f[i][j][k]=max(f[i][j][k], f[i-1][j-v[i][k]][s[i-1]]+w[i][k]);
    }
    cout<<f[n][V][s[n]];
    return 0;
}


活动打卡代码 AcWing 5. 多重背包问题 II

qsmy_41
1天前
#include <bits/stdc++.h>
using namespace std;
const int N=12000;
int n, V, v[N], w[N], s[N], f[N];

int main() {
    cin>>n>>V;

    int cnt=0;
    for (int i=0; i<n; i++) {
        int a, b, c;
        cin>>a>>b>>c;
        int s=1;
        while (s<=c) {
            v[++cnt]=a*s;
            w[cnt]=b*s;
            c-=s;
            s<<=1;
        }
        if (c) {
            v[++cnt]=a*c;
            w[cnt]=b*c;
        }
    }

    for (int i=1; i<=cnt; i++) for (int j=V; j>=v[i]; j--)
        f[j]=max(f[j], f[j-v[i]]+w[i]);
    cout<<f[V];

    return 0;
}


活动打卡代码 AcWing 5. 多重背包问题 II

qsmy_41
1天前
#include <bits/stdc++.h>
using namespace std;
const int N=12000;
int n, V, v[N], w[N], s[N], f[N];

int main() {
    cin>>n>>V;

    int cnt=0;
    for (int i=0; i<n; i++) {
        int a, b, c;
        cin>>a>>b>>c;
        int s=1;
        while (s<=c) {
            v[++cnt]=a*s;
            w[cnt]=b*s;
            c-=s;
            s<<=1;
        }
        if (c) {
            v[++cnt]=a*c;
            w[cnt]=b*c;
        }
    }

    for (int i=1; i<=cnt; i++) for (int j=V; j>=v[i]; j--)
        f[j]=max(f[j], f[j-v[i]]+w[i]);
    cout<<f[V];

    return 0;
}



qsmy_41
1天前

题目描述

有 $N$ 种物品和一个容量是 $V$ 的背包。

第 $i$ 种物品最多有 $s_i$ 件,每件体积是 $v_i$,价值是 $w_i$。

求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。

输入格式

第一行两个整数,$N$,$V$,用空格隔开,分别表示物品种数和背包容积。

接下来有 $N$ 行,每行三个整数 $v_i$,$w_i$,$s_i$,用空格隔开,分别表示第 $i$ 种物品的体积、价值和数量。

输出格式

输出一个整数,表示最大价值。

数据范围

$0<N,V\le 100$,
$0<v_i,w_i,s_i\le 100$

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例:

10

思路

状态可以定义成f[i][j][k],选到第i个物品,小于等于j体积,k个第i个物品已经被选,这时候最大的值是多少。

这样就会有三种情况要考虑来计算:
1. 不选当前第i个物品,即f[i-1][j][s[i-1]]
2. 第一次选第i个物品,即f[i-1][j-v[i]][s[i-1]]+w[i]
3. 第k次选第i个物品,即f[i][j-v[i]][k-1]+w[i]

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=110;
int n, V, v[N], w[N], s[N], f[N][N][N];

int main() {
    cin>>n>>V;
    for (int i=1; i<=n; i++) cin>>v[i]>>w[i]>>s[i];
    for (int i=1; i<=n; i++) for (int j=1; j<=V; j++) for (int k=1; k<=s[i]; k++) {
        f[i][j][k]=f[i-1][j][s[i-1]];
        if (j>=v[i]) f[i][j][k]=max({f[i][j][k], f[i][j-v[i]][k-1]+w[i], f[i-1][j-v[i]][s[i-1]]+w[i]});
    }
    cout<<f[n][V][s[n]];
    return 0;
}