//1. 铺地毯

T组样例

L长的数组：初始全为零，n个操作

每个操作将[l,r]闭区间上的数字加一

输出所有操作之后的数组

例如：

1

6 3

1 2

4 5

3 6

1 1 1 2 2 1

暴力直接过

本来还以为要用个分块或者线段树，结果数据真水。

100%代码

typedef long long ll;

int main() {

//ios::sync_with_stdio(false);

//freopen("in.txt", "r", stdin);

int T; cin >> T;

while (T--) {

int L, n; cin >> L >> n;

vector<int>s(L + 10);

while (n--) {

int l, r; cin >> l >> r;

for (int i = l; i <= r; i++) {

s[i]++;

}

}

for (int i = 1; i <= L; i++) {

cout << s[i] << ' ';

}

cout << endl;

}

}

//2.

T组样例

n长的a数组，m长的b数组

a数组的每个元素需要从b数组中找个元素配对

原则：a数组的元素要小于b数组的元素

找不到输出-1

输出：在a数组配对数量最多的情况下，a数组每个元素配对的元素在b数组中的位置（其中一种答案）

例如：

1

3 6

33 66 99

3 6 9 30 60 90

输出：

5 6 -1

思路：

将ab数组升序排序，注意保存原始的位置。

排序之后，使用双指针ij分别指向ab数组的最后一个元素

If（i指向的元素小于等于j指向的元素）说明符合条件

就记录答案

ij分别往前移动一位

else

说明i指向的元素已经没有解了

就让i往前移动一位

typedef long long ll;

struct node {

int val;

int it;

};

bool cmp(node a, node b) {

if (a.val == b.val) {

return a.it < b.it;

}

return a.val < b.val;

}

int main() {

//ios::sync_with_stdio(false);

//freopen("in.txt", "r", stdin);

int T; cin >> T;

while (T--) {

int m, n; cin >> n >> m;

vector<node>a(n);

vector<int>ans(n, -1);

vector<node>b(m);

for (int i = 0; i < n; i++) {

cin >> a[i].val;

a[i].it = i;

}

for (int i = 0; i < m; i++) {

cin >> b[i].val;

b[i].it = i;

}

sort(a.begin(), a.end(), cmp);

sort(b.begin(), b.end(), cmp);

int i = n - 1, j = m - 1;

while (i >= 0 && j >= 0) {

if (a[i].val <= b[j].val) {

ans[a[i].it] = b[j].it + 1;

i--;

j--;

}

else {

i--;

}

}

for (int i = 0; i < n; i++) {

cout << ans[i] << ' ';

}

cout << endl;

}

}

//3.爬楼梯

n个台阶楼梯，一步最少跨一个台阶，最多跨m个台阶

要求：接下来一步跨的台阶数量，不能和之前两步相同

输出移动到n台阶的方案数量。结果对1e9+7取模

例子：

7 3

输出：

2

解释：

{1 2 3 1}和{1 3 2 1}

其他情况都不符合要求

思路：

这一看就是dp，正好最近刚学。班门弄斧一下

这是一些题变化过来的

变化过程

第一阶段：完全背包、力扣518零钱兑换

这种题：给定一个数n，和一个数组，求组合成n的方案数量（数组中的每个元素随便使用），他对内部的顺序并不要求，（1 2 3）（1 3 2）算一种方案

第二阶段：力扣377组合总和

这个题：是在前面的基础上，规定不同的顺序是不一样的方案，（1 2 3）（1 3 2）算两种方案

第三阶段：就是这个题了

做这个题之前，可以先做一下力扣377，了解那个题之后，再做这个可能更好一点

dp主要就是想状态和方程

因为必须记录每个方案的最后两步所以想一个三维的状态

dp[a][b][c]：走到第c个台阶，最后两步是a、b的方案总数

然后：

遍历n和m（377的思路）

遍历的时候，遍历ab两个维度，加上符合条件的方案。

80%代码

感觉整体思路是没错的，80可能是因为有些细节（比如初始化）没处理好，没时间改了，写完的时候就剩两分钟了

typedef long long ll;

const int mod = 1e9 + 7;

int f[8][8][100005];

int main() {

//ios::sync_with_stdio(false);

//freopen("in.txt", "r", stdin);

int m, n; cin >> n >> m;

f[0][0][0] = 1;

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= m && j <= i; j++) {

for (int k = 0; k <= m; k++) {

for (int t = 0; t <= m; t++) {

if (k != j && t != j) {

f[t][j][i] += f[k][t][i - j];

f[t][j][i] %= mod;

}

}

}

}

}

ll ans = 0;

for (int i = 1; i <= m; i++) {

for (int j = 1; j <= m; j++) {

ans += f[i][j][n];

ans %= mod;

}

}

cout << ans << endl;

}