#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define INF 2000000000
#define Clear(x, Num) memset(x, Num, sizeof(x))
#define Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
#define Maxn 300010
typedef long long ll;

struct Segmentle_Tree
{
    int l, r, Add, Max, Cover;
}Seg[Maxn<<2];

struct Egde
{
	int u, v, w;
}Link[Maxn];

int T, n, tree_size;
int size[Maxn], son[Maxn], f[Maxn], dep[Maxn], w[Maxn], pos[Maxn], top[Maxn], x, y, z;
int To[Maxn<<1], Next[Maxn<<1], Head[Maxn], Cnt, root, q;
char str[110];


inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }
inline void read(int &x){ char ch; int N=1; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-1; while ((ch=G_c()) && (!Dig(ch))); } x=ch-48; while ((ch=G_c()) && (Dig(ch))) x=x*10+ch-48; x*=N; }
inline void Insert(int u, int v) { To[Cnt]=v; Next[Cnt]=Head[u]; Head[u]=Cnt++; }

inline void Mem()
{
	Clear(Head, -1); Cnt=0;
	root=(n+1)>>1; f[root]=0; tree_size=0; dep[root]=0;
}

void dfs(int u)
{
	size[u]=1; son[u]=0;
	for (int p=Head[u]; p!=-1; p=Next[p])
	{
		int v=To[p];
		if (v!=f[u])
		{
			f[v]=u;
			dep[v]=dep[u]+1;
			dfs(v);
			if (size[v]>size[son[u]]) son[u]=v;
			size[u]+=size[v];
		}
	}
}

void build_tree(int u, int father)
{
	w[u]=++tree_size; top[u]=father;
	if (son[u]) build_tree(son[u], father);
	for (int p=Head[u]; p!=-1; p=Next[p])
	{
		int v=To[p];
		if ((v^son[u]) && (v^f[u])) build_tree(v, v);
	}
}

void Create(int id, int l, int r)
{
	Seg[id].l=l; Seg[id].r=r; Seg[id].Max=0; Seg[id].Add=0; Seg[id].Cover=-1;
	if (l==r) return;
	int mid=(l+r)>>1;
	Create(id<<1, l, mid); Create(id<<1|1, mid+1, r);
}

inline void Push_down(int id)
{
	if (Seg[id].Cover!=-1)
		if (Seg[id].l!=Seg[id].r)
		{
			Seg[id<<1].Max=Seg[id<<1|1].Max=Seg[id<<1].Cover=Seg[id<<1|1].Cover=Seg[id].Cover;
			Seg[id<<1].Add=Seg[id<<1|1].Add=0;
			Seg[id].Cover=-1;
		}
		else Seg[id].Cover=-1;
	if (Seg[id].Add!=0)
		if (Seg[id].l!=Seg[id].r)
		{
			Seg[id<<1].Max+=Seg[id].Add, Seg[id<<1|1].Max+=Seg[id].Add;
			Seg[id<<1].Add+=Seg[id].Add, Seg[id<<1|1].Add+=Seg[id].Add;
			Seg[id].Add=0;
		}
		else Seg[id].Add=0;
}

inline void Update(int id)
{
	Seg[id].Max=max(Seg[id<<1].Max, Seg[id<<1|1].Max);
}

void Modify_Cover(int id, int l, int r, int delta)
{
	if (l>r) return;
	Push_down(id);
	if ((Seg[id].l==l) && (Seg[id].r==r))
	{
		Seg[id].Max=delta; Seg[id].Add=0; Seg[id].Cover=delta;
		return;
	}
	int mid=(Seg[id].l+Seg[id].r)>>1;
	if (r<=mid) Modify_Cover(id<<1, l, r, delta);
	else
		if (l>mid) Modify_Cover(id<<1|1, l, r, delta);
		else
			Modify_Cover(id<<1, l, mid, delta), Modify_Cover(id<<1|1, mid+1, r, delta);
	Update(id);
}

void Modify_Add(int id, int l, int r, int delta)
{
	if (l>r) return;
	Push_down(id);
	if ((Seg[id].l==l) && (Seg[id].r==r))
	{
		Seg[id].Max+=delta; Seg[id].Add+=delta;
		return;
	}
	int mid=(Seg[id].l+Seg[id].r)>>1;
	if (r<=mid) Modify_Add(id<<1, l, r, delta);
	else
		if (l>mid) Modify_Add(id<<1|1, l, r, delta);
		else
			Modify_Add(id<<1, l, mid, delta), Modify_Add(id<<1|1, mid+1, r, delta);
	Update(id);
}

void Modify_Change(int id, int id_, int delta)
{
	Push_down(id);
	if ((Seg[id].l==id_) && (Seg[id].r==id_))
	{
		Seg[id].Max=delta; Seg[id].Add=0; Seg[id].Cover=delta;
		return;
	}
	int mid=(Seg[id].l+Seg[id].r)>>1;
	if (id_<=mid) Modify_Change(id<<1, id_, delta); else Modify_Change(id<<1|1, id_, delta);
	Update(id);
}

int Query(int id, int l, int r)
{
	if (l>r) return 0;
	Push_down(id);
	if ((Seg[id].l==l) && (Seg[id].r==r)) return Seg[id].Max;
	int mid=(Seg[id].l+Seg[id].r)>>1;
	if (r<=mid) return Query(id<<1, l, r);
	else
		if (l>mid) return Query(id<<1|1, l, r);
		else
			return max(Query(id<<1, l, mid), Query(id<<1|1, mid+1, r));
}

inline void Exchange()
{
	for (int i=1; i<n; i++)
	{
		if (dep[Link[i].u]>dep[Link[i].v]) swap(Link[i].u, Link[i].v);
		Modify_Change(1, w[Link[i].v], Link[i].w);
	}
}

inline int Tree_Query(int u, int v)
{
	int f1=top[u], f2=top[v], res=0;
	while (f1^f2)
	{
		if (dep[f1]<dep[f2]) swap(u, v), f1=top[u], f2=top[v];
		res=max(res, Query(1, w[f1], w[u]));
		u=f[f1]; f1=top[u];
	}
	if (u^v)
	{
		if (dep[u]>dep[v]) swap(u, v);
		res=max(res, Query(1, w[son[u]], w[v]));
	}
	return res;
}

inline void Tree_Modify_Cover(int u, int v, int delta)
{
	int f1=top[u], f2=top[v];
	while (f1^f2)
	{
		if (dep[f1]<dep[f2]) swap(u, v), f1=top[u], f2=top[v];
		Modify_Cover(1, w[f1], w[u], delta);
		u=f[f1]; f1=top[u];
	}
	if (u^v)
	{
		if (dep[u]>dep[v]) swap(u, v);
		Modify_Cover(1, w[son[u]], w[v], delta);
	}
}

inline void Tree_Modify_Add(int u, int v, int delta)
{
	int f1=top[u], f2=top[v];
	while (f1^f2)
	{
		if (dep[f1]<dep[f2]) swap(u, v), f1=top[u], f2=top[v];
		Modify_Add(1, w[f1], w[u], delta);
		u=f[f1]; f1=top[u];
	}
	if (u^v)
	{
		if (dep[u]>dep[v]) swap(u, v);
		Modify_Add(1, w[son[u]], w[v], delta);
	}
}

int main()
{
	read(n); Mem();
	for (int i=1; i<n; i++)
	{
		read(Link[i].u), read(Link[i].v), read(Link[i].w);
		Insert(Link[i].u, Link[i].v), Insert(Link[i].v, Link[i].u);
	}
	dfs(root);
	build_tree(root, root);
	Create(1, 1, tree_size);
	Exchange();
	while (scanf("%s", str)!=EOF)
	{
		if (str[0]=='M') read(x), read(y), printf("%d\n", Tree_Query(x, y));
		if ((str[0]=='C') && (str[1]=='o')) read(x), read(y), read(z), Tree_Modify_Cover(x, y, z);
		if ((str[0]=='C') && (str[1]=='h')) read(x), read(z), Modify_Change(1, w[Link[x].v], z);
		if (str[0]=='A') read(x), read(y), read(z), Tree_Modify_Add(x, y, z);
		if (str[0]=='S') break;
	}
}

[bzoj2721][Violet 5]樱花

          x=y*n!/(y-n!)

          设p=y-n!, 有 x=(p+n!)*n!/p=(n!)^2/p+n!, ∵x∈Z ∴ p|(n!)^2

          所以就是求(n!^2)的因（约）数（叔叔）个数。。

          而对于某个整数z, n!中含有z的幂是Σ([n/(p^i)]), i∈N且i>=1（上标星号打不出，囧。。）

          就nlog(n)搞了。。问题就是WA了好多发。大概是我取模爆炸了？

#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define INF 2000000000
#define Clear(x, Num) memset(x, Num, sizeof(x))
#define Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
#define Maxn 1000010
#define Mod 1000000007
typedef long long ll;

ll n, prime[Maxn];
int cnt;
bool Isprime[Maxn];

inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }
inline void read(ll &x){ char ch; int N=1; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-1; while ((ch=G_c()) && (!Dig(ch))); } x=ch-48; while ((ch=G_c()) && (Dig(ch))) x=x*10+ch-48; x*=N; }
//inline void Insert(int u, int v) { To[Cnt]=v; Next[Cnt]=Head[u]; Head[u]=Cnt++; }

int main()
{
	read(n);
	for (ll i=2; i<=n; i++)
	{
		if (!Isprime[i]) prime[++cnt]=i;
		for (int j=1; (j<=cnt) && (prime[j]*i<=n); j++) Isprime[i*prime[j]]=1;
	}
	ll Ans=1ll;
	for (int i=1; i<=cnt; i++)
	{
		ll count=0ll;
		for (ll k=prime[i]; k<=n; k*=prime[i]) count+=(ll)(n/k);
		Ans=(Ans*(count*2ll+1ll))%Mod;
		while (Ans<0) Ans+=Mod;
	}
	while (Ans<0) Ans+=Mod;
	printf("%lld\n", Ans);
}

[bzoj1398]Vijos1382寻找主人 Necklace

          最小表示法biu过去。。变量打错o(╯□╰)o

#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define INF 2000000000
#define Clear(x, Num) memset(x, Num, sizeof(x))
#define Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
typedef long long ll;

char S[1000010], T[1000010];

inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }
inline void read(int &x){ char ch; int N=1; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-1; while ((ch=G_c()) && (!Dig(ch))); } x=ch-48; while ((ch=G_c()) && (Dig(ch))) x=x*10+ch-48; x*=N; }
//inline void Insert(int u, int v) { To[Cnt]=v; Next[Cnt]=Head[u]; Head[u]=Cnt++; }

inline int MinRepresent(char *s, int len)
{
	int i=0, j=1, k=0, t;
	while ((i<len) && (j<len) && (k<len))
	{
		t=s[(i+k)>=len?(i+k-len):(i+k)]-s[(j+k)>=len?(j+k-len):(j+k)];
		if (!t) k++;
		else
		{
			if (t>0) i=i+k+1;
			else j=j+k+1;
			if (i==j) j++;
			k=0;
		}
	}
	return min(i, j);
}

int main()
{
	scanf("%s", S); scanf("%s", T); int len=strlen(S);
	int p1=MinRepresent(S, len);
	int p2=MinRepresent(T, len);
	for (int i=0; i<len; i++)
	{
		int Ns=p1+i, Np=p2+i; if (Ns>=len) Ns-=len; if (Np>=len) Np-=len;
		if (S[Ns]!=T[Np]) { puts("No"); return 0; }
	}
	puts("Yes");
	for (int i=0; i<len; i++) { int Ns=p1+i; if (Ns>=len) Ns-=len; printf("%c", S[Ns]); } puts("");
}

[bzoj1828][Usaco2010 Mar]balloc 农场分配

          贪心，按r排序，然后线段树维护即可。。

#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define INF 2000000000
#define Clear(x, Num) memset(x, Num, sizeof(x))
#define Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
#define Maxn 100010
typedef long long ll;

struct Segmentle
{
	int l, r, tag, data;
}Seg[Maxn<<2];

struct Node
{
	int l, r;
}a[Maxn];
int n, m, c[Maxn], Ans;

inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }
inline void read(int &x){ char ch; int N=1; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-1; while ((ch=G_c()) && (!Dig(ch))); } x=ch-48; while ((ch=G_c()) && (Dig(ch))) x=x*10+ch-48; x*=N; }
//inline void Insert(int u, int v) { To[Cnt]=v; Next[Cnt]=Head[u]; Head[u]=Cnt++;  }
inline bool cmp(const Node &a, const Node &b) { return a.r<b.r; }

inline void Update(int id) { Seg[id].data=min(Seg[id<<1].data, Seg[id<<1|1].data); }

inline void Push_down(int id)
{
	if ((!Seg[id].tag) || (Seg[id].l==Seg[id].r)) return;
	Seg[id<<1].data-=Seg[id].tag; Seg[id<<1|1].data-=Seg[id].tag;
	Seg[id<<1].tag+=Seg[id].tag; Seg[id<<1|1].tag+=Seg[id].tag;
	Seg[id].tag=0;
}

void Create(int id, int l, int r)
{
	Seg[id].l=l; Seg[id].r=r;
	if (l==r) { Seg[id].data=c[l]; return; }
	int mid=(l+r)>>1;
	Create(id<<1, l, mid); Create(id<<1|1, mid+1, r);
	Update(id);
}

bool Query(int id, int l, int r)
{
	Push_down(id);
	if ((Seg[id].l==l) && (Seg[id].r==r)) return (Seg[id].data>=1);
	int mid=(Seg[id].l+Seg[id].r)>>1;
	if (r<=mid) return Query(id<<1, l, r);
	else
		if (l>mid) return Query(id<<1|1, l, r);
		else
			return Query(id<<1, l, mid)&&Query(id<<1|1, mid+1, r);
}

void Modify(int id, int l, int r)
{
	Push_down(id);
	if ((Seg[id].l==l) && (Seg[id].r==r))
	{
		Seg[id].tag++; Seg[id].data--;
		return;
	}
	int mid=(Seg[id].l+Seg[id].r)>>1;
	if (r<=mid) Modify(id<<1, l, r);
	else
		if (l>mid) Modify(id<<1|1, l, r);
		else Modify(id<<1, l, mid), Modify(id<<1|1, mid+1, r);
	Update(id);
}

int main()
{
	read(n); read(m);
	for (int i=1; i<=n; i++) read(c[i]);
	Create(1, 1, n);
	for (int i=1; i<=m; i++) read(a[i].l), read(a[i].r);
	sort(a+1, a+m+1, cmp);
	for (int i=1; i<=m; i++)
		if (Query(1, a[i].l, a[i].r)) Modify(1, a[i].l, a[i].r), Ans++;
	printf("%d\n", Ans);
}

[bzoj2048][2009国家集训队]书堆

          大概是2048玩多了。。

          初中物理题？求Σ(1/2*i)

          大的直接调和级数搞一搞，小的就暴力了 @卖萌的小搞堂

哪来的code...

[bzoj2221][Jsoi2009]面试的考验

          扭了好久的脖子。。跪求正解

          首先分块。然后先把A排序，再nsqrt(n)算出A[i]和每个块Block[j]的最小值。因为是排序后插入的，显然dp的时候只要f[i][j]和abs(a[i]-Last_Insert)比较更新一下就可以了。。这样需要正着反着都做一遍，最后f[i][j]应该更新一遍f[i][j-1]和f[i][j+1]（因为最小的差不一定是A[i]产生的）

          然后就是处理出块和块之间的最小值，可以枚举长度更新0.0

          这样询问就简单了。选出被[l, r]包含的最大区间。就可以得出答案了。。

          *别忘了把A还原

          P.s.最接近两个数之差的绝对值貌似不能为0？

#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define INF 2000000000
#define Clear(x, Num) memset(x, Num, sizeof(x))
#define Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
#define Maxn 100010
#define Maxb 410
typedef long long ll;
 
struct Dig
{
    int x, pos;
}a[Maxn];
int n, q, Block_size, Block_cnt, Pos[Maxn], left[Maxn], right[Maxn], f[Maxn][Maxb], block_f[Maxb][Maxb], Hv_Ins[Maxb], l, r, delta[Maxn], Cnt;
inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }
inline void read(int &x){ char ch; int N=1; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-1; while ((ch=G_c()) && (!Dig(ch))); } x=ch-48; while ((ch=G_c()) && (Dig(ch))) x=x*10+ch-48; x*=N; }
//inline void Insert(int u, int v) { To[Cnt]=v; Next[Cnt]=Head[u]; Head[u]=Cnt++; }
inline bool cmp(const Dig &a, const Dig &b) { return a.x<b.x; }
inline bool cmp_id(const Dig &a, const Dig &b) { return a.pos<b.pos; }
 
int main()
{
    read(n); read(q);
    Block_size=(int)sqrt(n+0.5);
    for (int i=1; i<=n; i++) read(a[i].x), a[i].pos=i; sort(a+1, a+n+1, cmp);
    for (int i=1; i<=n; i++) { Pos[i]=(i-1)/Block_size+1; if (Pos[i]^Pos[i-1]) right[Pos[i-1]]=i-1, left[Pos[i]]=i; } right[Pos[n]]=n;
    Block_cnt=Pos[n];
    for (int i=0; i<=n+1; i++)
        for (int j=1; j<=Block_cnt; j++) f[i][j]=INF;
    Clear(Hv_Ins, 0);
    for (int i=1; i<=n; i++)
    {
        if (a[i].x==a[i-1].x)
            for (int j=1; j<=Block_cnt; j++) f[a[i].pos][j]=min(f[a[i].pos][j], f[a[i-1].pos][j]);
        else
            for (int j=1; j<=Block_cnt; j++)
                if (Hv_Ins[j]) f[a[i].pos][j]=min(f[a[i].pos][j], a[i].x-Hv_Ins[j]);
        Hv_Ins[Pos[a[i].pos]]=a[i].x;
    }
//  for (int i=1; i<=n; i++) { for (int j=1; j<=Block_cnt; j++) printf("%d ", f[i][j]); puts(""); }
//  puts("");
    Clear(Hv_Ins, 0);
    for (int i=n; i>=1; i--)
    {
        if (a[i].x==a[i+1].x)
            for (int j=1; j<=Block_cnt; j++) f[a[i].pos][j]=min(f[a[i].pos][j], f[a[i+1].pos][j]);
        else
            for (int j=1; j<=Block_cnt; j++)
                if (Hv_Ins[j]) f[a[i].pos][j]=min(f[a[i].pos][j], Hv_Ins[j]-a[i].x);
        Hv_Ins[Pos[a[i].pos]]=a[i].x;
    }
//  for (int i=1; i<=n; i++) { for (int j=1; j<=Block_cnt; j++) printf("%d ", f[i][j]); puts(""); }
//  puts("");
    for (int i=1; i<=n; i++)
    {
        for (int j=Pos[i]+2; j<=Block_cnt; j++) f[i][j]=min(f[i][j], f[i][j-1]);
        for (int j=Pos[i]-2; j>=1; j--) f[i][j]=min(f[i][j], f[i][j+1]);
    }
//  for (int i=1; i<=n; i++) { for (int j=1; j<=Block_cnt; j++) printf("%d ", f[i][j]); puts(""); }
//  puts("");
    for (int i=0; i<=Block_cnt+1; i++)
        for (int j=0; j<=Block_cnt+1; j++) block_f[i][j]=INF;
    for (int i=1; i<=Block_cnt; i++)
        for (int j=1; j<=Block_cnt-i+1; j++)
        {
            block_f[j][j+i-1]=min(block_f[j][j+i-2], block_f[j+i-1][j+i-1]);
            for (int k=left[j+i-1]; k<=right[j+i-1]; k++) block_f[j][j+i-1]=min(block_f[j][j+i-1], f[k][j]);
        }
//  for (int i=1; i<=Block_cnt; i++) { for (int j=1; j<=Block_cnt; j++) printf("%d ", block_f[i][j]); puts(""); }
    sort(a+1, a+n+1, cmp_id);
    while (q--)
    {
        read(l); read(r);
        int Ans=INF; int Blo_l=Block_cnt+1, Blo_r=0; Cnt=0;
//      int Blo_l=Pos[l], Blo_r=Pos[r];
//      if (l!=left[Blo_l]) Blo_l++; if (r!=right[Blo_r]) Blo_r--;
        for (int i=1; i<=Block_cnt; i++)
            if ((l<=left[i]) && (r>=right[i])) Blo_l=min(Blo_l, i), Blo_r=max(Blo_r, i);
        if (Blo_l<=Blo_r)
        {
            Ans=block_f[Blo_l][Blo_r];
            for (int i=l; i<=left[Blo_l]-1; i++) Ans=min(Ans, f[i][Blo_r]), delta[++Cnt]=a[i].x;
            for (int i=right[Blo_r]+1; i<=r; i++) Ans=min(Ans, f[i][Blo_l]), delta[++Cnt]=a[i].x;
        }
        else
            for (int i=l; i<=r; i++) delta[++Cnt]=a[i].x;
        sort(delta+1, delta+Cnt+1);
        for (int i=2; i<=Cnt; i++) if (delta[i]-delta[i-1]) Ans=min(Ans, delta[i]-delta[i-1]);
        printf("%d\n", Ans);
    }
}

[JSOI2007]字符加密Cipher

          听说这题代码可以小于1k。。（反正我蒟蒻我不会）

          显然。我们可以把这个字符串再复制一遍拼起来后建后缀数组。。之后它的Suffix Array数组中的前n个就是所需要的答案。。输出所有s[sa[i]+len-1]就可以了。。

#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define INF 2000000000
#define Clear(x, Num) memset(x, Num, sizeof(x))
#define Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
#define Maxn 500010 
typedef long long ll;
  
char str[Maxn];
int Rank[Maxn], Rank_tmp[Maxn], s[Maxn], n, c[Maxn], sa[Maxn], Max_ranker;
  
inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }
inline void read(int &x){ char ch; int N=1; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-1; while ((ch=G_c()) && (!Dig(ch))); } x=ch-48; while ((ch=G_c()) && (Dig(ch))) x=x*10+ch-48; x*=N; }
//inline void Insert(int u, int v) { To[Cnt]=v; Next[Cnt]=Head[u]; Head[u]=Cnt++; }
  
inline void Build_sa(int m)
{
    int *x=Rank, *y=Rank_tmp, cnt=0;
    for (int i=0; i<m; i++) c[i]=0;
    for (int i=0; i<n; i++) c[x[i]=s[i]]++;
    for (int i=1; i<m; i++) c[i]+=c[i-1];
    for (int i=n-1; i>=0; i--) sa[--c[x[i]]]=i;
    for (int k=1; k<=n; k<<=1)
    {
        cnt=0;
        for (int i=n-k; i<n; i++) y[cnt++]=i;
        for (int i=0; i<n; i++) if (sa[i]>=k) y[cnt++]=sa[i]-k;
        for (int i=0; i<m; i++) c[i]=0;
        for (int i=0; i<n; i++) c[x[y[i]]]++;
        for (int i=1; i<m; i++) c[i]+=c[i-1];
        for (int i=n-1; i>=0; i--) sa[--c[x[y[i]]]]=y[i];
        swap(x, y);
        cnt=1; x[sa[0]]=0;
        for (int i=1; i<n; i++)
            if ((y[sa[i-1]]==y[sa[i]]) && (y[sa[i-1]+k]==y[sa[i]+k])) x[sa[i]]=cnt-1;
            else x[sa[i]]=cnt++;
        if (cnt>=n) break;
        m=cnt;
    }
}
 
int main()
{
    scanf("%s", str); int len=strlen(str); n=len;
    for (int i=0; i<n; i++) str[i+n]=str[i]; n<<=1;
    for (int i=0; i<n; i++)
    {
        s[i]=str[i];
        Max_ranker=max(Max_ranker, s[i]+1);
    }
    s[n++]=0;
    Build_sa(Max_ranker);
    for (int i=0; i<n; i++) if (sa[i]<len) printf("%c", s[sa[i]+len-1]);
    puts("");
}

[bzoj1632][Usaco2007 Feb]Lilypad Pond

                         水水哒。。直接笨法师即可。。优先级是（放置荷叶数）> （距离）>（方案数）。。之后转移方程就很容易列出来

#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define INF 2000000000
#define Clear(x, Num) memset(x, Num, sizeof(x))
#define Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
#define Maxq 10000
typedef long long ll;
 
const int dx[]={0, 1, 1, 2, 2, -1, -1, -2, -2};
const int dy[]={0, -2, 2, -1, 1, -2, 2, -1, 1};
struct Query
{
    int x, y;
}Queue[10010];
int n, m, Sx, Sy, Ex, Ey, a[31][31], dis[31][31], Add[31][31];
ll Ways[31][31];
bool used[31][31];
 
inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }
inline void read(int &x){ char ch; int N=1; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-1; while ((ch=G_c()) && (!Dig(ch))); } x=ch-48; while ((ch=G_c()) && (Dig(ch))) x=x*10+ch-48; x*=N; }
//inline void Insert(int u, int v) { To[Cnt]=v; Next[Cnt]=Head[u]; Head[u]=Cnt++; }
 
inline void Bfs()
{
    for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) dis[i][j]=Add[i][j]=INF; dis[Sx][Sy]=Add[Sx][Sy]=0; used[Sx][Sy]=Ways[Sx][Sy]=1;
    int top=0, bot=1; Queue[1].x=Sx, Queue[1].y=Sy;
    while (top<bot)
    {
        int x=Queue[top=(top+1)%Maxq].x, y=Queue[top].y; used[x][y]=0;
        if ((x==Ex) && (y==Ey)) continue;
        for (int i=1; i<=8; i++)
        {
            int x_=x+dx[i], y_=y+dy[i];
            if ((x_<1) || (x_>n) || (y_<1) || (y_>m)) continue;
            if (a[x_][y_]==2) continue;
            int Len=!a[x_][y_];
            if (Add[x_][y_]>Add[x][y]+Len)
            {
                Add[x_][y_]=Add[x][y]+Len;
                dis[x_][y_]=dis[x][y]+1;
                Ways[x_][y_]=Ways[x][y];
                if (!used[x_][y_]) Queue[bot=(bot+1)%Maxq].x=x_, Queue[bot].y=y_, used[x_][y_]=1;
            }
            else
                if ((Add[x_][y_]==Add[x][y]+Len) && (dis[x_][y_]>dis[x][y]+1))
                {
                    dis[x_][y_]=dis[x][y]+1;
                    Ways[x_][y_]=Ways[x][y];
                    if (!used[x_][y_]) Queue[bot=(bot+1)%Maxq].x=x_, Queue[bot].y=y_, used[x_][y_]=1;
                }
                else
                    if ((Add[x_][y_]==Add[x][y]+Len) && (dis[x_][y_]==dis[x][y]+1))
                    {
                        Ways[x_][y_]+=Ways[x][y];
                        if (!used[x_][y_]) Queue[bot=(bot+1)%Maxq].x=x_, Queue[bot].y=y_, used[x_][y_]=1;
                    }
        }
    }
}
 
int main()
{
    read(n); read(m);
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
        {
            read(a[i][j]);
            if (a[i][j]==3) Sx=i, Sy=j, a[i][j]=1;
            if (a[i][j]==4) Ex=i, Ey=j, a[i][j]=1;
        }
    Bfs();
    if (dis[Ex][Ey]==INF) { puts("-1"); return 0; }
    printf("%d\n%d\n%lld\n",  Add[Ex][Ey], dis[Ex][Ey], Ways[Ex][Ey]);
}

[bzoj3419]Poi2013 Taxis

          想了好久。。发现只要留下一辆可以到达的（随便哪辆都可以）。之后贪心就可以。。还是WA了好多发。。囧

你说会有吗？

[bzoj1785][Usaco2010 Jan]telephone

          显然叶节点的时候是可以扭脖子和他爹通信的。而且对于当前节点。设它是P。如果P的所有连接点个数小于等于2*k的话。那就加上。最后留下或者一个不留下（取决于点的奇偶），大于的话就只能加k组了。。

#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define INF 2000000000
#define Clear(x, Num) memset(x, Num, sizeof(x))
#define Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
#define Maxn 100010
typedef long long ll;

int n, k, Head[Maxn], To[Maxn<<1], Next[Maxn<<1], Cnt, x, y, Ans;

inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }
inline void read(int &x){ char ch; int N=1; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-1; while ((ch=G_c()) && (!Dig(ch))); } x=ch-48; while ((ch=G_c()) && (Dig(ch))) x=x*10+ch-48; x*=N; }
inline void Insert(int u, int v) { To[Cnt]=v; Next[Cnt]=Head[u]; Head[u]=Cnt++; }

int dfs(int u, int father)
{
	int Counter=0, Son=0;
	for (int p=Head[u]; p!=-1; p=Next[p])
	{
		int v=To[p];
		if (v!=father) Counter+=dfs(v, u);
		Son++;
	}
	if (Son==1) Counter++;
	if (Counter<=(k<<1)) { Ans+=Counter>>1; return Counter&1; }
	else { Ans+=k; return 0; }
}

int main()
{
	read(n); read(k); Clear(Head, -1); Cnt=0;
	for (int i=1; i<n; i++) read(x), read(y), Insert(x, y), Insert(y, x);
	Ans=0; dfs(1, -1); printf("%d\n", Ans);
}

[bzoj2022]Pku1837 Balance

          豆饼Dp。。最多只有(Σ1..20)*20*25==105000发可能性。。初始的时候f[0][105000/2]=1(即两边都不放），之后很容易相出用f[i-1][j]更新f[i][j+w[i]*c[k]]

          别忘了long long

#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define INF 2000000000
#define Clear(x, Num) memset(x, Num, sizeof(x))
#define Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
#define Maxn 21
#define MaxW 105000
typedef long long ll;

int C, n, c[Maxn], w[Maxn];
ll f[Maxn][MaxW+10];

inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }
inline void read(int &x){ char ch; int N=1; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-1; while ((ch=G_c()) && (!Dig(ch))); } x=ch-48; while ((ch=G_c()) && (Dig(ch))) x=x*10+ch-48; x*=N; }
//inline void Insert(int u, int v) { To[Cnt]=v; Next[Cnt]=Head[u]; Head[u]=Cnt++; }

int main()
{
	read(C); read(n);
	for (int i=1; i<=C; i++) read(c[i]);
	for (int i=1; i<=n; i++) read(w[i]);
	f[0][MaxW/2]=1;
	for (int i=1; i<=n; i++)
		for (int j=0; j<=MaxW; j++)
			if (f[i-1][j])
				for (int k=1; k<=C; k++) f[i][j+w[i]*c[k]]+=f[i-1][j];
	printf("%lld\n", f[n][MaxW/2]);
}

[bzoj1257][CQOI2007]余数之和sum

          枚举余数就可以了，之后就是等差序列求求和。。最多sqrt(n)

╮(╯_╰)╭

[bzoj1828][JSOI2010]Frozen Nova 冷冻波

          赤裸裸的二分+最大流。。开始的时候上界开成了INF就死循环了真是酸爽~~判断Lich、Wisper中间是否被Tree挡住只要判断Lich, Wisper, Tree(圆心)围成的三角形面积是否小于dist{Lich， Wisper}*Tree_r/2就可以了。。（画个图就明白了）

          之后就是脑残的常数优化（其实没有一样能过）。先是建图的时候直接改了Flow。。之后用了 @没注意 的基于二分图的Sap(据说跑的是标程的几分之一）。。。

#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define INF 2000000000
#define Clear(x, Num) memset(x, Num, sizeof(x))
#define Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
#define sqr(x) ((x)*(x))
#define Maxn 2010
#define Maxe 1000010
#define eps 1e-6
typedef long long ll;
 
int n, m, K, x_Lich[Maxn], y_Lich[Maxn], r_Lich[Maxn], t_Lich[Maxn], x_Wisp[Maxn], y_Wisp[Maxn], x_Tree[Maxn], y_Tree[Maxn], r_Tree[Maxn], t_Max;
int From[Maxe], To[Maxe], Flow[Maxe], Next[Maxe], Head[Maxn], Flow_[Maxe], Cnt;
int source, sink, cur[Maxn], gap[Maxn], dis[Maxn], pre[Maxn];
bool Could[Maxn][Maxn], Kill[Maxn];
 
inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }
inline void read(int &x){ char ch; int N=1; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-1; while ((ch=G_c()) && (!Dig(ch))); } x=ch-48; while ((ch=G_c()) && (Dig(ch))) x=x*10+ch-48; x*=N; }
 
inline void Insert(int u, int v, int w)
{
    From[Cnt]=u; To[Cnt]=v; Flow[Cnt]=w; Next[Cnt]=Head[u]; Head[u]=Cnt++;
    From[Cnt]=v; To[Cnt]=u; Flow[Cnt]=0; Next[Cnt]=Head[v]; Head[v]=Cnt++;
}
 
inline int Sap()
{
    int flow=0, aug=INF; bool flag=0;
    for (int i=0; i<=sink; i++) cur[i]=Head[i], gap[i]=dis[i]=0;
    int u; u=pre[source]=source; gap[source]=sink+1;
    while (dis[source]<=sink)
    {
        flag=0;
        for (int &p=cur[u]; p!=-1; p=Next[p])
        {
            int v=To[p];
            if ((Flow[p]>0) && (dis[u]==dis[v]+1))
            {
                flag=1, pre[v]=u, u=v; aug=min(aug, Flow[p]);
                if (u==sink) { flow+=aug; while (u!=source) u=pre[u], Flow[cur[u]]-=aug, Flow[cur[u]^1]+=aug; aug=INF; }
                break;
            }
        }
        if (flag) continue; int minl=sink;
        for (int p=Head[u]; p!=-1; p=Next[p]) { int v=To[p]; if ((Flow[p]>0) && (dis[v]<minl)) minl=dis[v], cur[u]=p; }
        if (!(--gap[dis[u]])) break; gap[dis[u]=minl+1]++, u=pre[u];
    }
    return flow;
}
 
inline int Dis(int x, int y) { return sqr(x)+sqr(y); }
 
inline bool Area(int Lic, int Wis, int Tre)
{
    double LW=sqrt(1.0*Dis(x_Lich[Lic]-x_Wisp[Wis], y_Lich[Lic]-y_Wisp[Wis]));
    double LT=sqrt(1.0*Dis(x_Lich[Lic]-x_Tree[Tre], y_Lich[Lic]-y_Tree[Tre]));
    double WT=sqrt(1.0*Dis(x_Wisp[Wis]-x_Tree[Tre], y_Wisp[Wis]-y_Tree[Tre]));
    double p=(LW+LT+WT)/2.0;
    double area=p*(p-LW)*(p-LT)*(p-WT);
    double Dist=LW*r_Tree[Tre]/2.0;
    if (Dist*Dist>=area) return 1;
    return 0;
}
 
inline void Build_Graph(int Time_Limit)
{
//  Clear(Head, -1); Cnt=0;
    for (int i=0; i<=Cnt; i++) Flow[i]=Flow_[i];
    for (int i=1; i<=n; i++) Flow[(i-1)<<1]=Time_Limit/t_Lich[i]+1;
/*  for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
            if (Could[i][j]) Insert(i, j+n, 1);
    for (int i=1; i<=m; i++) Insert(i+n, sink, 1);*/
}
 
inline void Build_First()
{
    for (int i=1; i<=n; i++) Insert(source, i, (t_Max*m+1)/t_Lich[i]+1);
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
            if (Could[i][j]) Insert(i, j+n, 1);
    for (int i=1; i<=m; i++) Insert(i+n, sink, 1);
    for (int i=1; i<=Cnt; i++) Flow_[i]=Flow[i];
}
 
int main()
{
    read(n); read(m); read(K); source=0; sink=n+m+1; Clear(Head, -1);
    for (int i=1; i<=n; i++) read(x_Lich[i]), read(y_Lich[i]), read(r_Lich[i]), read(t_Lich[i]), t_Max=max(t_Max, t_Lich[i]);
    for (int i=1; i<=m; i++) read(x_Wisp[i]), read(y_Wisp[i]);
    for (int i=1; i<=K; i++) read(x_Tree[i]), read(y_Tree[i]), read(r_Tree[i]);
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
            if (Dis(x_Lich[i]-x_Wisp[j], y_Lich[i]-y_Wisp[j])<=sqr(r_Lich[i]))
            {
                Could[i][j]=1; Kill[j]=1;
                for (int k=1; k<=K; k++) if (Area(i, j, k)) { Could[i][j]=0; break; }
            }
//  for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) printf("%d ", Could[i][j]); puts(""); }
    for (int i=1; i<=m; i++) if (!Kill[i]) { puts("-1"); return 0; }
    Build_First();
    int l=0, r=t_Max*m+1, Ans=-1;
    while (l<=r)
    {
        int mid=(l+r)>>1;
        Build_Graph(mid);
        if (Sap()>=m) r=mid-1, Ans=mid; else l=mid+1;
    }
    printf("%d\n", Ans);
}