T1 小W的病毒歼灭战

【总结】

简单 的打卡题，只需要一个任意版本的队列再加一个计数变量就行，但是出于我现在也不知道的原因（可能是因为我的一个判断里加入了 continue 导致当 mm 大于 nn 时不会有任何计数）就变成了 20′20' ，罚抄了 1010 遍 TnT

错误：没有把所有情况的输入数据都想到并测试一遍。

【题解】

题面里明示用队列，所以没有什么思路，直接流程：

  • 输入 nn 和长度为 nn 的数组。

  • 遍历数组，对于数组中的每个元素：

    • 遍历队列，判断小W身上有没有这种弹夹。
    • 如果这种弹夹存在，无事发生
    • 这种弹夹不存在，计数变量 cnt 增加，如果弹夹数量超过了 xx 个，则将队尾元素弹出。

  • 输出。

【具体实现】
#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1005;
int m,n,res,x[N];
queue<int> q;

signed main(){
	freopen("bd.in","r",stdin);
	freopen("bd.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>m>>n;
	for(int i=1;i<=n;i++) cin>>x[i];
	for(int i=1;i<=n;i++){
		bool flag=true;
		for(int j=0;j<q.size();j++){
			if(q.front()==x[i]) flag=false;
			int front=q.front();
			q.pop();
			q.push(front);
		}
		if(flag){
			res++;
			if(q.size()>=m) q.pop();
			q.push(x[i]);
		} 
	}
	cout<<res;
	return 0;
}

T2 小田的三倍数

【总结】

打卡水题 之二，从某些方面来说比第一题还简单，还是可以轻松 100′100' 的。

【题解】

题目要求把 nn 个数 拼 成 3 的倍数，也就是说每个数每位上的值是不变的，从这个特点出发再加上 3 的倍数特征：所有位相加，如果数位之和是 3 的倍数，那么原数就是 3 的倍数，反之则不是。

另外有一个小坑，专制不看数据范围的人，这题中的 aia_i 最大有 1010010^{100} ，明显要用字符串进行输入。

只要输入时用了字符串而且累加的结果没错那么就可以 100′100' 。

【具体实现】
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,t;
string s;

void solve(){
	int sum=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s;
		for(int j=0;j<s.size();j++) sum+=s[j]-'0';
	}
	if(sum%3==0) cout<<"Yes\n";
	else cout<<"No\n";
}
signed main(){
	freopen("three.in","r",stdin);
	freopen("three.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--) solve();
	return 0;
}

T3 小田的省钱计划

【总结】

2024年7月19日 最难的一题——这位说的

既然是最难的，那么必须没有提交了，本来的思路是 前缀和 加 双指针 ，但是在双指针环节失败了。

【题解】

实际上这题是一道DP的 最大子段和 问题，也可以用贪心的思想去推。

定义一个数组 sum ，其中sum[i] 代表所有以 ii 为结尾的区间中的最大值，它应该等于 sum[i-1]（也就是以i-1结尾的区间的最大值）加上 aia_i ，但是题目中没有保证 aia_i 是正整数，所以当 sum[i-1] 是负数时，sum[i] 就应该等于 aia_i 。所以完整的递推公式应该是：

sumi=max(sumi−1+ai−x,ai−x)sum_i=max(sum_{i-1}+a_i-x,a_i-x)
【具体实现】
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,t,maxx=-1,x[N],sum[N];

signed main(){
	freopen("money.in","r",stdin);
	freopen("money.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>t;
	for(int i=1;i<=n;i++) cin>>x[i];
	for(int i=1;i<=n;i++){
		sum[i]=max(sum[i-1]+x[i]-t,x[i]-t);
		maxx=max(maxx,sum[i]);
	}
	cout<<maxx;
	return 0;
}

T4 计算表达式的值

【总结】

数据结构 模板题 ，就是一个普通的中缀表达式求值加上了一个新的运算符 ^ ，表示 aa 的 bb 次幂，100′100' 也很简单。

【题解】

普通的中缀表达式求值的过程，唯一需要注意的是 ^ 运算符的优先级是最高的，其他没有任何难点。

【具体实现】
#include <bits/stdc++.h>
#define int long long
using namespace std;
stack<int> st1;
stack<char> st2;
unordered_map<char,int> mp={{'+',1},{'-',1},{'*',2},{'/',2},{'^',3}};
string s;

void clac(char opt){
	int b=st1.top();
	st1.pop();
	int a=st1.top();
	st1.pop();
	if(opt=='+') st1.push(a+b);
	else if(opt=='-') st1.push(a-b);
	else if(opt=='*') st1.push(a*b);
	else if(opt=='/') st1.push(a/b);
	else {
		int sum=1;
		for(int i=1;i<=b;i++) sum*=a;
		st1.push(sum);
	}
	st2.pop();
}
signed main(){
	freopen("bds.in","r",stdin);
	freopen("bds.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>s;
	for(int i=0;i<s.size();i++){
		if(s[i]>='0' and s[i]<='9'){
			int num=0;
			while(s[i]>='0' and s[i]<='9'){
				num=num*10+s[i]-'0';
				i++;
			}
			i--;
			st1.push(num);
		}
		else if(s[i]=='(') st2.push('(');
		else if(s[i]==')'){
			while(st2.top()!='('){
				clac(st2.top());
			}
			st2.pop();
		}
		else {
			while(st2.size() and mp[st2.top()]>=mp[s[i]]) clac(st2.top());
			st2.push(s[i]);
		}
	}
	while(st2.size()) clac(st2.top());
	cout<<st1.top();
	return 0;
}

T5 永夜的报应

【总结】

没有递交 ，思路也没有QwQ

【题解】

看上去非常难，但是只要根据这条 数学 结论就能得出答案：

a⊕b≤a+ba⊕b\le a+b

所以我们只需要把所有数放在一组取异或和，就是最小的权值。

【具体实现】
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,ans,x[N];

signed main(){
	freopen("huiye.in","r",stdin);
	freopen("huiye.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>x[i];
	if(n==1){
		cout<<x[1];
		return 0;
	}
	ans=x[1]^x[2];
	for(int i=3;i<=n;i++) ans^=x[i];
	cout<<ans;
	return 0;
}

T6 数学题2

【总结】

没有提交 。

【题解】

只需要用一个桶数组存储所有数的所有约数，再从大到小遍历桶数组，如果 cnt[i] 大于等于当前需要求 GCDGCD 的数的数量，那么输出 ii 。

TIPS：每次循环从上次的答案开始。

【具体实现】
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+5,M=1e6+5;
int n,x[N],cnt[M]; 

void ys(int r){
	for(int i=1;i*i<=r;i++){
		if(r%i==0){
			cnt[i]++;
			if(i!=r/i) cnt[r/i]++;
		} 
	}
}
int main(){
	freopen("math2.in","r",stdin);
	freopen("math2.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>x[i];
	for(int i=1;i<=n;i++) ys(x[i]);
	int t=1;
	for(int i=M;i>=1;i--){
		if(cnt[i]==0) continue;
		if(cnt[i]>=t){
			cout<<i<<'\n';
			t++,i++;
			continue;
		}
	}
	return 0;
}
  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 14ms
  4. Powered by Hydro v5.0.0-beta.13 Community