爱飞鱼的blog

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

给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。每个数字不超过1e9。 1234567891011121314151617181920212223242526272829303132333435363738394041int 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; //返回所查询的数据的下标}void add(int x,int c){ for(int...

AtCoder Beginner Contest 366 D.三维前缀和板子，预处理可以选择不容斥查询的时候只能容斥 123456789101112131415161718192021222324252627282930313233343536373839404142434445int 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++) { for (int j = 1; j <= n; j++)...

牛客周赛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，考虑从二进制位考虑？ 123456789101112131415void 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) { int tmp = 1 << i; cout <<...

https://blog.csdn.net/m0_57298796/article/details/123952640 简单来说，必须给出具体行数，以及列的详细类型信息 123vector<vector<int>> a(r, vector<int>(c))；int row = a.size(); //获取行数int column = a[0].size(); //获取列数

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表解决。 但我们可以利用我们只需要回答存在性，而不用具体回答，我们只需要维护前缀最大值，对于每个查询只需要检验ans[r]>=l即可 1234567891011121314151617181920212223242526int a[N];int...

1.有点后序遍历的思想，就是先把左子树，右子树的结果算出来，然后合并到根节点。 2.合并时四种情况分类讨论. 3.对于遇到要找的点就可以直接返回，不管另一个点在这个点下面还是在别的子树上，都是正确的 123456789101112131415161718192021222324252627282930313233int 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 root; if(l!=-1&&r==-1)return...

分治初步 归并排序求逆序对 Sol：在归并排序过程中，本身就是分治思想，递归的对左区间排序，右区间同理。对于已经有序两段进行合并只需要O(n)O(n)O(n)的时间，递归共log2nlog_{2}{n}log2​n层，时间复杂度为O(nlog2n)O(nlog_{2}{n})O(nlog2​n) debug:1.对于没有到达边界的一段也需要放入临时数组，并且继续统计答案 2，先审核一遍代码，出现了没有调用函数，只打个括号的情况，没有报错，需要注意 1234567891011121314151617181920212223242526272829int 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...

请你在树中找到一个点，使得该点到树中其他结点的最远距离最近。这个点被称为树的中心。 题解：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 开始运行换根动态规划。 算法讲解： 第一次dfs和求树的直径的时候一样，通过递归从下而上得到从...

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