https://www.luogu.com.cn/training/102#problems

P5718 【深基4.例2】找最小值

  1. #include<bits/stdc++.h> 
  2. using namespace std;
  3. int a[105];
  4. int main(void)
  5. {
  6.     int n; cin>>n; 
  7.     for(int i=0;i<n;i++) cin>>a[i];
  8.     sort(a,a+n);
  9.     cout<<a[0];
  10.     return 0;
  11. }

P5719 【深基4.例3】分类平均

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int sum1,sum2,cnt1,cnt2;
  4. int main(void)
  5. {
  6.     int n,k; cin>>n>>k;
  7.     for(int i=1;i<=n;i++)
  8.     {
  9.         if(i%k==0) sum1+=i,cnt1++;
  10.         else sum2+=i,cnt2++;
  11.     }
  12.     printf("%.1lf %.1lf",1.0*sum1/cnt1,1.0*sum2/cnt2);
  13.     return 0;
  14. }

P5720 【深基4.例4】一尺之棰

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(void)
  4. {
  5.     int n,cnt=1; cin>>n;
  6.     while(n!=1) n/=2,cnt++;
  7.     cout<<cnt;
  8. }

P5721 【深基4.例6】数字直角三角形

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(void)
  4. {
  5.     int n,cnt=1; cin>>n;
  6.     for(int i=n;i>=1;i--)
  7.     {
  8.         for(int j=1;j<=i;j++)
  9.         {
  10.             printf("%02d",cnt++);
  11.         }
  12.         puts("");
  13.     }
  14.     return 0;
  15. }

P1009 [NOIP1998 普及组] 阶乘之和

  1. #include<bits/stdc++.h> 
  2. using namespace std;
  3. int n;
  4. vector<int>A,ans;
  5. vector<int> add(vector<int> A,vector<int> B)
  6. {
  7.     int t=0;
  8.     vector<int>C;
  9.     for(int i=0;i<A.size()||i<B.size();i++)
  10.     {
  11.         if(i<A.size()) t+=A[i];
  12.         if(i<B.size()) t+=B[i];
  13.         C.push_back(t%10);
  14.         t=t/10;
  15.     }
  16.     if(t) C.push_back(1);
  17.     return C;
  18. }
  19. vector<int> mul(vector<int> A,int b)
  20. {
  21.     vector<int>C;
  22.     int t=0;
  23.     for(int i=0;i<A.size()||t;i++)
  24.     {
  25.         if(i<A.size()) t+=A[i]*b;
  26.         C.push_back(t%10);
  27.         t/=10;
  28.     }
  29.     return C;
  30. }
  31. int main(void)
  32. {
  33.     cin>>n;
  34.     ans.push_back(0);
  35.     A.push_back(1);
  36.     for(int i=1;i<=n;i++)
  37.     {
  38.         A=mul(A,i);
  39.         ans=add(ans,A);
  40.     }
  41.     for(int i=ans.size()-1;i>=0;i--) cout<<ans[i];
  42.     return 0;
  43. }

P1980 [NOIP2013 普及组] 计数问题

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,x,cnt;
  4. int main(void)
  5. {
  6.     cin>>n>>x;
  7.     for(int i=1;i<=n;i++)
  8.     {
  9.         int k=i;
  10.         while(k) 
  11.         {
  12.             if(k%10==x) cnt++;
  13.             k/=10;
  14.         }
  15.     }
  16.     cout<<cnt;
  17.     return 0; 
  18. }

P1035 [NOIP2002 普及组] 级数求和

  1. #include<bits/stdc++.h> 
  2. using namespace std;
  3. int n;
  4. int main(void)
  5. {
  6.     double sum=0;
  7.     cin>>n;
  8.     for(int i=1;i<=10000000;i++)
  9.     {
  10.         sum+=1.0/i;
  11.         if(sum>n)
  12.         {
  13.             cout<<i;
  14.             break;
  15.         }
  16.     }
  17.     return 0;
  18. }

P2669 [NOIP2015 普及组] 金币

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(void)
  4. {
  5.     int n; cin>>n;
  6.     int sum=0,k=1,cnt=0;
  7.     while(cnt+1<=n)
  8.     {
  9.         for(int i=1;i<=k&&(cnt+1)<=n;i++) sum+=k,cnt++;
  10.         k++;
  11.     }
  12.     cout<<sum;
  13.     return 0;
  14. }

P5722 【深基4.例11】数列求和

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(void)
  4. {
  5.     int n; cin>>n;
  6.     int sum=0;
  7.     for(int i=1;i<=n;i++) sum+=i;
  8.     cout<<sum;
  9.     return 0;
  10. }

P5723 【深基4.例13】质数口袋

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=1e5+10;
  4. int st[N],prime[N],cnt;
  5. int n;
  6. void solve(int n)
  7. {
  8.     int sum=0;
  9.     for(int i=2;i<=N;i++) 
  10.     {
  11.         if(!st[i])
  12.         {
  13.             prime[cnt++]=i;
  14.             if( (sum+i) > n ) return;
  15.             else sum+=i;
  16.         }
  17.         for(int j=0;prime[j]<=N/i;j++)
  18.         {
  19.             st[i*prime[j]]=1;
  20.             if(i%prime[j]==0) break;
  21.         }
  22.     }
  23. }
  24. int main(void)
  25. {
  26.     cin>>n;
  27.     solve(n);
  28.     for(int i=0;i<cnt-1;i++) cout<<prime[i]<<endl;
  29.     cout<<cnt-1<<endl;
  30.     return 0;
  31. }

P1217 [USACO1.5]回文质数 Prime Palindromes

  • 先线性筛筛出所有的质数，然后枚举质数判断即可。

注意: 打表到1e7即可，首先1e9一定不可以。故最大到99999999，因为[1e7-99999999],这些数是8位的数是偶数位的数一定可以被11整除。
故一定一个都没有，所以只需枚举到1e7即可。
性质:偶数位的回文数一定被11整除，这里除了11是质数外，其他所有的偶数位的回文数一定不是质数
能被11整除的数的性质：奇数位的数字之和 减 偶数位的数字之和能被11整除。

这里以4位的回文数为例:
在这里插入图片描述
故一定可以被11整除。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=1e6+10;
  4. const int M=1e7+10;
  5. int prime[N],cnt,l,r;
  6. bool st[M];
  7. void init(int n)
  8. {
  9.     for(int i=2;i<=n;i++)
  10.     {
  11.         if(!st[i]) prime[cnt++]=i;
  12.         for(int j=0;prime[j]<=n/i;j++)
  13.         {
  14.             st[i*prime[j]]=1;
  15.             if(i%prime[j]==0) break;
  16.         }
  17.     }
  18. }
  19. int check(int x)
  20. {
  21.     if(x<l||x>r) return 0;
  22.     string s=to_string(x);
  23.     for(int i=0;i<s.size()/2;i++)
  24.         if(s[i]!=s[s.size()-1-i]) return 0;
  25.     return 1;
  26. }
  27. int main(void)
  28. {
  29.     init(1e7);
  30.     cin>>l>>r;
  31.     for(int i=0;i<cnt;i++)
  32.         if(check(prime[i])) cout<<prime[i]<<endl;
  33.     return 0;
  34. }

P1423 小玉在游泳

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(void) 
  4. {
  5.     double n; cin>>n;
  6.     double sum=0,step=2;
  7.     int cnt=0;
  8.     while(sum<n) sum+=step,step*=0.98,cnt++;
  9.     cout<<cnt;
  10.     return 0;
  11. }

P1307 [NOIP2011 普及组] 数字反转

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(void)
  4. {
  5.     string s; cin>>s;
  6.     if(s[0]=='-') cout<<s[0],s=s.substr(1);
  7.     reverse(s.begin(),s.end());
  8.     while(s.size()>1&&s[0]=='0') s=s.substr(1);
  9.     cout<<s;
  10.     return 0;
  11. }

P1720 月落乌啼算钱（斐波那契数列）

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. double solve(int n)
  5. {
  6.     double sum1=1,sum2=1;
  7.     for(int i=1;i<=n;i++) sum1*=(1+sqrt(5))/2;
  8.     for(int i=1;i<=n;i++) sum2*=(1-sqrt(5))/2;
  9.     return (sum1-sum2)/sqrt(5);
  10. }
  11. int main(void)
  12. {
  13.     cin>>n;
  14.     printf("%.2lf",solve(n));
  15.     return 0;
  16. }

P5724 【深基4.习5】求极差 / 最大跨度值

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=1e5+10;
  4. int n,a[N];
  5. int main(void)
  6. {
  7.     cin>>n;
  8.     for(int i=0;i<n;i++) cin>>a[i];
  9.     sort(a,a+n);
  10.     cout<<a[n-1]-a[0];
  11.     return 0;
  12. }

P1420 最长连号

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,x,s[100010];
  4. int main(void)
  5. {
  6.     cin>>n;
  7.     for(int i=0;i<n;i++) cin>>s[i];
  8.     int ans=1;
  9.     for(int i=0;i<n;i++)
  10.     {
  11.         int temp=1;
  12.         for(int j=i+1;j<n;j++) 
  13.         {
  14.             if((s[j]-s[j-1])==1) temp++;
  15.             else break;
  16.         }
  17.         ans=max(ans,temp);
  18.     }
  19.     cout<<ans;
  20.     return 0;
  21. }

P1075 [NOIP2012 普及组] 质因数分解

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int check(int x)
  4. {
  5.     for(int i=2;i<=x/i;i++) if(x%i==0) return 0;
  6.     return 1;
  7. }
  8. int main(void)
  9. {
  10.     int n; cin>>n;
  11.     for(int i=2;i<=n/i;i++)
  12.     {
  13.         if(n%i==0&&check(i)&&check(n/i))
  14.         {
  15.             cout<<n/i;
  16.             return 0;
  17.         }
  18.     }
  19.     return 0;
  20. }

P5725 【深基4.习8】求三角形

  1. #include<bits/stdc++.h> 
  2. using namespace std;
  3. int main(void)
  4. {
  5.     int n; cin>>n;
  6.     int k=1;
  7.     for(int i=1;i<=n;i++)
  8.     {
  9.         for(int j=1;j<=n;j++) printf("%02d",k++);
  10.         puts("");
  11.     }
  12.     k=1;
  13.     puts("");
  14.     for(int i=1;i<=n;i++)
  15.     {
  16.         for(int j=1;j<=n-i;j++) cout<<"  ";
  17.         for(int j=1;j<=i;j++) printf("%02d",k++);
  18.         puts("");
  19.     }
  20.     return 0;
  21. }

P5726 【深基4.习9】打分

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=1e5+10;
  4. int a[N],n,sum;
  5. int main(void)
  6. {
  7.     cin>>n;
  8.     for(int i=0;i<n;i++) cin>>a[i],sum+=a[i];
  9.     sort(a,a+n);
  10.     sum-=a[0],sum-=a[n-1];
  11.     printf("%.2lf",1.0*sum/(n-2));
  12.     return 0;
  13. }

P4956 [COCI2017-2018#6] Davor

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. int main(void)
  5. {
  6.     cin>>n;
  7.     for(int i=100;i>=0;i--)
  8.     {
  9.         for(int j=1;j<=100000;j++)
  10.         {
  11.             int sum=7*i+7*6/2*j;
  12.             sum=sum*52;
  13.             if(sum==n)
  14.             {
  15.                 cout<<i<<endl;
  16.                 cout<<j<<endl;
  17.                 return 0;
  18.             }
  19.         }
  20.     }
  21.     return 0;
  22. }

P1089 [NOIP2004 提高组] 津津的储蓄计划

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(void)
  4. {
  5.     int s1=0,s2=0;
  6.     for(int i=1;i<=12;i++)
  7.     {
  8.         int x; cin>>x;
  9.         s2+=300,s2-=x;
  10.         if(s2<0)
  11.         {
  12.             printf("-%d\n",i);
  13.             return 0;
  14.         }
  15.         s1=s1+s2/100*100;
  16.         s2=s2%100;
  17.     }
  18.     cout<<s1*1.2+s2;
  19.     return 0;
  20. }