继续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 条评论