代码 采用三分法，然后算出[1,n]中二次函数的最大值，再进行比较就可以了。 思路 #include <bits/stdc++.h> #define debug(x) cout<<"x="<<x<<endl #define int long long using namespace std; const int maxn = 1e5 + 7; const int mod = 1e9 + 7; typedef long long ll; //ifstream mycin("in.txt"); //ofstre...

思路 求长度不小于L的平均值最大的子区间。可以用前缀和+二分的思想去做，复杂度O(nlogn)。对于每个数减去二分的平均值，并且算出前缀和。那么我们用一个数记录前i个数中总和最小的区间[0,k]，那么只需要判断前i个数最大区间[0,i]-[0,k]是否大于0即可。 代码 #include<bits/stdc++.h> #define int long long using namespace std; typedef long long ll; const int maxn=1e5+7; int n,a[maxn],L; double b[maxn],sum[maxn]; bool...

代码 转载自https://www.cnblogs.com/cj-xxz/p/9811806.html写得太好了，可惜没有注释，所以这里解释一下CDQ分治的写法。首先处理前缀和，要求的是sum[j]-sum[i]<t的区间数量。离线操作，对前缀和排序，就变成了一个二维偏序问题，对左区间任意i，右区间取j，答案加上满足偏序关系的对数，类似求逆序对。处理后效性：将计算完的区间排序成一个非降序的区间，可以消除对后续操作的影响。 #include<bits/stdc++.h> #define int long long const int maxn=2e5+7; inline voi...

思路 看到圆就很想吐，但幸好想到了每个圆代表的区间其实就是所以问题就转化为：最少能用多少个子区间将总区间表示出来。然后是怎么选区间的问题，只要将每个区间排序，然后贪心地去选就好了。先排序，每个区间L小在前，然后是R大在前，然后只要我没有达到最大长度，就选一个区间使得我能到达最远的距离，然后ans++，如果选完n个都无法达到那个长度，就输出-1，否则输出ans。做法是O(n^2)的，应该有更优的，但这个数据范围够用了。 代码 #include<iostream> #include<cstring> #include<cmath> #include<alg...

思路 首先tarjan缩点，保证是一个DAG之后，再输出topo排序的起点就可以了。不过数据是不是放水了，我求出来的强连通分量是按访问顺序定谁是fa的，交上去也是对的。难道不应该是要保证每个scc的fa都是里面编号最小那个点吗？所以我弄了个flag数组意义注释了。莫名其妙就A了希望大佬能帮我解答一下。 代码 #include<bits/stdc++.h> using namespace std; const int maxn=1e5+7; inline void read(int &data){ int x=0,f=1;char ch=getchar(); while(ch...

思路 首先如果要求最大前缀的话，我们用Kmp就能线性求出来。题目要求中间也有一个和最大前缀一样的东西，久相对增加了点难度。那我们失配数组每个值出现的次数，如果最终nxt[len]（即整个串的最长后缀）出现过不止一次，就可以输出答案了。但是这样写还需要考虑点细节。比如aaaa的情况，在中间出现的并不能达到最大后缀，该怎么处理？我们考虑一下kmp的失配数组是啥东西。在当前位置失配时，他会跳到前一个最大匹配，因此aaaa在中间找不到aaa这个匹配时，直接向下跳到nxt[nxt[len]]，就可以照顾到中间的字符串。 代码 #include<iostream> #include<cs...

思路 洛谷上额外要输出匹配方案，大家可以做一做，代码上注释了。对每个问题进行二分图最大匹配，套一个匈牙利算法的模板，如果没有找到匹配，马上跳出。 代码 #include<bits/stdc++.h> using namespace std; const int maxn=2005; struct E{ int next,to; }e[maxn<<2]; int n,m,u,v,ans; int head[maxn],cnt; int match[maxn],mt[maxn],vis[maxn],idx; inline void addedge(int from,int ...

思路 无非就两种情况：可二涂色或者存在奇环。那么我们在dfs的过程中留意有无涂色不符的情况，没有发现就直接输出一种涂色方案就行了。现在问题就是找到奇环该怎么输出呢？因为我是个笨比所以一开始写了个tarjan记录SCC，然后去输出第一个奇数并大于1个点的SCC的每一个点编号，结果只过了45.45%（所以看代码的时候请忽略没删的多余变量吧）实际上我们对一个点访问第二次的时候发现它涂色不符，就可以确定我们前面遍历了一个环，而这个环就是奇环，并且在栈中是连续的。我们只需要按照入栈顺序进行输出即可。(写了tarjan还是有所启发的) 代码 #include<bits/stdc++.h> us...

思路 本来想着这是一道最大匹配的水题，没想到忘了变量初始化WA了。用匈牙利算法水过，题意大概是这个意思，假设我们有两个点集X和Y，那么输入就可以转化为二分图两边点的连线情况。交换行列式的过程，实际上是固定一个点集，另外一个点集内部在交换位置（讲得很抽象，画图试试？）然后就可以想到只要每个点都有与之匹配的点就可以完成这个交换了，所以是二分图最大匹配。 代码 #include<bits/stdc++.h> using namespace std; const int maxn=205; struct X{ int next,to; }e[maxn*maxn]; int t,n,flag...

思路 我们采用动态规划的思想，从每一轮出发，计算每支队伍这轮获胜的概率。基于全概率公式，队伍概论胜利的概率可以由对阵其他可以打的队伍获胜的概率之和。现在问题就是如何表示该轮可对阵的队伍：假设由2^n只球队，如果j在[0,2^(n-1)]里面，k在[2^(n-1)+1,2^n]里面，那么很明显他们要在最后一轮才能对决。同理，我们缩小范围,如果将2^n对折i次后，j和k仍在同一区间，则说明在n-i轮他们可以对决(也只有那一轮他们可以对决)于是我们得出下面美观的代码和令人头疼的位运算。（代码参考林厚从的数学一本通） 代码 #include<stdio.h> #include<cst...

思路 稳定婚姻问题，可以直接应用Gale-Shapley算法求解。看到没人交我也不写了，抄了一下林厚从的板子，注释很清楚了。 代码 #include<stdio.h> #include<queue> #include<cstring> #include<algorithm> using namespace std; #define N 35 #define inf 1<<29 #define MOD 2007 #define LL long long using namespace std; int couple; int malel...

思路 先说一下个人思路，由于时间原因我把这题跳了：区间[0,b]中的RN-区间[0,a-1]中的RN就是区间[a,b]中的RN,求所有小于k的RN的个数，可以先找出二进制中k的每一个1，然后在这些1之后的几位数字中填入n个1和m个0(m>=n)，那么这些组合数的结果相加就是小于k的RN个数，答案就能求出来了。 下面这份代码与上面无关，题解转载自林厚从的数学一本通，注释也给你们打好了。 代码 #include<bits/stdc++.h> using namespace std; int c[33][33]={0}; int bin[35]; //十进制n的二进制数 void ...

思路 稍微用点群论的知识，我们可以感觉出它要我们求逆序对。于是我们可以先把a和b的数字和离散化结果记录下来，然后用x存储置换后的结果，然后套个归并排序的板子就OK啦。 代码 #include<bits/stdc++.h> using namespace std; const int maxn=1e5+7; const int mod=1e8-3; struct node{ int num,id; }a[maxn],b[maxn]; int n,x[maxn],t[maxn],ans; bool cmp(node a,node b){ return a.num<b.num; }...

思路 这是一道裸的欧拉函数题目，先线性预处理。对于所有n>2的欧拉函数进行前缀和，然后直接输出答案就可以了。 代码 #include<stdio.h> typedef long long ll; const int maxn=1e6+7; int n,isn_pri[maxn],pri[maxn],phi[maxn],cnt; ll sum[maxn]; void get(int N){ isn_pri[1]=1;phi[1]=1; for(int i=2;i<=N;i++){ if(!isn_pri[i]){ pri[++cnt]=i; phi[i]=i-1; } f...