题目 1.splay 题解   #include<cstdio> const int N=100003,inf=1<<30; int n,x,opt; struct Splay{ #define rt e[0].ch[1] struct node{ int ch[2],fa,v,sum,same; }e[N]; int n,point; void update(int x){ e[x].sum=e[e[x].ch[0]].sum+e[e[x].ch[1]].sum+e[x].same; } int id(int x){ return x==e[e[x].fa].ch[1...

题目 #1.Burnside引理 Burnside引理与Polya定理 题解 //d[i]表示第i个循环的长度，b[i]是标记 #include<bits/stdc++.h> using namespace std; int f[22][22][22],i,b[62],a[62][62],n,m,ans,sr,sb,sg,M,x,d[62],j,y; int dp(int x){ memset(b,0,sizeof(b)); int sum=0,p; for (int i=1;i<=n;i++) if (!b[i]){ d[++sum]=0; for (p=i;!b[p];p...

题目  题解 #include<bits/stdc++.h> #include<tuple> using namespace std; typedef tuple<int,int> ti; typedef long long ll; #define mt make_tuple const int N=4002; struct node{ int to,ne; }e1[N<<1],e2[N<<1]; int n,a,b,x,y,xx[N],yy[N],h1[N],h2[N],tot1,tot2,i,vis[N]; ll ans; inl...

题目 题解 BBP算法  题解 标程： #include<bits/stdc++.h> using namespace std; typedef long long ll; double v; int n,T,Case; void out(int x){ if (x<10) putchar(x+48); else putchar(x-10+'A'); putchar('\n'); } ll pow(ll x,ll y,ll M){ ll z=1; for (;y;y>>=1,x=x*x%M) if (y&1) z=z*x%M; return z; } do...

题目 题解： 因为每个点都对应年份和降雨量，我就用i，j代表年份，i值，j值代表这年的降雨量  四种情况：  （1）i，j均未知：输出可能；  （2）i知，j未知：因为j值最大可以和i值相等，所以如果i到j之间有大于i值的需输出错，否则输出可能；  （3）i未知，j知：如果i到j之间有大于j值的输出错，否则输出可能；  （4）i知，j知：如果i到j中已知的大于j值或j值大于i值，则输出错，如果没有大于j值的且i到j所有年份已知输出可能，否则输出对。  注：lower_bound(begin,end,k)函数这里找的是大于等于k的第一个位置 标程： #include<bits/stdc++...

题目  矩阵快速幂做法 题解： 这题真的很麻烦，有多种情况要讨论  公式不会编辑，将就着看一下吧  我的sigma如果上下界没注明，那就默认是1和n的   代码有点烦，还是不要看的好，最多拿来对拍一下  注意：ex_gcd中a，b不能是负数，要处理一下 #include<bits/stdc++.h> using namespace std; const int M=1e9+7; typedef long long ll; ll p,q,r,n,P,Q,tmp,k,K,y,t,T,ans; void ex_gcd(ll a,ll b,ll &x,ll &y){ if ...

题目  题解  树形DP，没有上司的舞会的模型  根据题目可以知道， 每一个联通块里有且只有一个环， 所以我们找到这个环然后从中间把它断开， 对断开的两个端点u1, u2, 分别舞会。  设dp[u][0]为不选u, dp[u][1]为选u，  那么这个联通块答案就是max(dp[u1][0], dp[u2][0])。  注意有好多联通块。对于所有联通块跑dp，加起来就是答案  我在这里解释一下为什么是max(dp[u1][0],dp[u2][0])  就拿样例来举例：  3  10 2  20 3  30 1  如果把2和3断开，那么就形成一条链2-1-3，如果是取了dp[u1][1]或dp...

题目 题解  用f[i][j][x][y]表示到第i个人，总共j个男生，以i结尾的任意长度中男生最多比女生多x，女生最多比男生多y的方案数。 状态转移如下： 如果x+1<=k，f[i+1,j+1,x+1,max(y-1,0)]+=f[i][j][x][y] 如果y+1<=k，f[i+1,j,max(x-1,0),y+1]+=f[i][j][x][y] 最终答案为∑(0≤i≤k)∑(0≤j≤k)f[n+m][n][i][j]。  #include<bits/stdc++.h> using namespace std; const int M=12345678; int n...

题目  题解  首先我们考虑偶数个点和奇数个点的方阵枚举中心方式不太相同，我们用类似manacher的处理方法，填上一堆0，把他们全都变成奇数的情况。然后我们枚举每一个点作为中心，二分答案找到以这个点为中心最大的合法方阵。就可以直接统计这个点对答案的贡献了。这样已经是O(n^2logn)的了，我们需要O(1)判断一个方阵是否上下左右均对称。类似不用manacher求最长回文子串的方法，把这个子串镜像过来求最长公共子串，我们分别做出这个矩阵的上下镜面和左右镜面，然后每次就只需要判定这三个方阵区域是否相同。可以用二维hash预处理来O(1)判断。  温馨提醒：此题需卡常，inline和读入优化需要...

转自f-zyj  ForeWord 六月六开始（话说，开始的日子真是个吉利的日子）到七月廿六，五十天整，终于将ACM在线模版整理完毕，想想还有点小激动呢~ 话说，我为什么执着于整理这个模板呢？既费时又费力，差不多，五十天都在忙这个。  想来，原因挺多的，毕竟网上模版那么多，如果单单只是其中任何一条存在，我一定不会这样卖力整理。 最直接的原因，上一次的ACM竞赛，让我深深认识到了模版的重要性，也让我感到了不适，比赛时很乏力。 说起来不适，就不得不承认一点，我的知识储备量严重不足，不足以驾驭模版，至于另一点则是对模版不熟悉，无法快速查阅。其实还有第三点原因，这个原因只会出现在我这种人面前，那就是编...

题目  题解 #include<bits/stdc++.h> using namespace std; const int N=1002; int P[N],C[N],c[N],p[N],cnt,cnt1,x,y,tag,i,n,tmp; void ins(int *A,int k,int x){ while (k && x<A[k-1]) A[k]=A[k-1],k--; A[k]=x; } int main(){ scanf("%d",&n); for (i=0;i<n;i++){ scanf("%d%d&quo...

题目 题解： 第一次做三维空间的题。提交7次，终于A了，感人啊  说一下我的心路历程。  刚开始，我的想法是，把所有空的都标记好，其他的都设为有方块（这部就叫做镂空吧），判断是否可行后灌水，看看联通块个数是否为1  但是，WA了，下载数据后发现，如果把剩下的都设为方块，有可能会多设了方块导致多出一个联通块，那怎么办呢  起先，我百思不得其解，在想如何构造一个符合要求的图（符合三视图）。但事实上不用这样，只要在镂空的基础上，判断每个联通块是否可以单独构成一个符合要求的图就行，只要有一个可行就possible  可是会不会我的构图方法中，每个联通块均不符合条件，但是有一张符合要求的图，也联通，却符...

题目 k-d树 题解 注意：程序中的D是全局变量，用于排序中的比较 #include<cstdio> #include<algorithm> using namespace std; const int N=200002; int n,m,x,y,ans,opt,A,xx,yy,D,i; inline char gc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } #...

博客1  博客2