继续acwing
1211.蚂蚁感冒
思路
这题一开始看,我说有点眼熟,在洛谷好像做到一题叫做独木桥的问题,是大兵过独木桥的问题,但是咋一看好像又不太一样。
我当时还在想,如何将开头到结尾所有的状态表示出来,还想着用同位素标记法(就是为每个蚂蚁设置一个是否感冒的标志)
后来思路陷入困境后只能求助于题解
想不到这题,竟然可以这样写,果然思路比方法更为重要
感谢acwing大佬Tony_Thomas
提供的解题思路
下面为本人用画图画的草图
如果第一只感冒的蚂蚁和一只健康的蚂蚁相遇
正常理解应该是这样的(毕竟遇到就掉头)
但是这道题的话,也可以理解为两只蚂蚁互相擦肩而过,互相到达对面,反正都得了感冒,也没有什么顺序,都一样
因此这道题就变得相对好解决了
可以理解为这只万恶之源的蚂蚁一直向指定方向前进
因此在其前进方向上的所有对向蚂蚁都会被传染
而对向被传染的蚂蚁往万恶之源的反方向行进,因此这个时候与万恶之源同向,并且在万恶之源背后的所有蚂蚁都会被传染
但是归纳完成后还存在一个特殊情况,就是,该万恶之源行进的方向上没有对向蚂蚁
这个时候就只留万恶之源一个走出去了,因此感染蚂蚁为1
其余情况的话,分别计算左侧符合条件与右侧符合条件的蚂蚁就可以了,最后加上万恶之源得出结果
本来以为要用动态规划的,没想到还有这么妙的方法
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.
Comments | 0 条评论