T1 小W的病毒歼灭战

思路：

用队列模拟小w换弹夹的过程；

过程：

• 如果这个队列里没有当前这个数字，就让那个数字入队(要注意如果队列的长度大于了$k$，那就要$s.pop( )$ )。

因为数据不大可以直接循环看队列里是否有和$a[i]$一样的数。

样例 1

输入

2 10
1 2 3 1 2 3 1 2 3 1

输出

10

模拟：

1. 1
2. 1 2
3. 2 3
4. 3 1
5. 1 2
6. 2 3
7. 3 1
8. 1 2
9. 2 3
10. 3 1

一共去总部取10次。

样例 2

输入

3 10
1 2 3 1 2 3 1 2 3 1

输出

3

模拟：

1. 1
2. 1 2
3. 1 2 3

一共去总部取3次。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1010],cnt;
queue <int> q;
int main(){
	freopen("bd.in","r",stdin);
	freopen("bd.out","w",stdout);
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		int f=0;
		for(int j=0;j<q.size();j++){
			if(q.front()==a[i]){
				f=1;
				int c=q.front();
				q.pop();
				q.push(c);
			}
			else {
				int c=q.front();
				q.pop();
				q.push(c);
			}
		}
		if(f!=1){
			cnt++;
			q.push(a[i]);
			if(q.size()>m)q.pop();
		}
	}
	cout<<cnt;
	return 0;
}

T2 小田的三倍数

思路：

判断输入的数字中按位相加，最终看是否为三的倍数。

3的倍数特征：

所有数位之和是3的倍数得数一定是3的倍数。

注意：

因为输入的数字最大是$10^{100}$，要用$string$输入

样例

输入

2
3
12 3 7
3
12 3 6

输出

No
Yes

第一组因为1+2+3+7=13，不是3的倍数；

第二组因为1+2+3+6=15，是3的倍数。

代码

#include<bits/stdc++.h>
using namespace std;
int n,t;
string s;
int main(){
	cin>>t;
	while(t--){
		cin>>n;
		int j=0;
		while(n--){
			cin>>s;
			for(int i=0;i<s.size();i++)j+=s[i]-'0';
		}
		if(j%3!=0)cout<<"No"<<endl;
		else cout<<"Yes"<<endl;
	}	
	return 0;
}

T3小田的省钱计划

思路：

先算出每个商品现在与之前的差价。 这题是一道DP的 最大子段和 问题，也可以用贪心的去写。

递推公式

$$sum[i]=max(sum[i-1]+a[i],a[i]);$$

样例

输入

6 2
1 1 4 5 1 4

输出

6

样例解释

购买 4,5,1,4这四件后，原价为 14，促销价格之和为 2+2+2+2=8，所以答案为 6。

代码实现：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
long long n,x,a[N],sum[N],maxx=0;
int main(){
	cin>>n>>x;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]-=x;
	}
	for(int i=1;i<=n;i++){
		sum[i]=max(sum[i-1]+a[i],a[i]);
		maxx=max(maxx,sum[i]);
	}
	cout<<maxx;
	return 0;
}