1.6万

codeep
iiiiiiire
Cauchy

wangyinuo23
37_1
M_137
_LRJ_

zzlhh

ShanLin
nooprush

ssdaf

wayne.fio

4/13

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5+10;

int n, m, a[N];

int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> a[i];
sort(a, a+n, greater<int>());

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

for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
for (int k = j+1; k < n; k++)
{
// cout << a[i] << ' ' << a[j] << ' ' << a[k]<< endl;
int sum = a[i]+a[j]+a[k];
if (sum % m == 0)
{
cout << sum;
return 0;
}
}

return 0;
}


4/13

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5+10;

int n, m, a[N];

int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> a[i];
sort(a, a+n, greater<int>());

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

for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
for (int k = j+1; k < n; k++)
{
// cout << a[i] << ' ' << a[j] << ' ' << a[k]<< endl;
int sum = a[i]+a[j]+a[k];
if (sum % m == 0)
{
cout << sum;
return 0;
}
}

return 0;
}


### 爆搜

dfs(u, i+1, sum+i); //实际上 i+1 应该是 i

#include <iostream>

using namespace std;

const int N = 15;

int n, m, q, res;
int num[N];
bool vi[N];

void dfs(int u, int start, int sum) //组合枚举， 0~n 选m 个，使和为n
{
if (u == m) //当选了m 个数
{
if (sum == n) res++;
return;
}

if (start > n) return; //剪枝，不过这题范围小，没用

for (int i = start; i <= n; i++)
dfs(u+1, i, sum+i); //下一个位置，从i 开始， 下一个位置还能从i 选
}

int main()
{
cin >> q;

while (q--)
{
cin >> n >> m;
res = 0;
dfs(0, 0, 0); //从第一个位置开始枚举，从0 开始枚举，总和为0
cout << res << endl;
}

return 0;
}


#include <iostream>

using namespace std;

const int N = 15;

int f[N][N]; //f[i, j]:总和为i, 个数为j 的方案数量
int q, n, m;

int main()
{
cin >>q;

while (q--)
{
cin >> n >> m;

f[0][0] = 1; //总和为0，不选的方案数量为1
for (int i = 0; i <= n; i++) //要从0开始推，因为初始从f[0][0]开始
for (int j = 1; j <= m; j++)
{
f[i][j] = f[i][j-1];
if (i >= j) f[i][j] += f[i-j][j]; //这里要保证数组不越界，才会判断i >= j
}

cout << f[n][m] << endl;
}

return 0;
}


### 爆搜

dfs(u, i+1, sum+i); //实际上 i+1 应该是 i

#include <iostream>

using namespace std;

const int N = 15;

int n, m, q, res;
int num[N];
bool vi[N];

void dfs(int u, int start, int sum) //组合枚举， 0~n 选m 个，使和为n
{
if (u == m) //当选了m 个数
{
if (sum == n) res++;
return;
}

if (start > n) return; //剪枝，不过这题范围小，没用

for (int i = start; i <= n; i++)
dfs(u+1, i, sum+i); //下一个位置，从i 开始， 下一个位置还能从i 选
}

int main()
{
cin >> q;

while (q--)
{
cin >> n >> m;
res = 0;
dfs(0, 0, 0); //从第一个位置开始枚举，从0 开始枚举，总和为0
cout << res << endl;
}

return 0;
}


#include <iostream>

using namespace std;

const int N = 15;

int f[N][N]; //f[i, j]:总和为i, 个数为j 的方案数量
int q, n, m;

int main()
{
cin >>q;

while (q--)
{
cin >> n >> m;

f[0][0] = 1; //总和为0，不选的方案数量为1
for (int i = 0; i <= n; i++) //要从0开始推，因为初始从f[0][0]开始
for (int j = 1; j <= m; j++)
{
f[i][j] = f[i][j-1];
if (i >= j) f[i][j] += f[i-j][j]; //这里要保证数组不越界，才会判断i >= j
}

cout << f[n][m] << endl;
}

return 0;
}


1≤n≤1000

### 输入样例:

5


### 输出样例:

7


#include <iostream>

using namespace std;

const int N = 1010, MOD = 1e9+7;

int f[N][N]; //f[i, j]:选到第i 个数字，背包容量为j,方案数量
int n;

int main()
{
cin >> n;

for (int i = 0; i <= n; i++) f[i][0] = 1; //每个数字都不选的方案为1

for (int i = 1; i <= n; i++)
for (int j = 0; j <= n; j++)
{
f[i][j] = f[i-1][j] % MOD; //先不选
if (j >= i) //若容量够
f[i][j] = (f[i-1][j] + f[i][j-i]) % MOD;
}

cout << f[n][n];

return 0;
}


#include <iostream>

using namespace std;

const int N = 1010;

int n, f[N][N]; //f[i, j]:总和为i, 个数为j 的方案数量

int main()
{
cin >> n;

f[0][0] = 1; //总和为0，不选的方案数量为1
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
f[i][j] = f[i-1][j-1] + f[i-j][j];

int res = 0;
for (int i = 1; i <= n; i++) res += f[n][i];

cout << res;

return 0;
}


#### 注

1、因为一直在往字符串后面走，碰到一个字符就会跳到下一个位置，所以这里不用设置左右孩子的参数
2、中序遍历是先访问根节点，再递归左子树，再递归右子树。之前写错了是在左括号那里碰到了左括号的时候，要递归到下一层，加上括号中间的数量。访问到右括号的时候，我们跳出本层递归，返回的是左括号那一层的递归。

if (s[k] == '(') //若碰到左括号，递归求字符数量
{
k++; //跳过左括号
res += dfs();
}

else if (s[k] == ')') //若是右括号
{
k++; //跳过右括号
break; //跳过本层递归，返回右子树数量
}


#include <iostream>

using namespace std;

string s;
int k;

int dfs()
{
int res = 0; //这一层递归中碰到x 的数量

while (k < (int)s.size())  //从当前位置开始往后判断字符
{
if (s[k] == '(') //若碰到左括号，递归求字符数量
{
k++; //跳过左括号
res += dfs();
k++; //跳过右括号
}
else if (s[k] == ')') //若是右括号
{
//k++; //右括号已经在左括号那里跳过了
break; //跳过本层递归，返回右子树数量
}
else if (s[k] == '|') //递归左右子树
{
k++; //跳过或
res = max(res, dfs()); //求左右子树最大值
}
else k++, res ++; //数量++,到下一个位置
}

return res;
}

int main()
{
cin >> s;
cout << dfs();

return 0;
}


#### 注

1、因为一直在往字符串后面走，碰到一个字符就会跳到下一个位置，所以这里不用设置左右孩子的参数
2、中序遍历是先访问根节点，再递归左子树，再递归右子树。之前写错了是在左括号那里碰到了左括号的时候，要递归到下一层，加上括号中间的数量。访问到右括号的时候，我们跳出本层递归，返回的是左括号那一层的递归。

if (s[k] == '(') //若碰到左括号，递归求字符数量
{
k++; //跳过左括号
res += dfs();
}

else if (s[k] == ')') //若是右括号
{
k++; //跳过右括号
break; //跳过本层递归，返回右子树数量
}


#include <iostream>

using namespace std;

string s;
int k;

int dfs()
{
int res = 0; //这一层递归中碰到x 的数量

while (k < (int)s.size())  //从当前位置开始往后判断字符
{
if (s[k] == '(') //若碰到左括号，递归求字符数量
{
k++; //跳过左括号
res += dfs();
k++; //跳过右括号
}
else if (s[k] == ')') //若是右括号
{
//k++; //右括号已经在左括号那里跳过了
break; //跳过本层递归，返回右子树数量
}
else if (s[k] == '|') //递归左右子树
{
k++; //跳过或
res = max(res, dfs()); //求左右子树最大值
}
else k++, res ++; //数量++,到下一个位置
}

return res;
}

int main()
{
cin >> s;
cout << dfs();

return 0;
}


104. 货仓选址（贪心）（找中位数）

 #include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long LL;

const int N = 1e6+10;

int n, a[N];
int c[N]; //存的是每个人与平均值之间差的糖果数量，后来更新为前缀和

int main()
{
cin >> n;
LL sum = 0;
for (int i = 1; i <= n; i++)
cin >> a[i], sum += a[i];

LL ave = sum / n;
for (int i = 1; i <= n; i++) //前缀和
c[i] = c[i-1] + a[i] - ave;
sort(c+1, c+n+1); //将前缀和排序

LL res = 0, mid = c[(n+1) / 2]; //下标从1 开始的中位数
for (int i = 1; i <= n; i++)
res += abs(c[i] - mid);

cout << res;

return 0;
}


104. 货仓选址（贪心）（找中位数）

 #include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long LL;

const int N = 1e6+10;

int n, a[N];
int c[N]; //存的是每个人与平均值之间差的糖果数量，后来更新为前缀和

int main()
{
cin >> n;
LL sum = 0;
for (int i = 1; i <= n; i++)
cin >> a[i], sum += a[i];

LL ave = sum / n;
for (int i = 1; i <= n; i++) //前缀和
c[i] = c[i-1] + a[i] - ave;
sort(c+1, c+n+1); //将前缀和排序

LL res = 0, mid = c[(n+1) / 2]; //下标从1 开始的中位数
for (int i = 1; i <= n; i++)
res += abs(c[i] - mid);

cout << res;

return 0;
}


### 数据范围

$1≤T≤50，1≤N≤1e5$

### 输入样例：

2
3
1 8 2
4
10 7 6 14


### 输出样例：

8
24


### dp分析

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5+10;

int w[N], f[N]; //f[i]:抢到第i 家店的现金数量，属性：max
int n, q;

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

f[1] = w[1]; //初始化第一家店能抢到的最大
for (int i = 1; i <= n; i++)
f[i] = max(f[i-1], f[i-2] + w[i]);

cout << f[n] << endl;
}

return 0;
}


### dp状态机

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5+10, INF = 0x3f3f3f3f;

int w[N], f[N][2]; //f[i][j]:抢到第i 家店，j为0：不抢，为1：抢。属性：max
int n, q;

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

f[0][1] = -INF; //第0家店抢了的状态不合法
f[0][0] = 0;
for (int i = 1; i <= n; i++)
{
f[i][0] = max(f[i-1][0], f[i-1][1]);
f[i][1] = f[i-1][0] + w[i];
}

cout << max(f[n][0], f[n][1]) << endl;
}

return 0;
}