链接：https://ac.nowcoder.com/acm/contest/370/I 来源：牛客网   题目描述 Rinne 最近学习了位运算相关的知识，她想运用自己学习的知识发明一个加密算法。 首先她有一个源数组 A，还有一个密钥数组 B，现在她想生成加密后的数组 C。 她发明的方法是：当计算CiCi的时候，首先将 CiCi 赋值为Ci−1Ci−1，然后加上 AiAi 分别与每一个满足 j < i 的 BjBj 异或后的和，然后加上 BiBi 分别与每一个满足 j < i 的 AjAj 异或后的和，最后加上 AiAi 与 BiBi 的异或和。 形式化的讲，关于 CiCi ...

链接：https://ac.nowcoder.com/acm/contest/369/A 来源：牛客网   题目描述 若你摘得小的星星 你将得到小的幸福  若你摘得大的星星 你将得到大的财富  若两者都能摘得 你将得到永远的愿望  摘星是罪孽的宽恕 摘星是夜晚的奇迹  抓住它吧 你所期望的那颗星   无法触及，因而耀眼   明明触及了，却还是耀眼 ——《少女☆歌剧 Revue·Starlight》 题目描述 "我明白。" 作为这命运剧场永远的观众，小D一直注视着这片星光璀璨的舞台，舞台上，少女们的身姿演绎出了一幕幕动人的场景，令人回味无穷。 有的...

题目链接 用来测几何板子真好。 1、已知三角形的三个顶点坐标，求三角形的外接圆圆心坐标和半径 证明： https://blog.csdn.net/MallowFlower/article/details/79919797 结论： x = ((y2-y1)*(y3*y3-y1*y1+x3*x3-x1*x1)-(y3-y1)*(y2*y2-y1*y1+x2*x2-x1*x1))/(2.0*((x3-x1)*(y2-y1)-(x2-x1)*(y3-y1))); y = ((x2-x1)*(x3*x3-x1*x1+y3*y3-y1*y1)-(x3-x1)*(x2*x2-...

不带修主席树模板 这篇博客代码挺好的 https://blog.csdn.net/creatorx/article/details/75446472 这篇博客图好评 https://blog.csdn.net/qq_39809664/article/details/79934516 #include <iostream> #include <algorithm> #define ll long long #define imid int mid=(left+right)/2; using namespace std; int n, m, cnt, a[10000...

题意： 有一个长度为  () 的区间，有  次询问 () ，每次询问三个数字L，R，H，询问区间 L - R 内有多少个数字小于等于H。 离线主席树裸题，把离线查询第K大的板子改改就行。但是，这个题目有点意思。 １、询问的 L，R 下标从０开始。所以每次询问先把 L，Ｒ 加１。 ２、大部分主席树的题目的序列都是的排列，所以不需要离散化，但这题比较妙。 ３、首先一定要离散化，然后考虑离散化的数字，长度为  的区间加上  个询问，一共  个数字，然后离散化，这题就做完了。 ４、交上去，MLE，嗯，算一算，空间复杂度  ，，结构体开小一点？WA了？ ５、所以我们只离散化长度为  的区间...

题意： 定义H为 ：如果区间内有H个大于等于H的paper，则是h-index 给你一个长度为  的序列，  次询问，每一次询问求区间内最大的H。 1、针对每一个区间，二分H，然后每次用主席树找出小于等于H-1的数的数量，然后减一下做判断就可以了。 #include <bits/stdc++.h> #define imid int mid=(left+right)/2; using namespace std; struct node { int l; int r; int sum; node() { sum = 0; } }tree[100005 * 20]; ...

暴力啊，先随便乱分，然后算A和C的差值，然后枚举所有可以让差值变小的两个数进行交换，注意可能会在枚举中陷入死循环，设置一个标记跳出就行。 Code： #include <bits/stdc++.h> using namespace std; int a[5005], c[5005], flag[5005]; set<int>aa1, cc1, ac1, other1, aa2, cc2, ac2, other2; vector<int>ans; int main() { int n; char ch; scanf("%d", ...

题意: 有n个数字，要你分成k组，要求每组内最大值与最小值的差值不超过5。求k组最多可以放多少个数。 思路： 线性DP，预计算出这个数字作为右端点时取的数字的个数，然后考虑每个数字取或者不取。 Code： #include <bits/stdc++.h> using namespace std; int a[5005], b[5005], dp[5005][5005], n, m; int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf...

其实一个线段树维护当前区间数字的个数和当前区间和就可以A了。 然后赛时加了很多了mod依旧没有过的原因是在存储询问的时，脑残的用了（看到op=1时，均小于的错觉）。 然后就过了。 思路： 1、首先想到需要离散化一下。 2、考虑用一颗线段树来维护当前区间的数字个数，和当前区间和（离散化前的数字的和）。 3、前缀和的思想，求第L小和第R小之间数字的和 就是 求前R小的数字和减去前L-1小的数字和。 Code： #include <bits/stdc++.h> #define ll long long #define lson left,mid,k<<1 #...

看不懂题解的蒟蒻来说说自己的想法。 1、 2、 3、 公式推导：

#include <bits/stdc++.h> using namespace std; int t, n, k, ans; void dfs(int num) { if (k == 0) ans = num; for (int i = 0; i < 10; i++) { if (num == 0 && i == 0) continue; if (num * 10 + i <= n) { k--; ...

T组，每组给出一个，求  矩阵快速幂，由第N个状态到第N+1个状态，推出关系矩阵，然后关系矩阵快速幂，再乘以出事矩阵就好了。 由于的最高项为立方，所以需要加上平方项和一次方项和零次方项 Code #include <bits/stdc++.h> #define ll long long using namespace std; const ll mod = 123456789; ll len = 6; struct node { ll matrix[6][6]; node() { memset(matrix, 0, sizeof matrix); } v...

显然每个人的最少次数是左边大于他的人数和右边小于他的人数，两次树状数组扫一下就ok了，由于H=1e6，所以先离散化一下，再套树状数组。 Code： #include <bits/stdc++.h> #define ll long long using namespace std; ll calc(int k) { return 1LL * k * (k + 1) / 2; } int a[100005], c[100005], cnt[100005], t[100005]; int lowbit(int k) { return k & -k; } void upd...

完全背包问题，先判所有数的Gcd是否为1，如果不是1的话，显然他们能凑出的数一定是Gcd的倍数，所以一定有无穷个凑不出来，然后两个for解决。 Code： #include <bits/stdc++.h> using namespace std; int dp[10005]; int a[105]; int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); } int main() { int n, f = 0; scanf("%d", &n); for (int i = 0; i &...