#牛客春招刷题训练营# + 链接首先将问题分解为 \型对角线 加上 /型对角线，这两条线是有交点的，但需要注意交点有可能不在边界交点不在边界时，最终个数是其中一条个数的两倍；交点在边界时，最终个数是其中一条个数的两倍再减1于是可以只分析 \型对角线，此时通过约分 a 和 b 的最大公约数 g 继续分解为子问题新的 a' b' 互质后，显然有个数=(a'+1)+(b'+1)-2=a'+b' ，且与 x y 均无关（水平边上a'+1个，竖直边上b'+1个，减去最外面2个重复的端点）然后扩大 g 倍，也就是去掉右下角的点复制 g 遍，再加回右下角的点，(a'+b'-1)*g+1最后把 g 乘进去就不...

#牛客春招刷题训练营# + 链接区间dp经典题啦先套路复制一遍解环，然后用dp[i][j]表示第i颗到第j颗聚合完之后的最优值，每次枚举最后是哪两段聚合就可以 #include <iostream> using namespace std; using ll = long long; const int mod=1e9+7; const int N=210; ll dp[N][N], a[N]; inline void getmax(ll &x, ll y) { if (y>x) x=y; } int main() { int n,m; scanf("%d&...

#牛客春招刷题训练营# + 链接动态规划经典问题第0阶段只有0体积设置为0，其他都设置为负无穷即可。 #include <bits/stdc++.h> using namespace std; const int INF=1e9; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<int> dp(m + 1, -INF); vector<int> v(n), w(n); for (int i = 0; i <...

#牛客春招刷题训练营# + 链接简单的倍数知识，n个x的倍数最短是 (n-1)*x+1，最长是 (n+1)*x-1，分类讨论一下 #include <cstdio> #include <iostream> using namespace std; int main() { unsigned n,k,x; scanf("%u%u%u", &n,&k,&x); if ((n-1)*x < k && k < n*x) { printf("%u %u\n", x, x+k-1); } e...

#牛客春招刷题训练营# + 链接通过优先选择结束时间最早且与前一个选定活动不冲突的活动，来最大化可以安排的活动数量。1.将所有活动按结束时间升序排序。2.遍历每个活动，对于一个活动，如果它的开始时间晚于或等于上一个选中活动的结束时间，则安排此活动。复杂度：时间复杂度O(nlogn)，空间复杂度O(n)。 #include <algorithm> #include <bits/stdc++.h> using namespace std; using PII = pair<int,int>; const int MAXN=200010; PII a[MAXN];...

#牛客春招刷题训练营# + 链接容易发现，只有全0的子串“自审值”才是0，因此计算全0子串的个数（res），从总数中减去顺序扫描的同时维护左侧最近的1的位置，扫描到0时作为右端点计算处理询问时，当第l位为0时res可能会包含左端点在区间外面的子串，需要特殊处理减去单次询问复杂度O(1) #include <bits/stdc++.h> using namespace std; using ll = long long; const int MAXN=200010; char s[MAXN]; int prep[MAXN], sufp[MAXN]; ll presy[MAXN]; i...

#牛客春招刷题训练营# + 链接想了半天最终决定还是暴力题目没有保证输入不重复，先判重，重了肯定不能单调然后遍历抽出哪一段，不在该段的全都插到平衡树里面，移动时只需要插一个数删一个数，单次复杂度O(logn)每次遍历在平衡树中查询（最小数）和（最大数+1）的序号，如果相等则说明当前这段可以插入到排序后的数组里另外，对于遍历的段，需要保证它本身是单调的，这个用简单计数器维护一下就可以了，具体可以看代码 #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_...

#牛客春招刷题训练营# + 链接假定染色后的气球形如 xxxyyyzzz ，三个区间的右端点分别为i,j,n用 s(x,i) 表示前i个气球中所有原本是x色的染色费用和则有 cost=(s(y,i)+s(z,i))+((s(x,j)-s(x,i))+(s(z,j)-s(z,i)))+((s(x,n)-s(x,j))+(s(y,n)-s(y,j)))简化可得 cost=s(x,n)+s(y,n)+(s(y,i)-s(x,i))+(s(z,j)-s(y,j))因此可以再维护(s(y,i)-s(x,i))的前缀最小值，使复杂度降为O(n)显然，xyz的枚举可以直接调用全排列函数最后，再通过设置i跟0...

#牛客春招刷题训练营# + 链接题意显然是并查集维护size，但是n平方复杂度是不对的从and考虑按位遍历，稍微注意下细节 #include <bits/stdc++.h> using namespace std; using ll = long long; const int MAXN=100010; ll w[MAXN]; int fa[MAXN], sum[MAXN]; inline int find(int x) { if(x != fa[x]) { int t = fa[x]; fa[x] = find(fa[x]); } return fa[x]; } inline v...

#牛客春招刷题训练营# + 链接首先要理解题意（过于简洁以至于刚开始愣了）01子序列指的就是 "01" 这样两位，那就很显然了计数数组辅助双指针，直接over #include <iostream> using namespace std; using ll = long long; const int MAXN=200010; char s[MAXN]; int main() { int n; ll k, res=0; scanf("%d%lld",&n, &k); scanf("%s", (s+1));...

#牛客春招刷题训练营# + 链接1.区间和的条件不好处理，转换为总和的三分之一以及前缀和。2.区间内至少有一个正数，转换为下一个正数的索引。3.向后计数，转换为计数的后缀和。 #include <iostream> using namespace std; using ll = long long; const int MAXN=200010; int a[MAXN], ddr[MAXN], np[MAXN]; ll s[MAXN]; int main() { int n; scanf("%d", &n); for (int i=1;i<=n;i+...

#牛客春招刷题训练营# + 链接dp[i][j]表示s串前i个字符跟p串前j个字符是否匹配，简单处理一下'*'字符和'?'字符。比较坑的是s串前缀的'*'字符需要特殊考虑。 #include <bits/stdc++.h> using namespace std; const int MAXN=128; char x[MAXN],y[MAXN]; bool dp[MAXN][MAXN]; bool ab(char c) { return ('a'<=c && c<='z') || ('0'<=c && c<='9'); } i...