😑 DAY11总结

T1 小W的病毒歼灭战（题目传送门）

💢思路

用一个数组模拟队列，遍历队列，如果没有这个弹夹，那么队头出队，这个弹夹入队 cnt++ 最后输出cnt

🎈代码

#include<bits/stdc++.h>
using namespace std;
int d[1010],cnt,a[1010],tt=-1,hh=0;
queue<int> q;
int main()
{
	freopen("bd.in","r",stdin);
	freopen("bd.out","w",stdout);
	int m,n,t=0,idx=0,ans=0;
	cin>>m>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		q.push(a[i]);
		int w=q.front();
		q.pop();
		int flag=0;
		for(int i=hh;i<=tt;i++) 
		{
			if(d[i]==w) 
			{
				flag=1;
				break;
			}
		}
		if(flag==0)
		{
			if(tt-hh+1>=m)	hh++;
			d[++tt]=a[i];
			cnt++;
		}
	}
	cout<<cnt;
}

错误原因

没有用模板写，导致最后找不到错（以后要用模板写）

分类 数据结构——队列

T2小田的三倍数（题目传送门）

思路

输入一个string ，遍历他的每一位，相加起来，最后判断是不是3的倍数

代码

#include<bits/stdc++.h>
using namespace std;
long long sum=0;
int main()
{
	freopen("three.in","r",stdin);
	freopen("three.out","w",stdout);
	string a;
	int t,n;
	cin>>t;
	for(int i=1;i<=t;i++)
	{
		sum=0;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>a;
			for(int i=0;i<=a.size()-1;i++) sum+=(a[i]-'0');
		}
		if(sum%3==0) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
 	return 0;
}

😓错误原因

没加换行（❌以后不要再犯这种错误了）

分类 简单语法

T3小田的省钱计划 （题目传送门）

思路

先将促销价格减去原价，获得每一个省的钱。在求一个最大子段和，用ans存他们的最大值。输出ans

代码

#include<bits/stdc++.h>
using namespace std;
long long a[100010],f[100010];
int main()
{
	freopen("money.in","r",stdin);
	freopen("money.out","w",stdout);
	long long n,x,ai,ans=0;
	cin>>n>>x;
	for(int i=1;i<=n;i++)
	{
		cin>>ai;
		a[i]=ai-x;
	}
	for(int i=1;i<=n;i++)
	{
		if(f[i-1]<0) f[i]=a[i];
		else f[i]=f[i-1]+a[i];
	}
	for(int i=1;i<=n;i++) ans=max(ans,f[i]);
	cout<<ans;
 	return 0;
}

😶错误原因

没有想到，以后要多积累

分类 简单算法？——最大子段和

T4 计算表达式的值（题目传送门）

思路

模板题，加了个'^'幂运算而已

代码

#include<bits/stdc++.h>
using namespace std;
stack<int> num;
stack<char> op;
void yx()
{
	int a=num.top();num.pop();
	int b=num.top();num.pop();
	char c=op.top();op.pop();
	int x;
	if(c=='+') x=b+a;
	else if(c=='-') x=b-a;
	else if(c=='*') x=b*a;
	else if(c=='/') x=b/a;
	else x=pow(b,a);
	num.push(x);
}
unordered_map<char,int> pr{{'+',1},{'-',1},{'*',2},{'/',2},{'^',3}};
bool is_number(char x)
{
	if(x>='0'&&x<='9') 
	{
		return true;
	}
	else return false;
}
int main()
{
	freopen("bds.in","r",stdin);
	freopen("bds.out","w",stdout);
	string str;
	cin>>str;
	for(int i=0;i<=str.size()-1;i++)
	{
		auto c=str[i];
		if(is_number(c))
		{
			int x=(c-'0');
			while(is_number(str[i+1]))
			{
				x=x*10+(str[i+1]-'0');
				i++;
			}
			num.push(x);
		}
		else if(c=='(') op.push(c);
		else if(c==')')
		{
			while(op.top()!='(') yx();
			op.pop();
		}
		else
		{
			while(op.size()&&op.top()!='('&&pr[c]<=pr[op.top()]) yx();
			op.push(c);
		}
	}
	int t=num.top();
	num.pop();
	if(!num.empty())
	{
		while(!num.empty())
		{
			num.push(t);
			yx();
			t=num.top();
			num.pop();
		}
	}
	cout<<t;
 	return 0;
}

错误原因

不会写模板（以后要多写，已完成）

分类 表达式求值