#include<bits/stdc++.h> #define endl "\n" #define int long long using namespace std; void slove() { int n, m; std::cin >> n >> m; std::vector<int> h(n + 1), x(n + 1); for (int i = 1; i <= n; i++) std::cin >> h[i]; std::map<int, int> mp; std::vector&lt...

#include<bits/stdc++.h> #define endl "\n" #define int long long using namespace std; void slove() { int n, m, x; std::cin >> n >> m >> x; std::vector<int> a(n + 2), fa(n + 1); for (int i = 1; i <= n; i++) std::cin >> a[i], fa[i] = i; auto find = [&amp...

#include<bits/stdc++.h> #define endl "\n" #define int long long using namespace std; struct node { int l, r, sum; } tree[4 * 100010]; const int mod = 1e9 + 7; void slove() { int n, q; std::cin >> n >> q; std::vector<int> a(n + 1); for (int i = 1; i <= n; i++) std...

#include<bits/stdc++.h> #define endl "\n" #define int long long using namespace std; struct node { int l, r, cnt, laz; } tree[500010 * 4]; void slove() { int n, q; std::cin >> n >> q; std::string s; std::cin >> s; s = ' ' + s; auto build = [&](auto&& bui...

#include<bits/stdc++.h> #define endl "\n" #define int long long using namespace std; int d[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; void slove() { int n; std::cin >> n; std::vector<std::vector<int>> a(n + 2, std::vector<int>(n + 2, 0)); for (int i = 1; i &l...

#include<bits/stdc++.h> #define endl "\n" #define int long long using namespace std; void slove() { int n; std::cin >> n; std::vector<std::vector<int>> edge(n + 1); std::vector<std::pair<int, int>> a(n + 1); std::vector<int> vis(n + 1); for (int i ...

#include<bits/stdc++.h> #define endl "\n" #define int long long using namespace std; void slove() { std::string s; std::cin >> s; int cnt0 = 0, cnt1 = 0; for (auto c : s) { if (c == '0') cnt0++; else cnt1++; } if (cnt0 % 2 == cnt1 % 2) { if (cnt1 & 1) { std::cout << &...

#include<bits/stdc++.h> #define endl "\n" #define int long long using namespace std; struct node { int u, v, w; bool operator <(const node& t)const { return w > t.w; } }; void slove() { int n; std::cin >> n; std::unordered_map<int, int> mp; std::vector<node&g...

#include<bits/stdc++.h> #define endl "\n" #define int long long using namespace std; int dp[200010][2][2];// 1 biao 1 li void slove() { int n, k; std::cin >> n >> k; std::vector<int> a(n + 1), b(n + 1); for (int i = 1; i <= n; i++) std::cin >> a[i]; for (in...

贪心。要凑到最大的数量，让可以更改的位置的数值更改成为上一个离自己最近位置并且有数值的数-x。注意如果减到小于值域下限，我们可以直接更改为值域上限。这样做的目的是方便让后面的可更改位置产生贡献。凑最小的答案，就一直让可更改位置的数值更改为上一个值-x+1即可。 #include<bits/stdc++.h> #define endl "\n" #define int long long using namespace std; /*inline __int128 read(){ __int128 x = 0, f = 1; char ch = getchar()...

分层图最短路 链接：https://ac.nowcoder.com/acm/problem/236176 来源：牛客网 做法：直接去连边的话因为数据范围过大，所以会出现tle的现象，也有段错误的现象不知道是为什么，所以对于层与层之间的边，我们建立一个平台，同层的点到这个平台的距离为0，层与层之间的距离为c，那注意不能建立一个双向的平台，这样的话会出现一些不存在的边，所以要建立一个向上的路径和向下的路径分别为i+n和i+2n，之后就是特殊边正常连，然后跑dij即可，spfa可能为卡，但如果数据弱的话也是能过的。 //本题代码 #include<bits/stdc++.h> #defi...

链接：https://ac.nowcoder.com/acm/problem/236173 来源：牛客网 有一片群岛，总共有30001个岛屿，编号从0到30000，其中有 n 个宝藏在这些岛屿中。Kitayuta是一位宝藏猎人，他初始在0号岛屿上。为了获得宝藏，他按照如下规则经过这些岛屿：  ​ 他第一步从 0 号岛屿跨越 d 个岛屿到达 d 号岛屿。 ​ 接下来每一步，他只能前往编号更大的岛屿。并且，假设他前一步跨越了 x 个岛屿，那么他下一步只能跨越 y 个岛屿，其中 y∈{x−1,x,x+1} 且 y>=1 。如果下一步没有可以到达的岛屿，Kitayuta就会停止寻找宝藏。  假设...

货船 链接：https://ac.nowcoder.com/acm/problem/236172 来源：牛客网 有 n个货物，需要装入货船，第 i 个货物的重量是 wi 。货船的最大载重量是 A ，请问在不超过货船最大载重量的前提下，一次最多能运送多少重量的货物。 做法：一眼是01背包，但是无论是物品数量还是重量上限都超过了复杂度和空间复杂度，所以选择去优化背包，01背包其实就是选和不选的选择，非常适合用01字符串去表示，正好可以用stl中的bitset去解决，对于两个状态的字符串，如果这个物品不选，两个状态字符串是相同的，选择这个物品的话，就是多加了a【i】这么多的重量。对于字符串来说就是每...