数学相关
最近把kzf、小狗的课件什么的都过了一下，复习了组合数学，看了两篇论文，然后准备开推鸿少给的题和其他的一些题。
乱入：话说罗大神终于要回来虐我们了真是TATQAQ2333！
BZOJ1968约数研究：只要统计每个数是多少个数的约数即可
BZOJ1211树的计数：直接搞prufer数列，因为每个节点在数列中出现di-1次。然后直接暴力枚举prufer数列个数，但是要注意特判无解。
BZOJ1005明明的烦恼：之前看的时候觉得好神，其实跟上题是一样的，直接搞prufer数列，反正已知的结点必须在数列中di-1次，然后其余部分就随便了，组合数搞搞就出来了。
BZOJ1485有趣的数列：《组合数学》原题，直接上Catalan数列。话说算答案的时候要加特技，先线性筛一下，统计出每个数的最小质因数是哪个，然后将每个合数的系数下传，细节看代码。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long
#define N 2000050
ll ans=1,n,m;
int c[N],p[N],ss=0,v[N];
inline ll Quick_mi(ll x,int y)
{
ll z=1;
while (y)
{
if (y&1) z=(z*x)%m;
x=(x*x)%m;
y/=2;
}
return z;
}
int main()
{
int i,j,k,l,q,w,e;
memset(c,0,sizeof(c));memset(v,0,sizeof(v));
memset(p,0,sizeof(p));
scanf("%d%d",&n,&m);
for (i=2;i<=n << 1;i++)
{
if (!v[i]) p[++ss]=i;
for (j=1;j<=ss;j++)
{
if (p[j]*i>n << 1) break;
v[p[j]*i]=p[j];
if (i%p[j]==0) break;
}
}
for (i=2;i<=n;i++) c[i]=-1;
for (i=n+2;i<=n << 1;i++) c[i]=1;
for (i=n << 1;i>=2;i--)
if (!v[i])
ans=ans*Quick_mi(i,c[i])%m;else
c[v[i]]+=c[i],c[i/v[i]]+=c[i];
printf("%lld\n",ans);
return 0;
}
BZOJ2425计数：这题只要从高位到低位一路扫过去就可以了，因为上界对答案是造成了影响的，所以只要对于每一位统计这一位不取上界并且前面几位都取了上界的答案数，只要记下还有哪些数字没用过，这个用组合数很容易统计。
BZOJ2431逆序对数列：很容易可以得到递推式，设ai,j为i个数j个逆序对的数列，个数就是上一行的j-i+1~j个数的和，这个可以通过ai,j-1消西格玛，然后n和m只有1000，所以O(nm)的递推可以直接出答案。
BZOJ2729排队：完全就是《组合数学》第二章的题，随便算算。
BZOJ2751容易题：设si为前i个数的数列的乘积和，则si+1=si*第i个数的可取的数的和，但是由于n太大了，所以可以对于有限制的数单独算，其余的数直接快速幂统计。
BZOJ3209花神的数论题：水过，也是从高位到低位统计出现1的次数为i的数的个数，最后快速幂乘起来
BZOJ2705Longge的问题：发现就是要我们求Σ(i|n) i*φ(n/i)，然后枚举n的因子i，算φ甚至sqrt(n)都不用，因为n已经因式分解过了，所以直接枚举n的因子算φ。
BZOJ2956模积和：看起来好神，然后随手点开记录发现了第一版的HJWJBSR在3月的记录，顿时吓傻，然后马上想起来当时这题是LAccelerator叫我做的，记得当时想了好久，还被罗大神D了。于是想了想感觉确实不算难：把模化去变成ΣΣ(n-i*[n/i])*(m-j*[m/j])=(nm)^2-n^2Σi[m/i]-m^2Σi[n/i]+ΣΣij[n/i][m/j]，第二项第三项可以通过分块计算n/i然后用前缀和去乘最后加起来就可以了，话说第四项就是第二项第三项的积啊。补：话说好像还有i!=j这个限制于是减去就好了，但是这样好像还是要分块搞，还要用到什么平方和公式的= =真是hentai
BZOJ2242计算器：第一问快速幂，第二问直接移项所以还是快速幂（我还想什么扩展欧几里得真是羞耻），第三问BSGS。
BZOJ2173整数的lqp拆分：直接打表找规律= =
BZOJ2301Problem b：化简式子，线性筛出莫比乌斯函数前缀和，然后貌似就可以分块做了。
BZOJ1004Cards：直接套Burnside引理，DP求中间值。
BZOJ2463谁能赢呢？：可以发现棋盘可以多米诺骨牌覆盖的时候就先手必胜，否则后手必胜。因为先手总要从多米诺骨牌一端走到另一端。所以直接判奇偶。
高斯消元
Orzei了hzwer的代码，还算是学了高斯消元吧。。。然后开始水了几道题。感觉高斯消元的题目有的思路还是很屌的。。。
BZOJ1013球形空间产生器：直接根据每个点到球心的距离相等列方程，然后直接Gauss()
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 105
#define eps 1e-6
#define INF 0x7f7f7f7f
double a[N][N],f[N];
int n;
inline double sqr(double x)
{
return x*x;
}
void Gauss()
{
int now=1,i,j,k;double t;
for (i=1;i<=n;i++)
{
j=now;while (fabs(a[j][i])<eps&&j<=n) j++;
if (j>n) continue;
for (k=i;k<=n+1;k++) swap(a[now][k],a[j][k]);
for (k=i+1;k<=n+1;k++) a[now][k]/=a[now][i];
a[now][i]=1;
for (j=1;j<=n;j++)
if (j!=i)
{
t=a[j][i];
for (k=1;k<=n+1;k++)
a[j][k]-=t*a[now][k];
}
now++;
}
return;
}
int main()
{
int i,j,q,w,e;double k,l;
freopen("input.txt","r",stdin);
memset(f,0,sizeof(f));memset(a,0,sizeof(a));
scanf("%d",&n);
for (i=1;i<=n;i++)
scanf("%lf",&f[i]);
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
{
scanf("%lf",&k);
a[i][j]=2*(k-f[j]);a[i][n+1]+=sqr(k)-sqr(f[j]);
}
Gauss();
for (i=1;i<=n-1;i++)
printf("%.3lf ",a[i][n+1]);
printf("%.3lf\n",a[n][n+1]);
return 0;
}
BZOJ1923外星千足虫：取模高斯消元，感觉很吊，而且新技能get了bitset。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>
using namespace std;
#define N 2050
#define INF 0x7f7f7f7f
typedef bitset<N> M[N];
M a;
int n,m,ans=0;
void Gauss()
{
int i,j,k,l;
for (i=1;i<=n;i++)
{
j=i;while (!a[j][i]&&j<=m) j++;
if (j>m)
{ans=-1;return;}else
ans=max(ans,j);
swap(a[j],a[i]);
for (k=1;k<=m;k++)
if (k!=i&&a[k][i])
a[k]^=a[i];
}
return;
}
int main()
{
int i,j,k,l,q,w,e;
char b[N],c[N];
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++)
{
scanf("%s%s",b,c);a[i][n+1]=c[0]-'0';
for (j=0;j<n;j++)
a[i][j+1]=b[j]-'0';
}
Gauss();
if (ans==-1)
{
printf("Cannot Determine\n");
return 0;
}
printf("%d\n",ans);
for (i=1;i<=n;i++)
if (a[i][n+1])
printf("?y7M#\n");else
printf("Earth\n");
return 0;
}
BZOJ2115XOR：感觉十分屌，可以将图转化为一条从1到n的路径及若干环，环有O(M)个，然后二进制按位看可不可以取，验证就用高斯消元。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 250050
#define ll long long
#define INF 0x7f7f7f7f
int ss=0,n,m,fi[N],c[N][2],tot=1,cir=0;
ll v[N],a2[N],s[N],ans=0,h[N];bool vis[N];
inline ll Read()
{
ll x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y,ll z)
{
c[++ss][0]=y;c[ss][1]=fi[x];s[ss]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];s[ss]=z;fi[y]=ss;
return;
}
void DFS(int x)
{
vis[x]=1;
for (int i=fi[x];i;i=c[i][1])
if (!vis[c[i][0]])
{
h[c[i][0]]=h[x]^s[i];DFS(c[i][0]);
}else
v[++cir]=h[c[i][0]]^h[x]^s[i];
return;
}
void Gauss()
{
int i,j,k,l;ll q,w,e;
for (q=a2[60];q;q >>= 1)
{
j=tot;while (j<=cir&&!(v[j]&q)) j++;
if (j>cir) continue;
swap(v[j],v[tot]);
for (i=1;i<=cir;i++)
if (i!=tot&&v[i]&q)
v[i]^=v[tot];
tot++;
}
return;
}
int main()
{
int i,j,k,l;ll q,w,e;
memset(s,0,sizeof(s));memset(h,0,sizeof(h));
memset(v,0,sizeof(v));memset(c,0,sizeof(c));
memset(a2,0,sizeof(a2));memset(fi,0,sizeof(fi));
memset(vis,0,sizeof(vis));
scanf("%d%d",&n,&m);
for (i=1,a2[0]=1;i<=60;i++) a2[i]=a2[i-1] << 1;
for (i=1;i<=m;i++)
k=Read(),l=Read(),q=Read(),Line(k,l,q);
DFS(1);Gauss();
ans=h[n];
for (i=1;i<tot;i++)
ans=max(ans,ans^v[i]);
cout <<ans<<endl;
return 0;
}
BZOJ2466树：据说只要高斯消元后暴力枚举未确定点DFS，总感觉dzy的代码很高能，现在还是不懂原理。。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define N 110
#define INF 0x7f7f7f7f
int a[N][N];
int n,m,ans,t[N];
void Gauss()
{
int i,j,k,l;
for (i=1;i<=n;i++)
{
j=i;while (!a[j][i]&&j<=n) j++;
if (j>n) continue;
swap(a[j],a[i]);
for (j=1;j<=n;j++)
if (j!=i&&a[j][i])
for (k=1;k<=n+1;k++)
a[j][k]^=a[i][k];
}
return;
}
inline void DFS(int x,int y)
{
if (y>=ans) return;
if (!x) {ans=min(ans,y);return;}
if (a[x][x])
{
t[x]=a[x][n+1];
for (int i=x+1;i<=n;i++)
t[x]^=(t[i]&a[x][i]);
DFS(x-1,y+t[x]);
}else
DFS(x-1,y+(t[x]=0)),DFS(x-1,y+(t[x]=1));
return;
}
int main()
{
int i,j,k,l,q,w,e;
while (scanf("%d",&n),n)
{
ans=INF;
memset(a,0,sizeof(a));memset(t,0,sizeof(t));
for (i=1;i<=n;i++)
a[i][i]=a[i][n+1]=1;
for (i=1;i<n;i++)
scanf("%d%d",&k,&l),a[k][l]=a[l][k]=1;
Gauss();DFS(n,0);
printf("%d\n",ans);
}
return 0;
}
BZOJ2337XOR和路径：之前一直在想怎么设从1到i的二进制位为1的概率写方程，其实还好，但是被样例卡了很久没想出来1怎么处理= =结果应该是设从i到n的二进制位为1的概率（好像确实没区别），并且a[n]设为0。然后按位跑高斯消元求出a[1]，然后带权求和即可。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define N 105
#define M 20050
#define INF 0x7f7f7f7f
int fi[N],c[M][3],n,m,ss=1,d[N];
double a[N][N],ans=0;
long long s=0;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y,int z)
{
c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;fi[y]=ss;
return;
}
void Gauss()
{
int i,j,k;double l;
for (i=1;i<n;i++)
{
j=i;while (!a[j][i]) j++;
swap(a[j],a[i]);
for (j=i+1;j<=n;j++) a[i][j]/=a[i][i];
a[i][i]=1;
for (j=1;j<n;j++)
if (a[j][i]&&j!=i)
{
l=a[j][i];
for (k=1;k<=n;k++)
a[j][k]-=a[i][k]*l;
}
}
return;
}
inline void Set_up(int x)
{
int i,j,k,l;double q,w,e;
for (i=1;i<n;i++)
{
q=1.0/d[i];a[i][i]=-1;
for (j=fi[i];j;j=c[j][1])
if (j%2&&c[j][0]==i) continue;else
if (c[j][0]==n) a[i][n]-=c[j][2]&x?q:0;else
if (c[j][2]&x)
a[i][c[j][0]]-=q,a[i][n]-=q;else
a[i][c[j][0]]+=q;
}
return;
}
int main()
{
int i,j,k,l,q,w,e;
memset(a,0,sizeof(a));memset(c,0,sizeof(c));
memset(fi,0,sizeof(fi));memset(d,0,sizeof(d));
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++)
{
k=Read(),l=Read(),Line(k,l,Read());
d[k]++;if (k!=l) d[l]++;
}
for (s=1;s<=1073741824;s <<= 1)
{
Set_up(int(s));Gauss();
ans+=(int)(s)*a[1][n];
memset(a,0,sizeof(a));
}
printf("%.3lf\n",ans);
return 0;
}
BZOJ3143游走：直接设每个点走过次数的期望列方程，注意边界是an=1以及a1的方程里面要加上1。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1050
#define M 1000050
#define INF 0x7f7f7f7f
struct Edge
{
int u,v;double t;
} b[M];
double a[N][N],ans=0;
int n,m,c[M][2],fi[N],ss=1,d[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line (int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
return;
}
void Gauss()
{
int i,j,k;double l;
for (i=1;i<n;i++)
{
j=i;while (!a[j][i]) j++;
swap(a[i],a[j]);
for (j=i+1;j<=n;j++)
a[i][j]/=a[i][i];
a[i][i]=1;
for (k=1;k<n;k++)
if (k!=i&&a[k][i])
{
l=a[k][i];
for (j=1;j<=n;j++)
a[k][j]-=l*a[i][j];
}
}
return;
}
void Set_up()
{
int i,j,k,l;double q,w,e;
for (i=1;i<n;i++)
{
a[i][i]=-1;
for (j=fi[i];j;j=c[j][1])
if (c[j][0]!=n)
a[i][c[j][0]]=1.0/d[c[j][0]];
}
a[1][n]=-1;
return;
}
inline bool cmp(Edge x,Edge y)
{
return x.t>y.t;
}
int main()
{
int i,j,k,l,q,w,e;
memset(c,0,sizeof(c));memset(a,0,sizeof(a));
memset(fi,0,sizeof(fi));memset(d,0,sizeof(d));
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++)
{
Line(b[i].u=k=Read(),b[i].v=l=Read()),d[k]++,d[l]++;
if (k==n) swap(b[i].u,b[i].v);
}
Set_up();Gauss();
for (i=1;i<=m;i++)
b[i].t=a[b[i].u][n]/d[b[i].u]+a[b[i].v][n]/d[b[i].v];
sort(b+1,b+m+1,cmp);
for (i=1;i<=m;i++)
ans+=b[i].t*i;
printf("%.3lf\n",ans);
return 0;
}
BZOJ3503和谐矩阵：由于元素数量过多，不能直接列方程，但是可以推出每个格子是哪些第一行元素的异或和，然后就直接列异或方程。但是最后求可行解的部分好像加了特技= =（其实是人太naive一开始还写什么DFS之类的什么找可行解）具体部分看代码吧。。。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 105
#define M 10050
#define ll long long
#define INF 0x7f7f7f7f
int a[N][N],n,m,c[N][N],ss;
ll b[N][N];
void Gauss()
{
int i,j,k,l;
for (i=1;i<=m;i++)
{
j=i;while (j<=m&&!a[j][i]) j++;
if (j>m) continue;
swap(a[i],a[j]);
for (j=1;j<=m;j++)
if (j!=i&&a[j][i])
for (k=1;k<=m;k++)
a[j][k]^=a[i][k];
}
for (i=m;i>=1;i--)
{
if (!a[i][i])
{c[1][i]=1;continue;}
for (j=i+1;j<=m;j++)
c[1][i]^=a[i][j]&c[1][j];
}
return;
}
int main()
{
int i,j,k,l,q,w,e;
memset(a,0,sizeof(a));memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
scanf("%d%d",&n,&m);
b[1][1]=1;for (i=2;i<=m;i++) b[1][i]=b[1][i-1] << 1;
for (i=2;i<=n+1;i++)
for (j=1;j<=m;j++)
b[i][j]=b[i-1][j-1]^b[i-1][j]^b[i-1][j+1]^b[i-2][j];
for (i=1;i<=m;i++)
for (j=1;b[n+1][i];j++)
a[i][j]=b[n+1][i]%2,b[n+1][i]/=2;
Gauss();ss=0;
for (i=2;i<=n;i++)
for (j=1;j<=m;j++)
c[i][j]=c[i-1][j-1]^c[i-1][j]^c[i-1][j+1]^c[i-2][j];
for (i=1;i<=n;i++)
{
for (j=1;j<=m;j++)
printf("%d ",c[i][j]);
printf("\n");
}
return 0;
}
先更到这里吧，感觉再多题目我也还是做不出来= =先提高自身姿势再来填坑吧。。。
可并堆（实际上只有左倾树）
最近状态实在爆炸，不知为何做题真心没劲。
学了下左倾树，（二项堆到现在都没写，因为没看到有什么题是二项堆能写但是左倾树不能的= =）然后做了两道裸题：
BZOJ2333棘手的操作：= =2333。。本来想怎么用二项堆做的= =但是二项堆貌似打标记很困难的样子，然后果断写了左倾树。然后这些操作就裸了。。（第一次写的左倾树代码好丑，还是不要看的好 虽然我的代码一直很丑。。。）
#include <iostream>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
#define N 500050
#define INF 0x7f7f7f7f
struct Point
{
int c[2],fa,v,adv,h,sg;bool ad;
} a[N];
int n,m,add=0,t[N];
multiset <int> li;
inline int Read()
{
int x=0;char y;bool z=0;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
inline void adj (int x)
{
if (!x||!a[x].ad) return;
a[x].v+=a[x].adv;
a[a[x].c[0]].ad=a[a[x].c[1]].ad=1;
a[a[x].c[0]].adv+=a[x].adv;a[a[x].c[1]].adv+=a[x].adv;
a[0].ad=a[0].adv=a[x].ad=a[x].adv=0;
return;
}
inline void Down(int x)
{
adj(x);adj(a[x].c[0]);adj(a[x].c[1]);
return;
}
void DFS (int x)
{
if (a[x].fa) DFS(a[x].fa);Down(x);
return;
}
int Merge(int x,int y)
{
if (!x||!y) return x+y;
Down(x);Down(y);
if (a[y].v>a[x].v)
swap(x,y);
a[x].c[1]=Merge(a[x].c[1],y);a[a[x].c[1]].fa=x;
a[x].h=min(a[a[x].c[1]].h,a[a[x].c[0]].h)+1;
if (a[x].h!=a[a[x].c[1]].h+1)
swap(a[x].c[0],a[x].c[1]);
return x;
}
inline void Line (int x,int y)
{
while (a[x].fa) x=a[x].fa;
while (a[y].fa) y=a[y].fa;
if (x==y) return;
li.erase(li.lower_bound(-a[x].v));
li.erase(li.lower_bound(-a[y].v));
li.insert(-a[Merge(x,y)].v);
return;
}
int main()
{
int i,j,k,l,q,w,e;
set <int> :: iterator it;
char b[20];li.clear();
scanf("%d",&n);a[0].v=INF;a[0].h=0;
for (i=1;i<=n;i++)
a[i].v=Read(),a[i].c[0]=a[i].c[1]=a[i].ad=a[i].adv=
a[i].fa=a[i].ad=0,a[i].h=1,li.insert(-a[i].v),
t[i]=a[i].sg=i;
scanf("%d",&m);
for (i=1;i<=m;i++)
{
scanf("%s",b);
if (b[0]=='F')
{
if (b[1]=='1')
DFS(k=t[Read()]),printf("%d\n",a[k].v+add);else
if (b[1]=='2')
{
k=Read();
while (a[k].fa) k=a[k].fa;
printf("%d\n",a[k].v+add);
}else printf("%d\n",-*li.begin()+add);
}else
if (b[0]=='A')
{
if (b[1]=='3') add+=Read();else
if (b[1]=='2')
{
k=Read();
while (a[k].fa) k=a[k].fa;
a[k].ad=1;a[k].adv=Read();
li.erase(li.lower_bound(-a[k].v));
Down(k);
li.insert(-a[k].v);
}else
{
DFS(k=t[Read()]);l=Read();
if (l<0)
{
w=a[k].fa;
if (!w) li.erase(li.lower_bound(-a[k].v));
a[k].v+=l;
while (1)
{
Down(k);
q=a[k].c[!a[k].c[0]||(a[k].c[1]&&a[k].
c[0]&&a[a[k].c[1]].v>a[a[k].c[0]].v)];
if (q&&a[q].v>a[k].v)
swap(a[q].v,a[k].v),
swap(a[q].sg,a[k].sg),
swap(t[a[q].sg],t[a[k].sg]),k=q;else
break;
}
if (!w)
{
while (a[k].fa) k=a[k].fa;
li.insert(-a[k].v);
}
}else
if (!a[k].fa)
{
li.erase(li.lower_bound(-a[k].v));
a[k].v+=l;li.insert(-a[k].v);
}else
{
a[k].v+=l;
while (a[k].v>a[a[k].fa].v&&a[a[k].fa].fa)
swap(a[k].v,a[a[k].fa].v),
swap(a[k].sg,a[a[k].fa].sg),
swap(t[a[k].sg],t[a[a[k].fa].sg]),
k=a[k].fa;
if (a[k].v>a[a[k].fa].v)
li.erase(li.lower_bound(-a[a[k].fa].v)),
li.insert(-a[k].v),
swap(a[k].v,a[a[k].fa].v),
swap(a[k].sg,a[a[k].fa].sg),
swap(t[a[k].sg],t[a[a[k].fa].sg]);
}
}
}else
Line(Read(),Read());
}
return 0;
}
BZOJ2809dispatching：据说是P神那届APIO的题，感觉还是很裸，我写了左倾树启发式合并。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100050
#define INF 0x7f7f7f7f
#define ll long long
ll ans=0,t[N];
int n,m,v[N],fa[N],c[N][2],fi[N],ne[N],gf[N],h[N],sum[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline int Merge(int x,int y)
{
if (!x||!y) return x+y;
if (v[x]<v[y]) swap(x,y);
c[x][1]=Merge(c[x][1],y);fa[c[x][1]]=x;
h[x]=min(h[c[x][0]],h[c[x][1]])+1;
if (h[x]!=h[c[x][1]]+1)
swap(c[x][1],c[x][0]);
return x;
}
inline int Pop(int x)
{
int i=v[gf[x]];
gf[x]=Merge(c[gf[x]][0],c[gf[x]][1]);fa[gf[x]]=0;
return i;
}
int DFS(int x)
{
int i,j,k,l,q,w,e;ll s=0;
gf[x]=x;h[x]=1;s=v[x];sum[x]=1;
for (i=fi[x];i;i=ne[i])
{
s+=DFS(i);gf[x]=Merge(gf[i],gf[x]);sum[x]+=sum[i];
}
while (s>m) s-=Pop(x),sum[x]--;
ans=max(t[x]*sum[x],ans);
return s;
}
int main()
{
int i,j,k,l,q,w,e;
memset(v,0,sizeof(v));memset(t,0,sizeof(t));
memset(c,0,sizeof(c));memset(h,0,sizeof(h));
memset(fi,0,sizeof(fi));memset(ne,0,sizeof(ne));
memset(gf,0,sizeof(gf));memset(fa,0,sizeof(fa));
memset(sum,0,sizeof(sum));
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
fa[i]=Read(),v[i]=Read(),t[i]=Read(),
ne[i]=fi[fa[i]],fi[fa[i]]=i;
DFS(1);
printf("%lld\n",ans);
return 0;
}
还有道题跟可并堆并没有什么关系的：
BZOJ1078斜堆：思路也都想的差不多，但是感觉自己就是集中不了注意力，感觉一直在胡思乱想，然后就直接翻题解去了，这种状态还怎么愉快地玩耍啊！其实感觉好像是晚饭吃太饱了= =可以发现最后删除的结点一定在当前树一直往左的路径上，并且不会有右子树，并且一定是这些点中深度最小的（还有种情况是左路径上存在两个没有右子树的点互为父子则选叶子结点的那个），这些性质都十分可证。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 205
#define INF 0x7f7f7f7f
int fa[N],gf=0,c[N][2],n,m,li[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
int DFS(int x)
{
int i;
if (!c[x][1]&&(!c[x][0]||c[c[x][0]][0]+c[c[x][0]][1]))
{
if (fa[x])
c[fa[x]][0]=c[x][0];else
gf=c[x][0];
fa[c[x][0]]=fa[x];
return x;
}
i=DFS(c[x][0]);swap(c[x][0],c[x][1]);
return i;
}
int main()
{
int i,j,k,l,q,w,e;
memset(fa,0,sizeof(fa));memset(c,0,sizeof(c));
scanf("%d",&n);gf=n+1;
for (i=1;i<=n;i++)
{
k=Read();
if (k<100) c[k][0]=i;else c[k-=100][1]=i;
fa[i]=k;
}
c[n+1][0]=c[0][0];c[n+1][1]=c[0][1];
fa[c[n+1][0]]=n+1;fa[c[n+1][1]]=n+1;
c[0][0]=c[0][1]=0;
for (i=1;i<=n+1;i++)
li[n+1-i]=DFS(gf);
for (i=0;i<=n;i++)
printf("%d ",li[i]==n+1?0:li[i]);
printf("\n");
return 0;
}
BZOJ4003城池攻占：裸的打标记左倾树，一开始写丑了，加了一堆不必要的东西，然后不想重写，于是一直改一直wa，后来重写之后又wa了几次终于过了。代码能力是硬伤！
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 300050
#define INF 0x7f7f7f7f
#define ll long long
int s[N],ss[N],gf[N],n,m,as[N],h[N];
int c[N][2],fi[N],ne[N],ff[N],nf[N],a[N];
ll v[N],t[N],ad[N],xj[N],r[N];
inline ll Read()
{
ll x=0;char y;bool z=0;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
inline void Down(int x)
{
if (!x) return;
if (xj[x]!=1)
{
t[x]*=xj[x];ad[c[x][0]]*=xj[x];ad[c[x][1]]*=xj[x];
xj[c[x][0]]*=xj[x];xj[c[x][1]]*=xj[x];xj[x]=1;
}
if (ad[x])
{
t[x]+=ad[x];ad[c[x][0]]+=ad[x];ad[c[x][1]]+=ad[x];ad[x]=0;
}
if (as[x])
{
s[x]+=as[x];as[c[x][0]]+=as[x];as[c[x][1]]+=as[x];as[x]=0;
}
return;
}
int Merge(int x,int y)
{
if (!x||!y) return x+y;
Down(x);Down(y);
if (t[x]>t[y]) swap(x,y);
c[x][1]=Merge(c[x][1],y);
h[x]=min(h[c[x][1]],h[c[x][0]])+1;
if (h[x]!=h[c[x][1]]+1) swap(c[x][0],c[x][1]);
return x;
}
inline void Pop(int x)
{
ss[x]++;gf[x]=Merge(c[gf[x]][0],c[gf[x]][1]);
return;
}
void DFS(int x)
{
for (int i=ff[x];i;i=nf[i])
gf[x]=Merge(gf[x],i);
for (int i=fi[x];i;i=ne[i])
DFS(i),gf[x]=Merge(gf[x],gf[i]);
while (Down(gf[x]),t[gf[x]]<v[x]&&gf[x]) Pop(x);
if (!gf[x]) return;Down(gf[x]);
if (a[x]) xj[gf[x]]=r[x];else ad[gf[x]]=r[x];
as[gf[x]]=1;
return;
}
int main()
{
int i,j,k,l,q,w,e;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++) v[i]=Read();
for (i=2;i<=n;i++)
ne[i]=fi[k=Read()],fi[k]=i,a[i]=Read(),r[i]=Read();
for (i=1;i<=m;i++)
t[i]=Read(),nf[i]=ff[k=Read()],ff[k]=i,xj[i]=h[i]=1;
v[0]=(ll)(1e18);
fi[0]=1;DFS(0);
for (i=1;i<=n;i++)
printf("%d\n",ss[i]);
for (i=1;i<=m;i++)
printf("%d\n",s[i]);
return 0;
}
可并堆也更到这里算了，话说右边那个播放器感觉蛮好玩的于是搞了一个，把看过的一些番的不错的OP、ED、人物歌什么的放上来了，Claris赛高！
网络流题汇总
最近一直在做网络流相关，于是都放上来了= =
BZOJ2127happiness：最小割
BZOJ3144切糕：最小割
BZOJ1497最大获利：胡BT论文题，裸最大权闭合子图。
BZOJ1443游戏Game：首先黑白染色构二分图，然后二分图中所有不一定在最大匹配中的点就是所求的答案。证明之类的细节详见CYB2015年论文
BZOJ2229最小割：图中的最小割两两不相交，然后n次最小割就可以了。
BZOJ2039employ人员雇佣：最小割
BZOJ2150部落战争：最小路径覆盖，网络流可以拆入点出点，S往出点连1，入点往T连1，中间的边INF，用点数-C[S,T]。或者直接Hungary
SPOJ Optimal Marks (OPTM)：胡BT论文题，按位跑网络流
BZOJ1066蜥蜴：最大流
BZOJ1433假期的宿舍：被模糊不清的题意坑了n次，而且^跟＾还有区别= =真心caodan。裸的二分图匹配，我用网络流写的= =
BZOJ1797Mincut最小割：貌似是跑一遍最小割，然后再残量网络中跑一遍强连通分量。设这条边的两端为u和v，如果这条边满流而且u和S在同一强连通分量里面且v和T在同一强连通分量里面就说明这条边必须割（试着给这条边增大流量限制显见）。如果这条边满流而且u和v不在同一强连通分量里面就说明这条边可以割。（真心不会证，网上也没什么好的证明= =跟duyege想了好久也是伪证）
BZOJ1266上学路线route：建最短路图然后跑最小割= =（然后这题时限caodan我换了几种姿势始终跑不过= =不知为何感觉我的dinic就是要比别人常数大）
BZOJ3504危桥：结论题，网上的题解都是些什么：“如果直接S连a1、b1，a2、b2连T，可能会a1流到b2、b1流到a2，所以要将起点换成b2，终点换成b1再跑一遍看两次是不是都是满流”，看上去好像“显而易见”一样，靠谱的证明一个都没有TATQAQ2333。
BZOJ1412狼和羊的故事：最小割
BZOJ1305跳舞dance：二分答案，拆点，给连坏边的点加上限制k，所有二分图中的边权为1，然后跑最大流= =
BZOJ1189紧急疏散：对于门按时间拆点，如果空地上这个人可以走到这个门就往这个门的那个时候连边，二分时间后每个门的当前时间t往t+1连INF。
BZOJ1822 Frozen Nova 冷冻波：建图很水，暴力连边然后二分答案跑网络流，但是计算几何真心caodan，而且貌似如果巫妖和小精灵与树相切是可以打到的。。。
BZOJ2756奇怪的游戏：显然如果n*m为偶数并且黑白染色后黑格之和不等于白格之和则无解，还有n*m为奇数并且黑白染色后黑格之和减去白格之和比最大值要小也是无解的。否则将图重建成二分图，然后二分答案网络流验证答案。如果学我的dinic不敢加优化会一直T一直T一直T= =
BZOJ1143祭祀：果然最近太颓了么= =一直没有看出来。传递闭包+最长反链（即最小链覆盖，即总点数-拆点后可达两点连边的二分图匹配数，YY可证）
为了方便，一条边的流量fi和费用vi用{fi,vi}表示
BZOJ1834网络扩容：第一问水过，第二问在残量网络上再给原图每条边复制一条流量INF、费用不变的边，残量网络无费用。
BZOJ1221软件开发：费用流，理解这么久我真是废到一定境界了，但确实感觉费用流比最小割的题目要caodan些= =。每个点拆成xi和yi，分别代表第i天的好毛巾和没洗毛巾，则S往xi连{ni,0}，S往yi连{INF,f}，yi往T连{ni,0}，xi往xi+1连{INF,0}，xi往y(i+a+1)连{INF,fa}，xi往y(i+b+1)连{INF,fb}，然后跑一遍。
BZOJ2661连连看：费用流。好神（keng）的题，看上去是一般图最大权匹配，实际上测试了一下才知道是二分图= =然后就黑白染色，暴力建图跑了。。（补：后来跑了一下大数据，然后这性质就果断不成立了，网上的什么拆点的如果碰到这种奇环也貌似是会挂的= =出题人sxbk）
BZOJ2424订货：费用流：拆点都不需要，很水的建图。
BZOJ2597剪刀石头布：费用流：确实很经典的题，很屌的建图。设每个点胜的场数为d[i]，则ans=C(n,3)-ΣC(d[i],2)，自行脑补。。然后化下式子变成C(n,3)+C(n,2)/2-Σd[i]^2/2，所以就对每个比赛建个点并且向T连{1,0}的边，每个点向它可能会胜利的比赛连{1,0}，S向每个点连{1,1}、{1,3}、{1,5}……这样可以保证是d[x]^2，然后跑费用流结果就是Σd[i]^2。
BZOJ1927星际竞速：费用流，最小权值路径覆盖。想了好久真是羞耻，就是拆点成Ui、Vi之后S往Ui连{1,0}，S往Vi连{1,Ai}，Vi往T连{1,0}，然后原图中的边i->j,w就连Ai往Bj连{1,w}，然后直接跑。
然后除了两个wa了n久的坑等着填，还有单纯性、zkw费用流什么的没学，网络流相关的东西就先搞到这里了。
现在貌似没什么很多时间了= =接下来是背堆模板？
算了感觉费用流的比例有点不太和谐，在颓废一个晚上算了= =应该不会拖进度吧。。。
不管了接着更，话说晚上状态真心不好：
BZOJ1930吃豆豆：看上去很裸，但是一来卡内存，二来卡时间，如果暴力建边会有n^2规模。（madan HZWER把把暴力建边的代码放到博客里面了，搞得我还一直以为这种暴力没人卡的。。。）反正就是要加优化：原来是对于每个点拆点然后流量限制都是1，但是现在允许一个点被走两次，但其中只算一次的豆豆，然后如果存在三个点a->b->c则a不往c连边，这样就可以跑出来了。这个正确性还算比较显然吧。。。
BZOJ1877晨跑：裸建图费用流
BZOJ3171循环格：反正每个点的入度都要为1，所以拆点，每两个相邻点相连，然后如果这条边原图中存在则费用为0否则为1，然后每个出点往T连1。
BZOJ2245工作安排：裸建图，一开始看错题了真是羞耻。。
BZOJ1070修车：把技术人员按倒数第几修的车拆点，然后连边跑跑跑！
BZOJ2879美食节：真心屌！虽然题目意思跟上题一毛一样，但是数据扩大了n倍，于是考虑优化连边，如果一个厨师倒数第k个还没流就不可能会流倒数第k+1个，于是动态连边，如果k满流了就建k+1的边。
BZOJ1565植物大战僵尸：最大权闭合子图乱入！很容易看出来是这个模型。同时还要注意有的点永远到不了，所以要先拓扑排序搞一波。
这次是真的不更了！
分层图
终于不是网络流了= =
BZOJ2763/2662
题意都差不多，代码都只差一点= =：都是在一个无向图中，你一共有k次改变一条边上的权值的机会，求最短路= =（两道题在细节上有一点区别= =）
做法：拆成k个点，然后再跑最短路= =，貌似叫做分层图。
2763：
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define N 10050
#define M 100050
#define INF 0x7f7f7f7f
struct Point
{
int a1,a2;
};
queue <Point> a;
int fi[N],c[M][3],h[N][20],n,m,v,S,T,ss=0;
bool b[N][20];
inline int Read()
{
int x=0;char y;
do y=getchar();while (y<'0'||y>'9');
do x=(x << 3)+(x << 1)+y-'0',y=getchar();
while (y>='0'&&y<='9');
return x;
}
inline void Line (int x,int y,int z)
{
c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;fi[y]=ss;
return;
}
int main()
{
int i,j,q,w,e;
Point k,l;
memset(c,0,sizeof(c));memset(h,0,sizeof(h));
memset(fi,0,sizeof(fi));memset(b,0,sizeof(b));
scanf("%d%d%d%d%d",&n,&m,&v,&S,&T);
for (i=1;i<=m;i++)
q=Read(),w=Read(),e=Read(),Line(q,w,e);
for (i=0;i<n;i++)
for (j=0;j<=v;j++)
h[i][j]=INF;
h[S][0]=0;k.a1=S;k.a2=0;a.push(k);b[S][0]=1;
while (!a.empty())
{
k=a.front();
for (i=fi[k.a1];i;i=c[i][1])
{
if (h[c[i][0]][k.a2]>c[i][2]+h[k.a1][k.a2])
{
h[c[i][0]][k.a2]=c[i][2]+h[k.a1][k.a2];
if (!b[c[i][0]][k.a2])
b[c[i][0]][k.a2]=1,l=k,l.a1=c[i][0],
a.push(l);
}
if (k.a2<v&&h[c[i][0]][k.a2+1]
>h[k.a1][k.a2])
{
h[c[i][0]][k.a2+1]=h[k.a1][k.a2];
if (!b[c[i][0]][k.a2+1])
b[c[i][0]][k.a2+1]=1,l=k,l.a1=c[i][0],l.a2++,
a.push(l);
}
}
a.pop();b[k.a1][k.a2]=0;
}
e=INF;
for (i=0;i<=v;i++)
e=min(e,h[T][i]);
printf("%d\n",e);
return 0;
}
2662：
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define N 10050
#define M 100050
#define INF 0x7f7f7f7f
struct Point
{
int a1,a2;
};
queue <Point> a;
int fi[N],c[M][3],h[N][20],n,m,v,S,T,ss=0;
bool b[N][20];
inline int Read()
{
int x=0;char y;
do y=getchar();while (y<'0'||y>'9');
do x=(x << 3)+(x << 1)+y-'0',y=getchar();
while (y>='0'&&y<='9');
return x;
}
inline void Line (int x,int y,int z)
{
c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;fi[y]=ss;
return;
}
int main()
{
int i,j,q,w,e;
Point k,l;
memset(c,0,sizeof(c));memset(h,0,sizeof(h));
memset(fi,0,sizeof(fi));memset(b,0,sizeof(b));
scanf("%d%d%d",&n,&m,&v);S=1;T=n;
for (i=1;i<=m;i++)
q=Read(),w=Read(),e=Read(),Line(q,w,e);
for (i=1;i<=n;i++)
for (j=0;j<=v;j++)
h[i][j]=INF;
h[S][0]=0;k.a1=S;k.a2=0;a.push(k);b[S][0]=1;
while (!a.empty())
{
k=a.front();
for (i=fi[k.a1];i;i=c[i][1])
{
if (h[c[i][0]][k.a2]>c[i][2]+h[k.a1][k.a2])
{
h[c[i][0]][k.a2]=c[i][2]+h[k.a1][k.a2];
if (!b[c[i][0]][k.a2])
b[c[i][0]][k.a2]=1,l=k,l.a1=c[i][0],
a.push(l);
}
if (k.a2<v&&h[c[i][0]][k.a2+1]
>h[k.a1][k.a2]+c[i][2]/2)
{
h[c[i][0]][k.a2+1]=h[k.a1][k.a2]+c[i][2]/2;
if (!b[c[i][0]][k.a2+1])
b[c[i][0]][k.a2+1]=1,l=k,l.a1=c[i][0],l.a2++,
a.push(l);
}
}
a.pop();b[k.a1][k.a2]=0;
}
e=INF;
for (i=0;i<=v;i++)
e=min(e,h[T][i]);
printf("%d\n",e);
return 0;
}
