做完 JLOI 2015 的题已经被题目描述雷得不能自拔……

有意义的字符串哪里有意义了嘛？

FaceBrother 是 ShenMeGui 啊！

明明我才是被你骗的，却还有脸在这里卖萌？！

还有，为毛感脚 day1 和 day2 的难度差那么大啊 T_T

有意义的字符串

其实这题看到时完全吓傻了有木有？看了题解才意识到居然是让你用答案去凑一个齐次线性递推数列出来，然后发现题目给的那些奇怪条件都能扯上了，剩下的就是搞个矩阵快速幂的事情……原来递推数列还可以这么玩真是太令人感动了～

#include <cstdio>
typedef unsigned long long ullint;
const ullint mod=7528443412579576937ull;

inline ullint getint();
inline void putint(ullint);

inline ullint mul(ullint, ullint);

struct matrix
{
	ullint a0, a1, a2, a3;

	inline matrix(ullint=0, ullint=0, ullint=0, ullint=0);
};
inline matrix operator * (const matrix & , const matrix & );
inline matrix operator ^ (matrix, ullint);

int main()
{
	ullint ans;
	ullint b, d, n;
	matrix a;

	b=getint(), d=getint(), n=getint();

	a=matrix(0, (d-b*b)>>2, 1, b)^n;
	ans=(mul(a.a0, 2)+mul(a.a2, b)-(d!=b*b && ~n&1))%mod;

	putint(ans);

	return 0;
}

inline ullint getint()
{
	register ullint 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(ullint 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 ullint mul(ullint a, ullint b)
{
	ullint c=0;

	for ( ;b;b>>=1)
	{
		if (b&1) c=(c+a)%mod;
		a=(a+a)%mod;
	}

	return c;
}

inline matrix::matrix(ullint _a0, ullint _a1, ullint _a2, ullint _a3)
{
	a0=_a0, a1=_a1, a2=_a2, a3=_a3;
}
inline matrix operator * (const matrix & a, const matrix & b)
{
	matrix c;

	c.a0=(mul(a.a0, b.a0)+mul(a.a1, b.a2))%mod;
	c.a1=(mul(a.a0, b.a1)+mul(a.a1, b.a3))%mod;
	c.a2=(mul(a.a2, b.a0)+mul(a.a3, b.a2))%mod;
	c.a3=(mul(a.a2, b.a1)+mul(a.a3, b.a3))%mod;

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

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

	return c;
}

城池攻占

一个逗比的带标记可并堆……话说这东西不是在 APIO 2012 上早被十一区人民玩过了么？

#include <cstdio>
typedef long long llint;
const llint inf=0x7fffffffffffffffll;
const int sizeofknight=524288;
const int sizeofcity=524288;

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

struct flag
{
	llint mul, add;
	inline flag(llint=1, llint=0);
};
inline flag operator + (flag, flag);

struct node
{
	llint key; flag up;
	int ord, npl;
	node * left, * right;

	inline node();
	inline void setf(flag);
	inline void pushdown();
	inline void maintain();
};
node * null=new node();
node memoryofnode[sizeofknight], * portofnode=memoryofnode;
inline node * newnode(int);
inline void swap(node *& , node *& );
node * merge(node * , node * );
inline void pop(node *& );

struct edge
{
	int point;
	edge * next;
};
edge memoryofedge[sizeofcity], * portofedge=memoryofedge;
inline edge * newedge(int, edge * );

int n, m;
node * t[sizeofcity];
edge * e[sizeofcity];
llint h[sizeofcity]; int a[sizeofcity]; llint v[sizeofcity]; int d[sizeofcity];
llint s[sizeofknight]; int c[sizeofknight];
int win[sizeofknight], die[sizeofcity];
void dfs(int);

int main()
{
	int f;

	n=getint(), m=getint();
	for (int i=1;i<=n;i++) h[i]=getintll();
	for (int i=1;i<=n;i++) t[i]=null;
	for (int i=2;i<=n;i++)
	{
		f=getint(), e[f]=newedge(i, e[f]);
		a[i]=getint(), v[i]=getintll();
	}
	for (int i=1;i<=m;i++)
	{
		s[i]=getintll(); c[i]=getint();

		if (s[i]>=h[c[i]])
			t[c[i]]=merge(t[c[i]], newnode(i));
		else
			die[c[i]]++;
	}

	dfs(1);
	for ( ;t[1]!=null;pop(t[1]))
		win[t[1]->ord]=d[c[t[1]->ord]]+1;

	for (int i=1;i<=n;i++) putint(die[i]);
	for (int i=1;i<=m;i++) putint(win[i]);

	return 0;
}

inline int getint()
{
	register int num=0;
	register char ch=0, last;
	do last=ch, ch=getchar(); while (ch<'0' || ch>'9');
	do num=num*10+ch-'0', ch=getchar(); while (ch>='0' && ch<='9');
	if (last=='-') num=-num;
	return num;
}
inline llint getintll()
{
	register llint num=0;
	register char ch=0, last;
	do last=ch, ch=getchar(); while (ch<'0' || ch>'9');
	do num=num*10+ch-'0', ch=getchar(); while (ch>='0' && ch<='9');
	if (last=='-') num=-num;
	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 flag::flag(llint _mul, llint _add)
{
	mul=_mul, add=_add;
}
inline flag operator + (flag a, flag b)
{
	return flag(a.mul*b.mul, a.add*b.mul+b.add);
}

inline node::node()
{
	key=inf, up=flag();
	ord=0, npl=-1;
	left=right=this;
}
inline void node::setf(flag _up)
{
	if (this==null) return ;
	key=key*_up.mul+_up.add;
	up=up+_up;
}
inline void node::pushdown()
{
	if (up.mul!=1 || up.add!=0)
	{
		left->setf(up);
		right->setf(up);
		up=flag();
	}
}
inline void node::maintain()
{
	npl=right->npl+1;
}

inline node * newnode(int _ord)
{
	node * ret=portofnode++;
	ret->key=s[_ord], ret->up=flag();
	ret->ord=_ord, ret->npl=0;
	ret->left=ret->right=null;
	return ret;
}
inline void swap(node *& a, node *& b)
{
	node * t=a; a=b; b=t;
}
node * merge(node * l, node * r)
{
	l->pushdown(), r->pushdown();
	if (l==null) return r;
	if (r==null) return l;
	if (l->key>r->key) swap(l, r);
	l->right=merge(l->right, r);
	if (l->left->npl<l->right->npl) swap(l->left, l->right);
	l->maintain();
	return l;
}
inline void pop(node *& t)
{
	t=merge(t->left, t->right);
}

inline edge * newedge(int point, edge * next)
{
	edge * ret=portofedge++;
	ret->point=point; ret->next=next;
	return ret;
}

void dfs(int u)
{
	for (edge * i=e[u];i;i=i->next)
	{
		d[i->point]=d[u]+1;
		dfs(i->point);
		t[u]=merge(t[u], t[i->point]);

		for ( ;t[u]->key<h[u];pop(t[u]), die[u]++)
			win[t[u]->ord]=d[c[t[u]->ord]]-d[u];
	}

	if (a[u]==0) t[u]->setf(flag(1, v[u]));
	else t[u]->setf(flag(v[u], 0));
}

装备购买（惊现 noip 良心题）

这是蛤么玩意儿？动态高斯消元——听上去挺高大上的……吗？

#include <cstdio>
#include <algorithm>
typedef long long llint;
const int sizeofvector=512;
const int sizeofdemension=512;
const int mod=1000000007;

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

inline int gcd(int, int);
inline int pow(llint, int);
inline int inv(int);
inline int mdiv(int, int);

int n, m;
int tot, ans;
int c[sizeofvector], ord[sizeofvector];
int a[sizeofvector][sizeofdemension];
int p[sizeofvector], l[sizeofvector];
inline bool cmp(int, int);
inline bool check(int);

int main()
{
	n=getint(), m=getint();
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
			a[i][j]=getint();
	for (int i=0;i<n;i++)
	{
		c[i]=getint();
		ord[i]=i;
	}

	std::sort(ord, ord+n, cmp);
	for (int i=0;i<n;i++)
		if (check(ord[i]))
		{
			p[tot++]=ord[i];
			ans+=c[ord[i]];
		}

	putint(tot), putchar(' ');
	putint(ans), putchar('\n');

	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]);
}

inline int gcd(int x, int y)
{
	for (int z;y;z=x%y, x=y, y=z);
	return x;
}
inline int pow(llint x, int y)
{
	llint z=1;

	for ( ;y;y>>=1)
	{
		if (y&1) z=z*x%mod;
		x=x*x%mod;
	}

	return z;
}
inline int inv(int x)
{
	return pow(x, mod-2);
}
inline int mdiv(int x, int y)
{
	int d=gcd(x, y);

	x/=d, y/=d;

	return 1ll*x*inv(y)%mod;
}

inline bool cmp(int i, int j)
{
	return c[i]<c[j];
}
inline bool check(int x)
{
	for (int i=0;i<tot;i++)
		if (a[x][l[i]])
		{
			int f=mdiv(a[x][l[i]], a[p[i]][l[i]]);

			for (int j=l[i];j<m;j++)
				a[x][j]=(a[x][j]-1ll*a[p[i]][j]*f%mod+mod)%mod;
		}

	for (int i=0;i<m;i++) if (a[x][i])
	{
		l[tot]=i;
		return true;
	}

	return false;
}

骗我呢

其实我还是不是很懂……

#include <cstdio>
typedef long long llint;
const int sizeofnumber=4194304;
const int mod=1000000007;

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

inline void swap(int & , int & );
inline int pow(llint, int);
inline int inv(int);

int n, m;
int f[sizeofnumber], g[sizeofnumber];
inline void prepare();
inline int C(int, int);
inline int calc(int, int);
inline void flip1(int & , int & );
inline void flip2(int & , int & );

int main()
{
	int ans;
	int x, y;

	n=getint(), m=getint();
	prepare();

	ans=calc(m+n+1, n);

	x=m+n+1, y=n;
	while (x>=0 && y>=0)
	{
		flip1(x, y);
		ans-=calc(x, y);
		flip2(x, y);
		ans+=calc(x, y);
		ans%=mod;
	}

	x=m+n+1, y=n;
	while (x>=0 && y>=0)
	{
		flip2(x, y);
		ans-=calc(x, y);
		flip1(x, y);
		ans+=calc(x, y);
		ans%=mod;
	}

	ans=(ans+mod)%mod;
	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(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 void swap(int & a, int & b)
{
	int t=a; a=b; b=t;
}
inline int pow(llint a, int b)
{
	llint c=1;

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

	return c;
}
inline int inv(int a)
{
	return pow(a, mod-2);
}

inline void prepare()
{
	f[0]=1;
	for (int i=1;i<sizeofnumber;i++)
		f[i]=1ll*f[i-1]*i%mod;
	g[sizeofnumber-1]=inv(f[sizeofnumber-1]);
	for (int i=sizeofnumber-1;i;i--)
		g[i-1]=1ll*g[i]*i%mod;
}
inline int C(int n, int m)
{
	if (n<m) return 0;
	return 1ll*f[n]*g[m]%mod*g[n-m]%mod;
}
inline int calc(int x, int y)
{
	if (x<0 || y<0) return 0;
	return C(x+y, x);
}
inline void flip1(int & x, int & y)
{
	swap(x, y);
	x--, y++;
}
inline void flip2(int & x, int & y)
{
	swap(x, y);
	x+=m+2, y-=m+2;
}

管道连接

又复习了一遍最小斯坦纳树也是蛮感动的，不过用状压 dp 来避免 2^p 次斯坦纳树还是挺赞的

#include <cstdio>
#include <cstring>
const int sizeofpoint=1023;
const int sizeofstate=1025;
const int sizeofedge=8192;
const int sizeofqueue=131072;
const int inf=0x3f3f3f3f;

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

inline int min(int, int);

struct edge
{
	int point, dist;
	edge * next;
};
edge memory[sizeofedge], * port=memory;
inline edge * newedge(int, int, edge * );
inline void link(int, int, int);

int n, m, p;
edge * e[sizeofpoint];
int belong[sizeofpoint], bit[sizeofpoint];
int dp[sizeofpoint][sizeofstate];
int f[sizeofstate];
inline void spfa(int);

int main()
{
	n=getint(), m=getint(), p=getint();
	for (int i=0;i<m;i++)
	{
		int u=getint(), v=getint(), w=getint();
		link(u, v, w);
	}

	memset(dp, 0x3f, sizeof(dp));
	for (int i=0;i<p;i++)
	{
		int c=getint(), d=getint();
		belong[d]=i, bit[c]|=1<<i;
		dp[d][1<<i]=0;
	}

	for (int state=1;state<(1<<p);state++)
	{
		for (int i=1;i<=n;i++)
			for (int j=(state-1)&state;j;j=(j-1)&state)
				dp[i][state]=min(dp[i][state], dp[i][j]+dp[i][state-j]);
		spfa(state);
	}
	for (int state=1;state<(1<<p);state++)
	{
		int connect=0;
		for (int i=0;i<p;i++)
			if ((state>>i)&1)
				connect|=bit[i];

		f[state]=inf;
		for (int i=1;i<=n;i++)
			f[state]=min(f[state], dp[i][connect]);
		for (int i=(state-1)&state;i;i=(i-1)&state)
			f[state]=min(f[state], f[i]+f[state-i]);
	}

	putint(f[(1<<p)-1]);

	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 min(int x, int y)
{
	return x<y?x:y;
}

inline edge * newedge(int point, int dist, edge * next)
{
	edge * ret=port++;
	ret->point=point; ret->dist=dist; ret->next=next;
	return ret;
}
inline void link(int u, int v, int w)
{
	e[u]=newedge(v, w, e[u]);
	e[v]=newedge(u, w, e[v]);
}

inline void spfa(int state)
{
	static int q[sizeofqueue];
	static bool vis[sizeofpoint];
	int l=0, r=0;

	for (int i=1;i<=n;i++)
	{
		q[r++]=i;
		vis[i]=true;
	}

	while (l<r)
	{
		int u=q[l++];
		for (edge * i=e[u];i;i=i->next)
			if (dp[u][state]+i->dist<dp[i->point][state])
			{
				dp[i->point][state]=dp[u][state]+i->dist;
				if (!vis[i->point])
				{
					q[r++]=i->point;
					vis[i->point]=true;
				}
			}
		vis[u]=false;
	}
}

战争调度（哎呦 wc 一连三道 dp 真是把我感动得泪流满面……）

用 f[i][j] 表示以 i 为根的子树中有 j 个人要去卖人头时的最大收益，然后 dfs 不断枚举每个点祖先的可能情况就搞掉了

#include <cstdio>
#include <cstring>
const int sizeofpeople=1025;

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

inline int lowbit(int);
inline int max(int, int);

int n, m, s;
int dp[sizeofpeople][sizeofpeople];
int lg[sizeofpeople];
int w[sizeofpeople], f[sizeofpeople];
int a[sizeofpeople][sizeofpeople];
int b[sizeofpeople][sizeofpeople];

void dfs(int, int, int);

int main()
{
	n=getint(), m=getint(), s=1<<(n-1);

	for (int i=0;i<n;i++) lg[1<<i]=i;
	for (int i=0;i<s;i++)
	{
		for (int j=1;j<n;j++)
			w[j]=getint();
		for (int j=1;j<s;j++)
			a[i][j]=a[i][j-lowbit(j)]+w[lg[lowbit(j)]+1];
	}
	for (int i=0;i<s;i++)
	{
		for (int j=1;j<n;j++)
			f[j]=getint();
		for (int j=1;j<s;j++)
			b[i][j]=b[i][j-lowbit(j)]+f[lg[lowbit(j)]+1];
	}

	dfs(1, 1, 0);

	int ans=0;
	for (int i=0;i<=m;i++)
		ans=max(ans, dp[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(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 lowbit(int x)
{
	return x & -x;
}
inline int max(int x, int y)
{
	return x>y?x:y;
}

void dfs(int u, int depth, int state)
{
	if (depth==n)
	{
		dp[u][0]=b[u-s][s-1-state];
		dp[u][1]=a[u-s][state];
		return ;
	}

	memset(dp[u], 0, sizeof(dp[u]));

	dfs(u<<1, depth+1, state<<1|1), dfs(u<<1|1, depth+1, state<<1|1);
	for (int l=0;l<=1<<(n-depth);l++)
		for (int r=0;r<=1<<(n-depth);r++)
			dp[u][l+r]=max(dp[u][l+r], dp[u<<1][l]+dp[u<<1|1][r]);

	dfs(u<<1, depth+1, state<<1),	dfs(u<<1|1, depth+1, state<<1);
	for (int l=0;l<=1<<(n-depth);l++)
		for (int r=0;r<=1<<(n-depth);r++)
			dp[u][l+r]=max(dp[u][l+r], dp[u<<1][l]+dp[u<<1|1][r]);
}

这各种 dp 真是不能再好好玩耍了啊……