Aurouki

二分应用 lower_bound(upper_bound)函数应用题目链接：https://ac.nowcoder.com/acm/contest/84444/E题意有n种猫粮，第i种猫粮的营养值为,数量为,猫猫每一天可以吃任意数量和种类的猫粮，但每种猫粮只会吃一份。求k天内猫猫可以获得的最大营养值。 数据范围 题解     易知，每个种类每天只能吃一次，显然，对于所有剩余的猫粮，每天都吃一次是得到最大营养值的最优解，不难想到，此时对答案的贡献就是所有存在猫粮的和！每过一天，所有猫粮的数量集体减一，直至所有猫粮的数量均为0；对所有猫粮按照数量为第一关键字进行结构体升序，那么每次对答案的贡献即为天数*后缀和！     我们遍历数组并用前缀和pre[i]维护前i天的最大营养值，但是会产生一个问题：给出的数量值是离散的，而询问的值可能恰好夹在离散的数量（天数）之间？所以，我们可以借助二分函数寻找第一个小于其天数的“离散块”，再通过多余天数的贡献算出答案，设找到的第一个小于天数的值为s，则答案为pre[s]+(k-s)*suf。     需要注意的是，由于数量值的范围极大，同时对应 ...

A. Bitwise Operation Wizard(交互+位运算)官方评分：*1700个人评分：*1600代码难度并不高，比较偏向思维和技巧，相当好玩 题意    有t组输入，每次给定一个长度为n的排列,里面只包含0~n-1，每个数恰好只出现一次，且顺序不定。我们需要找到两个下标i和j，使得的值最大化.    本题为交互题，每次询问的格式为”? a b c d”,最后会返回比较符号”<”或”=”或”>”,如果返回”<”，则说明，”=”和”>”同理。最终我们通过推理得到的答案用”! i j”的格式输出。 数据范围 询问次数不超过次 思路省流：找最大值下标 i(n-1次查询)+存”互补”数下标(n-1次查询)+找”互补”数中最小值下标 j(不超过n-1次查询)详解    位运算一定要拆位去考虑每个独立的二进制位对答案的贡献，不难想到，两个数的二进制位必须互不相同，如和,这样异或得到的最大值一定是形如“”,即每个二进制位都是1. 对于每次询问，我们询问出的答案只有大小关系而非具体的值，而且是或运算( | )的形式；由于每个数或上自己一定等于自己(x | x ...

拆位贡献题目链接：https://ac.nowcoder.com/acm/contest/22754/H题意给定一个长度为n的正整数数组，计算的值. 数据范围 ▶　题解     对于数字间的异或值的和，显然可以拆位对每个位进行单独的考虑；两个数之间异或，如果可以对答案产生贡献，那么两个位必然不相等，即.     而本题是平方形式的，显然不能直接用数值的平方来计算，因为位是独立存在的，应该将平方的两个式子都进行枚举讨论，即.     由上式可知，只有当和同时满足时，才能产生的贡献，否则贡献为零；所以最终化简得到的式子为.     因此，设dp[i][j][x][y]表示二进制的第i位为x，第j位为y的数量，预处理过后外面枚举a[i]和a[j]的位数，内层只需要枚举各个a[i]，通过dp数组就能找到符合条件的数量，最终以O()的复杂度通过此题. ▶　Code： #include #define int long long #define endl "\n" #define INF 1e15 using namespace std; typedef pairpii; int d ...

A.My First Sorting Problem(模拟)题意给定x和y，要求升序输出答案. Code:123456789101112131415#include<bits/stdc++.h>#define int long long#define endl '\n' using namespace std;signed main(){ std::ios::sync_with_stdio(false);cin.tie(0); int t;cin >> t; while(t--){ int x, y;cin >> x >> y; if(x > y) swap(x, y); cout << x << ' ' << y << endl; } return 0;} B.Different String(模拟)题意给定字符串s,要求重排该字符串，使得新字符串与原字符串s不相等，若有解，则输出“YES” ...

前缀和应用 区间值为定值trick题目链接：https://codeforces.com/contest/1915/problem/E题意给定一个数组a，问是否存在区间[l,r],使得该区间中奇偶下标的和相等.题解1    设奇数下标的前缀和为odd[i],偶数下标的前缀和为even[i],对于区间[l,r]要使得奇偶下标的和相同，即奇偶下标的前缀和相等，odd[r] - odd[l-1] = even[r] - even[l-1];    移项化简可得，odd[r] - even[r] = odd[l-1] - even[l-1],易知，对于$i \in [0,n]$，只要有至少两个odd[i]-even[i]相等，那么该区间的奇偶下标一定相等. Code1:123456789101112131415161718192021222324252627282930#include<bits/stdc++.h>#define int long long#define endl "\n&qu ...

用途用于RMQ（最值查询）问题中，运用倍增的思想，以O()的时间复杂度预处理，再以高效的O(1)进行查询 查询最大值12345678910111213int dp[200010][30];//dp[i][j]表示以i为起点，2^j为块大小的最大值（最小值同理）auto init=[&]()->void{ for (int i = 1; i <= n;i++) dp[i][0]=a[i]; for (int j = 1; (1 << j) <= n;j++) for (int i = 1; i + (1 << j) - 1 <= n;i++) dp[i][j] = max(max[i][j - 1], max[i + (1 << (j - 1))][j - 1]);};auto query=[&](int l,int r)->int{ int len=(int)(log2(r-l+1)); return max(dp[i][1< ...

标准解法双哈希+大质数取模用途O(1)求字符串以及子串 tip 进制数尽量使用233333，1313131等较大数，不容易被卡 取模使用孪生双素数和 Hash公式1hash[i] = hash[i-1] * base + s[i] - '0'（字母同理） 获取子串的Hash对于 的字符串子串，对应的区间Hash值为：    (% mod + mod ) % mod其中，需要率先预处理pw数组(base的指数)1234567891011121314151617181920212223242526272829303132#include <bits/stdc++.h>#define endl '\n'using i64 = long long;using namespace std;char s[200010];i64 Hash1[200010], Hash2[200010], pw1[200010],pw2[200010];const int base1 = 1313131, base2 = 233333;const int p1 = 1e9 + 7, p2 = 1e9 ...

曼哈顿距离题目链接：https://codeforces.com/contest/1968/problem/E题意给定一个整数n，在网格的网格中选择n个不同单元格，最大化任意单元格之间的不同曼哈顿距离，如下图所示. 数据范围 题解1     本人的取巧做法，个人感觉比较麻烦，不过代码确实能AC过本题。解题思路主要是从题目所给的样例6得到启示.     首先，一张网格的最大曼哈顿距离一定是处于对角两边形成的唯一最大值，所以曼哈顿距离的种类数最大也是加上本身的零.以n=6为例，其符合条件的距离为0,1,2,3,4,5,6,7,8,9,10.当我们放置对角两个以及某一角落的相邻两个时，剩下需要找的距离为0,1,2,3,4,5,6,7,8,9,10.     正是因为有临接在角落的三个，所以我们每次按三格单位距离向下倒推退，就一定会有三个从小到大的距离满足！如图，假设现有的棋子位居(1,1),(1,2),(1,3),(6,6)，那我们现在右下移动{2,1}格距离，也就是(3,4)格放置，此时剩下要找的距离为0,1,2,3,4,5,6,7,8,9,10.同理，再在(5,5)格放置棋子， ...

题目链接：https://codeforces.com/contest/1922/problem/B题意有一个正整数数组,从中取三个数，每个数对应的值为，求能够构成三角形的方案数. 数据范围 题解     由三角形的性质知，两边的和大于第三边，而对于本题中可以看成第i位的二进制值，由二进制的性质知，，相邻两位的值差了两倍，所以选择三角形的三边中，至少会有两条边的长度一致，即选择的相同.     将的值装入map存次数并从小到大进行遍历map，设当前次数为cnt,小于当前位数的总次数为sum，当次数大于等于2时，可行的方案数为；同时计算完该位次的还要累加sum. Code： #include< bits/stdc++.h> #define int long long #define endl "\n" using namespace std; int t,n,a[300010],pre[300010]; map< int,int> mp; int C_2(int n){ return n*(n-1)/(2LL); } int C_3(i ...

思维+树状数组题目链接：https://codeforces.com/contest/1791/problem/F题意操作 1 l r：区间[l,r]中每个数修改为数位和操作 2 x：查询当前a[x]的值 数据范围 题解     因为一个数通过若干次操作1的数位和是固定不变的，直到变为个位数后就不会发生变化，所以对于下标i只需要记录a[i]随操作次数的变化值（可以用二维vector保存），这题就将转化为了操作次数.     操作1就是对区间[l,r]执行操作数加一，区间二则是查询下标i的操作次数，经典的“区间修改+单点查询”问题，使用树状数组进行维护.     另外，完全不需要担心数位和与操作次数的范围，因为数值是非常小的，如 Code: #include < bits/stdc++.h> #define int long long #define endl '\n' using namespace std; vector< int> v[200010]; int diff[200010]; // 操作次数 signed main(){ ...