题单【模拟与高精度】

发布于：2025-08-03 ⋅ 阅读:(9) ⋅ 点赞:(0)

P1042 [NOIP 2003 普及组] 乒乓球

P1042 [NOIP 2003 普及组] 乒乓球 - 洛谷

#include<bits/stdc++.h>
using namespace std;

char C;
string S;
int n,A,B;

void Work(int Lim)
{
	for(char i:S)
	{
		if(i=='W')	A++;
		if(i=='L')	B++;

		if(max(A,B)>=Lim && abs(A-B)>=2)
		{
			cout<<A<<":"<<B<<endl;
			A=0,B=0;
		}
	}
	printf("%d:%d\n\n",A,B);
	A=B=0;	
}

int main()
{
	while(cin>>C)
	{
		if(C=='E')	break;
		S+=C;
	}
	Work(11),Work(21);
	return 0;
}

P2670 [NOIP 2015 普及组] 扫雷游戏

P2670 [NOIP 2015 普及组] 扫雷游戏 - 洛谷

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n,m;
	cin>>n>>m;
	char a[110][110];
	int b[110][110]={0};
	int sum[110][110]={0};
	
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>a[i][j];
			if(a[i][j]=='*')
			{
				b[i][j]=1;
			}
		}
	}
	
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if (a[i][j]=='*')
			{
				continue;
			}
			
			for(int p=i-1;p<=i+1;p++)
			{
				for(int q=j-1;q<=j+1;q++)
				{
					if(p>=0 && p<n && q>=0 && q<m)
					{
						sum[i][j]+=b[p][q];
					}
				}
			}
		}
	}
	
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(b[i][j]==1)
			{
				cout<<'*';
			}
			else
			{
				cout<<sum[i][j];
			}
		}
		cout<<endl;
	}
	return 0;
}

P1563 [NOIP 2016 提高组] 玩具谜题

P1563 [NOIP 2016 提高组] 玩具谜题 - 洛谷

设定------>顺时针减，逆时针加

#include<bits/stdc++.h>
using namespace std;
struct People
{
	string name;
	int toward;
}people[100005];

int main()
{
	int n,m;
	cin>>n>>m;
	int cur=0;
	for(int i=0;i<n;i++)
	{
		cin>>people[i].toward>>people[i].name;
	}
	
	int a=0,s=0;
	for(int i=0;i<m;i++)
	{
		cin>>a>>s;
		if(people[cur].toward==a)
// 两个相等的时候，即面向内部的左边和面向外部的右边都是顺时针方向，此时是减，所以要乘 -1
		{
			s*=-1;
		}
		cur=(cur+n+s)%n;
	}
	cout<<people[cur].name;
	return 0;
}

P1601 A+B Problem（高精）

P1601 A+B Problem（高精） - 洛谷

#include<bits/stdc++.h>
using namespace std;

int main()
{
	string x,y;
	cin>>x>>y;
	int num1=x.size();
	int num2=y.size();
	int a[501]={0};
	int b[501]={0};
	
	//低位数在前
	for(int i=0;i<num1;i++)
	{
		a[i]=x[num1-1-i]-'0';
	}
	
	for(int i=0;i<num2;i++)
	{
		b[i]=y[num2-1-i]-'0';
	}
	
	int maxn=max(num1,num2);
	int c[1002]={0};
	
	for(int i=0;i<maxn;i++)
	{
		c[i]=a[i]+b[i];
	}
	
	//处理进位
	for(int i=0;i<maxn+2;i++)
	{
		if(c[i]>9)
		{
			c[i+1]+=c[i]/10;
			c[i]%=10;
		}
	}

	int num=maxn+1;
	
	//看有没有进位，使结果多出了一位，没有的话就减掉不考虑
	while(num>0 && c[num]==0)
	{
		num--;
	}
	
	if(c[0]==0 && num==0)
	{
		cout<<0;
	}
	else
	{
		for(int i=num;i>=0;i--)
		{
			cout<<c[i];
		}
	}
	return 0;
}

P1303 A*B Problem

P1303 A*B Problem - 洛谷

#include<bits/stdc++.h>
using namespace std;

int main()
{
	string x,y;
	cin>>x>>y;
	int num1=x.size();
	int num2=y.size();
	int a[501]={0};
	int b[501]={0};
	
	//低位数在前
	for(int i=0;i<num1;i++)
	{
		a[i]=x[num1-1-i]-'0';
	}
	
	for(int i=0;i<num2;i++)
	{
		b[i]=y[num2-1-i]-'0';
	}
	
	int maxn=max(num1,num2);
	int c[1002]={0};
	
	for(int i=0;i<maxn;i++)
	{
		c[i]=a[i]+b[i];
	}
	
	//处理进位
	for(int i=0;i<maxn+2;i++)
	{
		if(c[i]>9)
		{
			c[i+1]+=c[i]/10;
			c[i]%=10;
		}
	}

	int num=maxn+1;
	
	//看有没有进位，使结果多出了一位，没有的话就减掉不考虑
	while(num>0 && c[num]==0)
	{
		num--;
	}
	
	if(c[0]==0 && num==0)
	{
		cout<<0;
	}
	else
	{
		for(int i=num;i>=0;i--)
		{
			cout<<c[i];
		}
	}
	return 0;
}

P1009 [NOIP 1998 普及组] 阶乘之和

P1009 [NOIP 1998 普及组] 阶乘之和 - 洛谷

#include<iostream>
#include<cstdio>
using namespace std;
int n,a[101]={0},s[101]={0};
void do_jiecheng(int x)
{
	int g=0;
	for(int i=100;i>=0;i--)
	//从末尾开始存，a[100]存的是个位数
	{
		a[i]=a[i]*x+g;
		g=a[i]/10;
		a[i]=a[i]%10;
	}
}
void jiecheng_add()
{
	int g=0;
	for(int i=100;i>=0;i--)
	{
		s[i]=s[i]+a[i]+g;
		g=s[i]/10;
		s[i]=s[i]%10;
	}
}
void output()
{
	int w;
	for(int i=0;i<=100;i++)
	{
		if(s[i]!=0)
		{
			w=i;
			break;
		}
	}
	for(int i=w;i<=100;i++)
	   printf("%d",s[i]);
}

int main()
{
	scanf("%d",&n);
	s[100]=a[100]=1;
	for(int i=2;i<=n;i++)
	{
		do_jiecheng(i);
		jiecheng_add();
	}
	output();
	return 0;
}

P4924 [1007] 魔法少女小Scarlet

P4924 [1007] 魔法少女小Scarlet - 洛谷

#include<bits/stdc++.h>
using namespace std;

int n,m;
int x,y,r,z;
int a[505][505]={0};
int b[505][505]={0};

int main()
{
	cin>>n>>m;
	int num=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			a[i][j]=num;
			num++;
		}
	}							//按顺序输入数字
	
	for(int i=0;i<m;i++)
	{
		cin>>x>>y>>r>>z;
		int len=2*r+1;
		if(z==0)
		{
			for(int p=x-r;p<=x+r;p++)
			{
				for(int j=y-r;j<=y+r;j++)
				{
					b[x-y+j][x+y-p] = a[p][j];
				}
			}
		}
		else if(z==1)
		{
			for(int p=x-r;p<=x+r;p++)
			{
				for(int j=y-r;j<=y+r;j++)
				{
					b[x+y-j][y-x+p] = a[p][j];
				}
			}
		}
		
		for(int p=x-r;p<=x+r;p++)
		{
			for(int j=y-r;j<=y+r;j++)
			{
				a[p][j]=b[p][j];
				b[p][j]=0;
			}
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cout<<a[i][j]<<" ";
		}
		cout<<endl;
	}
	
	return 0;
}

P1328 [NOIP 2014 提高组] 生活大爆炸版石头剪刀布

P1328 [NOIP 2014 提高组] 生活大爆炸版石头剪刀布 - 洛谷

#include<bits/stdc++.h>
using namespace std;

int N;                  //猜拳次数
int N_A;                //A的猜拳周期长度
int N_B;                //B的猜拳周期长度
int circle_A[205];      //A的猜拳周期
int circle_B[205];      //B的猜拳周期
int score_A = 0;		//A的得分
int score_B = 0;		//B的得分
int game[5][5] =        //游戏的结果情况，1表示A赢，-1表示A输，0表示平
{
	{0, -1, 1, 1, -1},
	{1, 0, -1, 1, -1},
	{-1, 1, 0, -1, 1},
	{-1, -1, 1, 0, 1},
	{1, 1, -1, -1, 0}
};

int main()
{
	cin >> N >> N_A >> N_B;

	for(int i = 0; i < N_A; i++)
	{
		cin >> circle_A[i];
	}

	for(int i = 0; i < N_B; i++)
	{
		cin >> circle_B[i];
	}

	int i = 0;          //遍历A的猜拳周期
	int j = 0;          //遍历B的猜拳周期

	while(N--)
	{
		if(i >= N_A)
		{
            i = 0;
		}
		if(j >= N_B)
		{
            j = 0;
		}

		//比较结果
		int result = game[circle_A[i]][circle_B[j]];

		if(result == 1)
		{
			score_A++;
		}
		else if(result == -1)
		{
			score_B++;
		}

		i++;
		j++;
	}

	cout << score_A << " " << score_B;	
	return 0;
}

P1518 [USACO2.4] 两只塔姆沃斯牛 The Tamworth Two

P1518 [USACO2.4] 两只塔姆沃斯牛 The Tamworth Two - 洛谷

#include<bits/stdc++.h>
using namespace std;

int main()
{
	char a[15][15];		//地图
	int cx,cy,fx,fy;	//坐标

	for(int i=0;i<10;i++)
	{
		for(int j=0;j<10;j++)
		{
			cin>>a[i][j];
			if(a[i][j]=='C')
			{
				cx=i;
				cy=j;
			}
			if(a[i][j]=='F')
			{
				fx=i;
				fy=j;
			}
		}
	}
	
	int flagf=1,flagc=1;	//flag=1--->向上走；flag=2--->向右走；flag=3--->向下走；flag=4--->向左走
	int cnt=0;
	
	while(!(cx == fx && cy == fy))
	{
		if(flagc==1)
		{
			if(cx-1<0 || a[cx-1][cy]=='*')	//向上走遇到障碍或者边界
			{
				flagc=2;
			}
			else
			{
				cx-=1;
			}
		}
		else if(flagc==2)
		{
			if(cy+1>=10 || a[cx][cy+1]=='*')	//向右走遇到障碍或者边界
			{
				flagc=3;
			}
			else
			{
				cy+=1;
			}
		}
		else if(flagc==3)
		{
			if(cx+1>=10 || a[cx+1][cy]=='*')	//向下走遇到障碍或者边界
			{
				flagc=4;
			}
			else
			{
				cx+=1;
			}
		}
		else if(flagc==4)
		{
			if(cy-1<0 || a[cx][cy-1]=='*')	//向左走遇到障碍或者边界
			{
				flagc=1;
			}
			else
			{
				cy-=1;
			}
		}
		
		
		if(flagf==1)
		{
			if(fx-1<0 || a[fx-1][fy]=='*')
			{
				flagf=2;
			}
			else
			{
				fx-=1;
			}
		}
		else if(flagf==2)
		{
			if(fy+1>=10 || a[fx][fy+1]=='*')
			{
				flagf=3;
			}
			else
			{
				fy+=1;
			}
		}
		else if(flagf==3)
		{
			if(fx+1>=10 || a[fx+1][fy]=='*')
			{
				flagf=4;
			}
			else
			{
				fx+=1;
			}
		}
		else if(flagf==4)
		{
			if(fy-1<0 || a[fx][fy-1]=='*')
			{
				flagf=1;
			}
			else
			{
				fy-=1;
			}
		}
		
		cnt+=1;
		
		if(cnt>=100000)
		{
			cout<<0<<endl;
			return 0;
		}
	}
	
	
	cout<<cnt;
	return 0;
}

P1067 [NOIP 2009 普及组] 多项式输出

P1067 [NOIP 2009 普及组] 多项式输出 - 洛谷

情况分为以下几种：

  • 当前 i=n 并且输入的数是正数，输出 +。
  • 当前 i=0 并且输入的数是 −1，输出 -。
  • 输入的数的绝对值大于 1 或者当前 i=0，输出输入的数。
  • 当前 i>1，输出 x^ 和 i。
  • 当前 i=1，输出 x。
#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	cin>>n;
	for(int i=n;i>=0;i--)
	{
		int x;
		cin>>x;
		if(x)
		{
			if(i!=n && x>0)
				cout<<'+';
			if(i!=0 && x==-1)
				cout<<'-';
			if(abs(x)>1 || i==0)
				cout<<x;
			if(i>1)
				cout<<"x^"<<i;
			if(i==1)
				cout<<'x';
		}
	}
	return 0;
}

P1065 [NOIP 2006 提高组] 作业调度方案

P1065 [NOIP 2006 提高组] 作业调度方案 - 洛谷

#include <iostream>
#define maxn 50
using namespace std;

int n,m;
int ans = 0;

// 给定的安排顺序
int worklist[maxn * maxn];

// 每个工件的每个工序所使用的机器号
int worknumber[maxn][maxn];

// 每个工件的每个工序的加工时间
int worktime[maxn][maxn];

// 表示当前取到工件的工序数
int cnt_now_work_step[maxn];

// 代表某个工件出现的最晚的时间（点）
int lasttime[maxn];

// 代表某一台机器在某一个时间（点）上是不是正在干活
// 时间轴要开大一点，不然样例通过不了
bool timeline[maxn * maxn][maxn * maxn * maxn];

// 检查一个机器是否在干活
bool check_in_line(int begin_time_point,int end_time_length,int workid)
{
    for (int time = begin_time_point; time <= end_time_length;time++)
        if (timeline[workid][time])
            return false;			// 在干活
    return true;    				// 不在干活
}

int main(){
    cin >> m >> n;
    
    for (int i=1;i<=n*m;i++)
        cin >> worklist[i];

    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            cin >> worknumber[i][j];

    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            cin >> worktime[i][j];

    for (int i=1;i<=n*m;i++)
	{
        int nowitem = worklist[i];		// 当前工件
        cnt_now_work_step[nowitem]++;	// 工序数
        
        // 记录当前工件在当前工序时位于哪一台机器
        int nownumber = worknumber[nowitem][cnt_now_work_step[nowitem]];
        
        // 做完这道工序应该花费的时间
		int costtime = worktime[nowitem][cnt_now_work_step[nowitem]];
        
		// lasttime[nowitem]+1便是我们扫描时间线的开端
		// 注意lasttime记录的是时间点
		// 这个for没有终止条件，因为时间轴可能会无穷远
        for (int time = lasttime[nowitem]+1;;time++)     			// 扫描时间轴
        {
            if (check_in_line(time,time+costtime-1,nownumber))		// 如果没有在干活
			{
                for (int marktime = time;marktime <= time+costtime-1;marktime++)
                {
                    timeline[nownumber][marktime] = true;			// 让这个机器干活
                }
                lasttime[nowitem] = time + costtime - 1;			// 更新下一轮的起始时间
                break;
            }
        }
    }

    for (int i=1;i<=n;i++)
    {
        ans = max(ans,lasttime[i]);
    }

    cout << ans << endl;

    return 0;
}

P1786 帮贡排序

P1786 帮贡排序 - 洛谷

【关键】怎么排序！！！

详见代码里的注释

【知识点】结构体；多级比较；排序

#include<bits/stdc++.h>
using namespace std;

string zhiwei[7]={"BangZhu","FuBangZhu","HuFa","ZhangLao","TangZhu","JingYing","BangZhong"};

struct BangPai
{
	string name;
	string position;
	int cost;
	int grade;
	int shunxu;
}BP[120];

// 比较函数1：帮贡降序 > 输入顺序升序
bool cmp_1(BangPai a, BangPai b)
{
    if (a.cost != b.cost) 
        return a.cost > b.cost;  		// 贡献值降序
    return a.shunxu < b.shunxu;    		// 输入顺序升序
}

// 比较函数2：职位 > 等级 > 输入顺序
bool cmp_2(BangPai a, BangPai b)
{
	// 获取职位优先级（数值越小职位越高）
    int priority_a = -1, priority_b = -1;
    for (int i = 0; i < 7; i++)
	{
        if (zhiwei[i] == a.position)
        {
			priority_a = i;
		}
        if (zhiwei[i] == b.position)
        {
        	priority_b = i;
		}
    }

    // 比较优先级
    if (priority_a != priority_b) 
        return priority_a < priority_b;

    // 比较等级
    if (a.grade != b.grade) 
        return a.grade > b.grade;

    // 比较输入顺序
    return a.shunxu < b.shunxu;
}

int main()
{
	int n;
	cin>>n;

	int num=0;
	
	for(int i=0;i<n;i++)
	{
		cin>>BP[i].name>>BP[i].position>>BP[i].cost>>BP[i].grade;
		BP[i].shunxu=i;
		
		// 统计帮主和副帮主数量
		if(BP[i].position=="BangZhu" || BP[i].position=="FuBangZhu")
		{
			num++;
		}
	}
	
	// 对普通成员排序（帮贡降序 > 输入顺序升序）
	sort(BP+num, BP+n, cmp_1);
	
	// 分配职位（注意边界检查）
    int idx = num;
    
    // 分配护法（最多2人）
    int count = min(2, n - idx);
	for(int i=0;i<count;i++)
	{
		BP[idx++].position=zhiwei[2];
	}
	
	// 分配长老（最多4人）
    count = min(4, n - idx);
	for(int i=0;i<count;i++)
	{
		BP[idx++].position=zhiwei[3];
	}
	
	// 分配堂主（最多7人）
    count = min(7, n - idx);
    for (int i = 0; i < count; i++)
	{
        BP[idx++].position=zhiwei[4];
    }
    
    // 分配精英（最多25人）
    count = min(25, n - idx);
    for (int i = 0; i < count; i++)
	{
        BP[idx++].position=zhiwei[5];
    }
    
    // 剩余成员为帮众
    while (idx < n)
	{
        BP[idx++].position=zhiwei[6];
    }

    // 整个帮派最终排序
    sort(BP, BP + n, cmp_2);
    
    // 输出结果
	for(int i=0;i<n;i++)
	{
		cout<<BP[i].name<<" "<<BP[i].position<<" "<<BP[i].grade<<endl;
	}
	return 0;
}

P1591 阶乘数码

P1591 阶乘数码 - 洛谷

  • memset 函数

  • 是一个C标准库中的函数，用于将一块内存区域的每个字节设置为指定的值；

void *memset(void *ptr, int value, size_t num);

函数的参数包括 ptr，表示要设置的内存区域的起始地址；
value，表示要设置的值，通常以整数表示；
num，表示要设置的字节数。
memset 函数的工作原理是将指定值 value 拷贝到指定内存区域 ptr 所指向的每个字节中，重复拷贝 num 次。
常见的用法是将内存区域初始化为特定值，例如将整个数组清零。

// 将数组清零
int arr[10];
memset(arr, 0, sizeof(arr));

 memset 函数只能设置每个字节的值，因此对于非 char 型的数组，设置的值可能会被截断或产生不可预测的结果。针对非字符类型的数组或结构体，应该使用其他方法来进行赋值。 

  • memcpy 函数

  • 是 C 标准库中的一个函数，用于在内存之间进行字节级别的数据拷贝。memcpy 可以将源内存区域的内容复制到目标内存区域，并返回指向目标内存区域的指针。

void *memcpy(void *dest, const void *src, size_t n);

函数的参数包括 dest，表示目标内存区域的起始地址；
src，表示源内存区域的起始地址；
n，表示要复制的字节数。
memcpy 函数会将源内存区域中的 n 个字节的数据复制到目标内存区域，可能包含原先的内容。函数不会检查边界，因此保证源和目标内存区域的大小至少为 n 是非常重要的。

// 示例
#include <stdio.h>
#include <string.h>

int main() {
    char src[] = "Hello, world!";
    char dest[20];

    memcpy(dest, src, strlen(src) + 1);

    printf("Copied string: %s\n", dest);

    return 0;
}
// 输出：Copied string: Hello, world!

 memcpy 函数在进行内存拷贝时是按字节级别操作的，不关心内存中保存的是什么类型的数据。这也意味着在使用 memcpy 时，应确保源和目标内存区域之间没有重叠，以免产生意想不到的结果。如果源和目标内存区域有重叠，可以使用 memmove 函数来避免数据被破坏。

  • memmove函数

  • 是一个 C 标准库中的函数，用于在内存之间进行字节级别的数据拷贝。与 memcpy 函数不同的是，memmove 函数可以处理可能发生重叠的内存区域的拷贝。
void *memmove(void *dest, const void *src, size_t n);

函数的参数包括 dest，表示目标内存区域的起始地址；
src，表示源内存区域的起始地址；
n，表示要复制的字节数。
memmove 函数将会将源内存区域中的 n 个字节的数据复制到目标内存区域中，即使源和目标内存区域有部分或完全重叠。函数会自动处理重叠情况，以确保数据被正确复制。

// 示例
#include <stdio.h>
#include <string.h>

int main() {
  char str[] = "Hello, world!";
  memmove(str + 7, str, strlen(str) + 1);

  printf("Moved string: %s\n", str);

  return 0;
}
// 输出：Moved string: world! Hello,

 上述代码将字符串 str 移动了 7 个位置，即将字符串的前部分移动到后部分。在这个例子中，memmove 函数被用来处理源和目标内存区域可能重叠的情况。

需要注意的是，相比于 memcpy 函数，memmove 函数的实现可能会更加复杂和耗时，因为需要处理内存区域的重叠情况。因此，在没有重叠的情况下，推荐使用 memcpy 函数来进行拷贝操作，因为它的实现更简单且通常更高效。只有当存在内存区域重叠的情况时，才需要使用 memmove 函数。

#include<bits/stdc++.h>
using namespace std;

int s[3001]={0};

void do_jiecheng(int x)
{
	int g=0;
	
	for(int i=3000;i>=0;i--)
	{
		int temp=s[i]*x+g;
		g=temp/10;
		s[i]=temp%10;
	}
}

int main()
{
	int t;
	cin>>t;
	int n,a;

	for(int i=0;i<t;i++)
	{
		cin>>n>>a;
		
		// 重置数组并初始化阶乘为1
        memset(s,0,sizeof(s));
        s[3000]=1;
        
        if(n>=1)
        {
        	for(int i=2;i<=n;i++)
			{
				do_jiecheng(i);
			}
		}
		
		int w=0;
		for(;w<=3000;w++)
		{
			if(s[w]!=0)
			{
				break;
			}
		}
		
		int num=0;
		for(int i=w;i<=3000;i++)
		{
			if(s[i]==a)
			{
				num++;
			}
		}
		cout<<num<<endl;
	}
	return 0;
}

P1249 最大乘积

P1249 最大乘积 - 洛谷

#include<bits/stdc++.h>
using namespace std;

int a[10001]={};	// 存储分解的数字
int s[10001]={};	// 高精度数组存储乘积

int n,len=1;		// len: 高精度数字的位数

// 高精度乘法 (s = s * x)
void mul(int x)
{
	// 逐位相乘
	for(int i=1;i<=len;i++)
	{
		s[i]*=x;
	}
	
	// 处理进位
	for(int i=1;i<=len;i++)
	{
		s[i+1]+=s[i]/10;
		s[i]%=10;
	}
	
	// 扩展位数
	while(s[len+1]>0)
	{
		len++;
		s[len+1]+=s[len]/10;
		s[len]%=10;
	}
}

int main()
{
	cin>>n;
	
	// 处理特殊情况
	if(n==3)
	{
		cout<<3<<endl;
		cout<<3<<endl;
		return 0;
	}
	
	if(n==4)
	{
		cout<<4<<endl;
		cout<<4<<endl;
		return 0;
	}
	
	// 初始化高精度数组 (s=1)
	s[0]=s[1]=1;
	
	// Sum: 当前总和, tot: 数字个数
	int Sum=0,tot=0;
	
	// 构建连续自然数序列 (从2开始)
	for(int i=2;Sum<n;Sum+=i,i++)
	{
		a[++tot]=i;
	}
	
	// 调整序列
	if(Sum>n+1)				// 情况1：超出值较大
	{
		a[Sum-n-1]=0;		// 去掉特定位置的数
	}
	else if(Sum==n+1)		// 情况2：刚好超出1
	{
		a[tot]++;			// 最后一个数加1
		a[1]=0;				// 去掉第一个数2
	}
	
	// 输出分解方案并计算乘积
	for(int i=1;i<=tot;i++)
	{
		// 跳过被去掉的数(值为0)
		if(a[i])
		{
			cout<<a[i]<<' ';
			mul(a[i]);		// 乘以当前数
		}
	}
	cout<<endl;

	// 输出高精度乘积 (逆序输出)
	for(int i=len;i>=1;i--)
	{
		cout<<s[i];
	}

	cout<<endl;
	return 0;
}

P1045 [NOIP 2003 普及组] 麦森数

P1045 [NOIP 2003 普及组] 麦森数 - 洛谷

使用快速幂（二进制取幂）来优化；

#include<bits/stdc++.h>
using namespace std;
int p;
int f[1005],l[1005];
int s[1005];						//用于存储高精度乘法的中间计算

//函数s1：计算 l=l*f（结果乘以当前基数）
void s1()
{
    memset(s,0,sizeof(s));			//清空临时数组
    
    for(int i=1;i<=500;i++)
	{
        for(int j=1;j<=500;j++)
		{
            s[i+j-1]+=l[i]*f[j];	//l的每一位乘以f的每一位
        }
    }
    
    //处理进位
    for(int i=1;i<=500;i++)
	{
        s[i+1]+=s[i]/10;			//进位到高位
        s[i]%=10;					//当前位保留个位数
    }
    memcpy(l,s,sizeof(l));			//将结果复制回l数组
}

//函数s2：计算f=f*f（基数平方），方法同函数s1
void s2(){
    memset(s,0,sizeof(s));
    for(int i=1;i<=500;i++)
	{
        for(int j=1;j<=500;j++)
		{
            s[i+j-1]+=f[i]*f[j];
        }
    }
    for(int i=1;i<=500;i++)
	{
        s[i+1]+=s[i]/10;
        s[i]%=10;
    }
    memcpy(f,s,sizeof(f));
}

int main()
{
    cin>>p;
    
    //计算2^P-1的位数公式：log10(2^P)=P*log10(2)，加1得到位数
    cout<<(int)(log10(2)*p+1);
    l[1]=1;
    f[1]=2;
    
    //通过二进制分解P
    while(p!=0)
	{
        if(p%2==1)
		{
            s1();
        }
        p/=2;						//去掉p二进制中的最后一位
        s2();
    }
    
    //直接对个位减1，因为末尾只可能是2，4，6，8
    l[1]-=1;
    
    //输出需从高位到低位输出，因为逆序存储
    for(int i=500;i>=1;i--)
	{
        if(i%50==0)cout<<"\n";		//每50位换行
        cout<<l[i];
    }
    return 0;
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布