拉原题什么的，果然 TJ 省就是任性。——进错省系列

线性代数

伪传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4307

伪题解门：http://www.cnblogs.com/dyllalala/p/3991656.html

第一次看见正式比赛有直接拉原题的真是吓呆了……（而且原题的数据范围和空间限制比他高到不知道哪里去了233）

出题人真的不怕被愤怒的人们群众们分尸吗

组合数学

很高兴与上一题一样，这道题的名字与做法究竟是有半毛钱的关系

听说有 Dilworth 定理真是吓尿了（@ __Shi：“来发贪心压压鲸”）

似乎是一个最小割，于是我又开始伪证，乱搞右上自左下的最大路径，对着数据把 dp 改到自己都不认识之后居然 AC 了

玛雅，这一定是对我 APIO 搞挂的补偿

#include <cstdio>
#include <cstring>
typedef long long llint;

inline int getint();
inline void putint(llint);

int t, n, m;
int ans;
int a[1024][1024];
llint f[1024][1024];

inline llint max(llint, llint);

int main()
{
	for (t=getint();t;t--)
	{
		n=getint(), m=getint();
		for (int i=1;i<=n;i++)
			for (int j=1;j<=m;j++)
				a[i][j]=getint();

		ans=0;

		memset(f, 0, sizeof(f));
		for (int i=1;i<=m;i++)
		{
			for (int j=n;j>=1;j--)
				f[j][i]=max(f[j][i-1], f[j+1][i-1]+a[j][i]);
			for (int j=n;j>=1;j--)
				f[j][i]=max(f[j][i], f[j+1][i]);
			ans=max(ans, f[1][i]);
		}

		putint(ans);
	}

	return 0;
}

inline int getint()
{
	register int num=0;
	register char ch;
	do ch=getchar(); while (ch<'0' || ch>'9');
	do num=num*10+ch-'0', ch=getchar(); while (ch>='0' && ch<='9');
	return num;
}
inline void putint(llint num)
{
	char stack[32];
	register int top=0;
	if (num==0) stack[top=1]='0';
	for ( ;num;num/=10) stack[++top]=num%10+'0';
	for ( ;top;top--) putchar(stack[top]);
	putchar('\n');
}

inline llint max(llint x, llint y)
{
	return x>y?x:y;
}

弦论（出题人你是有多中二，“数学系中二病"——似乎挺赞的）

写作弦论读作 string

后缀自动机 SB 题，但是我这种调了 2 hour 的 SB 似乎并没有资格说……

#include <cstdio>
#include <cstring>
typedef long long llint;
const int sizeofstring=1048576;
const int sizeoftype=26;

inline void assign();
inline void close();
inline int getint();
inline int getstr(char * );

struct node
{
	llint cnt, size;
	unsigned char vis;
	int step;
	node * fail, * ch[sizeoftype];
};
node memory[sizeofstring], * port=memory;
node * dfa, * last;
inline void prepare();
inline node * newnode(node * =NULL);
inline void insert(int);

int len;
int t, k;
char str[sizeofstring];
inline void bfs();
void dfs(node * );
 
int main()
{
	assign();

	len=getstr(str);
	t=getint(), k=getint();

	prepare();
	for (int i=0;i<len;i++)
	{
		insert(str[i]-'a');
		last->cnt++;
	}
	bfs();
	dfs(dfa);

	if (dfa->size<k)
	{
		puts("-1");
		return 0;
	}

	int j;
	for (node * i=dfa;i;i=i->ch[j])
	{
		if (k<=i->cnt) break;
		k-=i->cnt;

		for (j=0;j<sizeoftype;j++) if (i->ch[j])
		{
			if (k>i->ch[j]->size)
				k-=i->ch[j]->size;
			else
			{
				putchar(j+'a');
				break;
			}
		}
	}

	putchar('\n');
	close();
	return 0;
}

inline void assign()
{
	freopen("string.in", "r", stdin);
	freopen("string.out", "w", stdout);
}
inline void close()
{
	fclose(stdin);
	fclose(stdout);
}
inline int getint()
{
	register int num=0;
	register char ch;
	do ch=getchar(); while (ch<'0' || ch>'9');
	do num=num*10+ch-'0', ch=getchar(); while (ch>='0' && ch<='9');
	return num;
}
inline int getstr(char * str)
{
	register int len=0;
	register char ch;
	do ch=getchar(); while (ch<'a' || ch>'z');
	do str[len++]=ch, ch=getchar(); while (ch>='a' && ch<='z');
	return len;
}

inline void prepare()
{
	dfa=newnode(), dfa->fail=dfa;
	last=dfa;
}
inline node * newnode(node * p)
{
	node * newp=port++;
	newp->cnt=newp->size=newp->step=0;
	newp->vis=0;
	if (p==NULL) newp->fail=NULL, memset(newp->ch, 0, sizeof(newp->ch));
	else newp->fail=p->fail, p->fail=newp, memmove(newp->ch, p->ch, sizeof(p->ch));
	return newp;
}
inline void insert(int w)
{
	node * p=last, * newp=newnode();
	newp->step=p->step+1;

	for ( ;p->ch[w]==NULL;p=p->fail)
		p->ch[w]=newp;
	if (p->ch[w]==newp)
		newp->fail=dfa;
	else
	{
		node * q=p->ch[w];

		if (q->step==p->step+1)
			newp->fail=q;
		else
		{
			node * newq=newnode(q);
			newq->step=p->step+1;

			newp->fail=newq;
			for ( ;p->ch[w]==q;p=p->fail)
				p->ch[w]=newq;
		}
	}

	last=newp;
}
inline void bfs()
{
	static node * q[sizeofstring];
	int l=0, r=0;

	for (dfa->vis=1, q[r++]=dfa;l<r;l++)
	{
		node * u=q[l];
		for (int i=0;i<sizeoftype;i++) if (u->ch[i] && u->ch[i]->vis!=1)
			u->ch[i]->vis=1, q[r++]=u->ch[i];
	}

	for (int i=r-1;i;i--)
		q[i]->fail->cnt+=q[i]->cnt;
	if (!t) for (int i=r-1;i;i--)
		q[i]->cnt=q[i]->cnt>0;
	dfa->cnt=0;
}
void dfs(node * t)
{
	t->vis=2, t->size=t->cnt;
	for (int i=0;i<26;i++) if (t->ch[i])
	{
		if (t->ch[i]->vis!=2)
			dfs(t->ch[i]);
		t->size+=t->ch[i]->size;
	}
}

这份代码在国家队爷的电脑上 A 了却被 BZOJ 判 TLE 差评，粘代码党做好心理准备……

旅游

非常理性愉悦的数据结构题，但写起来似乎并不难嘛～

#include <cstdio>
#include <cstring>
const int sizeofcity=131072;
const int sizeofedge=262144;
const int sizeofseg=1048576;

inline int getint();
inline void putint(int);

inline int max(int, int);
inline int min(int, int);
inline void swap(int & , int & );

struct node
{
	int max, min, dup, dwn;

	inline node();
};
inline node operator + (const node & , const node & );

struct edge
{
	int point;
	edge * next;
};
edge memoryofedge[sizeofedge], * portofedge=memoryofedge;
inline edge * newedge(int, edge * );
inline void link(int, int);
inline void dfs();

struct seg
{
	node d;
	int f;
	seg * l, * r;

	inline seg();
	inline void setf(int);
	inline void pushdown();
	inline void maintain();
};
seg * null=new seg();
seg memoryofseg[sizeofseg], * portofseg=memoryofseg;
inline seg * newseg();
seg * build(int, int);
void update(seg * , int, int, int, int, int);
node query(seg * , int, int, int, int);

int N, Q;
seg * root;
edge * e[sizeofcity];
int p[sizeofcity];
int f[sizeofcity], d[sizeofcity], s[sizeofcity];
int cnt, son[sizeofcity], idx[sizeofcity], top[sizeofcity];
int ridx[sizeofcity];
inline void update(int, int, int);
inline int query(int, int);

int main()
{
	N=getint();
	for (int i=1;i<=N;i++)
		p[i]=getint();
	for (int i=1;i<N;i++)
	{
		int u=getint(), v=getint();
		link(u, v);
	}
	dfs();
	for (int i=1;i<=N;i++)
		ridx[idx[i]]=i;
	root=build(1, N);

	Q=getint();
	for ( ;Q;Q--)
	{
		int u=getint(), v=getint(), c=getint();
		putint(query(u, v));
		update(u, v, c);
	}

	return 0;
}

inline int getint()
{
	register int num=0;
	register char ch;
	do ch=getchar(); while (ch<'0' || ch>'9');
	do num=num*10+ch-'0', ch=getchar(); while (ch>='0' && ch<='9');
	return num;
}
inline void putint(int num)
{
	char stack[16];
	register int top=0;
	if (num==0) stack[top=1]='0';
	for ( ;num;num/=10) stack[++top]=num%10+'0';
	for ( ;top;top--) putchar(stack[top]);
	putchar('\n');
}

inline int max(int x, int y)
{
	return x>y?x:y;
}
inline int min(int x, int y)
{
	return x<y?x:y;
}
inline void swap(int & x, int & y)
{
	int t=x; x=y; y=t;
}

inline edge * newedge(int point, edge * next)
{
	edge * ret=portofedge++;
	ret->point=point, ret->next=next;
	return ret;
}
inline void link(int u, int v)
{
	e[u]=newedge(v, e[u]);
	e[v]=newedge(u, e[v]);
}
inline void dfs()
{
	static edge * t[sizeofcity];
	int u;

	memmove(t, e, sizeof(e));
	memset(f, 0xff, sizeof(f));

	u=1, f[1]=0;
	while (true)
	{
		if (!s[u])
			s[u]=1, son[u]=0;

		edge *& i=t[u];
		for ( ;i && f[i->point]>=0;i=i->next);
		if (i)
		{
			f[i->point]=u;
			d[i->point]=d[u]+1;
			u=i->point;
		}
		else
		{
			if (u==1) break;
			s[f[u]]+=s[u];
			if (s[u]>s[son[f[u]]])
				son[f[u]]=u;
			u=f[u];
		}
	}

	memmove(t, e, sizeof(e));
	memset(idx, 0, sizeof(idx));

	u=1, idx[1]=cnt=1, top[1]=1;
	while (true)
	{
		if (son[u] && !idx[son[u]])
		{
			idx[son[u]]=++cnt;
			top[son[u]]=top[u];
			u=son[u];
			continue;
		}

		edge *& i=t[u];
		for ( ;i && idx[i->point];i=i->next);
		if (i)
		{
			idx[i->point]=++cnt;
			top[i->point]=i->point;
			u=i->point;
		}
		else
		{
			if (u==1) break;
			u=f[u];
		}
	}
}

inline node::node()
{
	max=dup=dwn=0, min=0x7fffffff;
}
inline node operator + (const node & a, const node & b)
{
	node c;
	c.dwn=max(a.dwn, b.dwn), c.dwn=max(b.max-a.min, c.dwn);
	c.dup=max(a.dup, b.dup), c.dup=max(a.max-b.min, c.dup);
	c.max=max(a.max, b.max), c.min=min(a.min, b.min);
	return c;
}

inline seg::seg()
{
	d=node();
	f=0;
	l=r=this;
}
inline void seg::setf(int _f)
{
	d.max+=_f, d.min+=_f;
	f+=_f;
}
inline void seg::pushdown()
{
	if (f)
	{
		if (l!=null) l->setf(f);
		if (r!=null) r->setf(f);
		f=0;
	}
}
inline void seg::maintain()
{
	d=l->d+r->d;
}
inline seg * newseg()
{
	seg * ret=portofseg++;
	ret->d=node();
	ret->f=0;
	ret->l=ret->r=null;
	return ret;
}
seg * build(int l, int r)
{
	seg * t=newseg();
	int m=(l+r)>>1;

	if (l==r)
		t->d.max=t->d.min=p[ridx[m]];
	else
	{
		t->l=build(l, m);
		t->r=build(m+1, r);
		t->maintain();
	}

	return t;
}
void update(seg * t, int l, int r, int ql, int qr, int v)
{
	int m=(l+r)>>1;

	if (l==ql && r==qr)
		t->setf(v);
	else
	{
		t->pushdown();
		if (qr<=m) update(t->l, l, m, ql, qr, v);
		else if (ql>m) update(t->r, m+1, r, ql, qr, v);
		else update(t->l, l, m, ql, m, v), update(t->r, m+1, r, m+1, qr, v);
		t->maintain();
	}
}
node query(seg * t, int l, int r, int ql, int qr)
{
	node ans;
	int m=(l+r)>>1;

	if (l==ql && r==qr)
		 ans=t->d;
	else
	{
		t->pushdown();
		if (qr<=m) ans=query(t->l, l, m, ql, qr);
		else if (ql>m) ans=query(t->r, m+1, r, ql, qr);
		else ans=query(t->l, l, m, ql, m)+query(t->r, m+1, r, m+1, qr);
		t->maintain();
	}

	return ans;
}

inline void update(int u, int v, int c)
{
	while (top[u]!=top[v])
	{
		if (d[top[u]]<d[top[v]]) swap(u, v);
		update(root, 1, N, idx[top[u]], idx[u], c);
		u=f[top[u]];
	}
	if (d[u]>d[v]) swap(u, v);
	update(root, 1, N, idx[u], idx[v], c);
}
inline int query(int u, int v)
{
	node ansl, ansr;

	int tu=u, tv=v, ta;
	while (top[u]!=top[v])
	{
		if (d[top[u]]<d[top[v]]) swap(u, v);
		u=f[top[u]];
	}
	ta=d[u]<d[v]?u:v;

	u=tu;
	while (top[u]!=top[ta])
	{
		ansl=query(root, 1, N, idx[top[u]], idx[u])+ansl;
		u=f[top[u]];
	}
	ansl=query(root, 1, N, idx[ta], idx[u])+ansl;
	v=tv;
	while (top[v]!=top[ta])
	{
		ansr=query(root, 1, N, idx[top[v]], idx[v])+ansr;
		v=f[top[v]];
	}
	ansr=query(root, 1, N, idx[ta], idx[v])+ansr;

	return max(max(ansl.dup, ansr.dwn), ansr.max-ansl.min);
}

棋盘

好题看我打个惊叹号！

装压呀呀呀呀……搞一个 2^m * 2^m 的矩阵 f ，f[i][j] 表示从状态 i 能否转移到状态 j。数据很兹兹暴力搞出矩阵，套个快速幂就没有然后了

#include <cstdio>
#include <cstring>
#include <vector>
typedef unsigned int uint;

inline int getint();
inline void putint(uint);

struct matrix
{
	uint a[64][64];

	inline matrix(int=0);
	inline uint * operator [] (int);
};
inline matrix operator * (matrix & , matrix & );
inline matrix operator ^ (matrix, int);

int n, m, p, k, E;
std::vector<uint> d[3];
uint x[64];
matrix f;
inline bool chess(int);
inline bool check(int, int);

int main()
{
	n=getint(), m=getint();
	p=getint(), k=getint();
	E=1<<m;
	for (int i=0;i<3;i++)
		for (int j=0;j<p;j++)
			if (getint() && (i!=1 || j!=k))
				d[i].push_back(j-k);
	for (int i=0;i<E;i++)
		for (int j=0;j<E;j++)
			f[i][j]=check(i, j);

	for (int i=0;i<E;i++)
		x[i]=f[0][i];

	f=f^n;

	uint ans=0;
	for (int i=0;i<E;i++)
		ans+=x[i]*f[i][0];

	putint(ans);

	return 0;
}

inline int getint()
{
	register int num=0;
	register char ch;
	do ch=getchar(); while (ch<'0' || ch>'9');
	do num=num*10+ch-'0', ch=getchar(); while (ch>='0' && ch<='9');
	return num;
}
inline void putint(uint num)
{
	char stack[16];
	register int top=0;
	if (num==0) stack[top=1]='0';
	for ( ;num;num/=10) stack[++top]=num%10+'0';
	for ( ;top;top--) putchar(stack[top]);
	putchar('\n');
}

inline matrix::matrix(int x)
{
	memset(a, 0, sizeof(a));
	for (int i=0;i<64;i++)
		a[i][i]=x;
}
inline uint * matrix::operator [] (int _ord)
{
	return a[_ord];
}
inline matrix operator * (matrix & a, matrix & b)
{
	matrix c;

	for (int i=0;i<64;i++)
		for (int j=0;j<64;j++)
			for (int k=0;k<64;k++)
				c[i][j]+=a[i][k]*b[k][j];

	return c;
}
inline matrix operator ^ (matrix a, int b)
{
	matrix c(1);

	for ( ;b;b>>=1)
	{
		if (b&1) c=c*a;
		a=a*a;
	}

	return c;
}

inline bool chess(int x)
{
	return 0<=x && x<m;
}
inline bool check(int s1, int s2)
{
	int k;
	for (int i=0;i<m;i++) if ((s1>>i)&1)
	{
		for (int j=0;j<d[1].size();j++)
			if (chess(k=i+d[1][j]) && ((s1>>k)&1))
				return 0;
		for (int j=0;j<d[2].size();j++)
			if (chess(k=i+d[2][j]) && ((s2>>k)&1))
				return 0;
	}
	for (int i=0;i<m;i++) if ((s2>>i)&1)
	{
		for (int j=0;j<d[1].size();j++)
			if (chess(k=i+d[1][j]) && ((s2>>k)&1))
				return 0;
		for (int j=0;j<d[0].size();j++)
			if (chess(k=i+d[0][j]) && ((s1>>k)&1))
				return 0;
	}
	return 1;
}

概率论

为何要出公式题……

#include <cstdio>

int main()
{
	double n;

	scanf("%lf",&n);

	printf("%.9lf",(n*n+n)/(4*n-2));

	return 0;
}

var n:comp;begin read(n);write((n+1)/(4-2/n):0:9)end.