爱飞鱼的blog

title: 约瑟夫问题模拟categories: - ICPCtags: - nullabbrlink: e41dfa8bdate: 2023-05-16 00:00:00 习题集P79。编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。现在给定一个随机数m>0，从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。报m的人出圈，同时留下他的密码作为新的m值，从他在顺时针方向上的下一个人开始，重新从1开始报数，如此下去，直至所有的人全部出圈为止。 问题输入输入数据第一行为两个正整数n和m，分别表示人的个数及初始随机数，每组数据的第二行为n个整数，表示每个人持有的密码。 问题输出用一行输出n个整数表示依次出圈人的编号，整数之间用空格分隔 int a[N]; // 用于存储每个人的密码值 typedef struct Node{ int data; // 存储该节点代表的人的编号 struct Node *next; // 指向下一个节点的指针 }node; //...

title: 逆序对——权值树状数组+离散化categories: - ICPCtags: - nullabbrlink: d27c536fdate: 2023-05-12 00:00:00 给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。每个数字不超过1e9。 int n, m; int a[N]; int tr[N]; vector<int>lan; int lowbit(int x){ return x&(-x); } void discrete() { sort(lan.begin(), lan.end()); //排序 lan.erase(unique(lan.begin(), lan.end()), lan.end()); //去重 } //查询 int find(int x) { return lower_bound(lan.begin(), lan.end(), x)-lan.begin()+1; ...

title: AtCoder Beginner Contest 366categories: - ICPCtags: - nullabbrlink: e46359dcdate: 2023-05-09 00:00:00AtCoder Beginner Contest 366D.三维前缀和板子，预处理可以选择不容斥查询的时候只能容斥 int a[N][N][N]; void solve() { cin >> n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int k = 1; k <= n; k++) { cin >> a[i][j][k]; } } } for (int i = 1; i <= n; i++)...

title: 牛客周赛round56categories: - ICPCtags: - nullabbrlink: a5ac9e0cdate: 2023-05-05 00:00:00牛客周赛round56C.给定一个c，要求在给定范围内构造a,b满足$a\oplus b=c$.要求值域在1-1e9 Sol:本题的范围比较宽松，只需要构造1，c^1.注意到1e9情况有些特殊，我们特判即可。 思考：如果范围限定到$[l,r]$如何寻找b和c，考虑从二进制位考虑？ void solve() { cin >> n; if (n == 1) cout << 2 << " " << 3 << endl; else if (n == 1e9) { for (int i = 30; i >= 0; i--) { if ((n >> i) & 1) { ...

title: 二维vector的使用categories: - ICPCtags: - nullabbrlink: da2645ddate: 2023-05-04 00:00:00https://blog.csdn.net/m0_57298796/article/details/123952640简单来说，必须给出具体行数，以及列的详细类型信息 vector<vector<int>> a(r, vector<int>(c))； int row = a.size(); //获取行数 int column = a[0].size(); //获取列数

title: 一类区间查询对应答案具有单调性–维护前缀对应端点最大值categories: - ICPCtags: - nullabbrlink: 415ae054date: 2023-05-03 00:00:00https://www.luogu.com.cn/problem/P8773 [蓝桥杯 2022 省 A] 选数异或题目描述给定一个长度为 $n$ 的数列 $A_{1}, A_{2}, \cdots, A_{n}$ 和一个非负整数 $x$, 给定 $m$ 次查询, 每次询问能否从某个区间 $[l, r]$ 中选择两个数使得他们的异或等于 $x$...

title: 完全二叉树的公共父结点categories: - ICPCtags: - nullabbrlink: 76dac8fedate: 2023-04-27 00:00:001.有点后序遍历的思想，就是先把左子树，右子树的结果算出来，然后合并到根节点。2.合并时四种情况分类讨论.3.对于遇到要找的点就可以直接返回，不管另一个点在这个点下面还是在别的子树上，都是正确的 int n, m; int a[N]; int query(int root,int x,int y){ //cerr<<root<<endl; if(root>max(x,y))return -1; if(root==x||root==y)return root; int l=query(2*root,x,y); int r=query(2*root+1,x,y); if(l==-1&&r==-1)return -1; if(l!=-1&&r!=-1)return...

title: 分治初步categories: - ICPCtags: - nullabbrlink: ea185c20date: 2023-04-23 00:00:00分治初步归并排序求逆序对Sol：在归并排序过程中，本身就是分治思想，递归的对左区间排序，右区间同理。对于已经有序两段进行合并只需要$O(n)$的时间，递归共$log_{2}{n}$层，时间复杂度为$O(nlog_{2}{n})$debug:1.对于没有到达边界的一段也需要放入临时数组，并且继续统计答案2，先审核一遍代码，出现了没有调用函数，只打个括号的情况，没有报错，需要注意 int solve(int l,int r){ if(l==r)return 0; int mid=(l+r)>>1; int res=solve(l,mid)+solve(mid+1,r); int pl=l,pr=mid+1; int...

title: 树的中心——树形dp_换根dp启蒙categories: - ICPCtags: - nullabbrlink: 53d40c3adate: 2023-04-19 00:00:00请你在树中找到一个点，使得该点到树中其他结点的最远距离最近。这个点被称为树的中心。题解：https://www.cnblogs.com/dx123/p/17302104.html评测：https://www.acwing.com/problem/content/1075/暴力做法是以每个点为根，求出从根向下走的最远距离，这个过程需要做n遍，每一遍dfs的复杂度是O（n),时间复杂度是O（n^2),考虑优化。 https://oi-wiki.org/dp/tree/#%E6%8D%A2%E6%A0%B9-dp 树形 DP 中的换根 DP 问题又被称为二次扫描，通常不会指定根结点，并且根结点的变化会对一些值，例如子结点深度和、点权和等产生影响。通常需要两次 DFS，第一次 DFS 预处理诸如深度，点权和之类的信息，在第二次 DFS...

title: 树上启发式合并categories: - ICPCtags: - nullabbrlink: 3a024d41date: 2023-04-15 00:00:00树上启发式合并（常常也叫DSU On Tree，但其实和DSU并没有特别大关系），是一种解决某些树上离线问题的算法，尤其常被用于解决“对每个节点，询问关于其子树的某些信息”这样的问题。 假设我们要对树上的每个节点p求ans[p] ，且这个ans[p] 可以通过合并p的子节点的某些信息得知，一般来说我们可以用树形DP解决。但如果“子节点的某些信息”的规模较大，简单的树形DP在时间和空间上都可能爆炸。所以我们不能存储每个节点的信息，而是要实现某种资源复用。 - 有一棵 $n$ 个结点的以 $1$ 号结点为根的有根树。 每个结点都有一个颜色，颜色是以编号表示的， $i$ 号结点的颜色编号为 $c_i$。 如果一种颜色在以 $x$ 为根的子树内出现次数最多，称其在以 $x$ 为根的子树中占主导地位。显然，同一子树中可能有多种颜色占主导地位。 你的任务是对于每一个 $i\in[1,n]$，求出以 ...