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

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考试可能会用到的数学思维题选讲-自学教程-自学笔记

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

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

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考试可能会用到的数学思维题选讲-自学教程-自学笔记

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

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

第二题:

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

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

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

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

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

这道题当初是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成功!

上一篇:zedboard如何从PL端控制DDR读写(一)


下一篇:SQL Server XML基础学习之<7>--XML modify() 方法对 XML 数据中插入、更新或删除