有一块月饼，是正三角形的，又被分割成了许多块小正三角形的月饼，里面有若干块被吃掉了。现在想要在这块月饼中再找一个由小正三角形月饼的正三角形月饼，而且要求面积最大的。
样例解释：
大月饼的分解情况如图，灰的表示已被吃掉的月饼，白的表示未被吃的。最大的是由9个小月饼组成的（黑色粗线标记）。
输入单组测试数据。 第一行给出一个整数n (1 <= n <= 100)，表示三角形月饼的高度。 接下来n行，用#, -表示该行三角形月饼的状态，#表示已经被吃掉的，－表示未被吃掉的。 从第一行到最后一行每行的字符的数目总是奇数个，并且是从2*n-1到1递减的。输出
输出一个整数，表示找到的最大的月饼中包含的小三角形个数。输入样例
5 #-##----# -----#- ---#- -#- -输出样例
9代码 (something wrong)
#include2. 数塔取数问题#define N 105 #pragma GCC optimize(2) using namespace std; int a[N][N], b[N][N], dpA[N][N], dpB[N][N]; int main() { ios::sync_with_stdio(false); int n; cin >> n; string s; for (int i = 0; i < n; ++i) { cin >> s; for (int j = 0; j < (s.size() + 1 >> 1); j++) { if (s[2 * j] == '-') a[i][j] = 1; if (2 * j + 1 < s.size() && s[2 * j + 1] == '-') b[i][j] = 1; } } int ans = 0; for (int i = 0, prev1, prev2; i < n; ++i) { for (int j = 0; j < n - i; j++) { if (a[i][j] == 1) { prev1 = i > 0 ? dpA[i - 1][j] : 0; prev2 = i > 0 ? dpA[i - 1][j + 1] : 0; dpA[i][j] = min(prev1, prev2) * (i > 0 && b[i - 1][j] == 1) + 1; ans = max(ans, dpA[i][j]); } } for (int j = 0; j < n - i; j++) { if (b[i][j] == 1) { prev1 = j > 0 ? dpB[i][j - 1] : 0; prev2 = i > 0 ? dpB[i - 1][j] : 0; dpB[i][j] = min(prev1, prev2) * (a[i][j] == 1) + 1; ans = max(ans, dpB[i][j]); } } } cout << ans * ans; return 0; }
一个高度为N的由正整数组成的三角形，从上走到下，求经过的数字和的最大值。
每次只能走到下一层相邻的数上，例如从第3层的6向下走，只能走到第4层的2或9上。
5
8 4
3 6 9
7 2 9 5
例子中的最优方案是：5 + 8 + 6 + 9 = 28
输入第1行：N，N为数塔的高度。(2 <= N <= 500) 第2 - N + 1行：每行包括1层数塔的数字，第2行1个数，第3行2个数......第k+1行k个数。数与数之间用空格分隔（0 <= A[i] <= 10^5) 。输出
输出最大值输入样例
4 5 8 4 3 6 9 7 2 9 5输出样例
28代码
#include3. 制铁棒#define N 505 #pragma GCC optimize(2) using namespace std; using ull = unsigned long long; ull a[N][N]; int main() { ios::sync_with_stdio(false); int n; cin >> n; for (int i = 0; i < n; ++i) { for (int j = 0; j <= i; ++j) { cin >> a[i][j]; } } for (int i = 1; i < n; ++i) { for (int j = 0; j <= i; ++j) { a[i][j] += max(j > 0 ? a[i - 1][j - 1] : 0, a[i - 1][j]); } } cout << *max_element(a[n - 1], a[n - 1] + n); return 0; }
工厂里面，有n根待加工的铁棒，长度以米为单位，精确到小数点后两位（即厘米），现在市场上需求量是m根相同长度的铁棒。现在厂长想把这n根铁棒进行切割，切割的时候要精确到厘米，比如说，原来铁棒是1.00米的，那么可以切成0.50和0.50的，但是不能切成0.499和0.501的。并且不能将两根铁棒拼成一根铁棒。现在厂长想知道切出来的m根铁棒最长能有多长。
输入单组测试数据。 第一行给出两个整数n(1 <= n<= 10000)和m(1 <= m< = 10000)。 接下来n行给出原始铁棒的长度L[1],L[2],L[3],...,L[n] ，(1<=L[i]<=100,000)。以米为单位，精确到小数点后两位。输出
输出一个小数表示答案，精确到小数点后两位。输入样例
4 11 8.02 7.43 4.57 5.39输出样例
2.00代码
#include4. 子段统计#define N 10005 #pragma GCC optimize(2) using namespace std; int a[N]; int n, m, maxLength = numeric_limits ::min(); bool check(int length) { int cnt = 0; for (int i = 0; i < n; ++i) { cnt += a[i] / length; } return cnt >= m; } int main() { ios::sync_with_stdio(false); cin >> n >> m; double val; for (int i = 0; i < n; ++i) { cin >> val; a[i] = val * 100; maxLength = max(maxLength, a[i]); } int lo = 1, hi = maxLength + 1; while (lo < hi) { int mi = lo + ((hi - lo) >> 1); check(mi) ? lo = mi + 1 : hi = mi; } cout << fixed << setprecision(2) << (lo - 1) / 100.0 << endl; return 0; }
给定一个字符串S，只由k种小写字母组成。现在给定一个长度L，要求统计一下S有多少种不同的长度为L的子段(S中连续的几个字符)。
输入第一行两个整数L和k。（L>=1，1<=k<=26,k^L<=2*10^7） 第二行一个字符串S。（1<=|S|<=1000000）输出
输出一个整数表示答案。输入样例
1 2 ababab输出样例
2代码
#include5. 炮兵阵地 v1#pragma GCC optimize(2) using namespace std; int main() { ios::sync_with_stdio(false); unordered_set uset; int l, k; cin >> l >> k; string s; cin >> s; for (int i = 0; i + l <= s.size(); i++) { uset.insert(s.substr(i, l)); } cout << uset.size() << endl; return 0; }
司令部的将军们打算在 N × M Ntimes M N×M 的网格地图上部署他们的炮兵部队。
一个 N × M Ntimes M N×M 的地图由 N N N 行 M M M 列组成，地图的每一格可能是山地（用 H texttt{H} H 表示），也可能是平原（用 P texttt{P} P 表示），如下图。
在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。
图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
输入第一行包含两个由空格分割开的正整数，分别表示 N 和 M。 接下来的 N 行，每一行含有连续的 M 个字符，按顺序表示地图中每一行的数据。输出
一行一个整数，表示最多能摆放的炮兵部队的数量。输入样例
5 4 PHPP PPHH PPPP PHPP PHHP输出样例
6代码
#include参考：【题解】洛谷 2704炮兵阵地（NOI2001） 6. 炮兵阵地 v2#pragma GCC optimize(2) using namespace std; int n, m, ans, dp[(1 << 10)][(1 << 10)][3], a[105], Sum[(1 << 10)]; char x; int main() { ios::sync_with_stdio(false); cin >> n >> m; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> x, a[i] <<= 1, a[i] += (x == 'H' ? 1 : 0); for (int i = 0; i < (1 << m); i++) Sum[i] = __builtin_popcount(i); for (int S = 0; S < (1 << m); S++) if (!(S & a[0] || (S & (S << 1)) || (S & (S << 2)))) dp[0][S][0] = Sum[S]; for (int L = 0; L < (1 << m); L++) { if (L & a[0] || (L & (L << 1)) || (L & (L << 2))) continue; for (int S = 0; S < (1 << m); S++) if (!(L & S || S & a[1] || (S & (S << 1)) || (S & (S << 2)))) dp[L][S][1] = Sum[S] + Sum[L]; } for (int i = 2; i < n; i++) for (int L = 0; L < (1 << m); L++) { if (L & a[i - 1] || (L & (L << 1)) || (L & (L << 2))) continue; for (int S = 0; S < (1 << m); S++) { if (L & S || S & a[i] || (S & (S << 1)) || (S & (S << 2))) continue; for (int FL = 0; FL < (1 << m); FL++) { if (FL & L || FL & S || FL & a[i - 2] || (FL & (FL << 1)) || (FL & (FL << 2))) continue; dp[L][S][i % 3] = max(dp[L][S][i % 3], dp[FL][L][(i - 1) % 3] + Sum[S]); } } } for (int L = 0; L < (1 << m); L++) for (int S = 0; S < (1 << m); S++) ans = max(ans, dp[L][S][(n - 1) % 3]); //结束状态可以是最后一行的任何状态 cout << ans; return 0; }
司令部的将军们打算在 N ∗ N N*N N∗N的网格地图上部署他们的炮兵部队。一个 N ∗ N N*N N∗N的地图由 N N N行 N N N列组成，地图的每一格可能是山地（用"X"表示），也可能是平原（用"."表示）。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围是它所在位置的对应的行和列，但是大炮打出去之后如果被山地阻挡 了，那么攻击范围就到那块山地。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
输入单组测试数据。 第一行有一个整数N(1<=N<=4)。 接下来N行，每行有N个字符（只有两种字符：'.' 表示平原， 'X'表示山地）。输出
一行一个整数，表示最多能摆放的炮兵部队的数量。输入样例
4 .X.. .... XX.. ....输出样例
5代码
#include#define N 5 #pragma GCC optimize(2) using namespace std; int n, ans = 0; bool grid[N][N]; bool used[N][N]; bool check(int x, int y) { int i = x; while (++i < n && grid[i][y]) { if (used[i][y]) return false; } i = x; while (--i >= 0 && grid[i][y]) { if (used[i][y]) return false; } i = y; while (++i < n && grid[x][i]) { if (used[x][i]) return false; } i = y; while (--i >= 0 && grid[x][i]) { if (used[x][i]) return false; } return true; } void dfs(int cur) { ans = max(ans, cur); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] && !used[i][j] && check(i, j)) { used[i][j] = true; dfs(cur + 1); used[i][j] = false; } } } } int main() { ios::sync_with_stdio(false); cin >> n; char ch; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { cin >> ch; if (ch == '.') grid[i][j] = true; } } dfs(0); cout << ans; return 0; }
