PJ考试可能会用到的数学思维题选讲

by Pleiades_Antares

是学弟学妹的讲义——然后一部分题目是我弄的一部分来源于洛谷用户@

普及组的一些数学思维题，所以可能有点菜咯别怪我

OI中的数学题——你会你就能做，不会做就是真的做不出来QAQ

鲁迅曾说：一入数学深似海，从此AC是路人。

PJ考试可能会用到的数学思维题选讲-自学教程-自学笔记

一些会说到的题目：（都是洛谷编号）

这些题目全都是原来NOIP考过的真题喔

1010

1014

1029

1035

1045

1075

1012

1351

2119

ok咱们开始说

第一题，洛谷P1010幂次方

这道题很坑很毒瘤qwq

好了不废话了代码扔上来

#include <cstdio>

int po[]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};

void put(int n)

{

	if(n==0) {printf("0");return;}

	int i,flag=0;

	for(i=15;i>=0;i--)

		if(n>=po[i])

		{

			n-=po[i];

			if(flag==0) flag=1;

			else printf("+");

			if(i==1) printf("2");

			else

			{

				printf("2(");

				put(i);

				printf(")");

			}

		}

}

int main(void)

{

	int n;

	scanf("%d",&n);

	put(n);

	return 0;

}

第二题，P1014 Cantor表

//正解

#include <cstdio>

//ord:N在自己的层里的那个序号

int main(){

    int N,lin,cnt=0,ord;

    scanf("%d",&N);

    for(lin=1;cnt<N;lin++)

        cnt+=lin;

    lin--;cnt-=lin;

    ord=N-cnt;

    if(lin%2==0)

        printf("%d/%d",ord,lin-ord+1);

    else

        printf("%d/%d",lin-ord+1,ord);

    return 0;

}

//按层编号

第三题，P1029 最大公约数和最小公倍数问题

为了搞明白这道题，

放四张有助于理解的最大公约数最小公倍数的图片。

PJ考试可能会用到的数学思维题选讲-自学教程-自学笔记

//

//  1029.cpp

//  mars2333335

//

//

//  Copyright © 2018年 Pleiades_Antares. All rights reserved.

//

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

int x[1005],y[1005];

void factor(int n,int *p){

    int  i,sz=sqrt(n)+2;//+2是防错,可以删掉

    for(i=2;i<=sz;i++){

        while(n%i==0) {

            n/=i;

            p[i]++;

        }

    }

    if (n!=1) p[n]++;

}

int main(){

    int i,X,Y;

    long long ans=1;

    scanf("%d%d",&X,&Y);

    factor(X,x);

    factor(Y,y);

    for(i=2;i<=1000;i++){

        if (x[i]<y[i]) ans*=2;

        if (x[i]>y[i]) ans=0;

        if (x[i]==y[i]) ans=ans;

    }

    printf("%lld\n",ans);

    return 0;

}

//唯一分解定理

//当且仅当a整除

//里面的bug实际上非常严重，只是因为题目数据太水所以很容易就能通过。

//请在课后找到严重的bug，留作课后作业

第四题，P1035级数求和

代码：

#include <cstdio>

int main(void)

{

	double k,s=0;

	int n;

	scanf("%lf",&k);

	for(n=1;s<=k;n++)

		s+=1/double(n);

	printf("%d\n",n-1); 

	return 0;

}

第五题，P1045麦森数

关于P1045麦森数：

对数

PJ考试可能会用到的数学思维题选讲-自学教程-自学笔记

标程：

#include <cstdio>

#include <cstring>

#include <cmath>

struct bignum

{

	int w[1200];

	friend bignum operator * (bignum a,bignum b)

	{

		bignum ans;

		int i,j;

		for(i=0;i<500;i++)

			for(j=0;j<500;j++)

				ans.w[i+j]+=a.w[i]*b.w[j];

		for(i=0;i<500;i++)

			ans.w[i+1]+=ans.w[i]/10,ans.w[i]%=10;

		for(;i<1010;i++) ans.w[i]=0;

		return ans;

	}

	void minus()

	{

		int i;

		w[0]--;		//ans.w[0]= 2 4 6 8

	}

	void out()

	{

		int i,cnt=0;

		for(i=499;i>=0;i--)

		{

			printf("%d",w[i]);

			cnt++;

			if(cnt==50) cnt=0,puts("");

		}

		puts("");

	}

	bignum(int x=0)

	{

		memset(w,0,sizeof(w));

		w[0]=x;

	}

};

bignum one(1),two(2);

bignum Pow(bignum x,int p)

{

	if(p==0) return one;

	if(p==1) return x;

	bignum a=Pow(x,p/2);

	if(p%2==0) return a*a;

	return a*a*x;

}

int main(void)

{

	int p;

	scanf("%d",&p);

	printf("%d\n",int(double(p)*log10(2)+1)); 

	bignum ans=Pow(two,p);

	ans.minus();

	ans.out();

	return 0;

}

第六题，P1075质因数分解

这道题实在是太水了·······入门的应该都会（不会找你老师去这是应该教会的哇）

//

//  1075.cpp

//  mars2333335

//

//  Created by demi on 2018/10/2.

//  Copyright © 2018年 demi. All rights reserved.

//

#include <stdio.h>

#include<iostream>

using namespace std;

int main(){

    int n;

    cin>>n;

    for(int i=2;i*i<=n;i++){

        if (n%i==0){ cout<<n/i<<endl; break;}

    }

    return 0;

}

第七题，P1012拼数

这道题难点就是如何写cmp函数（判定哪个字符串大）

稍微尝试一下可以发现：

如果字符串a+字符串b（这个代表a后面跟着b）大于字符串b在前面+字符串a在后面，那么就返回1.

我们把这一段话翻译成程序语言，就是下面这个样子的：

bool cmp(string a,string b){

    return a+b>b+a;

}

这就是整个程序的精华之所在。

理解了以后就非常非常简单了。

附上标程

//

//  1012.cpp

//  mars2333335

//

//

//  Copyright © 2018年 Pleiades_Antares. All rights reserved.

//

#include <stdio.h>

//y用sort

//本质是贪心

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

bool cmp(string a,string b){

    return a+b>b+a;

}

int n;

string s[30];

int main(){

    cin>>n;

    for(int i=0;i<n;i++){

        cin>>s[i];

    }

    sort(s,s+n,cmp);

    for(int i=0;i<n;i++){

        cout<<s[i];

    }

    cout<<endl;

    return 0;

}

第八题，P1351联合权值

这道题是一道需要有图论基础的题目，要是没学过图论就不需要会了，考虑到NOIP考图论的几率不大且没有太大影响，这里仅放上标程，根据是否需要考虑是否阅读。

点击这里有很多很多大佬写的题解，包含详细解释，可供参考学习。

#include<cstdio>

#include<iostream>

using namespace std;

const int N=2e5+5,mo=10007;

struct cs{int to,nxt;}a[N*2];

int head[N],ll,v[N];

int n,ans,x,y,maxans;

void init(int x,int y){

    a[++ll].to=y;

    a[ll].nxt=head[x];

    head[x]=ll;

}

void work(int x){

    int sum=0,ma=0,m=0;

    for(int k=head[x];k;k=a[k].nxt){

        if(v[a[k].to]>ma){m=ma;    ma=v[a[k].to];}else

        if(v[a[k].to]>m)m=v[a[k].to];

        ans=(ans+sum*v[a[k].to])%mo;

        sum=(sum+v[a[k].to])%mo;

    }

    maxans=max(maxans,ma*m);

}

int main()

{

    scanf("%d",&n);

    for(int i=1;i<n;i++){

        scanf("%d%d",&x,&y);

        init(x,y); init(y,x);

    }

    for(int i=1;i<=n;i++)scanf("%d",&v[i]);

    for(int i=1;i<=n;i++)work(i);

    printf("%d %d",maxans,(ans*2)%mo);

}

（本程序源自这位大佬）

最后是P2119魔法阵这道题。

#include <cstdio>

#include<iostream>

using namespace std;

//可以说是本次最难的一道题了

int w[15005],A[40005],B[40005],C[40005],D[40005];

int x[40005];

int main(){

    int dis,su=0;

    int a,b,c,d,n,m,i;

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++){

        scanf("%d",&x[i]);

        w[x[i]]++;

    }

    for(dis=1;(9*dis+2)<=n;dis++,su=0){

        for(a=n-(9*dis+1);a>=1;a--){

            b=a+2*dis;

            c=b+6*dis+1;

            d=c+dis;

            su+=w[c]*w[d];

            A[a]+=su*w[b];

            B[b]+=su*w[a];

        }

    }

    for(dis=1;(9*dis+2)<=n;dis++,su=0){

        for(d=9*dis+2;d<=n;d++){

            c=d-dis;

            b=c-1-6*dis;

            a=b-2*dis;

            su+=w[a]*w[b];

            C[c]+=su*w[d];

            D[d]+=su*w[c];

        }

    }

    for(i=1;i<=m;i++){

        cout<<A[x[i]]<<" "<<B[x[i]]<<" "<<C[x[i]]<<" "<<D[x[i]]<<endl;

    }

    return 0;

}

下面我们看几道趣题放松下，讲下思路，当然如果兴致到了也会讲代码2333

这些趣题的话emm你要是不会就找规律，数学么就是找规律再总结

PJ考试可能会用到的数学思维题选讲-自学教程-自学笔记

那么这道题基本的思路做法是这个样子的：

——这道题的规律就是杨辉三角

第二题：

PJ考试可能会用到的数学思维题选讲-自学教程-自学笔记

据某不知名人士透露洛谷有可能未来会撤下此题（为啥orz）

所以保险起见截个屏留念⬇️

这道题当初是D1T1，没过很有可能影响选手心态qwq很坑爹

既然题目这样讲，那么一定存在n，现在我们来写个暴力：

//一道让人不爽的苟题

#include <cstdio>

int flag[10000000];

int main(){

    int a,b,x,y,i;

    scanf("%d%d",&a,&b);

    for(x=0;x<=1000;x++){

        for(y=0;y<=1000;y++){

            flag[a*x+b*y]=1;

        }

    }

    for(i=10000;i>=0;i--)//直觉不会超过10000

        if (flag[i]==0) break;

    printf("%d\n",i);

    return 0;

}

//(3,7):11 11+1=12 = 2*6  (3-1)*(7-1)

//(3,5):7  7+1=8   = 2*4  (3-1)*(5-1)

//(4,5):11 11+1=12 = 3*4  (4-1)*(5-1)

//一旦加了1问题就迎刃而解

//怎么想到加上1的呢？

//这是联赛的day1第1题，肯定很容易，那么基本上可能是和乘法有关

//11，7都是质数不方便分解，那么加上一以后就可以拆了

//某鬼畜同学此时给出了百度的证明：https://zhidao.baidu.com/question/305250238.html

//这道题其实不是很适合emmmm很呕

//批判一下233333

//考场上遇到这种题如何去处理？这是很重要的！

普及组考试策略：

近年题风分析

2015年

T1:模拟

T2:模拟

T3:计数，前缀和优化

T4:贪心

2016年

T1:模拟

T2:模拟

T3:模拟

T4:计数，前缀和优化

2017年

T1:模拟

T2:模拟

T3:图论（数据水，各种乱搞都能过）

T4:二分，DP检验，单调队列优化

总结起来，题风比较稳定

近几年题目的难度变化不大。

考察范围也不大。

非模拟知识点：DP，数学，图论。

整个noip在变难，TG变得很快，PJ变得很慢基本上很稳定

然后平常数学题的画风

应用的数学知识很简单

一般情况下，初中数学知识+夏令营教的内容足以应付

一般情况下，普及组的数学题只会考察一个数学知识

一句话：出题人不为难选手

如何对付数学题？

遇到的时候——别慌

——上个厕所冷静一下，清空自己的思路，重新想题目（省选大佬在对待OI时应如何应对自如？厕所冷静法）

数学是工具

一般来说，普及组不会考察纯数学知识。

在这种情况下，数学不是目的而是工具。

我们是暴力做法遇到了麻烦，然后利用数学来进行优化。

先想一想暴力做法，然后想想暴力做法的瓶颈，再进一步考虑。

推式子&&找规律

平心静气推式子。推不下来式子赶紧开始找规律，时间这么紧不要把大量时间浪费在死推式子上。

普及组不会为难你！

别慌调整好心态你能AK全场的！！

记住：每128MB可以开3200万个int。

祝各位NOIP成功！

秒客网