头像

fanfande




离线:4小时前



  • 朴素O(N^2) 方法,果不其然超时
#include<iostream>
#include<vector>
const int N=1e4+10;
using namespace std;
int  list[N];
int main()
{
    int k;
    cin>>k;

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

    int l=0,r=0,sum=0,max=0;
    for(int i=0;i<k;i++)
       for(int j=i;j<k;j++)
       {
           sum=0;
           for(int k=i;k<=j;k++) sum+=list[k];
           if(sum>max||(sum==0&&max==0))
           {
               max=sum;
               l=i,r=j;
           }
       }
    if(max==0&&l==0&&r==0) cout<<'0'<<' '<<list[0]<<' '<<list[k-1];
    else cout<<max<<' '<<list[l]<<' '<<list[r]<<endl;
    return 0;
}

  • 稍微优化下,仍然是O(N^2),但是可以pass
#include<iostream>
#include<vector>
const int N=1e4+10;
using namespace std;
int  list[N];
int main()
{
    int k;
    cin>>k;
    for(int i=0;i<k;i++)
    {
        cin>>list[i];
    }
    int l=0,r=0,sum=0,max=0;
    for(int i=0;i<k;i++)
    {
       sum=0;
       for(int j=i;j<k;j++)
       {
       sum+=list[j];
       if(sum>max||(max==0&&sum==0)) 
       {
           max=sum;
           l=i,r=j;
       }
       }
    }
    if(max==0&&l==0&&r==0) cout<<'0'<<' '<<list[0]<<' '<<list[k-1];
    else cout<<max<<' '<<list[l]<<' '<<list[r]<<endl;
    return 0;
}
  • 最后是动态归划
#include<iostream>
#include<vector>
const int N=1e4+10;
using namespace std;
int  list[N];
int main()
{
    int k;
    cin>>k;

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

   int l=0,r=0,max=0;//记录最大子序列
   int i=0,j=0,sum=list[0];
   while(j<k)
   {
       if(sum>max||(sum==0&&max==0))
       {
           max=sum;
           l=i;
           r=j;
       }
       if(sum>0&&sum<max)
       {

       }
       if(sum<0)
       {
           i=j+1;
           sum=0;
       }
       j++;
       sum+=list[j];
   }
   if(l==0&&r==0&&max==0) cout<<'0'<<' '<<list[0]<<' '<<list[k-1]<<endl;
   else cout<<max<<' '<<list[l]<<' '<<list[r]<<endl;
    return 0;
}



2020

A. ⽃⽜

给定五个 0~9 范围内的整数 a1, a2, a3, a4, a5。
如果能从五个整数中选出三个并且这三个整数的和为10 的倍数(包括 0),
那么这五个整数的权值即为剩下两个没被选出来的整数的和对 10 取余的结果,显然如果有多个三元组满⾜和是 10 的倍数,剩下两个数之和对 10 取余的结果都是相同的;
如果选不出这样三个整数,则这五个整数的权值为 -1。
现在给定 T 组数据,每组数据包含五个 0~9 范围内的整数,分别求这 T 组数据中五个整数的权值。

  • 【输⼊格式】
    第⼀⾏⼀个整数 T (1<=T<=1000),表⽰数据组数。
    接下来 T ⾏,每⾏ 5 个 0~9 的整数,表⽰⼀组数据。
    【输出格式】
    输出 T ⾏,每⾏⼀个整数,表⽰每组数据中五个整数的权值。

【样例输⼊】
4
1 0 0 1 0
1 0 0 8 6
3 4 5 6 7
4 5 6 7 8
【样例输出】
2
-1
-1
0

**#include<iostream>

using namespace std;
int a[4],sum2,sum3,sum5,power;

void dfs(int x,int y)
{
    sum2=a[x]+a[y];
    sum3=sum5-sum2;

    if(!(sum3%10) ) 
    {
        power=sum2%10;
        return;
    }
    else 
    {
        if(y==4) 
        {
            if(x!=3)

            {
                dfs(x+1,x+2);
            }
            else
            {
                power=-1;
                return;
            }
        }
        else
        {
            dfs(x,y+1);
        }
    }
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>a[0]>>a[1]>>a[2]>>a[3]>>a[4];
        sum5=a[0]+a[1]+a[2]+a[3]+a[4];
        dfs(0,1);  
        cout<<power<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 1547. 约会

#include<iostream>
using namespace std;
int main()
{
    string a,b,c,d;
    cin>>a>>b>>c>>d;
    int i;
    for( i=0;i<a.size();i++)
    {
        if(a[i]==b[i]&&a[i]>=65&&a[i]<=71)
        {
            if(a[i]=='A') cout<<"MON"<<' ';
            if(a[i]=='B') cout<<"TUE"<<' ';
            if(a[i]=='C') cout<<"WED"<<' ';
            if(a[i]=='D') cout<<"THU"<<' ';
            if(a[i]=='E') cout<<"FRI"<<' ';
            if(a[i]=='F') cout<<"SAT"<<' ';
            if(a[i]=='G') cout<<"SUN"<<' ';
            i++;
            break;
        }
    }
    while(a[i]!=b[i]||a[i]<48||(a[i]>57&&a[i]<65)||a[i]>78)  i++;

    if(a[i]>=48&&a[i]<=57)  cout<<'0'<<a[i]<<':';
    else cout<<a[i]-'A'+10<<':';
    for(int i=0;i<c.size();i++)
    {
        if(c[i]==d[i]&&((c[i]>=97&&c[i]<=122)||(c[i]>=65&&c[i]<=90)))
        {
            if(i<10)
           cout<<'0';
           cout<<i<<endl;
           break;
        }
    }
    return 0;
}


活动打卡代码 AcWing 1545. 质因子

#include<iostream>

using namespace std;

void divide(int n)
{
    if(n!=1)
    {
        for(int i=2;i<=n/i;i++)
        {
            int cnt=0;
            while(n%i==0)
            {
                cnt++;
                n/=i;
            }
            if(cnt==1) cout<<i;
            else if(cnt>1)  cout<<i<<'^'<<cnt;
            if(cnt!=0&&n!=1) cout<<'*';
        }
        if(n!=1)  cout<<n<<endl;
    }
}

int main()
{
    int n;
    cin>>n;
    if(n==1)  cout<<"1=1"<<endl;
    else  
    {
        cout<<n<<'=';
        divide(n);

    }

    return 0;
}


分享 质数相关

质数

大于1的整数中只包含1和本身这两个约数,为质数

质数的判定——试除法

  bool is_prime(int n)  //O(sqrt(n))
 {
    if(n<2) return false;
    else
    {
        for(int i=2;i<=n/i;i++)
        {
            if(!(n%i)) return false;
        }
    }
    return true;
 }

分解质因数
思路;从小到大尝试所有的因数,是就n/=i

   void divide(int n)  //O(sqrt(n))
   {
       for(int i=2;i<=n;i++)
         if(n%i==0)
         {
             int s=0;
             while(n%i==0)
             {
                 n/=i;
                 s++;
             }
             cout<<i<<' '<<s<<endl;
         }
      return ;
   }
   // 改良版
   void divide(int n)
   {
       for(int i=2;i<=n/i;i++)
         if(n%i==0)
         {
             int s=0;
             while(n%i==0)
             {
                 n/=i;
                 s++;
             }
             cout<<i<<' '<<s<<endl;
         }
        if(n>1)  cout<<n<<' '<<'1'<<endl;
      return ;
   }
筛素数法
   void get_prime(int n)
   //埃氏筛法O(nlog(log(n))) 
   {
       for(int i=2;i<=n;i++)
       {
           if(!st[i]) 
           {
           prime[cnt++]=n;
           for(int j=2*i;j<=n;j+=i) st[i]=true; 
           }
       }
   }

   //线性筛法 每一个数只会被它的最小质因子筛掉
   每次只要筛选小于等于i的第一个素因子的素数与i的乘积,既不会造成重复筛选,又不会遗漏, 时间复杂度O(N)。
   void   get_prime(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) 
        {
            prime[cnt++]=i;
        }

        for(int j=0;prime[j]*i<=n;j++)//筛除 prime[j]*i,直到prime[j]
        //是i的最小质因子
        {
            st[prime[j]*i]=true;
            if(i%prime[j]==0) break;

        }

    }
}




活动打卡代码 AcWing 1533. 1 的个数

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>

using namespace std;

int cal(int n)
{
    vector<int>  nums;
    while(n) nums.push_back(n%10),n/=10;

    int res=0;
    for(int i=0;i<nums.size();i++)
    {
        int d=nums[i];
        int l=0,r=0,power=0;
        for(int j=nums.size()-1;j>i;j--) l=l*10+nums[j];
        for(int j=i-1;j>=0;j--)  r=r*10+nums[j],power++;

        if(d==0)  res+=l*pow(10,power);
        else if(d==1)  res+=(l*pow(10,power)+r+1);
        else  res+= (l+1)*pow(10,power);
    }
    return res;
}

int main()
{
    int a;
    cin>>a;
    cout<<cal(a)<<endl;
    return 0;

}



题目描述

给定一个数字 N,请你计算 1∼N 中一共出现了多少个数字 1。

例如,N=12 时,一共出现了 5 个数字 1,分别出现在 1,10,11,12 中。

输入格式
包含一个整数 N。

输出格式
输出一个整数,表示 1 的个数。

数据范围
1≤N≤230


算法1

(暴力枚举) $O(n^2)$

统计数字1在每一位出现多少
奥数题



活动打卡代码 AcWing 1557. 说话方式

#include<iostream>
#include<unordered_map>
using namespace std;

bool check(char c)
{
  if(c>='0'&&c<='9') return true;
  if(c>='a'&&c<='z')  return true;
  if(c>='A'&&c<='Z' ) return true;

  return false;
}

char to_lower(char c)
{
    if(c>='A'&&c<='Z')  return c+32;
    return c;
}

int main()
{
    string s;
    getline(cin,s);

    unordered_map<string,int> hash;

    for(int i=0;i<s.size();i++)
    {     //双指针
       if(check(s[i]))
       {
           string word;
           int j=i;
           while(check(s[j])&&j<s.size())
               word+=to_lower(s[j++]);

           hash[word]++;
           i=j;
       }
    }

    string word;
    int cnt=-1;
    for(auto item:hash)
    {
      if(item.second>cnt||item.second==cnt&&item.first<word)
      {
          word=item.first;
          cnt=item.second;
      }
    }
    cout<<word<<' '<<cnt<<endl;
    return 0;
}


活动打卡代码 AcWing 1534. 字符串减法

#include<iostream>
#include<string>
#include<unordered_set>

using namespace std;
string a,b;
unordered_set <char>  uni;
int main()
{

    getline(cin,a);
    getline(cin,b) ;
    for(auto s:b) uni.insert(s);
    string res;
     for(auto s:a)
      if(!uni.count(s))  res+=s;

    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 1534. 字符串减法

#include<iostream>
#include<string>
#include<unordered_set>

using namespace std;
string a,b;
unordered_set <char>  uni;
int main()
{

    getline(cin,a);
    getline(cin,b) ;
    for(auto s:b) uni.insert(s);
    string res;
     for(auto s:a)
      if(!uni.count(s))  res+=s;

    cout<<res<<endl;
    return 0;
}