神秘花
变种 \(01\) 背包，原题链接。
回忆普通的 \(01\) 背包，\(dp[j]\) 代表容量为 \(j\) 时所能得到的最大价值，这样操作的时间复杂度为 \(O(nV)\)（其中 \(n\) 代表物品数量，\(V\) 代表容量）。
但是在本题中，\(V\) 的范围是 \(10^9\)。
观察发现，本题中的价值 \(k_i\) 较小，\(O(n\cdot \sum k_i)=O(n^2\cdot \max {(k_i)})\)，这样的复杂度可以接受。
所以考虑更换 \(dp\) 状态，用 \(dp[j]\) 来表示价值达到 \(j\) 时所需要的最小容量。
状态转移方程即为：\(dp_j = \min(dp_j, dp_{j - k_i} + v_i)\)。
最后从大到小遍历，找到最大的 \(dp_i \le V\) 的 \(i\) 即为最终答案。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 1e5 + 7;
int n, V, sum;
int v[107], k[107];
i64 dp[N];
int main()
{cin >> n >> V;for (int i = 1; i <= n; i++){cin >> v[i] >> k[i];sum += k[i];}memset(dp, 0x7f, sizeof(dp));dp[0] = 0;for (int i = 1; i <= n; i++){for (int j = sum; j >= k[i]; j--){dp[j] = min(dp[j], dp[j - k[i]] + v[i]);}}for (int i = sum; i > 0; i--){if (dp[i] <= V){cout << i << '\n';return 0;}}return 0;
}
树
该题一共可以分为
-
图的建立与存储
邻接表（链式前向星）和 \(vector\) 均可，此处使用 \(vector\)。
-
树的深度和宽度统计
通过一遍 \(dfs\) 即可统计每个点的深度，同时统计每种深度的个数，即可求出树的深度和宽度。
-
树上距离的统计
树上距离可以先求出两点之间的 \(lca\) 后，然后便可直接通过深度差求出距离。
什么？你不会求 \(lca\)？
罚你去看 Zvelig 的博客
这个题数据范围很小，可以直接暴力求。
什么？你不知道什么是 \(lca\)？
罚你去看 Zvelig 的博客
好的你应该看完了。
记录每个结点的父结点，当结点 \(x\) 与结点 \(y\) 深度不同时，我们选择较深的结点去寻找其父结点，直到结点的深度相同。此时若两结点已经相同，则说明已经找到 \(lca\)；否则两个结点同时寻找各自的父结点，直到两结点相同，此时即找到 \(lca\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 7;
vector<int> e[N];
int fa[N], dep[N], bre[N];
int maxd, maxb;
void dfs(int now)
{dep[now] = dep[fa[now]] + 1;maxd = max(maxd, dep[now]);bre[dep[now]]++;maxb = max(maxb, bre[dep[now]]);for (auto p : e[now])dfs(p);
}
int lca(int x, int y)
{if (dep[x] < dep[y])swap(x, y);while (dep[x] > dep[y])x = fa[x];if (x == y)return x;while (x != y)x = fa[x], y = fa[y];return x;
}int n, m;
void _()
{cin >> n;for (int i = 1; i < n; i++){int u, v;cin >> u >> v;fa[v] = u;e[u].push_back(v);}dfs(1);cout << maxd << '\n';cout << maxb << '\n';cin >> m;for (int i = 1; i <= m; i++){int x, y;cin >> x >> y;int l = lca(x, y);cout << (dep[x] - dep[l]) * 2 + (dep[y] - dep[l]) << '\n';}
}
signed main()
{int qwq = 1;// cin >> qwq;while (qwq--)_();return 0;
}
当你看懂了这个代码，就可以考虑对于数据范围为 \(n=10^5\) 时应该如何解决该问题。
去看 Zvelig 的博客就会了
学习一下倍增就可以了，其他的不用管。
黄教的题
总有人与我不期而遇在迷茫的路口
观察到数据范围很小，只有 \(1 \le |s| \le 3000 , \sum|s| \le 3000\)，所以 \(O(n^2)\) 的复杂度可以接受。
只需要枚举长度 \(len\)，然后判断当前 \(len\) 的前后缀是否相同（即是否为 border）即可。
注意枚举时要保证 \(<len\) 而非 \(\le len\)。
#include <bits/stdc++.h>
using namespace std;
void _()
{string s;cin >> s;int len = s.size(), ans = 0;for (int i = 1; i < len; i++){bool pd = 1;for (int l = 0, r = len - i; l < i; l++, r++){if (s[l] != s[r]){pd = 0;break;}}if (pd){ans = max(ans, i);}}cout << ans << '\n';
}
signed main()
{int qwq = 1;cin >> qwq;while (qwq--)_();return 0;
}
当数据范围扩大到 \(10^5- 10^6\) 时，则需要考虑字符串哈希或 KMP 算法。
为我再次寻回遗失在现实角落的梦
贪心的将最大的 \(k\) 个或者最小的 \(k\) 个放到第一组，剩下的放到第二组。
所以 sort 之后求前缀和，然后每次计算两种情况中两组的差即可。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void _()
{int n, q;cin >> n >> q;vector<i64> a(n + 7), sum(n + 7);for (int i = 1; i <= n; i++)cin >> a[i];sort(a.begin() + 1, a.begin() + n + 1);for (int i = 1; i <= n; i++)sum[i] = sum[i - 1] + a[i];while (q--){int k;cin >> k;cout << max((sum[n] - sum[k]) - sum[k], (sum[n] - sum[n - k]) - sum[n - k]) << endl;}
}
signed main()
{// ios::sync_with_stdio(0);// cin.tie(0), cout.tie(0);int qwq = 1;while (qwq--)_();return 0;
}
\(I/O\) 量较大，如超时可考虑关流。
记得使用 long long。
Whizney 的题
Whizneyの小小游戏！
一个很有意思的递推题，也可以是找规律题。
用 \(f_i\) 来代表产生一个 \(2^i\) 块时会得到的得分。
首先分析初始条件：块 \(2\) 不会产生任何得分，块 \(2^2=4\) 会获得 \(4\) 点得分。
然后，当产生块 \(2^i(i>2)\) 时，此时已经有了两个 \(2^{i-1}\) 块的得分，新块的得分为 \(2^i\)。
所以就有递推公式：\(f_i=f_{i-1} * 2 +2^i\)，进一步分析可得 \(f_i=(i-1)\times 2^i\)（数学归纳法可证明）。
最后通过最终得分便可分析每个块的数量。
从大到小枚举每个块，然后判断当前得分下，该块能有几个，并计算除去该块后的得分。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct node
{i64 val;int num;node() {}node(i64 val, int num) : val(val), num(num) {}
};
void _()
{int n, cnt;cin >> n;vector<i64> a(n + 7);i64 maxn = 0;for (int i = 1; i <= n; i++){cin >> a[i];maxn = max(maxn, a[i]);}vector<i64> f(107);f[2] = 4;for (int i = 3; i <= maxn; i++){f[i] = f[i - 1] * 2ll + (1ll << i);cnt = i;if (f[i] > maxn)break;}for (int i = 1; i <= n; i++){vector<node> ans;for (int j = cnt; j > 1; j--){int k = a[i] / f[j];a[i] %= f[j];ans.push_back(node(1ll << j, k));}if (a[i]){puts("miao?");continue;}for (auto i : ans){if (i.num)cout << i.val << ' ' << i.num << '\n';}}
}
signed main()
{int qwq = 1;while (qwq--)_();return 0;
}
小鸟公主の新冒险！
Floyd 经典板子题，建议搜索关键字自行学习
--Whizney
Floyd 本质上是一种 dp 思想，可以处理很多二元组的关系。
本题中注意处理重边和自环即可。
以及边权较大，记得开 long long。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 inf = 1e12 + 7;
void _()
{int n, m;cin >> n >> m;vector<vector<i64>> dis(n + 7, vector<i64>(n + 7, inf));for (int i = 1; i <= m; i++){int u, v;i64 w;cin >> u >> v >> w;dis[u][v] = min(dis[u][v], w);dis[v][u] = min(dis[v][u], w);}for (int i = 1; i <= n; i++)dis[i][i] = 0;for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);int q;cin >> q;while (q--){int u, v;cin >> u >> v;if (dis[u][v] == inf)cout << "404 NOT FOUND" << '\n';elsecout << dis[u][v] << '\n';}
}
signed main()
{int qwq = 1;while (qwq--)_();return 0;
}