|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 柿子饼同学 于 2024-8-29 15:59 编辑 各种计数... 但是没有那么难
对于描述状态要细分, 少了什么就加, 注意别重复
首先确定阶段, 即如何完成任务
然后描述状态分类, 转移
计数类问题要想哪些和哪些是无关的, 可以一起算
对于状态的变化, 考虑是由哪些操作变出来的, 提供转移的思路
正难则反
总情况数减去不合法情况数
计算贡献
A - 网格删边
f[i, j, 0/1] 前 i 列, 删除 j 个边, 是否连通的方案数
B - 染色边
发现只有同对角线上的才会互相影响, 每个对角线是并列的
于是预处理每个对角线长度的方案数, 然后预处理乘积
C - 分段 i
D - 神秘密码
状压
E - 树上连通块个数
给定一棵树
记 f(i, j) 表示所有编号在区间 [i, j] 的点在树上形成的联通块的个数。
对于所有的区间[i. j]的f(i, j)求和
一个结论, 一些点构成的连通块个数等于 这些点的个数 - 这些点直接相互连边的个数
然后先求总数, 对于每条边减去贡献
- cin >> n;
- // 假设没有边, 那么所有的 f 的和
- for (int i = 1; i <= n; i++) {
- ans += 1ll * (n - i + 1) * i;
- }
- // 有边了, 减去一些东西
- for (int i = 1; i < n; i++) {
- ll u, v;
- cin >> u >> v;
- if (u > v)
- swap(u, v);
- ans -= u * (n - v + 1);
- }
- cout << ans;
复制代码
F - 灵魂之树的三重考验
高维的运算可以由低维的堆出来
- // 现在对于一个点 u, 她的子树 (包括她的父节点上面的那个树) 大小分别是 a[1]...a[n]
- // f[i] 表示第 3 个数是 a[i], 前面两个数是 x, y (在 1...i-1 选) 的和
- // 不好求, 降维
- // g[i] 表示第 2 个数是 a[i], 前面一个数是 x (在 1...i-1 选) 的和
- // 现在 f[i] = a[i] * g[i]
- // g[i] = a[i] * s[i], s 是 a 的前缀和, 完成了
- // s[i] = s[i - 1] + a[i]
- // ans += f[i]
复制代码
G - 区间表达式
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const ll P = 998244353;
- string s;
- ll cur, sum, digit_s, k;
- ll ans;
- int main(){
- ios::sync_with_stdio(0);
- cin.tie(0);
-
- cin >> s;
- for(auto i : s){
- if(isdigit(i)){
- digit_s++;
- // i 自己也算
- k++;
- // cur 计算的是连续数字段的所有贡献
- // 这样子可以和 sum 拼起来就是完整的贡献
- cur = (cur*10 + k * (i - '0')) % P;
- // ... + ... + ... ](1) + ... * ... * ..i
- // i是右端点, 左端点可以取 (1) 处
- // 左端点可以取 (1) + 1 到 i 处
- ans = (ans + sum + cur) % P;
- }
- else if(i == '+'){
- // 如果是加号, 后面的每个数字会被算 (前面有几个数字) 次
- // sum 代表 i 前面的所有表达式的和, 连续乘积不能算进去
- sum += cur;
- k = digit_s;
- cur = 0;
- }
- else{
- // 如果是乘号, 后面的每个数会被计算 cur 次
- k = cur;
- cur = 0;
- }
- }
- cout << ans;
-
- return 0;
- }
复制代码
I - 色子
遇到小的数字想状压, 然后对于取不到的需要加上取不到的概率
J - 小数拆分
对于一个集合增长我们需要总结出经过了哪几类操作
K - 狼人
树形背包, 注意不能实时更新 f , 并且注意转移顺序
对于这种连边限制的题想想是否是一款树
L - 火柴棒等式
数据范围变成了 3e4
可以考虑同时枚举两个数, 算上进位
- // l 代表是否是第 1 位(不是第一位的话填 0 就无法截断, 第一位的话填什么都行) , d 代表进位, a, b 分别代表 A, B 是否截断了
- int dfs(int sum, bool l, bool d, bool a, bool b) {
- if (a && b)
- // 可能有进位
- return (!d && !sum) || (d && sum == 2);
- int& res = f[sum][l][d][a][b];
- if (~res)
- return res;
- res = 0;
- for (int x = 0; x <= (a ? 0 : 9); x++)
- for (int y = 0; y <= (b ? 0 : 9); y++) {
- int z = (x + y + d) % 10;
- int nsum = sum - (a ? 0 : t[x]) - (b ? 0 : t[y]) - t[z];
- bool nd = x + y + d > 9;
- // 分类讨论能否给 A, B 截断处理
- if (nsum < 0)
- continue;
- if (!a && !b)
- Add(res, dfs(nsum, 0, nd, 0, 0));
- if (!a && (y || b || l))
- Add(res, dfs(nsum, 0, nd, 0, 1));
- if ((x || a || l) && !b)
- Add(res, dfs(nsum, 0, nd, 1, 0));
- if ((x || a || l) && (y || b || l))
- Add(res, dfs(nsum, 0, nd, 1, 1));
- }
- return res;
- }
复制代码
|
|