PJ考试可能会用到的数学思维题选讲
by Pleiades_Antares
是学弟学妹的讲义——然后一部分题目是我弄的一部分来源于洛谷用户@
普及组的一些数学思维题，所以可能有点菜咯别怪我
OI中的数学题——你会你就能做，不会做就是真的做不出来QAQ
鲁迅曾说：一入数学深似海，从此AC是路人。
一些会说到的题目：（都是洛谷编号）
这些题目全都是原来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 最大公约数和最小公倍数问题
为了搞明白这道题，
放四张有助于理解的最大公约数最小公倍数的图片。
//
// 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麦森数：
对数
标程：
#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你要是不会就找规律，数学么就是找规律再总结
那么这道题基本的思路做法是这个样子的：
——这道题的规律就是杨辉三角
第二题：
据某不知名人士透露洛谷有可能未来会撤下此题（为啥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成功！