题意： 给出你一个字符串，代表油管的形状，但是这个形状不是固定的，你可以改变高为1的管道，管道的价格是a，支柱的价格是b，问你建成这样的管道最少花费多少？ 题解： 贪心策略，题目给出头尾都是高度为1的管柱，每次如果高度为2，要保证左面和右面的柱子一定要为2，如果高度为1，就要讨论是高度为1的花费少还是高度为2的花费少。 代码：#include <bits/stdc++.h> using namespace std; #define ll long long const ll inf = 1e17; char s[200010]; ll ans[200010][2]; int mai...

题意： 扩展kmp的匹配次数。 题解： 扩展kmp就是：定义母串S和子串T，S的长度为n，T的长度为m；求 字符串T 与 字符串S的每一个后缀 的最长公共前缀； 直接用模板写就行了 代码：#include <iostream> #include <cstdio> #include <string.h> #include <algorithm> using namespace std; #define ll long long const int MAX=1000010; //字符串长度最大值 int next1[MAX],extend[M...

题意： 给出一个数n<=1e18,问你将其分解成整数的唯一分解定理后对应的质数次幂的最大值。 题解： 这题数据真的非常狗血。 先用正常的中国剩余定理求出来前10001项的次幂，然后分类讨论， 如果n的四分之一次方是整数，更新最大值4 如果n的三分之一次方是整数，更新最大值3，这里不能直接用pow，应该用二分，精度问题 如果n的二分之一次方是整数，更新最大值2， 如果都不行，更新最大值1 代码：#include <bits/stdc++.h> using namespace std; #define ll long long const int maxx = 10010; ll...

题意： 给出4*4的矩阵，问你数字拼图能否能复原成原来的样子。 题解： 当逆序对个数的奇偶性和完成时空格所在行和初始时空格所在行的的差奇偶性相同时才有解。 代码： #include <bits/stdc++.h> using namespace std; int a[20]; int main() { int t; cin>>t; while(t--) { int k = 0,k2 = 0; for(int i=1;i<=4;i++) { for(int j=1;j<=4;...

题意： 题目给出一个数字P，让你找到一个小于P的数字Q，然后输出Q!%P即可。 题解： 威尔逊定理： 那么式子就成了 那么问题就成了求Q喽，注意求阶乘的时候用快速乘，否则会超时。 代码：#include <bits/stdc++.h> using namespace std; #define ll long long const int maxx = 1e7+10; ll p; int a[maxx+10]; bool pri[maxx+10]; int cnt1 = 0; bool is_prime(ll x) { for(int i=0;i<cnt1&&...

题意： 给出n个木棒，每次询问区间[l,r],问你选择任意三根木棒能够构成的最大的三角形，如果不存在三角形，输出-1 题解： 肯定都知道三角形的三边的定理，任意俩边之和大于第三边， 假设从最小的三角形都不匹配， 1，2，3，5，8，13，，，， 形成了斐波那契数列，第44项超过1e9，那么只需枚举前44项三角形就行了，如果还是没有符合的输出-1 找第k大值可以用主席树区间查找 代码：#include <bits/stdc++.h> using namespace std; #define ll long long const int maxx = 2e5+7; int n,m,q,...

题意： 给出一个无向连通图，每条边的权值都是1，可存在重边，a在1节点，b在n节点。 问你最少花费多少代价能将1到n的路径最远，如果不存在路径，输出0就行 题解： 先求出最短路，然后保留所有满足 dey dex = ew 的边，对于新的图求 1 到 n 的最小 割即为答案，最小割模板第一次用。 代码：#include <bits/stdc++.h> using namespace std; #define ll long long const ll inf = 1e16; const int maxx = 1e4+5; const int inf_int = 1e9+5; str...

题意： 给出n+1辆车，给出每辆车距离动物园的距离，速度，车长度，距离动物园最远的是你所在的车，当前后俩车相遇的时候，会合并，并以速度较小的车的移速接着行驶，问你自己的车车头到达动物园需要多少时间。 题解： 这题一开始想着模拟，但确实有些麻烦。 简单做法，也是最神奇的做法：最终通过停止线的时候，一定是一个车后面堵着剩余所有的车，那么影响时间的就只有最前面这辆车，所以对于每一辆车，假设是它是和 0 车堵在一起的最靠前的一辆车，那么可以计算出一个值，所有的车的计算值的最大值就是答案。 代码： #include <bits/stdc++.h> using namespace s...

题意： 就是典型的中国剩余定理 题解： 中国剩余定理的板子过不了，可能超long long，改成__int128就能过，或者用py直接写也行 代码：#include <bits/stdc++.h> #define ll __int128 using namespace std; const int maxn = 1e5+7; const int inf = 0x3f3f3f3f; const double PI = acos(-1.0); int n; ll top; ll a[maxn],m[maxn]; inline ll read() { ll x=0,f=1; ch...

题意: 求字符串的第n项的第k到第k+9个字符，输出 类似个斐波那契数列 题解： 基础递归，记录每个字符串的长度，和第n-2个比较，模拟着写就行 代码：#include <bits/stdc++.h> using namespace std; #define ll long long const ll inf = 1e13; const int maxx = 505; string s[2] = {"COFFEE","CHICKEN"}; ll t,n; ll a[maxx]; ll k; char solve(ll x,ll y) { ...

题意： 给你n个数，和一个数s 问你用哪几个数相加可以构成s，如果存在，只有唯一解，如果不存在输出-1 题解： 折半搜索，额，第一次见 赶紧记下来吧，模板 代码：#include <bits/stdc++.h> using namespace std; #define ll long long set<ll> s; map<ll,int> mp; ll a[40],sum; int n; int main() { cin>>n; int p=n/2; int q=n-p; cin>>sum; for(int i=0...

题意： 构造题，输入m，m是2的次方， 输出m行m列的矩阵，要求任意俩行的相加结果为0. 题解： 没有做过多少构造题，规律也找麻烦了，不知道怎么写 这里首先考虑最小的2*2的矩阵为 1 1 1 -1 m m m -m 可以令m = 1 那么转移到4*4里就成了 1 1 1 1 1 -1 1 -1 1 1 -1 -1 1 -1 -1 1 m m m m m -m m -m m m -m -m m -m -m m 不知道大家找到规律了吗 设a的解为m 那么2a的解就是 m m m -m 递归求解。 代码：#includ...

题意： 给一个01构成的字符串，要把该字符串切分成最少的份数，使得每一个字符串都是循环移位 字典序最小的字符串。 111011110 -> 111 01111 0 题解： 从后往前遍历，暴力求是否满足 代码：#include <bits/stdc++.h> using namespace std; #define ll long long bool ok(string s) { int l = s.length(); for(int i=1;i<l;i++) { for(int j=0;j<l;j++){ if(s[j]...

题意： 给出一个多项式，问你能否拆分。 题解: 实数域不可拆分多项式只有两种：一次多项式和二次的(b^2<4ac),记下来。。。 代码：#include <bits/stdc++.h> using namespace std; #define ll long long ll a[30]; int main() { ll t; cin>>t; while(t--) { ll n; int flag = 0; cin>>n; for(int i=1;i<=n;i++) { ...