Solve record Oct.

Return posted @ Oct 02, 2014 03:57:24 PM in OI with tags Oct 脖子OJ , 1394 阅读
 
都是水水的啦你们就别看了~~
 
[bzoj1984]月下“毛景树“
          裸的树链剖分,我特么还爆了10多发OJ。。。
          居然是线段树的Query写错了真是爆炸的人品。。
#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);
}
wgu student portal l 说:
Aug 19, 2022 06:12:36 AM

western governors university student login. Access the WGU student portal here. Students can find instructions for initial log in to the learning portal for the university. At WGU, we're student obsessed, wgu student portal login so you'll get one on one faculty support. ... distance, learning, and all other barriers to ensure that everyone has access 2021


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter