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;
}
: 帶有循環的Looping Graph(練習解答))
