- 博客(209)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 背包问题整理
动态规划中很经典的一类问题就是背包问题……01背包问题描述：有n个物品，每个物品体积为v[i]，价值为w[i]，每个物品只能选一次，现有一个背包体积大小为V，问如何选择物品使得装入背包里的价值总和最大。分析：定义状态f[i][j]为前i个物品装j体积大小能得到的最大价值。int f[n][V];for (int i = 1; i <= n; ++i) { for (int j = 1; j <= V; ++j) { if (v[i] > j) { f[i][j] =
2021-03-09 15:45:59
197
原创 牛客 F - 爬塔 （分组背包）
中国计量大学现代科技学院第四届“中竞杯”程序设计校赛（同步赛）F - 爬塔链接：https://ac.nowcoder.com/acm/contest/9680/F题目描述高川最喜欢的游戏当属 Slay the Spire，这是一款爬塔游戏，你需要从一座塔的底部一直爬到顶部，在爬塔的过程中，塔的每一层都有许多的宝物等你来拿。高川从塔的左侧开始攀爬，从底部爬到顶部，再从右侧从顶部逐步下到底部。塔总共有 n 层，每一层都有很多宝物从左到右排列。在左侧攀爬时，他只能从每层的最左边按顺序取宝物，在右侧下降时
2021-03-09 15:45:17
237
原创 牛客 J - 全排列（思维）
中国计量大学现代科技学院第四届“中竞杯”程序设计校赛（同步赛）J - 全排列链接：https://ac.nowcoder.com/acm/contest/9680/J题目描述白浅经过一段时间对字符串的学习之后，学会了如何使用递归输出一个字符串的所有全排列（虽然 C++ 中有自带的函数），甚至学会了如何输出所有去重后的全排列（即“本质不同的全排列”）！她拿到了一个字符串 S，现在她将 S 的所有本质不同的全排列按字典序大小进行排序。假如总共有 k 个本质不同的字符串，则这些字符串按照字典序大小分别编号为
2021-03-09 15:44:34
230
原创 Codeforces Round #687 (Div. 2, based on Technocup 2021 Elimination Round 2)
Codeforces Round #687 (Div. 2, based on Technocup 2021 Elimination Round 2)A. Prison Break题意：给出 n×m 的矩阵，每个点表示一个囚犯，移动一次时间为1，可同时移动，每个点上可以同时有多个囚犯，求让所有点移动到 (r,c) 点的最短的时间。思路：输出 (1,1)、(1,m)、(n,1)、(n,m) 四个点到 (r,c) 的最小距离的最大值。#include <iostream>#include
2021-03-09 15:43:29
162
原创 Coins HDU - 2844（多重背包 模板题）
http://acm.hdu.edu.cn/showproblem.php?pid=5572题目大意有n种面值的硬币，每种硬币有c[i]个，问1~m之间的所有价值，能用这些硬币组合出来的个数是多少个。(1≤n≤100), (m≤100000)分析明显的多重背包。把每种硬币二进制拆分优化。详细看 背包问题整理#include <bits/stdc++.h>using namespace std;const int N = 2e5 + 10;int a[110], c[110];
2021-03-09 15:37:20
131
原创 Trie字典树例题
前几天做了个Trie树的题，正好记一下。首先先看一个简单题AcWing 143. 最大异或对题目在给定的N个整数A1，A2……AN中选出两个进行 xor（异或）运算，得到的结果最大是多少？第一行输入一个整数N。第二行输入N个整数A1～AN。输出一个整数表示答案。1≤N≤105,0≤Ai<2311≤N≤10^5, 0≤A_i<2^311≤N≤105,0≤Ai<231Solution这个题看数据范围应该是O(nlogn)级别内的，先看暴力做法就是枚举Ai和Aj，这样是O
2021-03-09 15:35:49
163
原创 2019 ICPC Asia Nanjing Regional 题解
2019 ICPC Asia Nanjing RegionalA. A Hard Problem题意：给定一个正整数n，你需要找到最小整数k，对于大小为k的集合{1,2,3…n}的任何子集里，都存在两个不同的整数u，v，u是v的因子。思路：因子最小是2，所以从大到小找两倍。#include <iostream>using namespace std;int main() { int T, n; cin >> T; while (T--) {
2020-12-03 15:23:05
695
原创 求一个正整数的因子数与因子和
设正整数 nnn 唯一分解后为 n=p1a1+p2a2+...+pkakn=p_1^{a_1}+p_2^{a_2}+...+p_k^{a_k}n=p1a1+p2a2+...+pkak因子数：(a1+1)∗(a2+1)∗...∗(ak+1)(a_1+1)*(a_2+1)*...*(a_k+1)(a1+1)∗(a2+1)∗...∗(ak+1)因子和：(1+p1+p12+...+p1a1)∗(1+p2+p22+...+p2a2)∗...∗(1+pk+pk2+...+pkak)(1+p_1+
2020-11-22 12:21:29
899
原创 2020 China Collegiate Programming Contest Qinhuangdao Site-重现赛 7-6 Friendly Group（Tarjan 或 并查集）
7-6 Friendly Group题目Sample Input24 51 21 31 42 33 42 11 2Sample OutputCase #1: 1Case #2: 0分析把他们之间的好朋友关系对应到图上，两个人是好朋友的话，他们之间连一条边，显然环是要满足的最低要求，在一个环中，点和边个数一样，对答案的贡献是0，如果不是环，那么点的个数大于边数，那么对答案的贡献是负的。最后就是要对无向图强联通分量缩点，记下每个强联通分量中的点的个数和边的个数。code
2020-10-20 18:24:03
713
原创 Educational Codeforces Round 96 (Rated for Div. 2) （A - F）
Educational Codeforces Round 96 (Rated for Div. 2)A - Number of Apartments题意给一个数n，输出一组a，b，c，使得 3×a+5×b+7×c=n3\times a+5\times b+7\times c=n3×a+5×b+7×c=n ，输出任意一组解。（1≤t≤10001≤t≤10001≤t≤1000 ，1≤n≤10001≤n≤10001≤n≤1000）分析先考虑枚举，先枚举 5b 和 7c，判断 (n-5b-7c)%3==0
2020-10-15 22:08:54
286
原创 卡特兰数
卡特兰数卡特兰数 - 百度百科卡特兰数又称卡塔兰数，英文名Catalan number，是组合数学中一个常出现于各种计数问题中的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名，其前几项为（从第零项开始） : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6
2020-10-14 21:27:02
165
原创 求欧拉函数值
欧拉函数[SDOI2008]仪仗队题目链接const int N = 100000 + 10;int phi[N];int prime[N];bool vis[N];//即可以求出素数，还可以求出欧拉函数值void Euler() { int cnt = 0; phi[1] = 1; for (int i = 2; i < N; i++) { if (vis[i] == false) { prime[cnt++] = i;
2020-10-06 22:28:23
932
1
原创 马拉车算法例题 -- P3805 【模板】manacher算法、P1659 [国家集训队]拉拉队排练
马拉车模板看这个P3805 【模板】manacher算法code#include <iostream>#include <algorithm>#include <string>using namespace std;class Solution {public: static int longestPalindrome(const string &s) { int len = s.length();
2020-10-03 19:09:14
132
原创 马拉车算法求最长回文子串（模板）
Manacher 算法模板时间复杂度：O(N)O(N)O(N) ，由于 Manacher 算法只有在遇到还未匹配的位置时才进行匹配，已经匹配过的位置不再匹配，因此对于字符串 S 的每一个位置，都只进行一次匹配，算法的复杂度为 O(N)O(N)O(N) 。空间复杂度：O(N)O(N)O(N) 。五分钟学算法教程老司机开车，教会女朋友什么是「马拉车算法」codeclass Manacher1 {public: static string longestPalindrome(strin
2020-10-02 17:12:16
120
原创 P3373 【模板】线段树 2（区间乘+区间加）
P3373 【模板】线段树 2题目链接既有区间乘又有区间加，那么乘和加的顺序很关键先乘后加：a∗b+ca*b+ca∗b+c ，自然没什么影响先加后乘：(a+b)∗c=a∗c+b∗c(a+b)*c=a*c+b*c(a+b)∗c=a∗c+b∗c ，如果我们不进行处理，仅仅单独做乘和加的标记，就会变得混乱我们只需要对加法标记乘上 ccc 就行，也就是把这个式子的括号展开都变成加。code#include <iostream>#include <algorithm>#i
2020-09-29 16:44:44
87
原创 P3387 【模板】缩点（Tarjan缩点，拓扑序上dp）模板
P3387 【模板】缩点题目链接#include <iostream>#include <algorithm>#include <vector>#include <cstdio>#include <stack>#include <queue>#define sc(x) scanf("%d", &(x))#define sca(x, y) scanf("%d%d", &(x), &(y))#d
2020-09-25 16:03:51
149
转载 Min_25 筛法求素数和（模板）
Min_25 筛法求素数和大佬同学的模板求1~N的素数和，可以求 1e101e101e10 范围内的。#include <bits/stdc++.h>using namespace std;using ll = long long;const int N = 1000000 + 10;int prime[N], id1[N], id2[N], flag[N], ncnt, m;ll g[N], sum[N], a[N], T;ll n;int ID(ll x) {
2020-09-24 21:40:18
461
原创 Til the Cows Come Home POJ - 2387（Dijkstra模板 优先队列优化）
Til the Cows Come HomePOJ - 2387#include <cstdio>#include <vector>#include <queue>#include <cstring>using namespace std;typedef pair<int, int> pii;const int INF = 0x3f3f3f3f;const int N = 1000 + 5;struct node {
2020-09-23 21:33:07
117
原创 P3385 【模板】负环 （spfa模板，判断负环）
P3385 【模板】负环题目链接code#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <string>#include <vector>#include <stack>#include <queue>using namespace std;const int N = 3
2020-09-17 19:39:48
96
原创 高精度乘高精度（模板、压位）
ADV-353 高精度乘法蓝桥杯算法提高http://lx.lanqiao.cn/problemset.page?code=ADV-&userid=301004code#include <cstdio>#include <cstring>using namespace std;const int N = 10005;char str_a[N], str_b[N];int a[N], b[N], c[N << 1];int main() {
2020-09-16 09:35:58
134
原创 A Simple Problem with Integers POJ - 3468（线段树模板，区间修改，区间查询）
A Simple Problem with IntegersPOJ - 3468code#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <vector>#include <queue>using namespace std;typedef long long ll;const int N = 10
2020-09-15 12:10:04
79
原创 POJ-2352 Stars（树状数组模板）
StarsPOJ-2352树状数组下标是从1开始。#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <vector>#include <queue>using namespace std;const int N = 15005, M = 32005, INF = 0x3f3f3f3f;int n;
2020-09-14 21:06:45
111
原创 HDU-1698 Just a Hook（线段树模板，懒标记区间修改）
HDU-1698 Just a Hook/* * HDU-1698 Just a Hook * http://acm.hdu.edu.cn/showproblem.php?pid=1698 */#include <iostream>#include <algorithm>#include <cstring>#include <vector>#include <queue>using namespace std;const
2020-09-14 20:02:49
79
原创 I Hate It POJ - 1754（线段树 模板）
I Hate Ithttp://acm.hdu.edu.cn/showproblem.php?pid=1754线段树区间最大值，单点修改，区间查询。code#include <iostream>#include <algorithm>#include <cstring>using namespace std;const int N = 200005;int tree[N << 2];#define ls(x) (x <<
2020-09-13 20:59:00
86
原创 手写小根堆
小根堆int heap[1000], tot = 0;void insert_heap(int x) { tot++; heap[tot] = x; int i = tot; int j = i / 2; while ((j > 0) && heap[j] > heap[i]) { swap(heap[j], heap[i]); i = j; j = i / 2; }}in
2020-09-13 17:47:22
263
1
原创 敌兵布阵 HDU-1166（线段树 单点修改 区间查询）
/** 敌兵布阵 HDU-1166 线段树-单点修改-区间查询-敌兵布阵HDU-1166 */#include <iostream>#include <string>#define N 50005using namespace std;int n;int sum[N << 2];void push_up(int root) { sum[root] = sum[root << 1] + sum[root << 1 |
2020-09-13 10:04:07
116
原创 A Simple Problem with Integers POJ - 3468（线段树 区间修改 区间查询）
//A Simple Problem with Integers POJ - 3468//线段树-区间修改-区间查询#include <cstdio>#define N 100010typedef long long ll;ll sum[N << 2];ll lazy[N << 2];ll x;void push_up(int root) { sum[root] = sum[root << 1] + sum[root <<
2020-09-13 10:02:37
86
原创 小A盗墓 upc（线段树）
/*upc问题 E: 小A盗墓时间限制: 5 Sec 内存限制: 128 MB题目描述小A终于通过了保安的考验，来到了古墓门前，古墓门前有n根柱子，第i根柱子的高度是整数。古墓的门上会弹出一些暗号，机智小A猜到这个暗号表示询问第l到第r根柱子的高度在升序排序后是否构成一段连续且上升的序列。并且这些柱子的高度还可能在弹出暗号的过程中出现变化。现在小A需要回答出每个暗号的答案输入第一行两个整数，表示柱子的个数n以及操作的个数m。第二行n个整数，第i个整数表示第i根柱子的高度。接下来
2020-09-13 10:01:03
75
原创 牛客 A 古老的牛市，遗迹的天梯（dp）
https://ac.nowcoder.com/acm/contest/5968/A#include <bits/stdc++.h>using namespace std;int a[500], dp[500]; // dp[i]走到第i阶的最小步数int main() { int n; cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i]; }
2020-09-13 09:03:42
174
原创 牛客 [CQOI2010]扑克牌（二分答案+验证）
[CQOI2010]扑克牌题目链接题目描述你有n种牌，第i种牌的数目为ci。另外有一种特殊的牌：joker，它的数目是m。你可以用每种牌各一张来组成一套牌，也可以用一张joker和除了某一种牌以外的其他牌各一张组成1套牌。比如，当n=3时，一共有4种合法的套牌：{1,2,3}, {J,2,3}, {1,J,3}, {1,2,J}。 给出n, m和ci，你的任务是组成尽量多的套牌。每张牌最多只能用在一副套牌里（可以有牌不使用）。输入描述:第一行包含两个整数n, m，即牌的种数和joker的个数。第
2020-09-12 20:51:32
991
原创 牛客 K-th Number（二分答案+验证）
K-th Number题目链接题意：对数列A的每个长度大于等于K的区间取其第K大的数，插入到B中，再求B的第M大数。code// 对数列A的每个长度大于等于K的区间取其第K大的数，插入到B中，再求B的第M大数#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 1e5 + 5;ll n, k, m;int a[N];bool check(ll x) // B中第M大
2020-09-12 15:13:00
253
原创 P3376 【模板】网络最大流（Dinic模板）
code#include <bits/stdc++.h>using namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;const ll INFF = 0x3f3f3f3f3f3f3f3f;const ll MOD = 1e9 + 7;const int M = 1e6 + 5;const int N = 1e5 + 5;int n, m, s, t;// Dinic 每次寻找最短的增广路，并沿着..
2020-09-11 11:25:07
99
原创 牛客NC50999 表达式计算4（递归计算）
NC50999 表达式计算4题目链接题目描述给出一个表达式,其中运算符仅包含 +, -, *, /, ^（加 减 乘 整除 乘方）要求求出表达式的最终值数据可能会出现括号情况，还有可能出现多余括号情况数据保证不会出现 ≥231\geq 2^{31}≥231 的答案数据可能会出现负数情况code#include <bits/stdc++.h>using namespace std;string s;int qpow(int a, int b){ int res
2020-09-10 21:49:50
314
原创 博弈论 取石子（反 Nim 博弈）
字符串游戏阿里云 天池 超级码力在线编程大赛初赛 第3场描述Alice与Bob在一起玩一个游戏。现在有一个字符串s，每个人可以选择字符串中的某一个区间和一种字符，删除这个区间内的所有该字符（需要删除字符的数量至少为1）。从Alice开始，Alice与Bob轮流进行进行这个操作，若在某个玩家删除前，字符串已经为空，则该玩家获胜。假设Alice和Bob都会按照其最优的解法删除，Alice想知道，她是否可以获胜。1≤len(s)≤1000001\le len(s) \le 1000001≤len(s)≤
2020-09-06 21:09:06
412
原创 二叉苹果树（树形DP）
二叉苹果树题目链接code#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int, int> pii;typedef pair<ll, ll> pll;const int INF = 0x3f3f3f3f;const ll INFF = 0x3f3f3f3f3f3f3f3f;const ll MOD = 1e9 + 7;const int M
2020-08-31 20:14:38
303
原创 Codeforces Round #665 (Div. 2)（A - E）
Codeforces Round #665 (Div. 2)A Distance and Axis题意在X正半轴上有点 A=nA=nA=n，我们想找到一个整数点 B（也在OX轴上），使得 OBOBOB 的距离减 ABABAB 的距离的绝对值等于 kkk ，如果B找不到，可以将A点每次左移或右移一个单位，知道找到一个B点。求A的最少移动次数。Solution如果k大于n，那么B一定在A右边，就变成了 OB−AB=OAOB-AB=OAOB−AB=OA 的距离是k，就把A移动到k位置。如果k小于等于n
2020-08-25 22:10:15
194
原创 LeetCode 207.课程表（拓扑排序）
solutionbfs实现。注意题目中的边缘列表要转换成邻接表。codeclass Solution {private: vector<vector<int>> edge; vector<int> indeg;public: bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { edge.resize(nu.
2020-08-04 09:54:57
112
原创 NC53676 「土」秘法地震（二维前缀和）
链接：https://ac.nowcoder.com/acm/problem/53676题目描述帕秋莉掌握了一种土属性魔法这种魔法可以在一片k×k大小的一个正方形区域内产生地震但是如果某片即将产生地震的区域内有建筑物，帕秋莉会停止施法整个地图大小为n×m，其中一些地方有建筑请问有多少种可能的情况，使得帕秋莉会停止施法输入描述:第一行三个数n, m, k，意义见描述接下来一个n×m的01矩阵表示这篇区域的情况，1表示这个地方有建筑输出描述:输出一个数表示答案输入4 4 21000
2020-08-03 19:00:43
148
原创 NC14734 比赛（dp）
链接：https://ac.nowcoder.com/acm/problem/14734题目描述你在打比赛，这场比赛总共有12个题对于第i个题，你的队伍有a[i]的几率解决她如果解决不了她呢？由于所有人讨论的都很大声所以你有b[i]的概率从左边那个队那里听会这个题的做法有c[i]的概率从右边那个队那里听会这个题的做法请问最终你们队伍解出0-12题的概率分别是多少输入描述:第一行12个数表示a[1] -> a[12]第二行12个数表示b[1] -> b[12]第三行12个数
2020-08-03 16:35:44
174
原创 NC15034 德玛西亚万岁（状压dp）
链接：https://ac.nowcoder.com/acm/problem/15034题目描述德玛西亚是一个实力雄厚、奉公守法的国家，有着功勋卓著的光荣军史。这里非常重视正义、荣耀、职责的意识形态，这里的人民为此感到强烈自豪。有一天他们想去制裁邪恶的比尔吉沃特，于是派遣了自己最优秀的战士。结果比尔吉沃特领土太小，只有长为n宽为m共计n*m块土地，其中有些土地标记为0表示为高山峻岭或者深海湖泊，英雄们无法在其中站立，只有标记为1的土地才能容纳一个英雄。德玛西亚的英雄们战斗时有一个特点，他们不
2020-08-03 11:27:28
311
DOSBox-0.74.zip
2020-07-11
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人