搜索结果
查询Tags标签： 计数问题，共有 10条记录-
[codeforces]第6天
今天是正赛：Codeforces Round #785 (Div. 2) AB很快过了，没什么难度，C是一个完全背包计数问题，我想了好久都没想到 一开始以为跟牛客寒假营的一道题类似，结果没找到，后来发现是牛客另一场比赛的 我其实挺确定是dp的，我就一直在那找转移关系，把前面几个数怎么来的推…
2022/5/1 6:16:15 人评论 次浏览 -
LOJ #6089. 小 Y 的背包计数问题
题面传送门 奇妙的思维(技巧?)题。 发现每个物品有\(i\)个，体积为\(i\)，对于\(i>\sqrt n\)的物品来说，这个个数的限制是相当于没有的。所以相当于完全背包。 前面\(O(\sqrt n)\)个可以暴力多重背包算方案数。 考虑后面\(n\)个最多选择\(O(\sqrt n)\)个。所以可以设…
2022/4/9 23:19:27 人评论 次浏览 -
计数问题
计数问题P1179 [NOIP2010 普及组] 数字统计 题目描述 请统计某个给定范围[L,R]的所有整数中，数字2出现的次数。 比如给定范围[2,22]，数字2在数2中出现了1次，在数12中出现1次，在数20中出现1次，在数21中出现>1次，在数22中出现2次，所以数字2在该范围内一共出现了6次…
2022/2/7 6:12:30 人评论 次浏览 -
逆序对计数问题
7-4 求逆序对数目 (20 分)注意：本问题算法的时间复杂度要求为O(nlogn), 否则得分无效 题目来源：http://poj.org/problem?id=1804 Background Raymond Babbitt drives his brother Charlie mad. Recently Raymond counted 246 toothpicks spilled all over the floor in…
2021/9/21 6:27:21 人评论 次浏览 -
逆序对计数问题
7-4 求逆序对数目 (20 分)注意：本问题算法的时间复杂度要求为O(nlogn), 否则得分无效 题目来源：http://poj.org/problem?id=1804 Background Raymond Babbitt drives his brother Charlie mad. Recently Raymond counted 246 toothpicks spilled all over the floor in…
2021/9/21 6:27:21 人评论 次浏览 -
dijsktra次短路计数问题
题目链接：https://www.acwing.com/problem/content/385/ 次短距离一定只能由次短距离更新 代码： #include <iostream>#include <cstring>#include <algorithm>#include <queue>#include<vector>using namespace std;const int N = 2010,M…
2021/8/20 23:10:21 人评论 次浏览 -
dijsktra次短路计数问题
题目链接：https://www.acwing.com/problem/content/385/ 次短距离一定只能由次短距离更新 代码： #include <iostream>#include <cstring>#include <algorithm>#include <queue>#include<vector>using namespace std;const int N = 2010,M…
2021/8/20 23:10:21 人评论 次浏览 -
[做题笔记] 浅谈状压dp在图计数问题上的应用
无向图计数 题目描述 点此看题 有一个 \(n\) 个点 \(m\) 条边的无向图，对于每个 \(k\) 求出有多少种保留边的方案使得 \(1\) 能到 \(k\) \(n\leq 17,m\leq {n\choose 2}\) 解法 设 \(dp[s]\) 表示 \(1\) 能到集合 \(s\)，只考虑集合 \(s\) 中的边的方案数，转移考虑总方案…
2021/8/9 23:07:10 人评论 次浏览 -
[做题笔记] 浅谈状压dp在图计数问题上的应用
无向图计数 题目描述 点此看题 有一个 \(n\) 个点 \(m\) 条边的无向图，对于每个 \(k\) 求出有多少种保留边的方案使得 \(1\) 能到 \(k\) \(n\leq 17,m\leq {n\choose 2}\) 解法 设 \(dp[s]\) 表示 \(1\) 能到集合 \(s\)，只考虑集合 \(s\) 中的边的方案数，转移考虑总方案…
2021/8/9 23:07:10 人评论 次浏览 -
数位DP - AcWing 338 - 计数问题
数位DP - AcWing 338 - 计数问题 注意前导0的影响 #include <bits/stdc++.h> using namespace std;int a, b; int num[10]; int dp[10][10]; // 当前填位i,tar数已经出现的次数j int dfs(int i, int j, int flag, int first, int tar){if(!i) return j;if(!flag &am…
2021/4/19 10:56:27 人评论 次浏览
