title: ACM-NEFU15届校赛-大一组
tags:

  • ACM
  • NEFU
    abbrlink: ba287589
    date: 2020-12-09 17:30:22

A. 三角形面积

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. int main()
  6. {
  7.     double a,b,c;
  8.     double ans,p,tmp;
  9.     cin>>a>>b>>c;
  10.     p=(a+b+c)*0.5;
  11.     tmp=p*(p-a)*(p-b)*(p-c);
  12.     ans=sqrt(tmp);
  13.     printf("%.1lf", ans);
  14.     return 0;
  15. }

B. 最大质因子

唯一分解定理

唯一分解定理又称为算数基本定理，基本内容是：

每个大于1的自然数，要么本身就是质数，要么可以写为2个或以上的质数的积，而且这些质因子按大小排列之后，写法仅有一种方式。

用另一种方法表示就是：

对于任何一个大于1的正整数,都存在一个标准的分解式: N=p1^a1 * p2an;（其中一系列an为指数，pn为质数）

此定理表明：任何一个大于 1 的正整数都可以表示为素数的积。

然而这道题纯暴力就可解…

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. const int maxn=1e5+10;
  7. bool judge(int a)
  8. {
  9.     int flag=1;
  10.     for (int i=2;i*2<=a;i++)
  11.      if (a%i==0) {flag=0; break; }
  12.     if (a==1) return 0;
  13.      else return flag;
  14. }
  16. int main()
  17. {
  18.     int a;
  19.    while(cin>>a)
  20.    {
  21.        for (int i=a;i>=1;i--)
  22.        {
  23.            if (a%i==0)
  24.             if (judge(i))
  26.            {
  27.                cout<<i<<endl;
  28.                break;
  29.            }
  30.        }
  31.    }
  33.     return 0;
  35. }

C.杨辉三角

模板例题

  1. #include<bits/stdc++.h>
  3. using namespace std;
  5. int a[21][21];
  7. int main()
  8. {
  9.     memset(a, 0, sizeof(a));
  10.     a[1][1]=1;
  11.     a[2][1]=a[2][2]=1;
  12.     int n;
  13.     cin>>n;
  14.     for(int i=3;i<=n;i++)//行 
  15.     {
  16.         for(int j=1;j<=i;j++)
  17.         {
  18.             if(j==1 || j==i)    
  19.             {
  20.                 a[i][j]=1;continue;
  21.             }
  22.             a[i][j]=a[i-1][j-1]+a[i-1][j];
  23.         }
  24.     }
  25.     for(int i=1;i<=n;i++)
  26.     {
  27.         for(int j=1;j<=i;j++)
  28.         {
  29.             cout<<a[i][j]<<" ";
  30.         }
  31.         cout<<endl;
  32.     }
  33.     return 0;
  34. }

D.”nefu”的数目

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  5. using namespace std;
  7. string s;
  9. int scount(int p)
  10. {
  11.     int sum=0;
  12.     int len=s.length();
  13.     for(int i=p+1;i<len;i++)
  14.     {
  15.         if(s[i]=='e')
  16.         {
  17.             for(int j=i+1;j<len;j++)
  18.             {
  19.                 if(s[j]=='f')
  20.                 {
  21.                     for(int k=j+1;k<len;k++)
  22.                     {
  23.                         if(s[k]=='u')    sum++;
  24.                         //cout<<sum<<endl;
  25.                     }
  26.                 }
  27.             }
  28.         }
  29.     }
  30.     return sum;
  31. }
  33. int main()
  34. {
  35.     int ans=0,flag=0;
  36.     cin>>s;
  37.     int len=s.length();
  38.     //cout<<len;
  39.     for(int i=0;i<len;i++)
  40.     {
  41.         if(s[i]=='n')
  42.         {
  43.             ans+=scount(i);
  44.         }
  45.             //cout<<ans<<endl;
  46.     }
  47.     cout<<ans<<endl;
  48.     return 0;
  49. }

E. 最少修改次数(1)

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. const int maxn=2e5+10;
  7. int main()
  8. {
  9.  string s,t;
  10.    while(cin>>s)
  11.    {
  12.        cin>>t;
  13.        int ct=0;
  14.        int nums=s.size(),numt=t.size();
  15.        int min=1111;
  16.        for (int i=0;i<=nums-numt;i++)
  17.        {
  18.            int j=0;
  19.            ct=0;
  20.            for (int k=i;k<=i+numt-1;k++)
  21.             {
  22.                 if (s[k]!=t[j]) ct++;
  23.                 j++;
  24.             }
  26.             if (ct<min) min=ct;
  27.        }
  29.        cout<<min<<endl;
  30.    }
  31.     return 0;
  32. }

F.字典序

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. const int maxn=2e5+10;
  7. int main()
  8. {
  9.     int n;
  10.   while(cin>>n)
  11.   {
  12.      string s1,s,max="0";
  13.     for (int i=1;i<=n;i++)
  14.      {
  15.        int m=i;
  16.        s.clear();    s1.clear();
  17.        while(m!=0)
  18.         {
  19.          s+=m%8+'0';
  20.          m/=8;
  21.         }
  22.        for (int j=s.size()-1;j>=0;j--)
  23.        {
  24.                s1+=s[j];
  25.        }
  26.         if (s1>max) max=s1;
  27.      }
  28.     cout<<max<<endl;
  29.   }
  30.     return 0;
  31. }

G.最小差值

  1. #include<bits/stdc++.h>
  3. using namespace std;
  5. const int maxn=2e5+10;
  6. int a[maxn];
  8. int main()
  9. {
  10.     int n,tot=0;
  11.     cin>>n;
  12.     for(int i=0;i<n;i++)
  13.     {
  14.         cin>>a[i];
  15.         tot+=a[i];
  16.     }
  17.     long long sum=0,ans=999999;
  18.     for(int i=0;i<n;i++)
  19.     {
  20.         long long com;
  21.         sum+=a[i];
  22.         com=tot-sum;
  23.         ans=min(ans, abs(com-sum));
  24.     }
  25.     cout<<ans;
  26.     return 0;
  27. }

H.染色方案（待补）

I.最大正方形

  1. #include<iostream>
  3. #include<algorithm>
  5. using namespace std;
  7. int main()
  8. {
  9.     int a[1000+5];
  10.     int n;
  11.     cin>>n;
  12.     for(int i=1;i<=n;i++)
  13.     {
  14.         cin>>a[i];
  15.     }
  16.     sort(a+1, a+1+n);
  17.     int ans=0;
  18.     for(int i=n;i>=1;i--)
  19.     {
  20.         if(a[i]>=ans+1)
  21.         {
  22.             ans++;
  23.         }
  24.         else    break;
  25.     }
  26.     cout<<ans;
  27.     return 0;
  28. }

J.最大值

注意：此题用C++输入输出会超时

  1. #include<iostream>
  2. #include<cstdio>
  4. using namespace std;
  6. const int MAXN=2e5+10;
  7. int a[MAXN];
  8. int times=0;
  10. int main()
  11. {
  12.     int n;
  13.     while(cin>>n)
  14.     {
  15.         int maxn=0,next=0;
  16.         for(int i=0;i<n;i++)
  17.         {
  18.             scanf("%d", &a[i]);
  19.             maxn=max(maxn, a[i]);    
  20.         }
  21.         for(int i=0;i<n;i++)
  22.         {
  23.             if(a[i]==maxn)
  24.             {
  25.                 times++;
  26.                 continue;
  27.             }
  28.             next=max(next, a[i]);
  29.         }
  30.         for(int i=0;i<n;i++)
  31.         {
  32.             if(a[i]>=maxn && times<=1)
  33.             {
  34.                 printf("%d\n", next);
  35.             }
  36.             else
  37.             {
  38.                 printf("%d\n", maxn);
  39.             }
  40.         }
  41.     }
  42.     return 0;
  43. }

K.循环排列(待补)

L.库特与围棋(待补)