#牛客春招刷题训练营# + 链接显然最终的字母还是原串的字母，只是重复了很多遍维护一下原串每个字母每次操作后重复多少遍就好啦 #include <bits/stdc++.h> using namespace std; const int N = 1024; char s[N]; int c[N]; int main() { int n, q, l, r; scanf("%d%d", &n, &q); scanf("%s", s); vector<int> ve(n, 1); while (q--) { scanf(...

#牛客春招刷题训练营# + 链接首先将问题分解为 \型对角线 加上 /型对角线，这两条线是有交点的，但需要注意交点有可能不在边界交点不在边界时，最终个数是其中一条个数的两倍；交点在边界时，最终个数是其中一条个数的两倍再减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...