L-China

$\href{https://www.acwing.com/blog/content/30572/}{\huge{\color{gold}{卡塞尔学院}}}$

2.0万

._839

Luli

FJ_EYoungOneC

yxc的小迷妹

04辽宁大丑
Kir
-浪漫主义狗-
Sebastian_7

say774
Amaryllis_
candy.

L-China
9小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int w[N], f[N][3];

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

memset(f, -0x3f, sizeof f);
f[0][2] = 0;
for (int i = 1; i <= n; i ++)
for (int j = 0; j < 3; j ++)
if (j == 2 || (w[i] >> j & 1))
for (int k = 0; k < 3; k ++)
if (j == 2 || j != k)
f[i][j] = max(f[i][j], f[i - 1][k] + (j != 2));

cout << n - max({f[n][0], f[n][1], f[n][2]});

return 0;
}


L-China
9小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;

const int N = 1e7 + 10;

int n, x, y;
ll f[N];

int main() {
cin >> n >> x >> y;
memset(f, 0x3f, sizeof f);
f[0] = 0;

for (int i = 1; i <= n; i ++)
if (i % 2)
f[i] = min(f[(i + 1) / 2] + x + y, f[i - 1] + x);
else
f[i] = min(f[i / 2] + y, f[i - 1] + x);

cout << f[n];
return 0;
}


L-China
10小时前

# C++

$法一：$

### 思路：

$1、将a矩阵全部初始化为-1$

$2、先把当b[i][j]为0时的第i行和第j列全部更新为0$

$3、在判断b[i][j]为1时是否满足于第i行和第j列不全为0$

$时间复杂度:O(n^3)$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int m, n;
int b[N][N], a[N][N];
bool flag;

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

memset(a, -1, sizeof a); // a 矩阵初始化

for (int i = 1; i <= m; i ++) // 将 b[i][j]为0时的第i行和第j列全部更新为0
for (int j = 1; j <= n; j ++) {
if (b[i][j] == 0) {
for (int x = 1; x <= n; x ++) // 行
a[i][x] = 0;
for (int y = 1; y <= m; y ++) // 列
a[y][j] = 0;
}
}

for (int i = 1; i <= m; i ++)
for (int j = 1; j <= n; j ++) {
if (b[i][j] == 1) { // 判断b[i][j]为1时是否满足于第i行和第j列不全为0
flag = false;
for (int x = 1; x <= n; x ++) // 行
if (a[i][x] == -1 || a[i][x] == 1) {
a[i][x] = 1;
flag = true;
}
for (int y = 1; y <= m; y ++) // 列
if (a[y][j] == -1 || a[y][j] == 1) {
a[y][j] = 1;
flag = true;
}
if (flag == false) { // 不满足，直接输出NO
cout << "NO";
return 0;
}
}
}

cout << "YES" << endl;
for (int i = 1; i <= m; i ++) {
for (int j = 1; j <= n; j ++) {
cout << a[i][j] << ' ';
}
cout << endl;
}

return 0;
}


$法二：$

### 思路：

$1、将a矩阵全部初始化为-1$

$2、把当b[i][j]为0时的第i行和第j列全部更新为0$

$3、通过一个check函数判断b[i][j]为1时是否满足于第i行和第j列不全为0$

$时间复杂度:O(n^3)$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int m, n;
int b[N][N], a[N][N];

bool check() {
for (int i = 1; i <= m; i ++)
for (int j = 1; j <= n; j ++)
if (b[i][j]) {
int cnt = 0;
for (int x = 1; x <= n; x ++) cnt += a[i][x];
for (int y = 1; y <= m; y ++) cnt += a[y][j];
if (!cnt) return false;
}
return true;
}

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

memset(a, -1, sizeof a);
for (int i = 1; i <= m; i ++)
for (int j = 1; j <= n; j ++) {
cin >> b[i][j];
if (b[i][j] == 0) {
for (int x = 1; x <= n; x ++) a[i][x] = 0; // 让第i行全为0
for (int y = 1; y <= m; y ++) a[y][j] = 0; // 让第j列全为0
}
}

if (check()) {
cout << "YES" << endl;
for (int i = 1; i <= m; i ++) {
for (int j = 1; j <= n; j ++)
cout << !!a[i][j] << ' ';
cout << endl;
}
}
else cout << "NO";

return 0;
}


L-China
10小时前

### 法一：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int m, n;
int b[N][N], a[N][N];
bool flag;

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

memset(a, -1, sizeof a);

for (int i = 1; i <= m; i ++)
for (int j = 1; j <= n; j ++) {
if (b[i][j] == 0) {
for (int x = 1; x <= n; x ++) // 行
a[i][x] = 0;
for (int y = 1; y <= m; y ++) // 列
a[y][j] = 0;
}
}

for (int i = 1; i <= m; i ++)
for (int j = 1; j <= n; j ++) {
if (b[i][j] == 1) {
flag = false;
for (int x = 1; x <= n; x ++) // 行
if (a[i][x] == -1 || a[i][x] == 1) {
a[i][x] = 1;
flag = true;
}
for (int y = 1; y <= m; y ++) // 列
if (a[y][j] == -1 || a[y][j] == 1) {
a[y][j] = 1;
flag = true;
}
if (flag == false) {
cout << "NO";
return 0;
}
}
}

cout << "YES" << endl;
for (int i = 1; i <= m; i ++) {
for (int j = 1; j <= n; j ++) {
cout << a[i][j] << ' ';
}
cout << endl;
}

return 0;
}


### 法二：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int m, n;
int b[N][N], a[N][N];

bool check() {
for (int i = 1; i <= m; i ++)
for (int j = 1; j <= n; j ++)
if (b[i][j]) {
int cnt = 0;
for (int x = 1; x <= n; x ++) cnt += a[i][x];
for (int y = 1; y <= m; y ++) cnt += a[y][j];
if (!cnt) return false;
}
return true;
}

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

memset(a, -1, sizeof a);
for (int i = 1; i <= m; i ++)
for (int j = 1; j <= n; j ++) {
cin >> b[i][j];
if (b[i][j] == 0) {
for (int x = 1; x <= n; x ++) a[i][x] = 0; // 让第i行全为0
for (int y = 1; y <= m; y ++) a[y][j] = 0; // 让第j列全为0
}
}

if (check()) {
cout << "YES" << endl;
for (int i = 1; i <= m; i ++) {
for (int j = 1; j <= n; j ++)
cout << !!a[i][j] << ' ';
cout << endl;
}
}
else cout << "NO";

return 0;
}


L-China
14小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main() {
int n, m;
cin >> n >> m;

string str;
cin >> str;
char a = str[0], c = str.back();
cin >> str;
char d = str[0], b = str.back();

if (a == '>' && b == 'v' && c == '<' && d == '^' ||
a == '<' && b == '^' && c == '>' && d == 'v')
cout << "YES";
else
cout << "NO";

return 0;
}


L-China
15小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = N * 2;

int n, m;
int h[N], e[M], ne[M], idx;
int ans;

void add(int a, int b) { // 加边
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u, int fa) {
int d1 = 0, d2 = 0; // d1:当前点距离叶节点的最大值 d2:当前点距离叶节点的次大值
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i]; // 当前点的子节点
if (j == fa) continue; // 如果往上找，跳过
int d = dfs(j, u) + 1;
if (d >= d1) d2 = d1, d1 = d; // 更新最大值和次大值
else if (d > d2) d2 = d;
}

ans = max(ans, d1 + d2); // 更新一下答案
return d1; // 当前点距离叶节点的最大值
}

int main() {
cin >> n >> m;
memset(h, -1, sizeof h);

for (int i = 0; i < m; i ++) {
int a, b; cin >> a >> b;
}

dfs(1, -1);
cout << ans;

return 0;
}


L-China
16小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e3 + 10;

int n, m;
int w[N], q[N];

bool check(int mid) {
memcpy(q, w, mid * 4);
sort(q, q + mid, greater<int>());

int sum = 0;
for (int i = 0; i < mid; i += 2) { // 贪心
sum += q[i];
if (sum > m) return false;
}

return true;
}

int main() {
cin >> n >> m;
for (int i = 0; i < n; i ++) cin >> w[i];

int l = 0, r = n;
while (l < r) { // 二分
int mid = l + r + 1>> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}

cout << r;

return 0;
}


L-China
1天前

# C++

$40分做法：$

### 思路：

$暴力$

$直接预处理出来前1000行的杨辉三角形，然后暴力枚举，找到x，输出即可$

$code1:$

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1e3 + 10;

int n = 1000;
int a[N][N];

int main() {
a[1][1] = 1;
for (int i = 2; i <= n; i ++) // 预处理
for (int j = 1; j <= i; j ++)
a[i][j] = a[i - 1][j] + a[i - 1][j - 1];

int x; cin >> x;

int cnt = 0;
for (int i = 1; i <= n; i ++) // 枚举
for (int j = 1; j <= i; j ++) {
cnt ++;
if (a[i][j] == x) {
cout << cnt;
return 0;
}
}
return 0;
}


$50分做法：$

### 思路：

$推公式$

$code2:$

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

typedef long long ll;

int main() {
ll n;
cin >> n;
cout << n * (n + 1) / 2 + 2;
return 0;
}


$80分做法：$

### 思路：

$将上面两种方法相结合$

$code3:$

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1e3 + 10;
typedef long long ll;

int n = 1000;
int a[N][N];

int main() {
ll x; cin >> x;
if (x > 1000 * 999 / 2) {
cout << x * (x + 1) / 2 + 2;
return 0;
}

a[1][1] = 1;
for (int i = 2; i <= n; i ++)
for (int j = 1; j <= i; j ++)
a[i][j] = a[i - 1][j] + a[i - 1][j - 1];

ll cnt = 0;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= i; j ++) {
cnt ++;
if (a[i][j] == x) {
cout << cnt;
return 0;
}
}
return 0;
}


$满分（100分）做法：$

### 思路：

$code4:$

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

typedef long long ll;

int n;

ll C(int a, int b) { // 求组合数函数
ll res = 1;
for (int i = a, j = 1; j <= b; i --, j ++) {
res = res * i / j;
if (res > n) return res;
}
return res;
}

bool check(int k) {
ll l = k * 2, r = max(n, l);
while (l < r) {
ll mid = l + r >> 1;
if (C(mid, k) >= n) r = mid;
else l = mid + 1;
}
if (C(r, k) != n) return false;

cout << r * (r + 1) / 2 + k + 1;

return true;
}

int main() {
cin >> n;
for (int k = 16; ; k --)
if (check(k))
break;
return 0;
}


$ps：以上，皆为在蓝桥杯官网题库测试结果$

L-China
1天前

# C++

$40分做法：$

$code1:$

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1e3 + 10;

int n = 1000;
int a[N][N];

int main() {
a[1][1] = 1;
for (int i = 2; i <= n; i ++) // 预处理
for (int j = 1; j <= i; j ++)
a[i][j] = a[i - 1][j] + a[i - 1][j - 1];

int x; cin >> x;

int cnt = 0;
for (int i = 1; i <= n; i ++) // 枚举
for (int j = 1; j <= i; j ++) {
cnt ++;
if (a[i][j] == x) {
cout << cnt;
return 0;
}
}
return 0;
}


$50分做法：$

$code2:$

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

typedef long long ll;

int main() {
ll n;
cin >> n;
cout << n * (n + 1) / 2 + 2;
return 0;
}


$80分做法：$

$code3:$

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1e3 + 10;
typedef long long ll;

int n = 1000;
int a[N][N];

int main() {
ll x; cin >> x;
if (x > 1000 * 999 / 2) {
cout << x * (x + 1) / 2 + 2;
return 0;
}

a[1][1] = 1;
for (int i = 2; i <= n; i ++)
for (int j = 1; j <= i; j ++)
a[i][j] = a[i - 1][j] + a[i - 1][j - 1];

ll cnt = 0;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= i; j ++) {
cnt ++;
if (a[i][j] == x) {
cout << cnt;
return 0;
}
}
return 0;
}


$满分（100分）做法：$

$code4:$

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

typedef long long ll;

int n;

ll C(int a, int b) { // 求组合数函数
ll res = 1;
for (int i = a, j = 1; j <= b; i --, j ++) {
res = res * i / j;
if (res > n) return res;
}
return res;
}

bool check(int k) {
ll l = k * 2, r = max(n, l);
while (l < r) {
ll mid = l + r >> 1;
if (C(mid, k) >= n) r = mid;
else l = mid + 1;
}
if (C(r, k) != n) return false;

cout << r * (r + 1) / 2 + k + 1;

return true;
}

int main() {
cin >> n;
for (int k = 16; ; k --)
if (check(k))
break;
return 0;
}


$ps：以上，皆为在蓝桥杯官网题库测试结果$

L-China
2天前

# $\color{#cc33ff}{— > 算法基础课题解}$

### 思路：

$\color{blue}{模板}$

S[i, j] = 第i行j列格子左上部分所有元素的和

S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]+ a[i][j]; // 求前缀和
s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);//算子矩阵的和


$求二维前缀和：图解$

$求子矩阵和：图解$

$二维前缀和：$

$时间复杂度：O(nm)$

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1e3 + 10;

int n, m, q;
int a[N][N], s[N][N];

int main() {
cin >> n >> m >> q;

for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++) {
cin >> a[i][j];
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]; // 前缀和
}

while (q --) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << s[x2][y2] - s[x1 -  1][y2] - s[x2][y1 - 1] + s[x1 -1][y1 - 1] << endl; // 子矩阵
}

return 0;
}