蓝桥杯真题题解一

一、阶乘约数（数论，2020）

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

定义阶乘 n! = 1 × 2 × 3 × · · · × n。

请问 100!（100 的阶乘）有多少个正约数。

思路

本题实质上是一个模板题，考点是”约数的个数“。

我们对1~100内的所有的数都分解质因数，统计每一个质因数出现的次数，存入cnt[]数组中。根据算术基本定理，约数的个数因为（a1 + 1) * (a2 + 1) * …… * (an + 1)。

#include <iostream>using namespace std;typedef long long LL;const int N = 110;int cnt[N]; //记录的是每个质因子出现的次数int main()
{for(int i = 2; i <= 100; i ++ ) //对1~100内的每个数都分解质因子{int x = i;for(int j = 2; j <= x / j; j ++ ){while(x % j == 0){cnt[j] ++;x /= j; }}if(x > 1) cnt[x] ++; }LL res = 1; //注意最后的答案的范围for(int i = 2; i <= 100; i ++ )if(cnt[i]) res *= (cnt[i] + 1);cout << res << endl;return 0;
}

二、回文日期（枚举，2020）

题目描述

2020 年春节期间，有一个特殊的日期引起了大家的注意：2020 年 2 月 2 日。因为如果将这个日期按 “yyyymmdd” 的格式写成一个 8 位数是 20200202，恰好是一个回文数。我们称这样的日期是回文日期。

有人表示 20200202 是 “千年一遇” 的特殊日子。对此小明很不认同，因为不到 2 年之后就是下一个回文日期：20211202 即 2021 年 12 月 2 日。

也有人表示 20200202 并不仅仅是一个回文日期，还是一个 ABABBABA 型的回文日期。对此小明也不认同，因为大约 100 年后就能遇到下一个 ABABBABA 型的回文日期：21211212 即 2121 年 12 月 12 日。算不上 “千年一遇”，顶多算 “千年两遇”。

给定一个 8 位数的日期，请你计算该日期之后下一个回文日期和下一个 ABABBABA 型的回文日期各是哪一天。

输入描述

输入包含一个八位整数 N，表示日期。

对于所有评测用例，10000101 ≤ N ≤ 89991231，保证 N 是一个合法日期的 8 位数表示。

输出描述

输出两行，每行 1 个八位数。第一行表示下一个回文日期，第二行表示下一个 ABABBABA 型的回文日期。

思路

本题有两种枚举方式，第一种是枚举年月日，第二种是只枚举年。

1）对于第一种枚举方式。需要用三重循环来实现，第一重循环枚举年份，第二重循环枚举月份，第三重循环枚举日期。

且对于年份，我们需要判断以下是否是闰年，闰年的二月份是29天，平年的二月份是28天。

除此之外，还需要注意的是因为题目要求我们是枚举当前日期的下一个回文日期，因此年份可能是从当前年开始，月份可能是从当前月开始，日期则可能是从下一天开始。

/*
输入当前日期，对当前日期取出年份 
1.枚举年份，需要判断枚举的每一个年份是否是闰年
注意下一层枚举月份的初始值应该取决于年份 
1)如果年份是当前年，则月份要从当前月开始 
2.枚举月份（我们还需要将每个月份的天数存入一个数组）
注意下一层枚举日期的初始值也要取决于年份和月份 
3.枚举日期，主要是要注意以下二月份的日期 
4.接下来的主要操作就是判断回文日期了，因为总共只有八个数，因此我们可以
两两的来判断（对于此处，我们可以发现如果日期是一个字符串的话，我们会更容易判断一点） 
最后，对满足条件的结果输出即可 
还有一个可能产生疑惑的问题是，当日期或者是月份是个位数时，
例如2，我们如何将它转化为02 
*/
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;int n, ans;
int month[13] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};bool check1(int date)
{string s = to_string(date);if(s[0] == s[7] && s[1] == s[6] && s[2] == s[5] && s[3] == s[4])return true;return false; 
}bool check2(int date)
{string s = to_string(date);if(s[0] == s[2] && s[0] == s[5] && s[0] == s[7] && s[1] == s[3] && s[1] == s[4] && s[1] == s[6])return true;return false;
}int main()
{cin >> n;int y = n / 10000, m = n / 100 % 100, d = n % 100;for(int i = y; ; i ++ ){if(i % 400 == 0 || (i % 4 == 0 && i % 100 != 0)) month[2] = 29;else month[2] = 28; //注意这里一定要加上else的判断条件，以便日期还原int j = (i == y) ? m : 1;for( ; j <= 12; j ++ ){int k = (i == y && j == m) ? d + 1 : 1;for( ; k <= month[j]; k ++){int date = i * 10000 + j * 100 + k;if(check1(date) && ans == 0) ans = date; //此处一定要加上ans == 0的判断条件，为了避免重复执行这一条语句if(check2(date)) {cout << ans << endl << date << endl;exit(0);}}}}
}
/*
数字转字符串：to_string()
计算字符串的长度：strlen(字符串地址) 
字符串翻转：
strrev：只对字符数字有效，对string类型无效
algorithm中的reverse()函数：reverse()是翻转容器中的内容，对字符数组无效
*/

2）对于第二种枚举方式。我们只是枚举年份，所求的回文日期只需要在枚举年份的基础上构造出结果即可。

同时还需要记得判断以下当前的日期是否合法和是否是回文日期。

ABABBABA型的回文日期只是一种特殊的回文日期。

注：在构造回文日期的过程中，我们可能需要用到一些常用的字符串的函数。诸如，将字符串转化为数字、将数字转化为字符串以及字符串的翻转等。

/*
1.枚举年份
2.构造回文字符串
在构造回文日期的过程中需要涉及到字符串的翻转与拼接操作
个人感觉此部分写一个函数也许会更好看一点 
3.判断回文字符串是否合法
1）包括月份是否合法和日期是否合法
2）且对于特定年份的特定月份，其日期的范围有所不同 
4.还需要判断ABABBABA型的特殊的回文字符串 
*/
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;int n, ans;
int month[13] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};bool is_leap(int year)
{if(year % 400 == 0 || (year % 4 == 0 && year % 100 != 0))return true;return false;
}//判断日期是否合法 
string check1(int date)
{string s = to_string(date), t = to_string(date);reverse(t.begin(), t.end());s += t; //构造回文字符串//将相应的字符串转化为数字，以便判断合法性int y = stoi(s.substr(0, 4)), m = stoi(s.substr(4, 2)), d = stoi(s.substr(6, 2));if(is_leap(y)) month[2] = 29;else month[2] = 28;//若构造出来的字符串的月份或者是日期不合法的话，就返回-1 if(m < 1 || m > 12 || d < 1 || d > month[m])return "-1";return s;
}//判断是否是ABABBABA型的回文字符串 
bool check2(string s)
{if(s[0] = s[2] && s[0] == s[5] && s[0] == s[7] && s[1] == s[3] && s[1] == s[4] && s[1] == s[6])return true;return false;
}int main()
{cin >> n;string start = to_string(n);int date = n / 10000, cnt = 1;for(int i = date; ; i ++ ){string s = check1(i);if(s == start || s == "-1") continue;else{if(cnt){cout << s << endl;cnt --;}if(check2(s)){cout << s << endl;exit(0);}}}return 0;
}
/*
1.截取字符串的某一部分：substr(起始下标，截取长度）
1）注意substr()的用法：前面需指明对哪个字符串进行截取
例如：s.substr(0, 4)是正确的, 而substr(0, 4)则是错误的
2.将字符串变为int型：stoi(s)
3.将字符串变为float型：stoif(i)
4.将字符串变为double型：stoid(i)
5.将字符串变为long long 型：stoill(i) 
*/

三、穿越雷区（搜索，2015）

题目描述 X 星的坦克战车很奇怪，它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转，否则将报废。某坦克需要从 A 区到 B 区去（ A，B 区本身是安全区，没有正能量或负能量特征），怎样走才能路径最短？已知的地图是一个方阵，上面用字母标出了 A，B 区，其它区都标了正号或负号分别表示正负能量辐射区。例如： A + – + – – + – – + – + + + – + – + – + B + – + – 坦克车只能水平或垂直方向上移动到相邻的区。

输入描述第一行是一个整数n ，表示方阵的大小，4 $蓝桥杯真题题解一-编程之家$ n < 100。接下来是 n行，每行有 n个数据，可能是 A，B，+，- 中的某一个，中间用空格分开。A，B 都只出现一次。

输出描述输出一个整数，表示坦克从 A 区到 B 区的最少移动步数。如果没有方案，则输出 -1。

思路

本题是一个简单的搜索题，可以采用BFS或者是DFS来完成。

需要注意的是：本题有一条限制条件是坦克车只能在“+”“-”之间交替行走。

1）BFS。本题是一个在地图上面从起点A出发搜索到终点B的过程，且题目要求的是我们求出从A到B的搜索过程中的最小步数的问题。（为什么BFS可以搜索到最小步数，因为BFS是一层一层的往外拓展的，因此第一次搜索到的一定是满足最小步数的要求的）

/*
1.合理处理输入问题
本道题输入的时候有一点坑，就是相邻的元素之间存在空格
解决办法：我们需要用cin来处理字符串的读入，而不能使用scanf  
2.接下来就是经典的BFS模板，取出队头，对队头拓展 
3.本题还有一个需要注意的地方是：A,B出现的位置不确定，所以我们一开始就得把A的位置预处理出来（其实也只用处理A的位置
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;typedef pair<int, int> PII;const int N = 210;int n, res;
char g[N][N];
bool str[N][N];
int d[N][N]; //存储的是走到每个点所需要的最小步数 
PII q[N * N], st;int bfs()
{int hh = 0, tt = 0;q[0] = st;str[st.first][st.second] = true;d[st.first][st.second] = 0;int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};while(hh <= tt){PII t = q[hh ++ ];if(g[t.first][t.second] == 'B') return d[t.first][t.second];for(int i = 0; i < 4; i ++ ){int a = t.first + dx[i], b = t.second + dy[i];if(a < 0 || a >= n || b < 0 || b >= n) continue;if(g[t.first][t.second] == g[a][b]) continue;if(!str[a][b]){d[a][b] = d[t.first][t.second] + 1;str[a][b] = true;q[++ tt] = {a, b};}}}return -1;
}int main()
{scanf("%d", &n);for(int i = 0; i < n; i ++ )for(int j = 0; j < n; j ++ ){cin >> g[i][j];if(g[i][j] == 'A') st.first = i, st.second = j;}printf("%dn", bfs());return 0;
}

2）DFS（可能会TLE）。当然，本题也可以采用DFS来解决。首先需要明确的是，DFS是一定可以搜到所有可以走到终点的路径的，由于DFS搜索的顺序不一定，因此每一次搜到的路径都并非是最短路。

那我们如何来解决这个问题呢？

我们可以用一个res来保存第一次搜到终点的步数，当我们再次搜索的时候，如果步数一旦大于res就立刻结束搜索；如果成功的搜索到了终点，我们就更新res。这样，最后得到的res就一定是最小步数了。

/*
搜索的顺序：从起点开始遍历
每次遍历当前点的四个方向
同时辅佐可行性剪枝和最优性剪枝 
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int N = 110;int n, res;
char g[N][N];
int vis[N][N];
int x1, y1;void dfs(int x, int y, int cnt) //cnt是走到当前点的步数 
{if(x < 0 || x >= n || y < 0 || y >= n) return;if(cnt > res) return;if(cnt > vis[x][y]) return;if(g[x][y] == 'B'){res = cnt;return;}vis[x][y] = cnt;int tx, ty;//然后就是逐个枚举四个方向tx = x - 1, ty = y;if(g[tx][ty] != g[x][y]) dfs(tx, ty, cnt + 1);tx = x + 1, ty = y;tx = x, ty = y + 1;if(g[tx][ty] != g[x][y]) dfs(tx, ty, cnt + 1);tx = x, ty = y - 1;tx = x + 1, ty = y;if(g[tx][ty] != g[x][y]) dfs(tx, ty, cnt + 1);tx = x - 1, ty = y;tx = x, ty = y - 1;if(g[tx][ty] != g[x][y]) dfs(tx, ty, cnt + 1);tx = x, ty = y + 1;
}int main()
{cin >> n;res = 0x3f3f3f3f;for(int i = 0; i < n; i ++ )for(int j = 0; j < n; j ++ )vis[i][j] = 0x3f3f3f3f;for(int i = 0; i < n; i ++ )for(int j = 0; j < n; j ++ ){cin >> g[i][j];if(g[i][j] == 'A') x1 = i, y1 = j;}dfs(x1, y1, 0);cout << res << endl;return 0; 
}

四、人物相关性分析（字符串，2019）

题目描述小明正在分析一本小说中的人物相关性。他想知道在小说中 Alice 和 Bob 有多少次同时出现。

更准确的说，小明定义 Alice 和 Bob "同时出现" 的意思是：在小说文本中 Alice 和 Bob 之间不超过 K 个字符。

例如以下文本：

This is a story about Alice and Bob.Alice wants to send a private message to Bob.

假设 K = 20，则 Alice 和 Bob 同时出现了 2 次，分别是"Alice and Bob" 和 "Bob. Alice"。前者 Alice 和 Bob 之间有 5 个字符，后者有 2 个字符。

注意: 1. Alice 和 Bob 是大小写敏感的，alice 或 bob 等并不计算在内。 2. Alice 和 Bob 应为单独的单词，前后可以有标点符号和空格，但是不能有字母。例如出现了 Bobbi 并不算出现了 Bob。

输入描述第一行包含一个整数K（1 <= K <= $蓝桥杯真题题解一-编程之家$ ) 第二行包含一行字符串，只包含大小写字母、标点符号和空格。长度不超过 $蓝桥杯真题题解一-编程之家$ 。

输出描述输出一个整数，表示 Alice 和 Bob 同时出现的次数。

思路

这道题目有点复杂，设计到一些优化，但在没有真正敲出代码之前，我们很难确定我们会如何进行优化。因此我们首先需要想到一个朴素的做法，再根据实际的代码实现做出一些具体的改进。

朴素做法。（TLE）我们最容易想到的一种解决方案就是，首先用一层循环遍历一遍整个序列，找到所有的Alice，然后第二层循环再遍历一遍，找到Bob，与此同时判断一下Alice和Bob是否满足条件；如果满足条件，则记录一下出现的次数。

/*
注意本题的输入
使用cin输入字符串时，cin遇到空格就自动停止了，所以cin不适合用来输出带有空格的一段英文文本
如果是按照这种循环的方式来分别确定Alice和Bob的位置的话，好像也没有必要专门开一个数组来存储它们的下标 
*/
#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 1000010;int k, ans;
string s;bool check1 (int i)
{if(s[i] == 'A' && s[i + 1] == 'l' && s[i + 2] == 'i' && s[i + 3] == 'c' && s[i + 4] == 'e'){if((s[i - 1] < 65 || s[i - 1] > 122) && (s[i + 5] < 65 || s[i + 5] > 122)) return true;else return false;}
}bool check2 (int j)
{if(s[j] == 'B' && s[j + 1] == 'o' && s[j + 2] == 'b'){if((s[j - 1] < 65 || s[j - 1] > 122) && (s[j + 3] < 65 || s[j + 3] > 122)) return true;else return false;}
}int main()
{cin >> k;cin.get(); //吸收换行符getline(cin, s); for(int i = 0; i < s.length(); i ++ )if(check1(i)){for(int j = 0; j < s.length(); j ++ ){if(check2(j)){if((j - i - 5 >= 0 && j - i - 5 <= k) || (i - j - 3 >= 0 && i - j - 3 <= k)) ans ++;}}}cout << ans << endl;return 0;
}
/*
cin是c++中最常用的输入语句，当遇到空格或者回车键即停止
gets()可以无限读取，以回车结束读取，c语言中的函数，在c++中运行会产生bug
getline()若定义类型为String类型，则要考虑getline()函数，但需回车两次才能结束输入
cin.get()函数可以接收空格，遇回车结束输入
cin.getline()同cin.get()函数类似，也可接收空格，遇回车结束输入 
*/

复杂度优化。我们可以发现，双层循环＋判断的方法虽然简单，但是由于时间复杂度为 $蓝桥杯真题题解一-编程之家$ ，因此当前的代码一定会TLE。我们有两种解决方案：1）对双层循环+判断进行优化；2）再找其他的办法

对双层循环+判断的方法进行优化。先回顾一下双层循环+判断的过程：

第一层循环遍历整个序列，寻找Alice，时间复杂度为 $蓝桥杯真题题解一-编程之家$ ；

第二层循环还是遍历整个序列，寻找Bob，时间复杂度为 $蓝桥杯真题题解一-编程之家$ ;

最后Alice和Bob是否同时出现，时间复杂度为 $蓝桥杯真题题解一-编程之家$

事实上，第一步和第二步是不冲突的两个操作，即我们只需要一层循环或者不嵌套的两层循环即可找出所有的Alice和Bob。之所以采用嵌套循环，是为了方便第三步的判断。

考虑其他的方法。除了十分暴力的双层循环+判断外，还有一种常见的解题套路—枚举+计算贡献。解释：对于文本中的任意一个Alice，如果和它同时出现的Bob的个数为x个，那么它就能和这x个Bob组成共x对（Alice，Bob）。由于这x对（Alice，Bob）都能对答案的值产生影响，且都和这个Alice相关，因此，我们可以称这个Alice对答案的贡献为x。最终，答案就是文本中所有Alice的贡献总和。

Alice对答案的贡献可分为两部分：1）在它前面的，与Alice中的A相隔字符数不超过k的Bob的个数；2）在它后面的，与Alice中的e相隔字符数不超过k的Bob的个数。如果我们会求第一部分，那么第二部分也就自然会求了。

下面我们就以第二部分为例尝试求解：

假设Alice中的e在文本中的下标为i，那么我们可以确定一点：与该Alice同时出现的Bob中的B下标一定会大于i，也一定会小于i + k + 1。如此看来，我们要求解的其实就是[i + 1, i + k]这个区间内的Bob的数量。

如何求解区间[i + 1, i + k]内Bob的个数呢？

事实上，这个问题就等价于给你一个序列，序列中存在某种特殊数。现在有若干次询问，每次询问会给出一个区间，请你求出该区间内特殊数的个数。接下来我们来做一个等价代换：序列——文本；特殊数——Bob（准确来说是Bob中的B）；若干次询问，每次询问给出一个区间——每次找到一个Alice，就会得到一个特定的区间[i + 1, i + k]（其中i是在变化的，对应的是Alice中A的下标）。

考虑其他的方法之二分。

按照从左到右的顺序将所有特殊数的下标存进一个容器当中，对于每次询问给出的区间[L, R]，二分找出容器中比L大的数的最小数的编号（容器内的编号）、二分找出容器中比R小的最大数的编号（容器内的编号），那么两者相减的值再加1即为所求。

二分时间复杂度： $蓝桥杯真题题解一-编程之家$

/*
1.首先我们需要处理一个特殊数的下标
我们需要开两个vector数组，第一个vector数组存储的是B的下标，第二个vector数组存储的是b的下标
需要注意的是：判断一下Bob的合法性，其前后都只能是标点符号且不能其下标不能越界
2.开始处理一下位于Alice后面的合法的Bob的数量
3.同样的，也要处理一下位于Alice前面的合法的Bob的数量 
*/
#include<bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;bool check(char x)
{if (x >= 'a' && x <= 'z')  return true;if (x >= 'A' && x <= 'Z')  return true;if (x >= '0' && x <= '9')  return true;return false;
}vector<int> B , b;int main()
{int k ; string s;cin >> k;cin.get();getline(cin , s); // 整行读入字符串int n = s.size();B.push_back(-1000000000) , b.push_back(-1000000000);for (int i = 0 ; i < n ; i ++){if (i + 2 < n && s.substr(i , 3) == "Bob"){if (i - 1 >= 0 && check(s[i - 1]) || i + 3 < n && check(s[i + 3]))  continue ;B.push_back(i + 1) , b.push_back(i + 3);}}B.push_back(1000000000) , b.push_back(1000000000);long long ans = 0;for (int i = 0 ; i < n ; i ++ ){if (i + 4 < n && s.substr(i , 5) == "Alice"){if (i - 1 >= 0 && check(s[i - 1]) || i + 5 < n && check(s[i + 5]))  continue ;int A = i + 1 , e = i + 5;// Alice 在 Bob 前面int p1 = upper_bound(B.begin() , B.end() , e + k) - B.begin() - 1; // 找到比e+k大的最小数的下标，把下标-1就是小于等于e+k的最大数的下标。int p2 = lower_bound(B.begin() , B.end() , e) - B.begin();ans += p1 - p2 + 1;// Alice 在 Bob 后面p1 = upper_bound(b.begin() , b.end() , A) - b.begin() - 1; // 找到比A大的最小数的下标，把下标-1就是小于等于A的最大数的下标。p2 = lower_bound(b.begin() , b.end() , A - k) - b.begin();if(b[p2] > A) continue ;ans += p1 - p2 + 1;}}cout << ans << 'n';return 0;
}
/*
1.注意substr的用法：它的作用是截取某一段字符串
s.substr(起始坐标，字符串的长度），其中s指明它要截取的字符串 
一定要主要这里指的是字符串的长度，并不是终点坐标，要不然真的容易搞错
2.upper_bound和lower_bound使用：都是利用二分查找在一个排好序的数组中进行查找
使用前提：这两个函数默认是在按从小到大的序列中进行查找 
lower_bound(begin, end, num):从数组的begin位置到end - 1位置二分查找第一个大于等于(>=)num的数字，找到返回该数字的地址 
upper_bound(begin, end, num):从数组的begin位置到end - 1位置二分查找第一个大于(>)num的数字，找到返回该数字的地址
在vector容器中二分查找元素写起来有点子麻烦，这里就直接用函数来代替了 
*/

五、砝码称重（DP，2021）

问题描述

你有一架天平和 N个砝码，这 N个砝码重量依次是 $蓝桥杯真题题解一-编程之家$ ， $蓝桥杯真题题解一-编程之家$ ，……， $蓝桥杯真题题解一-编程之家$ 。请你计算一共可以称出多少种不同的重量？注意砝码可以放在天平两边。

输入格式输入的第一行包含一个整数N 。第二行包含 N个整数： $蓝桥杯真题题解一-编程之家$ ， $蓝桥杯真题题解一-编程之家$ ，……， $蓝桥杯真题题解一-编程之家$ 。

输出格式输出一个整数代表答案。

评测用例规模与约定对于 50% 的评测用例，1 <= N <= 15 。对于所有评测用例，1 <= N <= 100,N个砝码总重不超过100000 。

思路

1）如果我们暂时想不出这道题目是动态规划问题的话，我们至少可以先想到暴力的方法（DFS）。分析可知对于每一个砝码，我们都有三种选择，放在左边，放在右边或者是不放。所以时间复杂度应为 $蓝桥杯真题题解一-编程之家$ ，可以帮助我们过掉部分数据。

对于暴力搜索（TLE）来说，最重要的就是搜索的顺序。那么我们如何搜索才能保证我们不重不漏的搜索到所有的方案呢？我们可以顺次考虑所有的砝码，对于每一个砝码我们都有三种选择，如果画成一颗搜索树的话，就对应着三个分支，放好第一个砝码之后，我们再放置第二个砝码，依次类推，直到我们放置好第n个砝码之后，结果自然也就出来了。

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 110;int n, ans;
int a[N], s[100000]; //s[x] = 1表示当前重量已经被称出来了 void dfs(int u, int left, int right)
{if(u > n){s[max(left, right) - min(left, right)] = 1;return;}dfs(u + 1, left + a[u], right);dfs(u + 1, left, right + a[u]);dfs(u + 1, left, right);
} int main()
{cin >> n;for(int i = 1; i <= n; i ++ ) cin >> a[i];dfs(1, 0, 0); //从第1个砝码开始摆放，此时左边的重量为0，右边的重量也为0 for(int i = 1; i <= 100000; i ++ ) //注意是正整数数量，因此i应该从1开始 if(s[i]) ans ++;cout << ans << endl;return 0;
}

2）考虑用动态规划解决，整体步骤可以分为三步。设计状态数组，设置初始状态，推导转移方程。

设计状态数组：我们设计一个boolean型的数组d[i][j]，其所代表的含义为：d[i][j] = true表示用前i个砝码可以称出重量为j的物体；d[i][j] = false表示用前i个砝码不可以称出重量为j的物体。在我们求解完所有的数组之后，我们遍历d[n][i ~ j]，求出里面true的个数，就可以这些砝码一共可以称量的物体的重量。

设置初始状态：起初，天平的两端并未放置任何的物体，天平处于平衡状态，我们可以认为它称出了重量为0的物体，因此，d[0][0] = true。

推导转移方程：假设我们现在已经处理完了第i – 1个砝码，那么在处理完第i个砝码之后，天平所能称出的重量根据第i个砝码不同的处理方式得到三种不同的结果，分别为：

j + a[i]：将第i个砝码放在较重的那一侧

j – a[i]：将第i个砝码放在较轻的那一侧

j：两侧都不放

注意：对于j – a[i]可能会出现j – a[i] < 0的情况，为了放置数组的下标越界产生错误，我们需要加上一个偏移量

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 110, M = 1e5 + 10, off = 1e5; int n, ans;
int a[N], d[N][2 * M];int main()
{cin >> n;for(int i = 1; i <= n; i ++ ) cin >> a[i];d[0][0 + off] = 1;for(int i = 1; i <= n; i ++ )for(int j = 0; j <= M + off; j ++ ){if(j - a[i] >= 0) d[i][j] = d[i][j] | d[i - 1][j - a[i]];d[i][j] |= d[i - 1][j + a[i]] | d[i - 1][j];}for(int i = 1 + off; i < M + off; i ++ ) //因为题目要求的是称出来的结果是正整数，所以i从1 + off开始if(d[n][i]) ans ++;cout << ans << endl;return 0;
}
/*
'|'是位运算符，表示按位或的意思 
*/