本题考查 二维差分+二维前缀和虽然点(1,1)在左下角，(n,m)在右上角，但画图翻转一下可发现无影响 1.二维前缀和，a[i][j]求得是从(1,1)开始到(i,j)这一块矩形的总和，公式如下 For(i, 1, n) For(j, 1, m) a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + a[i][j];2.(x1,y1)到(x2,y2)构成矩形数据和 k = a[x2][y2] - a[x2][y1 - 1] - a[x1][y2 - 1] + a[x1 - 1][y1 - 1];可仿上图自己推3.二维差分 ++a[x1]...

本题考查了并查集+离散化题干中“如果 A 与 B 友好，B 又与 C 友好，那么 A 与 C 也是友好的”---->并查集关于并查集可看看CSDN：https://blog.csdn.net/qq_41593380/article/details/81146850“手下1e9个”说明直接使用hash和map并不适用，需要考虑进行 离散化 处理即：将题目中出现的数据整合起来，进行去重处理（对于vector可考虑直接使用unique函数） 1.读入数据，对出现过的“下属”进行存储；2.对下属进行排序；3.进行去重处理； For(i, 1, n) { cin >> R[i].a &...

题目所求三个部分1.斐波那契2.n!在m进制下末尾零的个数3.N皇后问题前导一：求n!中质因子p的个数基于事实：n!的质因子p的个数等于：1~n中p的倍数(n/p)加上(n/p)!中质因子p的个数递归代码： ll getcnt(ll p, ll n) { if (n < p) return 0; return n / p + getcnt(p, n / p); }转换为非递归代码： ll getcnt(ll p, ll n) { //求x!有几个p ll res(0); while (n) res += n / p, n /= p; return res; }二：求n!在m进制末尾零的个...

这个题解实话说都是抄的其他dl的题解写这个的用意主要是为了便于自己理解以及把dl觉得显而易见的写出来 前导一:整合树，建立数组fa[N]来确定每个点的父节点Method one: vector vector<int> q[N]; inline void dfs(int x, int f) {//确定父节点 fa[x] = f; for (auto i : q[x]) { if (i == f) continue; else dfs(i, x); } //for(auto i:q[x]) --> vector<int>::iterator it; //for(it=...

碎碎念https://ac.nowcoder.com/acm/contest/3006/F  本题涉及动态规划针对第i次喊叫，有AC和RJ两种情况，分别用DP[i][0]和DP[i][1]表示可划分为两种情况i<x时候，只能是AC,DP[i][0]=DP[i-1]0此时DP[i-1][1]是0i>=x时，分两种情况：1：第i次是AC，则DP[i][0]=DP[i-1][0]+DP[i-1][1]2：第i次是RJ，则DP[i][1]=DP[i-x][0] (RJ前一次必定是AC)临界条件：DP[0][0]=1,DP[0][1]=0; DP[0][0]=1,DP[0][1]=0; fo...

牛牛战队的比赛地https://ac.nowcoder.com/acm/contest/3006/B  题目要求为求最大距离最小值，联想到三分法（凹形序列？） 如果一个函数是若干个开口向上的二次函数的最大值 这个函数只能先减后增，那么这就只有一个凹形序列了如果一个函数是若干个开口向下的二次函数的最小值 这个函数只能先增后减，那么这就只有一个凸形序列了 #pragma warning (disable :4996) #include <iostream> #include <cstdio> #include <bits/stdc++.h> using name...

树上博弈https://ac.nowcoder.com/acm/contest/3005/F首先，注意到输掉的唯一方法是自己的唯一一条边有另一个人，那么自己一定是在叶子上。令两个人之间的距离为D。请注意，每人行动后D增加1或减少1。 因此，每有人走一步D的奇偶性都会改变。假设最初，在牛牛移动之前，D是偶数。 那么当牛牛移动时D将始终为偶数，而当牛妹移动时D将始终为奇数。请注意，只要牛牛和牛妹的令牌位于相邻的节点中，D=1。因此，如果D为偶数，则他们不在相邻的单元格中，并且牛牛始终可以移动。另一方面，由于牛牛总是可以移动，因此他可以向牛妹的方向移动，将牛妹必然会最终移动到叶子上。同样，如果最初D...

子段乘积https://ac.nowcoder.com/acm/contest/3005/C  逆元：拓展欧几里得、费马小定理maxn初始值应设为0 #pragma warning (disable :4996) #include <iostream> #include <cstdio> #include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const ll mod = 998244353; const int N = 2...

子段异或https://ac.nowcoder.com/acm/contest/3005/D  亦或运算中连续一段的运算 a[0]^...a[i]^a[i+1]^...^a[i+k]^...^a[n] 中若出现相同的亦或前缀和，如a[0]^...^a[i]的亦或前缀和 与 a[0]^...^a[i+k]的亦或前缀和相等，则a[i+1]^...^a[i+k]=0如 1 2 4 7 2 1 中 有1^2=3 1^2^4^7^2^1=3 则1^2^4^7^2^1=0另配合map食用更佳 #pragma warning (disable :4996) #include <iostream>...

建通道https://ac.nowcoder.com/acm/contest/3003/I  算是考察位运算吧？lowbit(0)=0，连接代价为0，可进行去重操作，去掉与之权值相等的如果最后只剩一个 则直接输出 0x=vi^vj！=1时，找最小位的二进制k（在该位上，所有权值中 1 与 0 同时并存（因1^0=1），若同时并存，所有通道间可 进行1-0 0-1 全部连通，若仅存在1或仅存在0，就没有通道能够相连） #pragma warning (disable :4996) #include <iostream> #include <cstdio> #include...

施魔法https://ac.nowcoder.com/acm/contest/3003/H  先从小到大排序，极差转换为--连续一段数尾部和开头的差值DP[i]就是前i个元素以i为尾划分段的最小值i可以是 作为前一段的新尾，DP[i]=DP[i-1]-A[i-1]+A[i]也可是新开一段k，作为段尾 DP[i]=DP[i-k]-A[i-k+1]+A[i] (A[i-k+1]是头，A[i]是尾)则动态转移方程为 DP[i]=min(DP[i-1]-A[i-1]+A[i],DP[i-k]-A[i-k+1]+A[i])需要注意的是1~k必须组成一个段，所以循环从 k+1 开始注意：能够新开一段最早是...

判正误https://ac.nowcoder.com/acm/contest/3003/G  考察快速幂求余g<=1e9，可考虑mod=1e9+7在左边三项求幂运算中，对其进行快速幂同时mod即可 #pragma warning (disable :4996) #include <iostream> #include <cstdio> #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5 + 10; ll mod = 1e9 + 7; ...

拿物品https://ac.nowcoder.com/acm/contest/3003/F  本题实际考虑贪心对于任意一个物品，倘若牛牛拿了，则牛牛得到ai,牛可乐失去bi，差值为ai+bi故而每次牛牛和牛可乐都会选择 ai+bi当前最大的 #pragma warning (disable :4996) #include <iostream> #include <cstdio> #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e5 + ...

做计数https://ac.nowcoder.com/acm/contest/3003/E  两边平方后可得 i+j+2(根号ij)=k，若k为正整数，则ij为完全平方数且ij<=n遍历1到n可得ij为完全平方数时的数据，并求ij的因数和即得 O（nlogn)或者直接遍历完全平方数 i*i<=n 为条件 #pragma warning (disable :4996) #include <iostream> #include <cstdio> #include <bits/stdc++.h> using namespace std; typedef...