题单【模拟与高精度】
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;// 重置数组并初始化阶乘为1memset(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]++; // 最后一个数加1a[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;//通过二进制分解Pwhile(p!=0){if(p%2==1){s1();}p/=2; //去掉p二进制中的最后一位s2();}//直接对个位减1，因为末尾只可能是2，4，6，8l[1]-=1;//输出需从高位到低位输出，因为逆序存储for(int i=500;i>=1;i--){if(i%50==0)cout<<"\n"; //每50位换行cout<<l[i];}return 0;
}