约瑟夫问题模拟
title: 约瑟夫问题模拟 categories: ICPC tags: null abbrlink: e41dfa8b date: 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: ICPC tags: null abbrlink: d27c536f date: 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; ...
AtCoder Beginner Contest 366
title: AtCoder Beginner Contest 366 categories: ICPC tags: null abbrlink: e46359dc date: 2023-05-09 00:00:00 AtCoder Beginner Contest 366 D.三维前缀和板子，预处理可以选择不容斥查询的时候只能容斥 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++)...
牛客周赛round56
title: 牛客周赛round56 categories: ICPC tags: null abbrlink: a5ac9e0c date: 2023-05-05 00:00:00 牛客周赛round56 C.给定一个c，要求在给定范围内构造a,b满足a⊕b=ca\oplus b=ca⊕b=c.要求值域在1-1e9 Sol:本题的范围比较宽松，只需要构造1，c^1.注意到1e9情况有些特殊，我们特判即可。 思考：如果范围限定到[l,r][l,r][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)...
二维vector的使用
title: 二维vector的使用 categories: ICPC tags: null abbrlink: da2645d date: 2023-05-04 00:00:00 https://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: ICPC tags: null abbrlink: 415ae054 date: 2023-05-03 00:00:00 https://www.luogu.com.cn/problem/P8773 [蓝桥杯 2022 省 A] 选数异或 题目描述 给定一个长度为 nnn 的数列 A1,A2,⋯ ,AnA_{1}, A_{2}, \cdots, A_{n}A1,A2,⋯,An 和一个非负整数 xxx, 给定 mmm 次查询, 每次询问能否从某个区间 [l,r][l, r][l,r] 中选择两个数使得他们的异或等于 xxx 。 ##Solution:我们预处理每个端点对应的左边最近的配点，然后O(1)O(1)O(1)回答询问。 详细来说，对于每个右端点我们找到其左边最近的对应位置。进一步，我们考虑对于一个区间，我们只需要存在一个点他的对应端点在区间内就可以了，于是我们需要维护对应端点的区间最大值，RMQ问题可以线段树或者st表解决。 ...
完全二叉树的公共父结点
title: 完全二叉树的公共父结点 categories: ICPC tags: null abbrlink: 76dac8fe date: 2023-04-27 00:00:00 1.有点后序遍历的思想，就是先把左子树，右子树的结果算出来，然后合并到根节点。 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: ICPC tags: null abbrlink: ea185c20 date: 2023-04-23 00:00:00 分治初步 归并排序求逆序对 Sol：在归并排序过程中，本身就是分治思想，递归的对左区间排序，右区间同理。对于已经有序两段进行合并只需要O(n)O(n)O(n)的时间，递归共log2nlog_{2}{n}log2n层，时间复杂度为O(nlog2n)O(nlog_{2}{n})O(nlog2n) 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...
树的中心——树形dp_换根dp启蒙
title: 树的中心——树形dp_换根dp启蒙 categories: ICPC tags: null abbrlink: 53d40c3a date: 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/#换根-dp 树形 DP 中的换根 DP 问题又被称为二次扫描，通常不会指定根结点，并且根结点的变化会对一些值，例如子结点深度和、点权和等产生影响。 通常需要两次 DFS，第一次 DFS 预处理诸如深度，点权和之类的信息，在第二次 DFS...
树上启发式合并
title: 树上启发式合并 categories: ICPC tags: null abbrlink: 3a024d41 date: 2023-04-15 00:00:00 树上启发式合并（常常也叫DSU On Tree，但其实和DSU并没有特别大关系），是一种解决某些树上离线问题的算法，尤其常被用于解决“对每个节点，询问关于其子树的某些信息”这样的问题。 假设我们要对树上的每个节点p求ans[p] ，且这个ans[p] 可以通过合并p的子节点的某些信息得知，一般来说我们可以用树形DP解决。但如果“子节点的某些信息”的规模较大，简单的树形DP在时间和空间上都可能爆炸。所以我们不能存储每个节点的信息，而是要实现某种资源复用。 - 有一棵 nnn 个结点的以 111 号结点为根的有根树。 每个结点都有一个颜色，颜色是以编号表示的， iii 号结点的颜色编号为 cic_ici。 如果一种颜色在以 xxx 为根的子树内出现次数最多，称其在以 xxx 为根的子树中占主导地位。显然，同一子树中可能有多种颜色占主导地位。 你的任务是对于每一个 ...