L-China

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

4.4万

TT_84
hnsqls

SchwarzS
FJ_EYoungOneC
nobody123
sma11pi9

LABOUR
AkariSP

3343806536

L-China
16小时前

# $\color{gold}{— > 蓝桥杯辅导课题解}$

### 思路：

DP

闫氏DP分析法：

集合：所有总数是i，且分成j个数的和的方案
状态表示
f[i][j]     属性：数量
DP

最小值是0： f[i][j - 1]
状态计算
最小值不是0：f[i - j][j]



#include <bits/stdc++.h>
using namespace std;

int m, n;

int main() {
int t; cin >> t;
while (t --) {
cin >> m >> n;

int f[11][11] = {0};
f[0][0] = 1;
for (int i = 0; i <= m; i ++)
for (int j = 1; j <= n; j ++) {
f[i][j] = f[i][j - 1];
if (i >= j) f[i][j] += f[i - j][j];
}
cout << f[m][n] << endl;
}
return 0;
}


L-China
16小时前
#include <bits/stdc++.h>
using namespace std;

int m, n;

int main() {
int t; cin >> t;
while (t --) {
cin >> m >> n;

int f[11][11] = {0};
f[0][0] = 1;
for (int i = 0; i <= m; i ++)
for (int j = 1; j <= n; j ++) {
f[i][j] = f[i][j - 1];
if (i >= j) f[i][j] += f[i - j][j];
}
cout << f[m][n] << endl;
}
return 0;
}


L-China
3天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n;
int path[10];
bool st[10];

void dfs(int u) {
if (u == n) {
for (int i = 0; i < n; i ++) cout << path[i] << ' ';
cout << endl;
return;
}

for (int i = 1; i <= n; i ++)
if (!st[i]) {
path[u] = i;
st[i] = true;
dfs(u + 1);
st[i] = false;
}

}

int main() {
cin >> n;
dfs(0);
return 0;
}


L-China
4天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

int n;
char s[N];
int ne[N];

int main() {
int T = 1;
while (cin >> n, n) {
cin >> s + 1;

for (int i = 2, j = 0; i <= n; i ++) {
while (j && s[i] != s[j + 1]) j = ne[j];
if (s[i] == s[j + 1]) j ++;
ne[i] = j;
}
printf("Test case #%d\n", T ++);

for (int i = 1; i <= n; i ++) {
int t = i - ne[i];
if (i % t == 0 && i / t > 1)
cout << i << ' ' << i / t << endl;
}
puts("");
}

return 0;
}


L-China
4天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;

int n, m;
char p[N], s[M];
int ne[N];

int main() {
cin >> n >> p + 1 >> m >> s + 1;

for (int i = 2, j = 0; i <= n; i ++) {
while(j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++;
ne[i] = j;
}

for (int i = 1, j = 0; i <= m; i ++) {
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++;
if (j == n) {
cout << i - n << ' ';
j = ne[j];
}
}
return 0;
}


L-China
6天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;

int n, k, a, b, q;
int d[N];
int tr1[N], tr2[N];

int lowbit(int x) {
return x & -x;
}

void add(int tr[], int x, int v) {
for (int i = x; i <= n; i += lowbit(i))
tr[i] += v;
}

int query(int tr[], int x) {
int sum = 0;
for (int i = x; i; i -= lowbit(i))
sum += tr[i];
return sum;
}

int main() {
cin >> n >> k >> a >> b >> q;

while (q --) {
int t; cin >> t;
if (t == 1) {
int x, y; cin >> x >> y;
add(tr1, x, min(d[x] + y, b) - min(d[x], b));
add(tr2, x, min(d[x] + y, a) - min(d[x], a));
d[x] += y;
}
else {
int p; cin >> p;
printf("%d\n", query(tr1, p - 1) + query(tr2, n) - query(tr2, p + k - 1));
}
}
return 0;
}


L-China
6天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int f[N];

int main() {
int v, w;
cin >> n >> m >> v >> w;
for (int i = v; i <= n; i ++) f[i] = f[i - v] + w; // 完全背包

for (int i = 1; i <= m; i ++) { // 多重背包
int l, h;
cin >> l >> h >> v >> w;
for (int j = n; j >= 0; j --)
for (int k = 1; k <= l / h && k * v <= j; k ++)
f[j] = max(f[j], f[j - k * v] + k * w);
}
cout << f[n];
return 0;
}


L-China
6天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n, m;
int f[1010];

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

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


L-China
6天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

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

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


L-China
7天前

$$\huge\color{#ff00ff}{蓝桥杯C++\ AB组辅导课-题解汇总}$$

# $$\color{#ff4500}{第一讲\ 递归与递推}$$

$AcWing\ 92.\ 递归实现指数型枚举$

$AcWing\ 94.\ 递归实现排列型枚举$

$AcWing\ 93.\ 递归实现组合型枚举$

$AcWing\ 1209.\ 带分数$

$AcWing\ 1208.\ 翻硬币$

# $$\color{#ff4500}{第二讲\ 二分与前缀和}$$

$AcWing\ 789.\ 数的范围$

$AcWing\ 790.\ 数的三次方根$

$AcWing\ 795.\ 前缀和$

$AcWing\ 796.\ 子矩阵的和$

$AcWing\ 730.\ 机器人跳跃问题$

$AcWing\ 1221.\ 四平方和$

$AcWing\ 99.\ 激光炸弹$

# $$\color{#ff4500}{第三讲\ 数学与简单DP}$$

$AcWing\ 1211.\ 蚂蚁感冒$

$AcWing\ 2.\ 01背包问题$

$AcWing\ 1015.\ 摘花生$

$AcWing\ 895.\ 最长上升子序列$

# $$\color{#ff4500}{第四讲\ 枚举、模拟与排序}$$

$AcWing\ 1210.\ 连号区间数$

$AcWing\ 1236.\ 递增三元组$

$AcWing\ 1245.\ 特别数的和$

$AcWing\ 1204.\ 错误票据$

$AcWing\ 466.\ 回文日期$

$AcWing\ 787.\ 归并排序$

$AcWing\ 1219.\ 移动距离$

$AcWing\ 1231.\ 航班时间$

$AcWing\ 1241.\ 外卖店优先级$

$AcWing\ 788.\ 逆序对的数量$

# $$\color{#ff4500}{第五讲\ 树状数组与线段树}$$

$AcWing\ 1215.\ 小朋友排队$

$AcWing\ 1237.\ 螺旋折线$

$AcWing\ 797.\ 差分$

# $$\color{#ff4500}{第六讲\ 双指针、BFS与图论}$$

$AcWing\ 1238.\ 日志统计$

$AcWing\ 1101.\ 献给阿尔吉侬的花束$

$AcWing\ 1113.\ 红与黑$

$AcWing\ 1224.\ 交换瓶子$

$AcWing\ 1240.\ 完全二叉树的权值$

$AcWing\ 1096.\ 地牢大师$

$AcWing\ 1207.\ 大臣的旅费$

$AcWing\ 826.\ 单链表$

# $$\color{#ff4500}{第七讲\ 贪心}$$

$AcWing\ 1055.\ 股票买卖 II$

$AcWing\ 104.\ 货仓选址$

$AcWing\ 112.\ 雷达设备$

$AcWing\ 1239.\ 乘积最大$

# $$\color{#ff4500}{第八讲\ 数论}$$

$AcWing\ 1246.\ 等差数列$

# $$\color{#ff4500}{第九讲\ 复杂DP}$$

$AcWing\ 1050.\ 鸣人的影分身$

# $$\color{#ff0000}{第十一届蓝桥杯省赛第一场C++A/B组真题}$$

$AcWing\ 2065.\ 整除序列$

$AcWing\ 2066.\ 解码$

$AcWing\ 2067.\ 走方格$

$AcWing\ 2068.\ 整数拼接$

# $$\color{#ff0000}{第十二届蓝桥杯省赛第一场C++A/B/C组真题}$$

$AcWing\ 3416.\ 时间显示$

$AcWing\ 3417.\ 砝码称重$

$AcWing\ 3418.\ 杨辉三角形$

$AcWing\ 3419.\ 双向排序$

$AcWing\ 3420.\ 括号序列$

$AcWing\ 3422.\ 左孩子右兄弟$

$AcWing\ 3424.\ 最少砝码$

# $$\color{#ff0000}{第十二届蓝桥杯省赛第二场C++B组真题}$$

$AcWing\ 3496.\ 特殊年份$

$AcWing\ 3490.\ 小平方$

$AcWing\ 3491.\ 完全平方数$

# $$\color{#ff0000}{第十三届蓝桥杯省赛C++组真题}$$

### $A组$

$AcWing\ 4644.\ 求和$

### $B组$

$AcWing\ 4402.\ 刷题统计$

$AcWing\ 4403.\ 修剪灌木$

$AcWing\ 4404.\ X 进制减法$

$AcWing\ 4405.\ 统计子矩阵$

### $C组$

$AcWing\ 4652.\ 纸张尺寸$

$AcWing\ 4644.\ 求和$

$AcWing\ 4653.\ 数位排序$

$AcWing\ 4655.\ 重新排序$