一道几何题。
![北京大学2010年自主招生数学试题[第一题] - 天之骄子 - 天之骄子的家](https://blog.boleyn.su/wp-content/uploads/2010/06/2368611929020188201.jpg "北京大学2010年自主招生数学试题[第一题] - 天之骄子 - 天之骄子的家")
第一题: AB为边长为1的正五边形边上任意两点,证明AB最长为(sqrt(5)+1)/2.(注:sqrt(x)=x的平方根) 解: 显然AB在图中的位置应该如图所示. 我们设AB=x,那么AB=CD=BD=x,那么A(-1/2,a),C(1/2,a),B(x/2,0),D(-x/2,0),其他不管了. 然后(1/2+x/2)^2+a^2=x^2 (CD=x) (1/2-x/2)^2+a^2=1^2 (BC=1) 然后x^2-x+1=0 解方程,x=(sqrt(5)+1)/2(舍负根).
下面的话来自http://acm.pku.edu.cn/JudgeOnline/showmessage?message_id=144157。
我们从右到左，将每2个棋子看成一对来处理。
如果对方移动某对棋子中的左边棋子x步，那么我方就移动右边棋子x步。
如果对方一定某对棋子中的右边棋子，那么就可以看作NIM游戏了。
恩，然后，贴代码。
CODE:
/*
AUTHOR: Su Jiao
DATE: 2010-6-19
DESCRIPTION:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1704
*/
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
#include <vector>
using std::vector;
#include <string>
using std::string;
#include <algorithm>
using std::sort;
class Application
{
int T,N;
vector<int> P;
string get()
{
sort(P.begin(),P.end());//IMPORTANT
int SG=(N&1)?P[0]-1:0;
for (int i=N-2;i>=0;i-=2)
SG^=P[i+1]-P[i]-1;
if (SG) return “Georgia will win”;
else return “Bob will win”;
}
public:
Application()
{
std::ios::sync_with_stdio(false);
}
int run()
{
cin>>T;
for (int i=0;i<T;i++)
{
cin>>N;
P.resize(N);
for (int j=0;j<N;j++)
cin>>P[j];
cout<<get()<<endl;
P.clear();
}
return 0;
}
};
int main()
{
Application app;
return app.run();
}
就是如果放了一个在某个位置，那么就不能放他旁边的四个了(左边两个，右边两个)。如下图，如果A在红画了X，如果B在绿画了X，那么A再在蓝画了X，A就能赢。
![POJ3537[Crosses and Crosses] - 天之骄子 - 天之骄子的家](https://blog.boleyn.su/wp-content/uploads/2010/06/1510676200006308777.jpg "POJ3537[Crosses and Crosses] - 天之骄子 - 天之骄子的家")
/*
AUTHOR: Su Jiao
DATE: 2010-6-19
DESCRIPTION:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3537
*/
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
#include <vector>
using std::vector;
class Application
{
int n;
vector<int> _sg;
int SG(int x)
{
if (x<0) return 0;
if (_sg[x]!=-1) return _sg[x];
else
{
vector<bool> found(n+1,false);
for (int i=1;i<=x;i++)
found[SG(i-2–1)^SG(x-i-2)]=true;
for (int i=0;i<=n;i++)
if (!found[i]) return _sg[x]=i;
}
}
public:
Application()
{
std::ios::sync_with_stdio(false);
}
int run()
{
cin>>n;
_sg.resize(n+1,-1);
if (SG(n)) cout<<1<<endl;
else cout<<2<<endl;
return 0;
}
};
int main()
{
Application app;
return app.run();
}
利用(SG^k[i])^(k[i]-(k[i]-(SG^k[i])))=0，推走哪一步可以让对方处于必败态。
SG为起初所有k[]的NIM和（即异或结果）。
那么SG^k[i]=所有k[]中除去k[i]后的NIM和(由a^b=c等价于a=b^c得)。
所以当k[i]>(k[i]-(SG^k[i]))时，从k[i]中取走(k[i]-(SG^k[i]))，剩下(k[i]-(k[i]-(SG^k[i])))=(SG^k[i])。
然后(SG^k[i])^(SG^k[i])=0，是一个必败态。
CODE:
/*
AUTHOR: Su Jiao
DATE: 2010-6-18
DESCRIPTION:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2975
*/
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
#include <vector>
using std::vector;
class Application
{
int n;
vector<int> k;
public:
Application()
{
std::ios::sync_with_stdio(false);
}
int run()
{
for (cin>>n;n;cin>>n)
{
k.resize(n);
int SG=0,answer=0;
for (int i=0;i<n;i++)
{
cin>>k[i];
SG^=k[i];
}
if (SG)
for (int i=0;i<n;i++)
if ((SG^k[i])<k[i]) answer++;
//(SG^k[i])^(k[i]-(k[i]-(SG^k[i])))=0
cout<<answer<<endl;
k.clear();
}
return 0;
}
};
int main()
{
Application app;
return app.run();
}
博弈，用SG函数。经典NIM改一点点，SG(x)=mex{SG(x-S[i])}。
CODE:
/*
AUTHOR: Su Jiao
DATE: 2010-6-18
DESCRIPTION:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2960
*/
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
#include <string.h>
class Application
{
static const int MAXK=100;
static const int MAXL=100;
static const int MAXH=10000;
int k,m,l;
int S[MAXK],h[MAXL],_sg[MAXH+1];
int SG(int x)
{
if (_sg[x]!=-1) return _sg[x];
else
{
bool found[MAXH];
memset(found,0,sizeof(found));
for (int i=0;i<k;i++)
if (x-S[i]>=0)
found[SG(x-S[i])]=true;
for (int i=0;i<MAXH;i++)
if (!found[i]) return _sg[x]=i;
}
}
char get()
{
int sg=0;
for (int i=0;i<l;i++)
sg^=SG(h[i]);
if (sg) return ‘W’;
else return ‘L’;
}
public:
Application()
{
std::ios::sync_with_stdio(false);
}
int run()
{
for (cin>>k;k;cin>>k)
{
for (int i=0;i<k;i++)
cin>>S[i];
memset(_sg,-1,sizeof(_sg));
cin>>m;
for (int i=0;i<m;i++)
{
cin>>l;
int max;
for (int j=0;j<l;j++)
{
cin>>h[j];
if (h[j]>max) max=h[j];
}
cout<<get();
}
cout<<endl;
}
return 0;
}
};
int main()
{
Application app;
return app.run();
}
博弈动归，方程f[i]=pool[i]-max{f[next[i]]}，从后往前推，next[i]表示可能为i的后继的值。
CODE:
/*
AUTHOR: Su Jiao
DATE: 2010-6-18
DESCRIPTION:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1678
*/
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
#include <vector>
using std::vector;
#include <algorithm>
using std::sort;
class Application
{
int t,n,a,b;
vector<int> pool;
int get()
{
const int oo=~(1<<31);
sort(pool.begin(),pool.end());
//f[i]=pool[i]-max{f[next[i]]}
vector<int> f(n,-oo);
int answer=-oo;
bool have_first=false;
for (int i=n-1;i>=0;i–)
{
bool have_next=false;
for (int j=i+1;j<n;j++)
if (a<=pool[j]-pool[i]
&&pool[j]-pool[i]<=b
&&f[i]<f[j])
f[i]=f[j],
have_next=true;
if (have_next) f[i]=pool[i]-f[i];
else f[i]=pool[i];
if (a<=pool[i]
&&pool[i]<=b
&&answer<f[i])
answer=f[i],
have_first=true;
}
if (!have_first) answer=0;
return answer;
}
public:
Application()
{
std::ios::sync_with_stdio(false);
}
int run()
{
cin>>t;
for (int i=0;i<t;i++)
{
cin>>n>>a>>b;
pool.resize(n);
for (int j=0;j<n;j++)
cin>>pool[j];
cout<<get()<<endl;
pool.clear();
}
return 0;
}
};
int main()
{
Application app;
return app.run();
}
AC自动机再试。
CODE:
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2010-6-12
DESCRIPTION:
UVa10679
*/
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
#include <string>
using std::string;
#include <list>
using std::list;
#include <string.h>
#define H(c) (((c)<=’z’&&(c)>=’a’)?((c)-‘a’):((c)-‘A’+’z’-‘a’+1))
#define NEXT_SIZE (‘z’-‘a’+1)+(‘Z’-‘A’+1)
#define NODE_SIZE 1000000
#define QUEUE_SIZE 1000000
#define CHECK_SIZE 1000000
#define NEW 1
#define DELETE 2
struct node
{
node* fail;
node* next[NEXT_SIZE];
bool end;
};
node* who[CHECK_SIZE];
node* get(int flag=0)
{
static node* pool;
static int top;
if (!flag)
{
memset(pool+top,0,sizeof(node));
return pool+top++;
}
else
{
switch (flag)
{
case NEW:
pool=new node[NODE_SIZE];
top=0;
break;
case DELETE:
delete[] pool;
break;
}
return 0;
}
}
void insert(node* const root,const char* str,int id)
{
node* p=root;
do
{
if (!p->next[H(*str)]) p->next[H(*str)]=get();
p=p->next[H(*str)];
}
while (*(++str));
who[id]=p;
}
void build_ac_automation(node* const root)
{
static node* q[QUEUE_SIZE];
node** head;
node** tail;
*(head=tail=q)=root;
while (head<=tail)
{
node* qh=*(head++);
for (char i=’a’;i<=’z’;i++)
if (qh->next[H(i)])
{
if (qh==root) qh->next[H(i)]->fail=root;
else
{
node* p=qh->fail;
while (p)
{
if (p->next[H(i)])
{
qh->next[H(i)]->fail=p->next[H(i)];
break;
}
p=p->fail;
}
if (!p) qh->next[H(i)]->fail=root;
}
*(++tail)=qh->next[H(i)];
}
for (char i=’A’;i<=’Z’;i++)
if (qh->next[H(i)])
{
if (qh==root) qh->next[H(i)]->fail=root;
else
{
node* p=qh->fail;
while (p)
{
if (p->next[H(i)])
{
qh->next[H(i)]->fail=p->next[H(i)];
break;
}
p=p->fail;
}
if (!p) qh->next[H(i)]->fail=root;
}
*(++tail)=qh->next[H(i)];
}
}
}
void query(node* const root,const char* str)
{
int result=0;
node* p=root;
do
{
while (!p->next[H(*str)]&&p!=root) p=p->fail;
p=p->next[H(*str)];
if (!p) p=root;
node* t=p;
while (t!=root)
{
t->end=true;
t=t->fail;
}
}
while (*(++str));
}
class Application
{
int CASE,N;
string keywords;
string description;
public:
Application()
{
std::ios::sync_with_stdio(false);
cin>>CASE;
}
int run()
{
for (int i=0;i<CASE;i++)
{
cin>>description;
cin>>N;
get(NEW);
node* root=get();
for (int j=1;j<=N;j++)
{
cin>>keywords;
insert(root,keywords.c_str(),j);
}
build_ac_automation(root);
query(root,description.c_str());
for (int j=1;j<=N;j++)
cout<<char(who[j]->end?’y’:’n’)<<endl;
get(DELETE);
}
return 0;
}
};
int main()
{
Application app;
return app.run();
}
AC自动机初试。
CODE:
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2010-6-12
DESCRIPTION:
http://acm.hdu.edu.cn/showproblem.php?pid=2222
*/
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
#include <string>
using std::string;
#include <string.h>
#define H(c) ((c)-‘a’)
#define NEXT_SIZE (‘z’-‘a’+1)
#define NODE_SIZE 500000
#define QUEUE_SIZE 500000
#define NEW 1
#define DELETE 2
struct node
{
node* fail;
node* next[NEXT_SIZE];
int count;
};
node* get(int flag=0)
{
static node* pool;
static int top;
if (!flag)
{
memset(pool+top,0,sizeof(node));
return pool+top++;
}
else
{
switch (flag)
{
case NEW:
pool=new node[NODE_SIZE];
top=0;
break;
case DELETE:
delete[] pool;
break;
}
return 0;
}
}
void insert(node* const root,const char* str)
{
node* p=root;
do
{
if (!p->next[H(*str)]) p->next[H(*str)]=get();
p=p->next[H(*str)];
}
while (*(++str));
p->count++;
}
void build_ac_automation(node* const root)
{
static node* q[QUEUE_SIZE];
node** head;
node** tail;
*(head=tail=q)=root;
while (head<=tail)
{
node* qh=*(head++);
for (int i=’a’;i<=’z’;i++)
if (qh->next[H(i)])
{
if (qh==root) qh->next[H(i)]->fail=root;
else
{
node* p=qh->fail;
while (p)
{
if (p->next[H(i)])
{
qh->next[H(i)]->fail=p->next[H(i)];
break;
}
p=p->fail;
}
if (!p) qh->next[H(i)]->fail=root;
}
*(++tail)=qh->next[H(i)];
}
}
}
int query(node* const root,const char* str)
{
int result=0;
node* p=root;
do
{
while (!p->next[H(*str)]&&p!=root) p=p->fail;
p=p->next[H(*str)];
if (!p) p=root;
node* t=p;
while (t!=root)
{
result+=t->count;
t->count=0;
t=t->fail;
}
}
while (*(++str));
return result;
}
class Application
{
int CASE,N;
string keywords;
string description;
public:
Application()
{
std::ios::sync_with_stdio(false);
cin>>CASE;
}
int run()
{
for (int i=0;i<CASE;i++)
{
get(NEW);
cin>>N;
node* root=get();
for (int j=0;j<N;j++)
{
cin>>keywords;
insert(root,keywords.c_str());
}
build_ac_automation(root);
cin>>description;
cout<<query(root,description.c_str())<<endl;
get(DELETE);
}
return 0;
}
};
int main()
{
Application app;
return app.run();
}
KMP练习，第一次写KMP。
CODE:
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2010-6-12
DESCRIPTION:
RQNOJ382
*/
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
#include <string>
using std::string;
#include <vector>
using std::vector;
class Application
{
string s1,s2;
public:
Application()
{
std::ios::sync_with_stdio(false);
cin>>s1>>s2;
}
int run()
{
vector<int> shift;
int i,j;
vector<int> pi(s1.length());
j=pi[0]=-1;
for (i=1;i<s1.length();i++)
{
while (j>=0&&s1[j+1]!=s1[i]) j=pi[j];
if (s1[j+1]==s1[i]) j++;
pi[i]=j;
}
j=-1;
for (i=0;i<s2.length();i++)
{
while (j>=0&&s1[j+1]!=s2[i]) j=pi[j];
if (s1[j+1]==s2[i]) j++;
if (j==s1.length()-1)
j=pi[j],shift.push_back(1+(i-s1.length()+1));
}
if (shift.size())
for (cout<<shift.size()<<endl,i=0;i<shift.size();i++)
cout<<shift[i]<<endl;
else cout<<“There must be something wrong.”<<endl;
return 0;
}
};
int main()
{
Application app;
return app.run();
}
首先，肯定最后要移到N所在的那一根杆上，然后参见URAL1054[Hanoi tower]。
CODE:
/*
AUTHOR:Su Jiao
DATE:2010-6-10
DESCRIPTION:
@NOI LINUX
CEOI2003 hanoi
*/
#include <stdio.h>
#include <algorithm>
using std::swap;
class Application
{
FILE* in;
FILE* out;
static const int STACK=3;
static const int MAXN=100000;
static const int MOD=1000000;
int N;
int top[STACK];
int stack[STACK][MAXN];
public:
Application(const char* input=0,const char* output=0)
:in(input?fopen(input,“r”):stdin),
out(output?fopen(output,“w”):stdout)
{
fscanf(in,“%d”,&N);
for (int i=0;i<STACK;i++)
fscanf(in,“%d”,top+i);
for (int i=0;i<STACK;i++)
for (int j=0;j<top[i];j++)
fscanf(in,“%d”,stack[i]+j);
}
int run()
{
int pos[MAXN+1];
for (int i=0;i<STACK;i++)
for (int j=0;j<top[i];j++)
pos[stack[i][j]]=i;
int f[MAXN+1]={1};
for (int i=1;i<=N;i++)
f[i]=f[i-1]*2%MOD;
int put=pos[N]+1;
int step=0;
int A,B,C;
if (put==1) A=0,B=1,C=2;
if (put==2) A=1,B=0,C=2;
if (put==3) A=2,B=0,C=1;
for (int i=N;i>=1;i–)
if (pos[i]!=A)
{
step=(step+f[i-1])%MOD;
if (pos[i]==B) swap(A,C);
if (pos[i]==C) swap(A,B);
}
else swap(B,C);
fprintf(out,“%d\n%d\n”,put,step);
return 0;
}
};
int main()
{
Application app(“hanoi.in”,“hanoi.out”);
return app.run();
}