【算法狂想曲】第一次实战做题进度(二)

2020-04-08   146 次阅读


继续acwing

1211.蚂蚁感冒

题目地址

思路

这题一开始看,我说有点眼熟,在洛谷好像做到一题叫做独木桥的问题,是大兵过独木桥的问题,但是咋一看好像又不太一样。
我当时还在想,如何将开头到结尾所有的状态表示出来,还想着用同位素标记法(就是为每个蚂蚁设置一个是否感冒的标志)
后来思路陷入困境后只能求助于题解
想不到这题,竟然可以这样写,果然思路比方法更为重要

感谢acwing大佬Tony_Thomas提供的解题思路
下面为本人用画图画的草图

如果第一只感冒的蚂蚁和一只健康的蚂蚁相遇
1.PNG
正常理解应该是这样的(毕竟遇到就掉头)
2.PNG
但是这道题的话,也可以理解为两只蚂蚁互相擦肩而过,互相到达对面,反正都得了感冒,也没有什么顺序,都一样
3.PNG
因此这道题就变得相对好解决了
可以理解为这只万恶之源的蚂蚁一直向指定方向前进
因此在其前进方向上的所有对向蚂蚁都会被传染
而对向被传染的蚂蚁往万恶之源的反方向行进,因此这个时候与万恶之源同向,并且在万恶之源背后的所有蚂蚁都会被传染
但是归纳完成后还存在一个特殊情况,就是,该万恶之源行进的方向上没有对向蚂蚁
这个时候就只留万恶之源一个走出去了,因此感染蚂蚁为1
其余情况的话,分别计算左侧符合条件与右侧符合条件的蚂蚁就可以了,最后加上万恶之源得出结果
本来以为要用动态规划的,没想到还有这么妙的方法
5.PNG

AC代码

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

using namespace std;

int main()
{
    int N;                    //存储总蚂蚁个数
    int first;                //储存第一个蚂蚁
    int left=0;               //储存左边符合条件的潜在感染蚂蚁数
    int right=0;	      //储存右边符合条件的潜在感染蚂蚁数
    int current=0; 	      //存放当前的蚂蚁索引
    std::cin>>N;
    std::cin>>first;
    for(int i=1;i<N;i++)
    {
        std::cin>>current;
        if((abs(current)>abs(first))&&(current<0))	//在万恶之源蚂蚁前面,并且对向
        left++;
        if((abs(current)<abs(first))&&(current>0)) 	//在万恶之源蚂蚁后面,并且对向
        right++;
    }
    //std::cout<<"left:"<<left<<" right:"<<right<<std::endl;
    if((left==0&&first>0)||(right==0&&first<0))          //特殊情况
    std::cout<<1;
    else std::cout<<left+right+1;
    
    return 0;
}

2.01背包问题

思路

题目地址
非常裸的背包了,不解释

AC代码

#include<iostream>
using namespace std;

int U,V;
int v[1001];
int w[1001];
int dp[1001][1001];
int main()
{
    std::cin>>U>>V;
    for(int i=0;i<U;i++)
    {
        std::cin>>w[i]>>v[i];
    }
    for(int i=0;i<U;i++)
    {
        for(int j=0;j<=V;j++)
        {
            if(w[i]>j)
            dp[i+1][j]=dp[i][j];
            else{
                dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
            }
        }    
        
    }
    std::cout<<dp[U][V];
    return 0;
}

1216.饮料换购

题目地址

思路

很简单的一道数学题,不知道咋的就AC了

#include<iostream>
using namespace std;

int main()
{
    int N;
    int total;     //统计总饮料数目
    int newA=1;     //用于存储可兑换的新饮料数
    std::cin>>N;    
    total=N; 
    while(newA!=0)   //如果有新饮料,持续遍历
    {
        newA=N/3;
        N=N%3+newA;
        total+=newA;
    }
    std::cout<<total<<std::endl;
    return 0;
}

1210.连号区间数

题目地址

题目思路

这题做了好久了,真的脑子不够用,最后想出来的代码还是过不了500那组数据,每次都TLE

超时代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;

int N;
int total=0;
int atten[10001];
int result[10001];
int to=0;
bool whether(int result[10001],int pos);
int main()
{

   std::cin>>N;
   for(int i=0;i<N;i++)
   std::cin>>atten[i];
   int i;
    for(int j=0;j<N;j++)
   {
       result[to++]=atten[j];
       total++;
       for(i=j+1;i<N;i++)
   {
      result[to++]=atten[i];
       whether(result,to);
     
           
   }
     
       to=0;
   }

   //whether(result);
   std::cout<<total<<std::endl;
   return 0;
}
int cmp(int a,int b)
{
   return a>b;
}

bool whether(int result[10001],int pos)
{
   int sign=0;

   int v1[pos];
   memcpy(v1, result, pos * sizeof(int));
   sort(v1,v1+pos,greater<int>());

   if(pos==1)
       {
           total++;
           return true;
       }
    else if(pos)
   {
       for(int i=0;i<pos-1;i++)
   {
       if(v1[i]-1!=v1[i+1])
       {
           sign=1;
           break;
       }
   }
   if(!sign)
       {
           total++;
           return true;
       }
   }
return false;

}


换了数据结构还是不够用,因此肯定断定不能这样做,每次枚举排序肯定超时

感谢acwing用户田所浩二提供的灵感

因为题目所讲述的1~N个数中包含1~N所有的数,都有且仅有出现一次
因此我们给定一个区间,比如[5,3,4]
每次遍历时找出每个区间中的最大值与最小值,然后相减,如果结果等于区间长度-1,说明这是一个连号区间
[5,3,4]最大值为5,最小值为3,5-3=2,区间长度-1=3-1 = 2
相等,证明这是一个连号区间

在考虑[1,5,3,6,4],最大值为6,最小值为1,相减结果为5,区间长度-1=4,不相等证明不是连号区间,手动验证后确实不是连号区间,缺乏数字2

所以说灵感还是很总要的。大佬就是不一样

AC代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;

int N;
int total=0;
int atten[10001];

int main()
{

    std::cin>>N;            
    for(int i=0;i<N;i++)
    std::cin>>atten[i];
    int i;
     for(int j=0;j<N;j++)
    {
        int MAX=-1;
        int MIN=65535;
        for(i=j;i<N;i++)
    { 
       MAX=max(MAX,atten[i]);    //每次寻找区间中最大值(因为之前的区间最大值已经知道,所以只要将新进来的数跟最大值对比就行了)
       MIN=min(MIN,atten[i]);    //最小值同理
       //std::cout<<"MAX:"<<MAX<<" MIN:"<<MIN<<" i-j:"<<i-j<<std::endl;
       if(MAX-MIN==i-j)		//满足条件total++
       total++;
    }
    }
    std::cout<<total<<std::endl;
    return 0;
}



1245.特别数的和

题目地址

思路

因为数据量较少,所以靠列举所有的数进行判断即可(简单的模拟)
然后定义一个函数用来判断,然后从这个数的个位开始判断,如果检测到数为2019中的任一个数就将该数加到结果中

AC代码

#include<iostream>

using namespace std;
bool whether(int n);
int total=0;
int main()
{
    int N;
    std::cin>>N;
    for(int i=1;i<=N;i++)			//从1到N进行遍历
    {
        if(whether(i))
            total+=i;
    }
    std::cout<<total<<std::endl;
    return 0;
}

bool whether(int n)
{
    int rest;
    while(n!=0)
    {
        rest=n%10;                     		 //提取当前状态数的个位
        if(rest==0||rest==1||rest==2||rest==9)   //检测到2019中的任意一个就判断为正
        return true;
        n=n/10;					//更新状态数
    }
    return false;
}

787. 归并排序

题目地址

思路

模板题,标准的归并排序(但是本人竟然还忘了咋写,还特地到网上去学习了一下差劲
不多解释,想必各位大佬对归并排序也了如指掌,这玩意最香的地方是最好,最坏时间复杂度都为O(nlogn),还是有东西的
高效稳定

AC代码

#include<iostream>
using namespace std;
 int N;
void sort(int s,int e,int temp[]);
void merge(int s,int mid,int e,int temp[]);
 int arr1[100001];
 int temp1[100001];
 void print()
 {
     for(int j=0;j<N;j++)
     std::cout<<arr1[j]<<" ";
     std::cout<<std::endl;
 }
int main()
{
   
   
    std::cin>>N;
    for(int i=0;i<N;i++)
    std::cin>>arr1[i];
    sort(0,N-1,temp1);
    print();
    return 0;
}

void sort(int s,int e,int temp[])
{
    if(s<e)
    {
    int mid=(s+e)/2;
    sort(s,mid,temp);
    sort(mid+1,e,temp);
    merge(s,mid,e,temp);
    }
    
}

void merge(int s,int mid,int e,int temp[])
{
    int left=s;
    int right=mid+1;
    int t=0;
    while(left<=mid&&right<=e)
    {
        if(arr1[left]>=arr1[right])
        temp[t++]=arr1[right++];
        else
        temp[t++]=arr1[left++];
    }
    while(left<=mid)
    temp[t++]=arr1[left++];
    while(right<=e)
    temp[t++]=arr1[right++];
 
        t=0;
    for(int i=s;i<=e;i++)
    arr1[i]=temp[t++];
   
}

1219.移动距离

题目链接

思路

这题求移动距离不是关键,关键是要确定所给的两个楼层的坐标位置
经过对楼层进行列举后(在AC代码中的注释部分,有兴趣的可以拿来对比debug)
发现了规律,因为奇数行是正向递增,偶数项是反向递增
并且每一行最大项都是w的倍数

 1  2  3  4  5  6
 12 11 10 9  8  7
 13 14 15 16 17 18

观察上述数据可得,

  • 第一行的1~5,模6之后刚好等于当前的位置
  • 而第一行最后一个数6,以及第二行从右往左数的7~11,被6整除结果都等于1
    • 6处于最末尾的位置,即x=w,所处行数刚好是结果1
    • 其他数处于第二行,是运算结果数+1,列数则是从后往前数第(余数)个位置

右端和后续规律也是相同的规律,感兴趣的可以自行验证

AC代码

#include<iostream>
#include<math.h>
using namespace std;
int w,m,n;
void detect(int &posx,int &posy,int atten);
int main()
{
    
    /*
    1  2  3  4  5  6
    12 11 10 9  8  7
    13 14 15 16 17 18
    24 23 22 21 20 19
    
    1 2 3 4 5 6 7 8 9 10 11
    22 21 20 19 18 17 16 15 14 13 12 
    23 24 25 26 27 28 29 30 31 32 33
    44 43 42 41 40 39 38 37 36 35 34
    45 46 47 48 49 50 51 52 53 54 55
    66 65 64 63 62 61 60 59 58 57 56
    

    */
    
    std::cin>>w>>m>>n;
    int rest1,rest2;
    int result1,result2;
    int posx1,posx2,posy1,posy2;
    detect(posx1,posy1,m);
    detect(posx2,posy2,n);
    //std::cout<<posx1<<" "<<posy1<<" "<<posx2<<" "<<posy2<<std::endl;
    int ans=abs(posx1-posx2)+abs(posy1-posy2);
    std::cout<<ans<<std::endl;
    
    
    
    return 0;
}
    void detect(int &posx,int &posy,int atten)
    {
    int rest1=atten%w;          //偏移距离,确定横向x
    int result1=atten/w;	//确定纵向y,也就是楼层在第几列
   // std::cout<<"rest1:"<<rest1<<" result1:"<<result1<<std::endl;
        if(result1%2==0)        
    {
        if(result1==0)		//第一行的特殊情况
        {
            posx=rest1;
            posy=1;
        }
        else if(rest1!=0)	//如果偏移距离不为0,正常偏移
        {
            posx=rest1;
            posy=result1+1;
        }
        else			//否则其是上一行的最大值
        {
            posx=1;
            posy=result1;
        }
    }
    else{
        if(rest1!=0)		//如果偏移距离不为0,正常偏移
        {
            posx=w-rest1+1;	//反向递增
            posy=result1+1;
        }
        else{			//否则其是上一行的最大值
            posx=w;	
            posy=result1;
        }
    }
    }
    
    //11 13 2974

此代码梳理博客到此,由于题量过多,因此分P进行,剩下的题目将会在下一P呈现

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议