【斯坦纳树】【LA5717】Beijing 2011 Peach Blossom Spring解题报告

在不务正业大半年后继续开始写正经的解题报告……


题目链接:

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3718


题意:

一个N<=50,M<=1000的边带权无向图,给定K<=5,第1~K号点是住宅,第N-K+1~N号点是避难所。要求选出一些边,把它们连起来,使得每个住宅都能走到一个避难所(注意一个避难所只能给一个住宅用),求最小的权值之和。


斯坦纳树:

这道题是基于斯坦纳树的。斯坦纳树的定义是:给定一张图和一个顶点集合,要求选出一些边,使得集合中的顶点连通。显然最小生成树是斯坦纳树的一个特殊情况:集合就是整个顶点集合V。

可以用状压DP求解斯坦纳树:令f[i][s]=(以i为根,集合中顶点连通情况至少为s的最小代价)。

首先从小到大枚举s转移。有两种转移方式:

1. f[i][s]=min(f[i][s], f[i][t]+f[i][s-t]),要求t是s的子集。枚举i和t即可完成。 枚举t可以用:for(t=s;t;t=(t-1)&s)。这个转移的意思是,将以i为根的两棵树“拼”起来。

2. f[i][s]=min(f[i][s], f[j][s]+w(i,j)),要求i,j之间有连边。这个意思是从j这个根往外“长”。

第二种转移比较麻烦,因为没有一个确定的顺序。怎么办呢?SPFA。在第一种转移结束后,建超级源S,向每个点连边w(S,i)=f[i][s],原图中的边保持不变。然后从超级源S开始做一次最短路,就可以把第二种转移搞定了。


题解:

我们的这道题基本就是斯坦纳树。但还有一小点不同:最后不一定是所有的住宅&避难所都在同一个联通块中。例如:住宅1,2和避难所8,9连通,住宅3和避难所10连通,这也是符合基本法的,可以作为一组解。

怎么办呢?在求完斯坦纳树之后,额外再进行一次“子集合并”的DP,注意,这里所有的合法状态都必须是住宅数=避难所数的。


代码:

#include
#include
#include
#include
#include
#include
using namespace std;
const int INF=0x7fffffff/2;
const int SIZEN=60;
int N,M,K;
vector > c[SIZEN];
void SPFA(int S,int dis[]){
	static bool inq[SIZEN];
	static queue Q;
	for(int i=0;i<=N;i++) inq[i]=false,dis[i]=INF;
	while(!Q.empty()) Q.pop();
	dis[S]=0;Q.push(S);inq[S]=true;
	while(!Q.empty()){
		int x=Q.front();Q.pop();inq[x]=false;
		for(int i=0;i

由于忘掉“No Solution”,WA掉一次……

[CodeChef FEB14]Graph Challenge解题报告(求半支配点)

题意

给一张有向图,使得从1开始按某种顺序DFS,可以让每个点的标号等于其DFS序号。求每个点的半支配点。

题解

使用Lengauer Tarjan算法,对这一算法的描述和证明见我的上一篇博文:

当然本题只需要求半支配点。
首先按照适当顺序DFS,还原题目描述中所称的DFS生成树。然后直接套算法。
代码如下,思路很简单。要点都写在注释中了。

#include
#include
#include
#include
#include
using namespace std;
const int SIZEN=100010;
void getint(int &x){
	char c=0;
	for(;c<'0'||c>'9';c=getchar());
	for(x=0;'0'<=c&&c<='9';c=getchar()) x=x*10+c-'0';
}
int N,M,Q;
vector c[SIZEN],ct[SIZEN];
int timer=0,fa[SIZEN];
int ufs[SIZEN],best[SIZEN],sdom[SIZEN];
int find(int x){//将x连接到路径最上端,并计算出一路上诸点的best 
	if(x==ufs[x]) return x;
	int y=find(ufs[x]);
	if(sdom[best[ufs[x]]]=1;i--){
		for(int j=0;ji的那些,find之后得到了它到根的最优sdom
			注意,对于第二种情况,u~v这一路上必然全大于i*/
			int u=ct[i][j];
			find(u);
			sdom[i]=min(sdom[i],sdom[best[u]]);
		}
		ufs[i]=fa[i];
	}
}
bool vis[SIZEN];
void DFS(int x){
	vis[x]=true;
	timer++;
	for(int i=0;i

在流程图中求支配点的一种快速算法

0.说明

本文译自Tarjan的论文:

选取了其中的一部分,有删改,以原文为准。

1.简介

在学习全局流分析和程序优化时,如下图论问题自然地浮现出来。设G(V,E,r)是一张流程图(本文中可以简单地代之以‘有向图’——译者注),以r为起点。我们称G中的节点v支配了另一个节点w,如果每一条从r到w的路径都包含了v。如果v支配w,并且w的其他支配点均支配v,我们就称v是w的最近支配点(又译最近必经点——译者注),记为v=idom(w)。

定理1. 流程图G=(V,E,r)中,除r外的所有节点均有唯一的最近支配点。边集{(idom(w),w)|w∈V-{r}}形成一棵以r为根的有向树,我们称之为G的支配树。v支配w当且仅当v在支配树中是w的完全祖先(非本身的祖先——译者注)。见图1、2.


图1.一张流程图


图2.图1中的支配树。

我们希望为任意的流程图G构造支配树。如果G代表了某种控制流程或计算机程序,支配树能够帮助我们分辨关于哪些代码修改是安全的。


2.深度优先搜索和支配点

快速支配点算法包含三个部分。首先,对输入的流程图G=(V,E,r)进行从r开始的深度优先搜索,并将图G中节点按照DFS访问顺序从1到n编号。DFS建立了一棵以r为根的生成树T,其节点以先根顺序编号。见图3.


图3.对图1进行深度优先搜索。实线是生成树边,虚线是非树边。括号中的数字是节点编号,字母是半支配点。

为方便陈述, 我们以编号代指点。

如下的“路径引理”是DFS的一个重要性质,在支配点算法的正确性证明中起决定性作用。

引理1. 若v,w是G中节点且v<=w,则任意从v到w的路径必然包含它们在T中的一个公共祖先。

其次,我们对每个节点w≠r计算一个值,称为它的“半支配点”,记作sdom(w),定义如下:

sdom(w)=min{v|有路径v=v0, v1, …, vk=w使得vi>w对1<=i<=k-1成立}.                   ···(1)

见图3.

然后,我们使用半支配点计算所有点的最近支配点。

半支配点的一些性质使之成为计算支配点的良好中介。若节点w≠r,则sdom(w)一定是T中w的完全祖先,而idom(w)是sdom(w)的(可能不完全)祖先。如果我们将G中非树边替换为边集{(sdom(w),w)|w∈V且w≠r},则各节点支配关系不变。于是,只要我们知道了生成树T和半支配点,我们就能计算支配点。

在本章节的余下部分中,我们将证明半支配点和最近支配点的一些性质,由它们可以推出算法的合法性。接下来三个引理给出了生成树、半支配点和最近支配点的一些基本关系。

引理2. 对任意节点w≠r,idom(w)+->w.(原注:本文中,记号”x·->y”意味着x是y在DFS生成树T中的祖先,而”x+->y”意味着x·->y且x≠y。)
证明. w的支配点必然在T中从r到w的路径上。

引理3. 对任意节点w≠r,sdom(w)+->w.
证明. 设w在T中的父亲为parent(w).由于(parent(w),w)是G中的一条边,由(1)式,sdom(w)<=parent(w)w对1<=i<=k-1成立。由引理1,路径上的某节点vi是sdom(w)和w在T中的公共祖先。但必然有vi<=sdom(w).这意味着i=0,即vi=sdom(w),且sdom(w)是w的一个完全祖先。

引理4. 对任意节点w≠r,idom(w)·->sdom(w).
证明. 由引理2,3,idom(w)和sdom(w)都是w的完全祖先。我们在从r到w的路径后面接上(1)式规定的路径sdom(w)=v0, v1, …, vk=w(其中vi>w对1<=i<=k-1成立),这条从r到w的路径避开了T中既是w的完全祖先,也是sdom(w)的完全后代(不等于它自身的后代——译者注)的那些点。因此idom(w)一定是sdom(w)的祖先。

引理5. 设节点v,w满足v·->w。则v·->idom(w)或者idom(w)·->idom(v).
证明. 设x是idom(v)的任意一个完全后代,且同时是v的完全祖先。则必然有一条从r到v不经过x的路径。将这条路径和从v到w的树上路径连接起来,我们就得到了一条从r到w不经过x的路径。因此idom(w)要么是v的后代,要么是idom(v)的祖先。

使用引理1~5,我们得到了两个有用的结论,它们提供了一种根据半支配点计算最近支配点的方法。

定理2. 设w≠r。假设所有使得sdom(w)+->u·->w的u都满足sdom(u)>=sdom(w),那么idom(w)=sdom(w).
证明. 由引理4,只需要证明sdom(w)支配了w。考虑任意一条从r到w的路径p。设x为这条路径上最后一个满足xy·->w的第一个点。设路径q=(x=v0, v1, v2, …, vk=y)是路径p中从x到y的部分。
我们断言对于1<=i<=k-1有vi>y。否则如果有vi=sdom(w),这意味着sdom(w)·->vj·->y·->w,这和y的选择矛盾。这证明了上述断言。
这一断言,加上半支配点的定义,得到了sdom(y)<=x

定理3. 设w≠r,u是所有满足sdom(w)+->u·->w的节点中sdom(u)最小的那个。则sdom(u)<=sdom(w),而且idom(u)=idom(w).
证明. 设节点z满足sdom(w)->z·->w。则sdom(u)<=sdom(z)<=sdom(w).(译者注:似误?sdom(u)<=sdom(w)是显然的,因为u可以等于w嘛!)
由引理4,idom(w)是sdom(w)的祖先,因此是u的完全祖先。由引理5,idom(w)·->idom(u).为了证明idom(u)=idom(w),只需要证明idom(u)支配了w。
考虑从r到w的任意路径p。设x是路径中最后一个满足xy·->w的节点。设路径q=(x=v0, v1, v2, …, vk=y)是路径p中从x到y的一部分。和定理2中的证明类似,x和y的选择意味着vi>y对1<=i<=k-1成立。因此sdom(y)<=x.由引理4,idom(u)<=sdom(u),所以sdom(y)<=x
由于u的选择,y不可能是sdom(w)的完全后代。并且,y不可能既是u的祖先,也是idom(u)的完全后代,因为在此情况下,把从r到sdom(y)的树上路径接上路径sdom(y)=v0, v1, …, vk=y(其中vi>y对1<=i<=k-1成立),再接上从y到u的树上路径,就形成了一条从r到u且避开idom(u)的路径,这和idom(u)的定义矛盾。
由于idom(u)·->y+->u·->w(译者注:原文‘y’处为‘v’,似误),并且idom(u)·->y·->w,余下的唯一可能就是idom(u)=y.因此idom(u)位于r到w的路径上。由于p是任意的,idom(u)必然支配w。证毕。

推论1. 设w≠r,u是所有满足sdom(w)+->u·->w的节点中sdom(u)最小者。那么,
idom(w)= sdom(w)(若sdom(w)=sdom(u)),或者idom(u)(其他状况)。                        ···(2)
证明. 由定理2,3,这是显然的。

下面的定理给出了一种计算半支配点的方式。

定理4. 对任意节点w≠r,
sdom(w)=min({v|(v,w)∈E且vw且存在边(v,w)满足u·->v})                        ···(3)
证明. 设x等于(3)式右端。我们首先证明sdom(w)<=x。如果x使得(x,w)∈E且xw,且存在边(v,w)满足u·->v。由(1),存在一条路径x=v0, v1, …, vj=u,使得vi>u>w对于1<=i<=j-1成立。而树上路径u=vj->vj+1->…->vk-1=v满足vi>=u>w对j<=i<=k-1成立。因此路径x=v0, v1, ..., vk-1=v, vk=w满足vi>w对1<=i<=k-1成立。由(1),sdom(w)<=x。
我们还需要证明sdom(w)>=x。设简单路径sdom(w)=v0, v1, …, vk=w满足vi>w对1<=i<=k-1成立。若k=1,那么(sdom(w),w)∈E。而根据引理3,sdom(w)=x。对k>1的另一种情况,设j是使得j>=1并且vj·->vk-1的最小值。这样的j一定存在,因为j可以等于k-1.
我们断言:对于1<=i<=j-1,vi>vj成立。否则,我们选取所有满足1<=i<=j-1且vi<=vj的i中使得vi最小的那个。由引理1,vi·->vj,和j的选择矛盾。这证明了断言。
根据上述断言,sdom(w)>=sdom(vj)>=x。因此无论k=1还是k>1,都有sdom(w)>=x,定理得证。

ps.我的下一篇博文:http://blog.csdn.net/wmdcstdio/article/details/50152713 给出了一道求半支配点的题目的代码。

[CodeChef FEB15]Payton numbers(CUSTPRIM)解题报告

题目

(翻译来自洪华敦)
定义三元组的乘法

def multiply((a1,b1,c1), (a2,b2,c2)):

s = (a1a2 + b1b2 + c1c2) + (a1b2 + b1a2) + (c1 + c2)

t = floor[s/2] + 16(c1 + c2) – c1c2

A = (t – 2(a1b2 + b1a2) – (a1c2 + c1a2) + 33(a1 + a2)+ (b1b2 – a1a2))

B = (t – 5(a1b2 + b1a2) – (c1b2 + b1c2) + 33(b1 + b2)+ (2b1b2 + 4a1a2))

if s is even: return (A-540,B-540,24)

else: return (A-533,B-533,11)

定义zero:若x*任何y=0,则称x是zero

定义单位元,若x*任何y=y,则称x是单位元

定义质数,若x不是zero且不能分解成两个非单位元的乘积,则称x是质数

给定一个三元组,问他是不是质数

题解

CC上有自带的(英文)题解:
还有一篇中文翻译:
翻译有遗漏之处,以原文为准。反正我就是看CC上的英文题解看懂的。
解法简直出(sang)神(xin)入(bing)化(kuang),大家还是去看原文吧……
(没错这真的是一篇解题报告)

代码

#include
#include
#include
#include
using namespace std;
typedef long long LL;
LL realmod(LL a,LL m){
	a%=m;
	if(a<0) a+=m;
	return a;
}
inline LL quickmul(LL x,LL y,LL MOD){
	x=realmod(x,MOD),y=realmod(y,MOD);
	return ((x*y-(LL)(((long double)x*y+0.5)/MOD)*MOD)%MOD+MOD)%MOD;
}
LL quickpow(LL a,LL n,LL M){
	a=realmod(a,M);
	LL ans=1;
	while(n){
		if(n&1) ans=quickmul(ans,a,M);
		a=quickmul(a,a,M);
		n>>=1;
	}
	return ans;
}
LL Legendre_symbol(LL a,LL p){//p是奇素数 
	//1代表a是平方剩余,-1代表a不是平方剩余,0代表a=0 
	//a^((p-1)/2)
	a=realmod(a,p);
	LL flg=quickpow(a,(p-1)/2,p);
	if(flg==0||flg==1) return flg;
	if(flg==p-1) return -1;
}
bool Rabin_Miller(LL n,LL p){//合数返回0
	if(n==2) return true;
	if(n==1||(n&1)==0) return false;
	LL d=n-1;
	while(!(d&1)) d>>=1;
	LL m=quickpow(p,d,n);
	if(m==1) return true;
	while(d

[CodeChef OCT13]斐波那契数Fibonacci Number解题报告

题目


分析

这道题是CodeChef上难得一见的优美数论题,比那些(净是中国人出的)丧心病狂的数据结构高到不知道哪里去了。

题目基于两个算法:第一个是Tonelli-Shanks算法,第二个是Shanks大步小步算法(这个Shanks是会玩的)。前者参见我的上一篇博文:http://blog.csdn.net/wmdcstdio/article/details/49862189,后者资料众多,不再赘述。
Tonelli-Shanks算法是一个“开根号”的算法。即,给出奇素数p和某个a,它能在O(log^2p)内找到一个r,使得r^2=a (mod p),或者判断不存在这样的r。而大步小步算法则是求“离散对数”的:给出a,b,求最小的非负整数n使得a^n=b (mod p)。
Tonelli-Shanks算法能干什么呢?首先可以求出模P意义下的“根号5”,即某个x使得x^2=5 (mod P,下略),然后就能求出模P意义下的”(sqrt(5)+1)/2″,记为y。

如此一来,我们可以把Fibonacci数列的通项公式写成:
Fn=(1/x)*(y^n-(-1/y)^n),其中的“除法”自然就是乘以乘法逆元的意思。
我们需要求出最小的非负整数n,使得Fn=c,把通项公式中的x乘过去,就是C*x=y^n-(-1/y)^n。

先假设n是偶数(n是奇数的情况非常类似,把它作为练习留给读者)。设C*x=d,我们的方程变成了:
d=y^n-1/(y^n).
在这里就可以看出来我们要做什么了,再写开一点:
设u=y^n,则d=u-1/u,u^2-du-1=0,这是一个标准的一元二次方程!只是它是在模P意义下的。
怎么解这个一元二次方程呢?
回想(实数系下)一元二次方程的求根公式,没错就是初中数学毒瘤题经常用的那个:(-b±sqrt(b^2-4ac))/2a,其中用到的操作无非加减乘除和开平方——这些操作,我们都能做!除法就是求逆元,开平方用Tonelli-Shanks。
于是我们得到了y^n的值。现在问题变成了:求最小的非负偶数n,使得y^n=u,当然可能的u有两个,即二次方程的两个根。
怎么解决“偶数”的问题呢?用Tonelli-Shanks把u开平方即可。当然你也可以先不管奇偶求一个n,然后再求y对P的阶数,试图累加。

如果你想这么做,还可以继续优化常数。这道题的主要复杂度来自于大步小步算法,可以主要由它下手:先把所有的u求出来,在一次大步小步算法中同时求解;以及把大步小步算法的map换成哈希表,都能有效减少常数。

代码:

#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
//取模,返回非负数 
LL realmod(LL a,LL M){
	a%=M;
	if(a<0) a+=M;
	return a;
}
//快速幂,用普通乘法实现 
LL quickpow(LL a,LL n,LL M){
	a=realmod(a,M);
	LL ans=1;
	while(n){
		if(n&1) ans=ans*a%M;
		a=a*a%M;
		n>>=1;
	}
	return ans;
}
//乘法逆元 
LL inverse(LL a,LL p){//a对p的乘法逆元,p是素数 
	return quickpow(a,p-2,p);
}
//勒让德符号 
LL Legendre_symbol(LL a,LL p){//p是奇素数 
	//1代表a是平方剩余,-1代表a不是平方剩余,0代表a=0 
	//a^((p-1)/2)
	LL flg=quickpow(a,(p-1)/2,p);
	if(flg==0||flg==1) return flg;
	if(flg==p-1) return -1;
}
//模意义平方根 
LL sqrt_mod(LL n,LL p){//解方程组x^2=n(mod p),Tonelli-Shanks算法,p是奇素数
	n=realmod(n,p);//保证n非负 
	//返回方程的一个根 
	if(Legendre_symbol(n,p)!=1) return -1;//无解
	LL S=0,Q=p-1; 
	while(!(Q&1)){
		S++;
		Q>>=1;
	}
	//现在Q是奇数,p-1=Q*2^S
	LL z;//选择一个二次非剩余z 
	while(true){
		z=rand()%p;//随机一个数,这个rand有可能太小,不知道会不会出问题 
		if(Legendre_symbol(z,p)==-1) break;
	}
	LL c=quickpow(z,Q,p),R=quickpow(n,(Q+1)/2,p),t=quickpow(n,Q,p),M=S,i,tmp,b;
	while(true){
		if(t==1) return R;
		for(i=0,tmp=t;tmp!=1;i++,tmp=tmp*tmp%p);
		b=quickpow(c,1LL<<(M-i-1),p),R=R*b%p,c=b*b%p,t=t*c%p,M=i;
	}
}
//二次同余方程 
bool quadratic_mod(LL a,LL b,LL c,LL p,LL &x1,LL &x2){//解同余方程ax^2+bx+c=0(mod p),p是奇素数 
	a=realmod(a,p),b=realmod(b,p),c=realmod(c,p);
	LL dlt=realmod(b*b%p-4*a%p*c%p,p);
	LL sd=sqrt_mod(dlt,p);
	if(sd==-1) return false;//无解
	LL inv2a=inverse(2*a,p);
	x1=realmod((-b+sd)%p*inv2a,p);
	x2=realmod((-b-sd)%p*inv2a,p);
	return true;
}
//扩展欧几里得算法 
void extend_gcd(LL a,LL b,LL &x,LL &y,LL &d){
	if(b==0){d=a;x=1;y=0;}
	else{extend_gcd(b,a%b,y,x,d);y-=(a/b)*x;}
}
vector > suspects;
LL C,P,ans;
void update(LL n){
	if(ans==-1||n

Tonelli–Shanks算法

Tonelli-Shanks算法是一个求解二次平方根的算法。即,对于奇素数p,和p的一个二次剩余n,求解x^2≡n (mod p)这样的方程。“n是二次剩余”是什么意思呢?就是这个方程有解,如果没解,就叫“二次非剩余”……


关于二次剩余,有一个叫“勒让德符号”(Legendre symbol)的玩意,它能判断对于奇素数p,a是否为p的二次剩余。懒得贴图片,把它写成L(a,p),其定义就是:

L(a,p)≡a^(
(p-1)/2 ) (mod p),这个值有-1,0,1三种可能。如果a不是p的二次剩余,这个值就是-1;如果a是0,这个值就是0;如果a是p的二次剩余,这个值就是1。

这叫做“欧拉判别法”(Euler’s criterion)。证明如下:

如果a=0,结论是显然的。

否则,由费马小定理,a^(p-1)≡1
(mod p),即:

(
a^( (p-1)/2 )-1 )*( a^( (p-1)/2 )+1 )≡0 (mod p)

由于p是素数,等式左边的两项中有一项模p余0.(p≠2,所以不可能两项都模p余0)

如果a是二次剩余,即存在x使得a≡x^2
(mod p),则显然x≠0,

a^( (p-1)/2 )≡x^2^(
(p-1)/2 )≡x^(p-1)≡1
(mod p).

因此,模p的每个二次剩余a都能使第一项为零。自然地,每个二次非剩余都会使第二项为零。

证毕。


回到我们的Tonelli-Shanks算法。算法如下:

输入:奇素数p,模p的一个二次剩余n(意味着勒让德符号L(n,p)=1).

输出:整数R,使得R^2≡n
(mod p,以下默认)

算法步骤:

①从p-1中除去所有因子2,设p-1=Q*2^S,其中Q是奇数(也就是除去所有因子2的结果)。如果S=1,即p≡3
(mod 4),那么直接返回R=±n^( (p+1)/4 ).

②选择一个z,使得勒让德符号L(z,p)= -1(即,z是p的二次非剩余),令c≡z^Q.

③令Rn^(
(Q+1)/2 ), tn^Q, M=S.

④循环:

1.若t1,返回R,程序终止。

2.否则,找出最小的i,使得0≡1。可以重复做平方完成这一点。

3.令b≡c^2^(M-i-1),令R≡R*b,tt*b^2,c≡b^2,M=i.

如果得到了一个解R,另一个解就是p-R。


算法正确性证明:

我们知道p-1=Q*2^S。令r≡n^(
(Q+1)/2 ),t≡n^Q,注意到r^2≡nt,这一同余式在每次循环中都保持正确。如果某时刻t≡1,那就有r^2≡n,于是我们找到了n的二次平方根R≡±r,算法终止。

如果t模p不等于1,那么考虑二次非剩余z。令c≡z^Q。则c^2^S≡(z^Q)^2^S≡z^(Q*2^s)≡z^(p-1)≡1.并且c^2^(S-1)≡z^(
(p-1)/2 )≡-1.这意味着c的阶是2^S.

类似地,t^2^S≡1,故t的阶能整除2^S.设t的阶是2^S’,由于n是模p的二次剩余,S’<=S-1.

现在令b≡c^2^(S-S’-1),r’≡b*r,c’≡b^2,t’≡c’t。和先前一样,r’^2≡n*t’仍然成立。但现在t和c’的阶数都是2^S’。这意味着t’的阶数2^S”满足S”

若S”=0,则t’≡1,算法终止,返回二次平方根±r’。否则,我们重新执行循环,定义b’,r”,c”和t”……直到停止。由于S序列严格递减,算法一定能结束。


算法复杂度:

平均2m+2k+S(S-1)/4+1/(2^(S-1))-9次乘法取模,其中m是p的二进制位数,k是p的二进制表示中1的数量。如果二次非剩余z的取法是随机选数,那么平均需要计算2次勒让德符号。因为随机选取一个数,是二次剩余的概率为((p+1)/2)/p=(1+1/p)/2,这个数小于1但略大于1/2。因此计算勒让德符号的期望次数是2.

换言之,我们将复杂度粗略估计为log^2(p),其中p是素数。


本文主要译自wiki有关章节。很惭愧,做了一点微小的工作,谢谢大家。

[CodeChef September Challenge 2012]Knight Moving(KNGHTMOV)题解翻译

首先,让我们忘掉答案可能会非常大,需要模10^9+7这一事实。我们将稍后考虑这一问题,讨论这将对解答造成何种影响。

问题分为两种情况。

情况1:A和B线性无关

由于A和B线性无关,我们可以对空间中的所有点,向由正交向量A和B确定的空间中做一线性映射。
这意味着我们可以将每个点(u,v)用(p,q)代替,使得:

p*Ay + q*Bx = u
p*Ay + q*By = v

如果终点(X,Y)无法转换成整点(x’,y’),那么即使不考虑障碍,合法的方案数也是0。
如果某个障碍点无法转换成整点(p,q),那么该障碍点永不可能到达,可以直接忽略。

现在,我们得到了障碍点集的一个子集,不妨称之为Q。在前往终点(x’,y’)的路径上必须避开。但现在,A和B被换成了(0,1)和(1,0)。

当每步可走(1,0)或(0,1)时,从(0,0)到达(p,q)的方法就是:

ways(p,q)=C(p+q,p)

对于障碍点集Q,可以用几种方法解决。

方法1. 容斥:

Sort Q, the subset of mapped forbidden points
totalWays = ways(0, dest)
for each subset S of Q
    cWays = 1
    visit points in S using i = 2 to S.size, in order of appearance in Q
        cWays *= ways(S[i] - S[i-1])
    sign = (S.size % 2 == 1) ? -1 : 1
    totalWays += sign * cWays


时间复杂度:O(K*2^K)


方法2. 高斯消元:

到达终点而不经过Q的方案数 = 到达终点的总方案数 – 到达终点且途径Q中至少一个点的方案数。

到达终点且途径P中至少一个点的方案数=
for i = 1 to Q.size, ways += x(i) * ways(i, dest)


其中x(i)是到达Q中第i个点,而不途径Q中别的点的方案数。


令Qc为Q包含的元素个数。

现在,

ways(0,j)=
for i = 1 to Qc, ways += x(i) * ways(i, j)

对所有同样在Q中的j。


如此,我们就有了关于Qc个变量的Qc个方程:

ways(0, 1) = x(1)*ways(1, 1) + x(2)*ways(2, 1) ... + x(Qc)*ways(Qc, 1)
ways(0, 2) = x(1)*ways(1, 2) + x(2)*ways(2, 2) ... + x(Qc)*ways(Qc, 2)
ways(0, 3) = x(1)*ways(1, 3) + x(2)*ways(2, 3) ... + x(Qc)*ways(Qc, 3)
...
ways(0, Qc) = x(1)*ways(1, Qc) + x(2)*ways(2, Qc) ... + x(Qc)*ways(Qc, Qc)


我们可以用高斯消元法在O(N^3)的时间内解出所有的x。


一旦算出了x,我们就可以计算到达(x’,y’)且途径Q中至少一个点的方案数,自然也可以计算到达(x’,y’)而不途径Q中任何点的方案数。

方法3. 排序:

现在我们知道Q中的点是有序的。故,
Sort Q
x(1) = ways(0, 1)
for i = 2 to Q.size
    x(i) = ways(0, i)
    for j = 1 to i-1
        x(i) -= x(j) * ways(j, i)


这样在O(N^2)的时间内,就可以算出上述的x。


如此一来,整个问题就解决了。

情况2:A和B线性相关

有众多的特殊情况需要仔细考虑:


①A=(0,0)且B=(0,0),那么(X,Y)=(0,0)时答案为-1,否则为0。
②如果Ax和Bx都是0但X非零,答案为0.
③如果Ay和By都是0但Y非零,答案为0.

令Gx为Ax和Bx的最大公约数,Gy为Ay和By的最大公约数。

④如果X不能被Gx整除,或Y不能被Gy整除,则答案为0.

我们可以忽略掉所有符合上述条件,因而无法到达的障碍点。

现在,我们可以将X坐标缩小Gx倍,将Y坐标缩小Gy倍。当然,我们只讨论那些可以到达的点。

由于A和B线性相关,我们知道两个坐标上的情况是相似的。因此,我们可以只在X坐标上进行DP,计算到达X的方案数,我们知道这也同样会到达Y。

我们可以用Bellman-Ford算法加上动态规划来计算到达终点的方案数——最初是(x’,y’)。我们可以做两次Bellman-Ford来判断是否有环。

如果有环,将有无穷多种方案。否则DP将得到方案数。

对这种情况更详细的说明,请看tester’s solution

还有数论

在解决过程中,我们始终需要计算组合数模10^9+7的值。

而且,我们需要在模10^9+7的域内进行高斯消元,这意味着高斯消元中所有的除法都由乘以逆元的方法进行。

组合数的问题可以用预先计算阶乘模10^9+7的余数以及乘法逆元来解决。由于组合数的范围不很大,我们可以这么做:

inv = Array[10000]
for i = 2 to 10000
    inv[i] = modulo_power(i, 1000000005)
fact = Array[10000]
ifact = Array[10000]
fact[1] = ifact[1] = 1
for i = 2 to 10000
    fact[i] = fact[i-1] * i mod 1000000007
    ifact[i] = ifact[i-1] * inv[i] mod 1000000007


其中fact是阶乘模10^9+7的余数,而ifact是其乘法逆元。


现在,

C(n,r) = fact[n]*ifact[r]*ifact[n-r] mod 1000000007


SETTERS SOLUTION

点击此处

TESTERS SOLUTION


点击此处

星系模拟器开发日志(二) 各个组件

2015.8.13更新:

上一章中解决了基本的画图技术,现在就该写真正的程序组件了。

我们将程序分成四个组件:

1)物理学组件physical module,包含基础的物理学和数学工具。

2)场景组件scene,包含场景相关的定义和方法。

3)绘图组件plotting,包含绘图方法。

4)头文件constants.h,包含程序中可能用到的诸多常量。

先写物理学组件physical module.h/cpp。

出于显然的原因,所有值均按国际单位制。

物理学组件包含:

①坐标类Vec3,成员是x,y,z三个坐标,均为float。Vec3这个名字沿用自OpenGL标准。之所以是三维是为了给将来(可能的)改成立体留余地。

②质点类Partical。成员:当前位置(Vec3),质量(float),速度(Vec3)。其中速度的方向就是向量的指向,大小则为向量的模长。

③向量加减、数乘、求模长等数学函数

④求一个质点对另一个质点所产生重力加速度的函数。公式就是a=G*m2/r^2,其中m2是施力物的质量,r是二者距离。这个公式其实就是万有引力公式约掉m1得到的。写着并不难,主要是逻辑结构要清晰。

万有引力常数G定义在constants.h中。

现在尚未解决“两点间距离为零”的问题,这个bug怎么处理我还没想好,姑且先放着

然后写场景组件scene.h/cpp。

为了未来魔改方便,写两个类:

①物体类Object,成员:将该物体视作的质点(Partical),颜色(int),颜色就是显示在屏幕上的颜色了……

②场景类Scene,成员:所有物体列表(vector),还有两个函数,分别是读入场景的函数Read和“推算下一时刻状态”的函数Step_Move。

Read其实就是OI中烂大街的那种读入了……用ifstream打开一个文件,然后读入各个物体。每个物体五个数(都是float):x坐标,y坐标,质量,速度x坐标,速度y坐标。

重点说一下Step_Move。它需要传入一个参数dt,代表从现在的状态推算dt时间之后的状态。由于三体问题没有一般解析解,所以这必然只是一个近似的模拟。这里采用的思路是:对于每个物体,假设其速度为v,我们计算当前时刻它所受到的加速度dv,然后假定它的速度在这dt时间内始终保持v+dv不变。这相当于假设速度只在当前时刻瞬间变化,然后一直做了时长为dt的匀速直线运动。

这个模型是可以修改的,比如说换做假定该物体在dt时间内做匀加速运动。这一点以后看情况再说。

然后是绘图组件plotting.h/cpp。

现在,我们的绘图方式是每一帧将所有物体都画在屏幕上。因而,绘图组件包含三个函数:

①将实际坐标转换成屏幕坐标的函数Coordinate_Transform。注意,这里需要一个有“比例尺”Plotting_Scale,它定义在constants.h中。

②在屏幕上显示一个物体(Object)的函数Plot_On_Graph。方法就是先用Coordinate_Transform转换坐标,然后再用EGE的绘制填充椭圆函数进行绘制。

③在屏幕上显示一个场景(Scene)中所有物体的函数Plot_On_Graph(重载了②)。方法就是遍历储存物体的vector,一个一个绘制。

最后还有一个constants.h,里面存放诸多常量。

把所有组件写好了,呼……睡觉去了,明天试着把它们合一块跑通。

8.14更新:

首先解决了“单独开一个控制台输出”的问题:
//打开一个控制台窗口
	if (AllocConsole()) {
		freopen("CONOUT$", "w", stdout);
	}


然后该写主cpp,即Solar Simulator.cpp了。


主要思路就是:
①先读取各物体
②进行循环,每次在屏幕上绘制所有物体
③之后让整个场景演进一小段时间

写完之后跑了一个例子,发现两个质点飞快地相离而去……然后发现“演进一步”的函数写挫了,不管dt是几都相当于加速了一秒钟。果断改。然后还修了几个小bug,程序算是初步能运行了。

效果图:

点是一个物体,椭圆是另一个物体的轨迹。把“另一个物体”的质量设为了零,所以中央那个点并不移动。由于懒得算比例尺了,我把引力常数调成了4……

放一个三体问题的轨迹图:

这个版本是v1.0。

然后接着改。

先改一个明显的问题:v1.0中很多参数都放在了contsants.h中,这样每改一次就要重新编译一次,并不优美。所以把它改成:config.txt中,每次运行之前读取。这样就需要用fscanf。不过fscanf会报错,而我又懒得学fscanf_s了,姑且把那个报错先关掉。

这样需要修改各常数的生命方式。需要建一个constants.cpp,在这里定义所有的数值,然后在constants.h中将它们都extern一下,这样才能达到各文件共享的目的。

然后就是修改物理模型:改为假定一个物体在dt时间内做匀加速运动,即加速度不变。

这样的运行结果科学了一些,但还是存在问题:



那个螺旋形轨道本来应该是一条圆轨道的……这弄得跟蚊香似的。

原因就是:匀加速运动不可避免地让物体总是有着与其同向的加速度分量,因此速度不断加快。

怎么减小这个误差呢?容易想到的就是:缩小每一步的时间间隔。所以我们设立一个值Frame_Step_Cnt,代表每一帧都要计算这么多步。

改为每帧100步(上图较之每帧时长相同,但每帧只有一步),就好多了:



效果拔群!

再玩一个三体模型:


如果跑v1.0图中那个三体模型的话,其实结果是很不一样的:


(混沌系统的锅,怪我咯……)

测试中可以发现,当每帧步数不同时结果甚至会有很大差异,主要是在某些特定帧步数时,两物体会很快地“弹飞”而去。这可能就是那个“距离为零”的问题,也可能是别的。我猜原因之一可能是:在距离很小的时候,加速度的改变非常剧烈,这就让“加速度在dt内恒定”的预设和现实产生较大偏差。这一点应设法予以解决。但反正是混沌系统,不要在意这种细节……

8.16更新:

更换为匀加速模型,并且在config.txt中读入参数的版本是v1.1.
懒癌发作不想接着写了,歇两天……

星系模拟器开发日志(一) 如何科学地用C++画图

代码下载地址:

2015.8.11更新:

最近突然有一个想法:写一个程序,用来模拟太阳系的行星运动,甚至是任意星球的运动。感觉这个想法非常excited,所以就准备开始写。程序的名字就叫“星系模拟器”吧,或者也可以称作“拉普拉斯的长者?”,英文名Solar Simulator

为了避免写完后过一个月看不懂代码的悲剧重演,我准备把整个开发过程都记在这里。

工具:
①一只NOIP选手
②一台电脑
③稍有的物理学常识

2015.8.13更新:

首先说一下思路。
①每个物体都是一个质点,只考虑万有引力
②先假设所有物体都在二维平面上运动,三维的以后再说
③每个物体都用一个小点表示
④怎么模拟运动呢?最早想的是能不能用方程,然后我突然想到“三体问题没有解析解”这回事……果断大模拟

先解决“在屏幕上显示图形”这回事。毕竟作为一只NOIP选手,我以前写过的都是“黑白屏幕的傻X程序”。

先找了半天,找了两个备选方案:一是按着《C++图形与游戏编程基础》用Dark GDK,但它只兼容vs2008,而且功能非常受限。二是用DirectX,但找了找教程发现相当于学习windows编程,上来就给一堆乱码般的函数和类名跪了,写个显示亮点的小程序我至于吗我……

后来经光神指点,找到一个好东西:Easy Graphics Engine(EGE),主页http://tcgraphics.sourceforge.net/,在VS2015下的安装教程见http://www.jianshu.com/p/b12163e5a0b7

环境已备好(VS2015 Community+EGE),可以开始了。

EGE的函数名称啥的都很直白,我也不介绍了,主页里写的非常清楚。先写个“画东西”的小程序压压惊吧:

#include "stdafx.h"
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

int main() {
	//初始化一个200*200的图像区域
	initgraph(200, 200);
	//设置绘图颜色
	setcolor(WHITE);
	//画空心圆
	circle(100, 100, 3);
	//设置填充颜色
	setfillcolor(WHITE);
	//填充圆
	floodfill(100, 100,WHITE);
	//等待按任意键
	getch();
	//关闭图像
	closegraph();
	return 0;
}


效果图:


我们将用这样的“亮点”表示物体,当然屏幕肯定比200*200大。

EGE中,坐标(x,y)代表距离左边x,距离上边y,不要搞反了

EGE还可以画像素。画一个抛物线作为练习:

#include "stdafx.h"
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#pragma warning(disable:4996)//无视掉freopen的警告

const int gsize = 600;

int main() {
	//打开图像
	initgraph(gsize, gsize);
	
	//绘图
	for (float x = 0, y = 0 ; y < gsize ; x+=0.001, y = x*x/500) {
		putpixel(int(x+0.5), int(y+0.5), WHITE);//画像素
	}

	//关闭图像
	getch();
	closegraph();
	return 0;
}


方程y=x^2/500


效果图:




接下来该画动图了。按照EGE官网上的教程,写了一个画动图的程序:

#include "stdafx.h"
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#pragma warning(disable:4996)//无视掉freopen的警告


void mainloop()//主循环
{

	//将线条和填充颜色设为白色
	setcolor(WHITE);
	setfillcolor(WHITE);

	float x = 0, y = 0;

	for (; is_run(); delay_fps(60))//每秒60帧
	{
		
		//cleardevice();//清屏
		y = x*x / 500.0;
		fillellipsef(x, y, 3, 3);//画以(x,y)为中心,长短轴均为3的椭圆
		x += 1.0;//更新x
	}
}

int main(void)
{
	//设置初始化图形,差不多就是默认
	setinitmode(INIT_DEFAULT | INIT_NOFORCEEXIT);
	//初始化窗口
	initgraph(600, 600);
	//初始化随机种子
	randomize();
	//设置更新窗口模式,为手动模式
	setrendermode(RENDER_MANUAL);
	//主循环
	mainloop();
	//关闭窗口
	closegraph();
	return 0;
}


这是动态绘制上述抛物线的程序。

注意,每一帧绘制完成后我没有清屏,这意味着它将绘制出整条轨迹。

画到一半的效果图:



Farewell, OI!

听说写退役感言是传统,那我也写一个吧……

 

似乎很多OIer会对信息学竞赛怀有一种特殊的感情,我可能没那么强烈。NOI之后,我最主要的感受就一条:结束了,终于结束了。

 

初一最早听说有信息学竞赛的时候,我其实是拒绝的,因为当时我是一个搞数学竞赛的骚年……但还是抱着试一试的心态去了,结果就一发不可收拾,初中是OI数竞一块搞,高中就翘掉数竞全力搞OI,直到现在。

 

我对于OI的记忆大致分两半:一半是浮躁,一半是干活。

 

浮躁的自然很爽。

初中被xwy、cjj、xys、sqh等一堆人带着打CS,NOIP前联机大家被专家BOT血虐,怒而上半自动狙+屏幕中央小红点。

初三愉快地和高中的OIer搬到一起,开始和zjm、wyf、cyr、光神、峰神等一堆人连红警,机房最多凑过八人局,几十辆V3火箭车在河边排开,导弹在空中爆炸的气浪让对面的防空车跳起。

连求生之路,四人打剧情始终过不去游乐场那一关,站在台子上总是被Smoker拖下地然后被各种吊打……

连MC,我的最爱是建一个深埋于地下的掩体当家,然后在地底种上农作物等一套完整的维生体系,这个事在不同的服务器里干了好几次,其中只有一次是最满意的,连树都种上了。

每次出去比赛都是浮躁高峰,一堆人趴在宾馆床上连红警/CS的感觉不能更赞。CTSC/APIO2014时人太多,把酒店房间都给弄跳闸了……

高二,上一届机房党纷纷退役之后浮躁的就少多了,也就是看电影、WOT啥的。电影倒是真看了不少。

 

干活……内容比较复杂。

初中就是各种花式刷题,找COGS上历年省选和NOI试题刷。

高一开始刷USACO Training,然后刷历年集训队论文,刷完了刷集训队互测题,刷了两年的互测题再刷集训队作业,14年是50道TC,15年是100道CF和50道USACO月赛/GCJ,我刷完100道CF后刷了几道USACO,就结束了。

总共做了有1000多道题,但我最开心的倒不是刷了多少题,而是往COGS上添了几百道题目,大概就三块:整理了一套完整可做的USACO Training列表(除了Chapter 6);把00年开始的集训队论文题中能放的都放到了COGS上(当然也有我自己懒没写的,就跳过了_(:з」∠)_);把11年和12年的集训队互测题放了上去(也有少数没放的……)。剩下还有一些零散的TC/CF/USACO,我看着有意思就放+博客写题解,没意思就罢。还有刘汝佳训练指南上的一些题,包括插头DP那一节的全部题目,个人感觉这是我OI生涯中干过最毒瘤的事情了,哈哈。这些题有不少人做,包括衡中以ztx为代表的若干神犇和十一中的Chenyao神犇,还有我校的wjx、zlx、lyc……总之,后人如果也做这些题的话,就不用像我这样花式Google数据和花式随机造数据了。

 

当然还有出去培训和比赛。

初一的时候参加了HAOI初中组,写了个大暴力排序(当时还只会选择排序)+骗样例,貌似拿了个第6名啥的,当然初中组这种蒟蒻水平都是小朋友自己玩……

初二参加了NOIP普及组,拿了个250分(貌似报名费就是250……)。

然后参加了HAOI高中组,以为A掉了“外星人”那道题,还兴奋地给小伙伴们讲做法,结果后来发现是错的_(:з」∠)_。

初三NOIP2012提高组考了200多分,好像是二等奖。

13年冬令营去晃了一圈,那次是在电子科大办的,住一个不近不远的酒店,那次翘了所有的晚上讲课蹲在酒店玩游戏,翘了半天(貌似)英文讲课去看007电影。现在还记得有一位教授讲的,用程序模拟合肥托卡马克装置中氦轰击对容器壁的影响(应该是这,只记得大意了),他说“讲这些不是为了让你们听懂,而是为了让你们开阔眼界”,深以为然。王宏讲IOI题目出很长的原因是为了防止领队泄题,还说个人感觉韩国队干过这事(……)。电子科大的早餐非常好,闭幕式搞了个会餐,饭和节目都不错,excited。那次是用常老师的名义去的,所以没有参加比赛,比赛那天在宾馆对着纸质题面愉快地写了大暴力,晚上丽洁讲题全程没听懂,发现自己真是什么都不会啊……

13年参加了APIO,但没参加CTSC。APIO是在北大,比赛前河南众人绕着未名湖散步,路上和郑外的ck神犇(ps:此君特点是喝水多,曾有在省实验到火车站的公交上干掉2.5L水的光辉事迹)扯了半天地震武器,云爆弹啥的。比赛用的是Dev-C,还摸索了半天用法(当时英语渣)。我作为一名蒟蒻专攻提交答案题(因为前面两道都不会……),在线显示得了40来分,出成绩的时候貌似又成了20来分,总之胸牌滚粗。考试结束之后大家说去吃KFC,在1.7公里外有一个,结果走了半小时才到,ck曰:望山跑死马啊……

13年NOI打了个酱油。Day1大暴力,Day2大暴力,提交答案题大家都是全输0,能得十来分,我不知道脑子怎么抽了全输1,就两分,恰好弥补了笔试丢掉的两分,结果总分250(我跟250有缘……),铜牌线245,于是卡线铜牌,对了,多那5分还是来自于某道重评后给大家都加5分的DP题╮(╯▽╰)╭

值得一提的是NOI2013的团抗。这一年的团抗是“圈地为王”,我、cyr、wyf等人分工合作,在尝试后写了一个能搜索11步的程序,后来证明这个思路是正确的,高分的各队都这么做。当时缺乏写长代码的经验,搞的有点混乱,直到NOI上还在完善代码。弄了个什么“威慑度”,用各种加补丁的方式试图解决了“逻辑锁死”问题,反正个人感觉代码写得一片鸡飞狗跳。最终决赛现场欢乐无比,比如丧心病狂的河北代码(在最初的策略失败后改成追着人跑,誓死把你拖下水……),众多异常退出的错误,还有代码奇异的走位……最后拿了第6,奖品是ipod
shuffle,看着近1800行的代码还是很有成就感的。

NOI2013是在电子科大另一个校区办的,宿舍有水有电没空调,湖南队出去住还被杜子德批判了一番。

高一,NOIP2013拿了450分,终于有了一等奖……

WC2014持续打酱油。这次是在八十中,看守甚严不让外出,于是我们请了一次假,去外面超市搬了两箱零食回来。讲了哪些课,其实我已经不太记得了,只记得我们带着插线板抢占最后排中央唯一的插座,然后给旁边众人插线板接插线板,最长转接三次……应景的是,有一道题大致就是给个电阻网络,求等效电阻。这次也是最简单暴力+提答,甚至连稍微复杂一点的暴力都没写,然后就奇奇怪怪地拿了个铜牌。

HAOI2014稳妥进队(题比较水,有个计算几何题本来过不了,但没出坑人数据)。zjm提前交卷,悲剧地被监考老师认成初中生,发了初中的密码……结果卡线没进队。wmy也没进队。

APIO/CTSC2014都去了,是在北航。首次见到了Chenyao神犇。这次考试也是各种跪,APIO非常傻叉地专攻一道Tree DP,结果前面的简单暴力都没写。最后还是拿了两个铜牌。没进成北航的航空航天博物馆,不开心。喝到了传说中的北冰洋汽水。

然后去学军中学培训了一段时间。

然后是NOI2014,在深圳外国语。考前给省队集训出了两套题,结果只做了一套,就和wyf去学军中学培训了。这次总之水平太弱,LCT不会写,卡时也不会,提答找不出规律,KMP树不懂,大暴力没看出来,最后斜率优化DP还写了个错误的链剖。卡银牌线铜牌,之前清华夏令营签的协议也没用。

这次团抗是麻将,Chenyao神犇基本写了全部代码。他对大工程的控制水平比我高到不知道哪里去了,最终代码简洁而优美。团抗现场他带着我膜拜各省参赛队,最后拿了个第二,奖品ipod nano。第一是甘肃,他们只去了两个人,白白浪费一个ipad mini……╮(╯▽╰)╭

NOIP2014满分。

WC2015之前和Chenyao神犇去学军中学培训。

WC2015是在学军中学,住在对面的浙大宿舍。考试前一天,我们九个人愉快地去吃了一顿饭。考后又翘掉社会活动,去浙江博物馆转了一圈。考试拿了第一名,我也不知道怎么回事,人呐都不知道,自己不可以预料。

APIO/CTSC2015是在人大。CTSC2015第一天写挂了一点,第二天A了一道题,总之是一等奖。APIO满分。

然后又和Chenyao神犇去学军中学培训。

NOI2015前又和Chenyao神犇去学军中学培训。NOI2015第一天考完,校方组织看《模仿游戏》,在看到图灵破解出密码的时候,某人高呼“暴力出奇迹!”全场掌声雷动。第一天300,第二天230,是花一上午写了第三题,灵魂debug出425行代码。一共630,总之终于进队了。去了北大,不妨说个戏谑的理由吧:北大擅长搞学潮,哈哈。

 

我一直试图给高一时从数学转向OI找出原因。

OI较之数学更好进队或许是原因之一,但当时我其实真心认为数学竞赛的含金量高于OI,故自招的机会也更大。

更深层的原因可能是内核上的。

数学本质是一种纤巧而优美的逻辑结构,像一件富丽堂皇而又精美繁复的艺术品。我欣赏这种美,也乐于学习这种美,但或许缺乏将其作为毕生事业的热情。

至于OI,不妨先看看别的。

我始终爱好“复杂而精确的机械”,对此不妨直观地想象《模仿游戏》中的破译机器:无数齿轮、传动轴、连杆相互啮合,在电机的驱动下轰鸣作响。这是工业和科学的胜利,是人类智慧和力量的荣耀。

不妨再想想别的。探测器沿着既定的轨道飞往深空,精度“相当于抛出一根针,让它穿过50千米外的针眼”;恰到好处的中子射流在瞬间引爆氘化锂;压气机将稀薄的空气送入燃烧室,上千度高温的气体在喷口后形成明亮的马赫环;垂发装置的顶盖按次序打开,导弹在烟雾和火光中逐个升起……这是壮丽的,也是浪漫的,我所理解的“男人的浪漫”。

因此我总是对物理学和军事装备有一种情感上的喜好,直到四月份清华夏令营之前我还把“高考去某物理系/国防科大”作为一种选项(当然后者的最大障碍可能是太胖_(:з」∠)_)。

不过,其实我也没法真学这个,原因无他,手残。不是普通的残,是惊天动地的残,是惨绝人寰的残,是念天地之悠悠独怆然而涕下的残。从小到大的美术课,手工作品我一个像样的都没做出来过,画画被评为“有幼儿园墙上涂鸦的风范”。所以我要真去了需要做实验的专业,估计这效果跟杨振宁是一样的,哪里爆炸都想我,哪里着火都有哥……

但是!编程不一样。编程不需要手巧,会敲键盘就行。0就是0,1就是1,int main()就不是int mian(),long long long就是too long。我们可以窝在空调房里写出复杂性让巴贝奇的差分机黯然失色的程序,而不用动手拧哪怕一个螺丝。不要999,也不要888,只要21天,只要21天,帮你完成机械梦想,手残党福音,包好,包好!

因此,我在OI中的成就感事实上并非来自于那一个个“Accepted”,而是“构筑机械”的过程本身。将头脑中的逻辑结构在屏幕上奠基、立柱、砌墙、封顶,“We have laid the wide foundations, built it skyward stone by stone”,这是何等快意!

这也可以解释,我对OI的热情随着学习的加深实际上出现了某种程度的减退——因为新的知识和技巧越来越少了,常用的各种算法模块也已不再新鲜,题目更倾向于“脑筋急转弯”,尤其是CF的题。USACO的这个问题倒少很多,大多都是好玩的数学题,这也是我喜欢USACO胜过CF的原因。学习OI仍然是一件令人高兴的事情,但如果这次NOI失败,我也不会选择再考一年,因为剩下的也多是脑筋急转弯、刷熟练度和模块拼装,这不和高考一样嘛。

在整个OI生涯中,我始终在说“不当码农”,并似乎将其作为了某种提高格调用的信条。但仔细看来,我也并非是“不当码农”,而是“不当普通的码农”,就是那种在公司里写一个xx模块的码农,我总是有种参与“为国家/人类做贡献的大工程”的冲动——要是有人找我给空间探测器/EAST/LHC写代码,我肯定第一个去。或者要是没有涉密人员出国限制这种玩意,并且国家找我给飞机飞控软件/火箭制导系统写代码,我也第一个去。用巴顿的话说,“二十年后,当你在壁炉边,孙子坐在你的膝盖上,问你:“爷爷,你当年在干什么呢?”你不用尴尬地干咳一声,把孙子移到另一个膝盖上,吞吞吐吐地说:“啊……爷爷我当时在写一个投放广告用的数据挖掘算法。”与此相反,你可以直盯着他的眼睛,理直气壮地说:“孙子,爷爷我当年在给国家研制狗娘养的战斗机!”

仔细想想也是中二感十足啊。当然,这是偏颇的——我完全知道有多少伟大的成就是在公司研究院做出的,也完全知道贡献不分贵贱,因为科学仰赖于无数随机的探索,今天看似毫无意义的成果在明天就可能成为文明进步的柱石,如椭圆曲线和开普勒定律,如非欧几何和广义相对论。但我就是本能地反感写高频交易,或着广告投放之类的算法。情感必然是偏颇的,否则也就不是情感了。

 

上面扯了一通,其实并没有什么实际意义——空谈误国,实干兴邦嘛。作为年轻人,多学习理论,提高自己的知识水平才是最好的。向前!向前!向前!