给你n个数 1到n 你全排列相邻差序列 有字典序第k大差序列的 输出 数据到1e4 大于 8 的直接暴力 n 后面 1 ~ n-1 的第k-1排列 就是解 然后 1 到 8 打表处理 #include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 6; struct node { int num[10]; char st[10]; bool operator < (const node &a) const { return strcmp(st, a.st) < 0; }...

算法竞赛进阶指南 差不多就是 分形之城 看作向量旋转 平移 细节还不算多 #include <bits/stdc++.h> using namespace std; long long f(int n, int x, int y) { if (n == 0) return 1; int m = 1 << (n - 1); if (x <= m && y <= m) { return f(n - 1, y, x); } if (x <= m && y &gt...

类似 斐波那契数列 这个字符在coffe 还是 chicken 我们只需要 每次减去 dp[n - 2] 判断它在那个串中 能减去就意味是每个串重新换了减去 ad– 不然-=2 #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll maxn=1e3+10; ll dp[maxn]; int main() { dp[1] = 6, dp[2] = 7; for(ll i=3; i<=60; i++) dp[i]=dp[i-1]+dp[i-2]; ll t; cin&gt...

这题找到他们的不同特征判断就好了 题意还说 不是下面的 随便输出 就可以少盘一种了 虽然也没有少写啥 第一个 连边 只有2个是出现1次的 4 和 5 用 2个 3边 和 一个4边 判断 2 和 3 我dfs2边 3 的话 4深度出现2次 剩下的直接出 2图就好 #include <bits/stdc++.h> #define int long long using namespace std; int f[100]; int n, m; string str = "*COFFEECHICKEN"; int head[10], cnt; int n...

我们考虑跑 网络流 首先是 二分图最大匹配 == 入侵者数量时 时间可以缩小点才最多50个 50 * 50 最多发 3000 不到的导弹3000 和 原点连 3000个边3000 和 入侵者连 最多15000边开 前向星 按 40000 * 8 边 差不多了就 因为连的太多了暴力点建图 将塔分成很多导弹每个点 最多建立50个 我们预先建出来 原点到炮塔发出得导弹上之后 按炮弹发射和冷却路上总时间 和 入侵者相连最后 入侵者与汇点相连我们跑最大流 如果 最大流不是 入侵者数目 r = mid 不然 l = mid #include <bits/stdc++.h> using n...

线段树 上套每个区间可以有哪些并查集 一直向下 如果已经有大区间的管道到n 这个点覆盖区间线段树 往下就不必要走了 然后学会了 安秩合并(启发式搜索) 不能压缩路径 我们把大的合并到小的上面 就使得 长的 被查询的的路径 尽可能慢的长 这样不压缩路径 不超时 的完成 我们合并 和 实现撤销的操作 #include <bits/stdc++.h> using namespace std; #define fastio ios::sync_with_stdio(false);cin.tie(0) const int maxn = 2e5 + 10; int n, m, ans; ...

f(i)=f(i-1)+i-(vis[a[i]]?vis[a[i]]:0) 公式怎么出来的呢?考虑 由1-i 如果 第i个数字出现过,那么他对前一个出现过的i维护的区间是没有贡献的,只有vis[i]-i有贡献. 如果没出现过肯定 是前面维护的 都+1: 有人可以看出 是总ans不断减 现在数据之前出现过所有同样数据(不止当前这个)出现的位置 和 #include<bits/stdc++.h> using namespace std; #define int long long int a[100005]; int k[100005]; signed main(){ int ...

第3次了 关于最大01矩阵的 这次找 尽可能大 不相互包含的 寻找策略是 下一层1的长度 不等于我当前这层长度 剩下的依然是 单调栈维护1矩阵 左右到哪里 #include<bits/stdc++.h> using namespace std; const int maxn = 3000 + 10; int n, m; int a[maxn][maxn], dp[maxn][maxn]; int vis[maxn][maxn]; int l[maxn], r[maxn], sum[maxn][maxn]; int que[maxn], head; signed main() ...

带权并查集+二分图解法 带权并查集 分析A，B之间的相对距离，可以得到rnk[fa] = rnk[A]+x-rnk[B]。 注意到这时，对于原来的A的树，只更新了fa跟结点的权值， 那么其它结点的更新在查找的那一步里面实行了。维护是相对距离 一开始 ab之间关系 a到b是s 在 fa fb 不一样是 我们可以当 a到fa b到fb 还有 a到b距离s 是向量 那么 rnk[fb]=rnk[a]-rnk[b]+s 种类并查集很多耶可以转到带权上orz http://acm.hdu.edu.cn/showproblem.php?pid=3047Zjnu Stadium HDU - 3047 带权...

题描述 有n头奶牛，已知它们的身高为 1~n 且各不相同，但不知道每头奶牛的具体身高。 现在这nn头奶牛站成一列，已知第i头牛前面有AiAi头牛比它低，求每头奶牛的身高。 输入格式第1行：输入整数nn。 第2..n行：每行输入一个整数AiAi,第i行表示第i头牛前面有AiAi头牛比它低。（注意：因为第1头牛前面没有牛，所以并没有将它列出） 输出格式输出包含nn行，每行输出一个整数表示牛的身高。 第ii行输出第ii头牛的身高。 数据范围1≤n≤105 样例 输入样例：51210输出样例：24531 算法1 树堆每次找第a[i] 大的数据 同时不能与后面出现的冲突 C++ 代码 #include...

Problem Description You a given a permutation p1,p2,…,pn of size n. Initially, all elements in p are frozen. There will be n stages that these elements will become available one by one. On stage i, the element pki will become available. For each i, find the longest increasing subsequence among avai...

P4145 上帝造题的七分钟2 / 花神游历各国 洛谷 区间开根 最多开几次根就变成1了 这里我们选择 维护区间 和 如果区间和等于区间长度 不更新 不等于 更新到底 反正最多跟新不了几次 正好问的也是区间和。。 #include <iostream> #include <cmath> using namespace std; typedef long long ll; const int maxn = 100050; ll n, k; ll tree[maxn << 2]; void pushup(int rt) { tree[rt] = t...

DFS序 前置的几道题 线段树DFS序 1 单点更新 区间查询 https://blog.csdn.net/qq_40831340/article/details/84501232 线段树DFS序 2 区间子树更新 单点查 https://blog.csdn.net/qq_40831340/article/details/84501478 以上都是关于统计 跟改子树的 欧拉序 这里我们可以处理出 关于树上路径的 虽然我觉得 都是DFS搞这数组也没有啥大区别 树上操作 https://www.luogu.org/problem/P3178 其实我代码没有过样例 能过题的原因 是我读...

一种优化分层图建图方法 直接暴力建这样线特别乱得图 因为中转得关系 我们得暴力扫完这些中转 用一个虚拟点代表中专 这样建就 直接处理得换线得问题了 考虑分层图最短路。 很容易想到建 m 层图，如果多条地铁线都经过同一个点，则在这些点之间暴力两两连边，这样连边是 O(nm^2)的，可能会超时。 我们可以多建一层虚点，所有点到它对应的虚点不需要代价，从虚点到它对应的点需要对应的代价，这样就可以优化到 O(nm) 建图。最后跑一边最短路就好了。 #include<bits/stdc++.h> using namespace std; typedef long long l...