题目链接：https://codeforces.com/contest/1379/problem/A题目描述：对于一个字符串判断能否通过将“？”替换为字母，从而使得字符串中出现仅一次“abacaba”解题思路：第一次for循环枚举目标字符串的起点，第二层for循环是用来消去‘？’的，然后每次消完‘？’都check一遍字符串中是否只有一个“abacaba”。 代码： #include <bits/stdc++.h> using namespace std; string a="abacaba"; bool check(string s) { int cnt=0; ...

题目链接：https://ac.nowcoder.com/acm/contest/5668/L手速签到题代码： #include<bits/stdc++.h> using namespace std; int main() { string s; cin >>s; if((s[0]=='L'||s[0]=='l')&&(s[1]=='O'||s[1]=='o')&&(s[2]=='V'||s[2]=='v')&&(s[3]=='E'||s[3]=='e')&&(s[4]=='L'||s[4]=='l')&a...

题目链接：https://vjudge.net/contest/381841#problem/G题目描述：每次输入a,b,c，跟据题目描述的w(a,b,c)来输出答案解题思路：记忆化搜索，就注意一下(-1,7,8)这种序号为负的情况无法用数组存，提前处理一下。代码： #include<bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f typedef long long ll; ll f[100][100][100]; ll dfs(int a, int b, int c) { if(f[a][b][c] > ...

题目链接：https://vjudge.net/contest/381841#problem/I题目描述：定义LCM(a,b,c)是a，b，c的最小公倍数，现在给你a,b,L,求满足LCM(a,b,c)=L的最小的c是多少。解题思路：很有趣的一道题，突破口是通过唯一分解定理来理解lcm。先求出a,b的最小公倍数设为m，先把L/m，得到a,b中肯定不含或L指数大的减去m指数小的素因子，然后求出L和m都有的公因子按照需求累乘上去就行了。 代码： #include <iostream> #include <stdio.h> #include <string.h> ...

题目链接：https://vjudge.net/contest/381841#problem/B题目描述：有n头奶牛排成一列，现在告诉你最高的奶牛的序号以及它的身高，有R行表示i能看见j，i能看见j需要满足ij之间的牛的高度小于i的高度，且j的高度大于等于i的高度。输出每个奶牛的最大身高。解题思路：这题一看就是要用差分。i能看到j也就是ij之间的高度都至少比i的高度小1，那么s[i+1]--;s[j]++。然后最后求一个前缀和就完了。本题有几个细节上的坑值得注意：1.i可能大于j，差分的时候注意。2.可能会有重复数据，比如之前说了i能看到j，后面有说了一遍i能看到j，你总不能再差分一遍吧。需要...

题目链接：https://ac.nowcoder.com/acm/contest/5667/E题目描述：给n个整数A1~An，从n个数中可重复的选i个数出来，算它们的异或和，能得到最大值就是答案。解题思路：这个题首先考虑i>19的时候有ansi=ansi-2，证明也很简单，首先 只需要在ansi的基础上再随便挑一个数异或两次就可以了。然后如果i>19之后，如果ansi>ansi-2，则至少需要i-1个数才能达到满秩，而这里i-1至少为19，但题目保证最大秩为18，这两者是矛盾的。对于ansi(i<=19)，如果A数组储存所有输入进来的数，B数组从1到1<<1...

刚学完FFT，拿来连练手题目链接：https://www.luogu.com.cn/problem/solution/P1919解题思路：FFT是解决多项式乘法的，想办法把数给变成多项式比如：有了这个处理以后，我们可以直接看出来数的乘法不就是多项式乘法吗？！代码中有些细节问题已做出注释代码： #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <complex> using namespace std; #define ...

默认n是2的整数幂次。f(x)=a0+a1+...+an-1，比如8，对应的bit就是3，因为只有a0a7，rev[i]是把一个数在二进制下倒过来，思想是把一个数在2进制下分为前bit-1位和最后一位的话，需要让前bit-1位倒过来，并把最后一位放到前面去，由于让rev[i>>1]倒过来会多出一个后缀0，因此需要>>1，然后把i给移动bit-1位到最前面。在实现提前把a[i]放到正确位置上的时候，要在irev[i]的时候之前到rev[i]的时候已经把原来的rev[i]的位置已经与i的位置交换了，再交换就换回来了。后面mid是枚举要合并的一半，temp中应该cos(2pi...

题目链接：https://ac.nowcoder.com/acm/contest/5666/J解题思路：要是你知道沃里斯公式，就知道这是个结论，但要是你不知道就老老实实积分吧。再做一遍换元，然后作二项式展开。  最后写出W1,W2,W3...找找规律解决。 这道题还可以用分部积分法来做。(是不是求着求着就发现其实结构相似)最后推出来的公式里有分母中n！阶乘的逆元的话打个表就搞定了。 代码： #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e6; const ll ...

题目链接：https://ac.nowcoder.com/acm/contest/5667/D解题思路:签到题，比手速。一开始写成了：s[1][0]-s[0][0]-’0‘，但不需要-'0'。在那看了3，4分钟才看出错误。以此铭记自己的错误。代码： #include<bits/stdc++.h> using namespace std; string s[3]; int main() { cin >> s[0]; cin >> s[1]; sort(s,s+2); int h = (s[1][0]-s[0][0])*10+(s[1][1]-s[0][1]);...

题目链接：https://ac.nowcoder.com/acm/contest/5667/F这道题我们队之前没用过单调队列，这道题用二维线段树其实有点杀鸡用宰牛刀的感觉。并且由于数据量的原因导致二位线段树不用树套树会tle，用树套树会mle。预备知识：单调队列：单调队列要从一个比较经典的问题说起来这道题的题意是用一个固定长度的窗口，在一个数列上从左向右移动，找到每个窗口覆盖区域里的最大值。暴力比较：O(N^2)复杂度高的原因是在求解f(i)的时候，重复比较了它前面的m-1个数。单调队列优化：O(N)基本思想：同样维护队首元素作为答案，去掉多余元素。(维护单调性)队列中的每一个元素用一个二元组...

题目链接；https://vjudge.net/contest/381841#problem/AA题是个威佐夫博弈的裸题，先了解一下威佐夫博弈。预备知识：博弈论之威佐夫博弈威佐夫博弈 是指的这样一个问题：有两堆各若干个物品，两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品，规定每次至少取一个，至多不限，最后取光者胜利。关于威佐夫博弈的推导请看：https://blog.csdn.net/qq_41311604/article/details/79980882只需要知道：1.满足威佐夫博弈则会有一些先手必输的局势。2.我们会发现他们的差值(b[k]-a[k])是递增的，分别是0...

题目链接：https://ac.nowcoder.com/acm/problem/23616解题思路：O(nm)算法超时，使用莫比乌斯反演把时间复杂度降低成线性。目前做的题目当中，要使用莫比乌斯反演的题目通常是答案是关于gcd的题目且数据规模大，暴力卒。*推导过程：**  代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 1e6+7; const int mod = 1000000007; int prime[MAXN], prime_tot; bool p...

详见：https://www.acwing.com/blog/content/31/