思考时间,答案在下面(字体是白色的)。
设一根棍与平行线成角(逆时针旋转角),那么它与平行线相交的概率为
,然后答案就是
64匹马能否通过50场比赛比出任意两匹马之间的优劣(每场比赛至多8匹马参赛)
这是2009年清华大学自主招生数学试题(理综)。
思考时间,答案在下面(字体是白色的)。
这道题其实考的是归并排序。
首先将马分为8组,每组排一下序,就比了8场。
然后再将这8组合并为4组,两两合并。
比如A和B组合并:
选A组的前4名和4个B组的前4名,比一场,如果从A中的选出的第4名比B中选出的第4名排名高,那么在A中的选出的第4名前和他自己一定是这些马中靠前的,于是把他们排到新的队中,其余马回到原来的位置;否则,同理分析。所以这样比一场可以确定至少4匹马在新的小组中的的位置。
接下来在剩下的马中继续这样做,直到所有马在新的小组中的位置都确定了。
由于每次都可以至少确定4匹马的位置,而且最后还剩8匹马时只需要比一次就可以确定8匹马的位置,所以两个8匹马的有序的小组合并为一个16匹马的有序小组只需要(16-8)/4+1=3次比赛。
所以8个8匹马的有序的小组合并为4个16匹马的有序小组需要4*3=12次比赛。
所以4个16匹马的有序的小组合并为2个32匹马的有序小组需要2*7=14次比赛。
所以2个32匹马的有序的小组合并为1个64匹马的有序小组需要1*15=15次比赛。
所以一共只需比49场就可以了。
请写出所有三个数均为质数,且公差为8的等差数列,并证明你的结论
这是2009年清华大学自主招生数学试题(理科)。
思考时间,答案在下面(字体是白色的)。
答案是3 11 19。
首先它是一个解,下面我们证明没有其它解。
设最小的一个数为X,那么数列为X,X+8,X+16。
然后
X mod 3 = X mod 3
X + 8 mod 3 = X+ 2 mod 3
X + 16 mod 3 =X + 1 mod 3
所以无论X为何值,这个数列中都有一个数是3的倍数,又它们都是质数,所以只可能是有一个数是3,那么显然这个问题解决了。
NOIP2009[Hankson的趣味题/son]
NOIP2010即将到来,这道题用来练练手感。
这道题的思路就是分解质因数。
首先,不难得到gcd(x/a1,a0/a1)=1以及gcd(b1/x,b1/b0)=1。
假设对于一个质因数y,a0含有a0c个y,a1含有a1c个y,b0含有b0c个y,b1含有b1c个y。
那么不难得到,如果a0c<a1c,那么就无解;如果a0c=a1c,那么x至少含有a1c个y;如果a0c>a1c,那么x只可能含有a1c个y。
同理,如果b1c<b0c,那么就无解;如果b1c=b0c,那么x至多含有b1c个y;如果b1c>b0c,那么x只可能含有b1c个y。
由此,可以求出对于每一个质数,x可能含有几个它,并求出一共有多少种选择方式。然后根据乘法原理,将每一个质数的选择方案数乘起来,就得到了答案。
CODE:
/*
AUTHOR: Su Jiao
DATE: 2010-10-14
DESCRIPTION:
$DESCRIPTION
*/
#include <stdio.h>
const int MAXSIZE=5000;
int prime_table[MAXSIZE];
int prime_table_size;
void initialize_prime_table()
{
prime_table_size=0;
prime_table[prime_table_size++]=2;
for (int i=3;prime_table_size<MAXSIZE;i++)
{
bool is_prime=true;
for (int j=0;j<prime_table_size;j++)
if (i%prime_table[j]==0)
{
is_prime=false;
break;
}
if (is_prime) prime_table[prime_table_size++]=i;
}
}
void calculate_one_step(int& a0,int& a1,int& b0,int& b1,int& result,int p)
{
int a0c=0,a1c=0,b0c=0,b1c=0;
while (a0%p==0) a0/=p,a0c++;
while (a1%p==0) a1/=p,a1c++;
while (b0%p==0) b0/=p,b0c++;
while (b1%p==0) b1/=p,b1c++;
if (a0c<a1c||b0c>b1c) result*=0;
else if (a0c==a1c&&b0c==b1c)
{
if (a1c<=b1c) result*=b1c-a1c+1;
else result*=0;
}
else if (a0c==a1c&&b0c<b1c)
{
if (a1c<=b1c) result*=1;
else result*=0;
}
else if (a0c>a1c&&b0c==b1c)
{
if (a1c<=b1c) result*=1;
else result*=0;
}
else //if (a0c>a1c&&b0c<b1c)
{
if (a1c==b1c) result*=1;
else result*=0;
}
}
int calculate(int a0,int a1,int b0,int b1)
{
//gcd(x/a1,a0/a1)=1
//gcd(b1/x,b1/b0)=1
if (a0%a1!=0||b1%b0!=0) return 0;
int result=1;
for (int i=0;i<prime_table_size;i++)
calculate_one_step(a0,a1,b0,b1,result,prime_table[i]);
if (a0!=1) calculate_one_step(a0,a1,b0,b1,result,a0);
else if (b1!=1&&b1!=a0) calculate_one_step(a0,a1,b0,b1,result,b1);
return result;
}
int main()
{
freopen(“son.in”,“r”,stdin);
freopen(“son.out”,“w”,stdout);
int n,a0,a1,b0,b1;
initialize_prime_table();
scanf(“%d”,&n);
for (int i=0;i<n;i++)
{
scanf(“%d%d%d%d”,&a0,&a1,&b0,&b1);
printf(“%d\n”,calculate(a0,a1,b0,b1));
}
return 0;
}
SGU107[987654321 problem]
先离线处理出在[0,10^9)内中所有平方末尾数为987654321的数,然后显然应该写成下面那样。
CODE:
/*
AUTHOR: Su Jiao
DATE: 2010-9-11
DESCRIPTION:
$DESCRIPTION
*/
#include <stdio.h>
int main()
{
/*
for (long long int i=0;i<1000000000;i++)
if (i*i%1000000000==987654321) printf(“%d\n”,int(i));
output:
111111111
119357639
380642361
388888889
611111111
619357639
880642361
888888889
*/
int n;
scanf(“%d”,&n);
if (n<=8) printf(“%d\n”,0);
else if (n==9) printf(“%d\n”,8);
else
{
printf(“%d”,72);
for (int i=10;i<n;i++) printf(“%d”,0);
printf(“\n”);
}
}
SGU106[The equation]
数学题。扩展欧几里得解模同余方程。
CO
/*
AUTHOR: Su Jiao
DATE: 2010-8-26
DESCRIPTION:
$DESCRIPTION
*/
#include <iostream>
#include <math.h>
using namespace std;
#define lli long long int
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define ceil_div(a,b) ceil(double(a)/double(b))
#define floor_div(a,b) floor(double(a)/double(b))
lli gcd(lli a,lli b,lli& x,lli& y)
{
//ax+by=gcd(a,b)
if (b==0)
{
x=1,y=0;
return a;
}
else
{
lli g=gcd(b,a%b,y,x);
//b*y+a%b*x=gcd(b,a%b)=gcd(a,b)
// b*y+a%b*x
//=b*y+(a-a/b*b)*x
//=b*y-a/b*b*x+a*x
//=a*x+b*(y-a/b*x)
y-=a/b*x;
return g;
}
}
lli get_answer(lli a,lli b,lli c,lli x1,lli x2,lli y1,lli y2)
{
//ax+by+c=0
if (!(x1<=x2&&y1<=y2)) return 0;
else if (a==0&&b==0)
return (c==0)*(x2-x1+1)*(y2-y1+1);
else if (a==0)
{
lli y=-c/b;
return ((b*y+c==0)&&(y1<=y&&y<=y2))*(x2-x1+1);
}
else if (b==0)
{
lli x=-c/a;
return ((a*x+c==0)&&(x1<=x&&x<=x2))*(y2-y1+1);
}
else
{
//a*x = c (mod b)
lli x,y,g;
g=gcd(a,b,x,y);//ax+by=g
if (c%g==0)
{
a/=g,b/=g,c/=g;//ax+by=1
x*=-c,y*=-c;//ax*(-c)+by*(-c)=-c
//set of root = {(x+b*k,y-a*k)}
lli rxa,rxb;
if (b>0) rxa=ceil_div(x1-x,b),rxb=floor_div(x2-x,b);
else rxa=ceil_div(x2-x,b),rxb=floor_div(x1-x,b);
lli rya,ryb;
if (a<0) rya=ceil_div(y-y1,a),ryb=floor_div(y-y2,a);
else rya=ceil_div(y-y2,a),ryb=floor_div(y-y1,a);
lli ra,rb;
ra=max(rxa,rya);
rb=min(rxb,ryb);
if (ra<=rb) return (rb-ra+1);
else return 0;
}
else return 0;
}
}
int main()
{
lli a,b,c,x1,x2,y1,y2;
cin>>a>>b>>c>>x1>>x2>>y1>>y2;
cout<<get_answer(a,b,c,x1,x2,y1,y2)<<endl;
}
SGU105[Div 3]
数学题。一个数能被3整除,当且仅当它的各位数的和能被3整除。
CODE:
/*
AUTHOR: Su Jiao
DATE: 2010-8-26
DESCRIPTION:
$DESCRIPTION
*/
#include <stdio.h>
int main()
{
int N;
scanf(“%d”,&N);
printf(“%d\n”,N/3*2+(N%3==2));
}
SGU104[Little shop of flowers]
动态规划经典题目,据说是IOI上出现的首个动态规划题目。
CODE:
/*
AUTHOR: Su Jiao
DATE: 2010-8-24
DESCRIPTION:
$DESCRIPTION
*/
#include <iostream>
using namespace std;
const int MAXF=100+2,MAXV=100+2;
const int oo=19930309;
int F,V;
int A[MAXF][MAXV];
int f[MAXF][MAXV];
void print(int v,int i)
{
if (i)
{
int j;
for (j=1;j<=V;j++)
if (f[i][j]==v)
break;
print(v-A[i][j],i-1);
cout<<j<<char(i==F?’\n’:’ ‘);
}
}
int main()
{
cin>>F>>V;
for (int i=1;i<=F;i++)
for (int j=1;j<=V;j++)
cin>>A[i][j];
#define max(a,b) ((a)>(b)?(a):(b))
for (int i=1;i<=F;i++)
for (int j=0;j<=V;j++)
{
f[i][j]=-oo;
for (int k=0;k<j;k++)
f[i][j]=max(f[i][j],f[i-1][k]+A[i][j]);
}
int answer=-oo;
for (int i=0;i<=V;i++)
answer=max(answer,f[F][i]);
cout<<answer<<endl;
print(answer,F);
}
SGU103[Traffic Lights]
最短路。
CODE:
/*
AUTHOR: Su Jiao
DATE: 2010-8-24
DESCRIPTION:
$DESCRIPTION
*/
#include <iostream>
using namespace std;
const int MAXE=14000*2;
const int MAXV=300+2;
typedef struct struct_edge* edge;
struct struct_edge{int v,d;edge n;};
struct node
{
int c,r,t[2];
int color(int timeline)
{
int alpha=timeline%(t[0]+t[1]);
if (r<=alpha&&alpha<r+t[!c]) return !c;
else return c;
}
int remain(int timeline)
{
int alpha=timeline%(t[0]+t[1]);
if (alpha<r)
return r-alpha;
else if (alpha<r+t[!c])
return r+t[!c]-alpha;
else return t[0]+t[1]-alpha;
}
};
struct_edge pool[MAXE];
edge top=pool;
int S,T;
int V,E;
node vertex[MAXV];
edge adj[MAXV];
const int oo=19930309;
int d[MAXV];
int visited[MAXV];
int pre[MAXV];
void add_edge(int u,int v,int d)
{
top->v=v,top->d=d,top->n=adj[u],adj[u]=top++;
top->v=u,top->d=d,top->n=adj[v],adj[v]=top++;
}
int min(int a,int b)
{
return a<b?a:b;
}
int wait(int u,int v,int now=0,int change_times=0)
{
if (change_times>3) return oo;
if (vertex[u].color(now)==vertex[v].color(now)) return now;
else
{
int wt=wait(u,v,now+min(vertex[u].remain(now),vertex[v].remain(now)),change_times+1);
if (wt==oo) return oo;
else return wt;
}
}
void dijkstra()
{
for (int u=1;u<=V;u++)
d[u]=oo;
d[S]=0;
for (int i=1;i<=V;i++)
{
int u,du=oo;
for (int tu=1;tu<=V;tu++)
if (!visited[tu]&&d[tu]<du)
du=d[u=tu];
visited[u]=true;
for (edge i=adj[u];i;i=i->n)
if (!visited[i->v])
{
int tdv=wait(u,i->v,d[u])+i->d;
if (d[i->v]>tdv)
d[i->v]=tdv,
pre[i->v]=u;
}
}
}
void print(int u)
{
if (u!=S) print(pre[u]);
cout<<u<<char(u==T?’\n’:’ ‘);
}
int main()
{
ios::sync_with_stdio(false);
cin>>S>>T;
cin>>V>>E;
for (int i=1;i<=V;i++)
{
char color;
cin>>color>>vertex[i].r>>vertex[i].t[0]>>vertex[i].t[1];
vertex[i].c=(color==’P’);
}
for (int i=0;i<E;i++)
{
int a,b,d;
cin>>a>>b>>d;
add_edge(a,b,d);
}
dijkstra();
if (d[T]==oo) cout<<0<<endl;
else
{
cout<<d[T]<<endl;
print(T);
}
}
SGU102[Coprimes]
求最大公约数。
CODE:
/*
AUTHOR: Su Jiao
DATE: 2010-8-24
DESCRIPTION:
$DESCRIPTION
*/
#include <iostream>
using namespace std;
int main()
{
int N,answer=0;
cin>>N;
for (int i=1;i<=N;i++)
{
int a=N,b=i,t;
while (b) t=a,a=b,b=t%b;
if (a==1) answer++;
}
cout<<answer<<endl;
}