学习求余（数学）

思路

通过打表可以发现，$k$最大是$(n/2)+1$。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
	freopen("mod.in","r",stdin);
	freopen("mod.out","w",stdout);
	int n;
	cin >>n;
	int res=(n/2)+1;
	cout <<res*(n%res);
	return 0;
}

提取数字（模拟）

思路没想到的原因

题目的意思理解错了，以为是一个一个的数字，实际上是连续的数字。

思路

直接模拟，不用管前导零的问题。

先遍历整个字符串，判断当前的$s[i]$是否是数字；如果不是，就直接跳过。

如果是的话，就把一整个数字存在答案里，别忘了还要$+5$。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
	freopen("number.in","r",stdin);
	freopen("number.out","w",stdout);
	int n;
	cin >>n;
	string s;
	cin >>s;
	int cnt=0;
	for(int i=0;i<s.size();i++){
		if(isdigit(s[i])){
			int res=0;
			while(isdigit(s[i])){
				res=res*10+s[i]-'0';
				i++;
			}
			cnt+=res+5;
		}
	}
	cout <<cnt;
	return 0;
}

武器选择（前缀和优化）

思路没想到的原因

当时没有想到怎么去优化，于是用了暴力解法，骗了$10$分。

思路

这道题目我们要注意几个优化方法：

• 因为编号$>n$的武器永远都拿不了，所以只需要统计编号$<=n$的武器；

• 预处理一下，并求个前缀和：$f[i][j]$表示武器$i$在前$j$个关卡中出现了几次。这样就不需要再次遍历了。

代码

#include <bits/stdc++.h>
using namespace std;

const int tt=1e5+10;
long long a[tt],b[tt],cnt[tt];
long long flag[tt];
int f[500][tt];
long long idx=0;
long long n,m;

int main(){
	freopen("wq.in","r",stdin);
	freopen("wq.out","w",stdout);
	cin >>n;
	for(int i=1;i<=n;i++){
		cin >>a[i];
		if(a[i]<=n) cnt[a[i]]++;
	}
	for(int i=1;i<=n;i++){
		if(a[i]>n) continue;
		if(cnt[a[i]]<a[i]) continue;
		if(flag[a[i]]) continue;
		b[++idx]=a[i];
		for(int j=1;j<=n;j++){
			f[idx][j]=f[idx][j-1]+(a[j]==a[i]);
		}
		flag[a[i]]=1;
	}
	cin >>m;
	while(m--){
		long long res=0;
		int l,r,k;
		cin >>l>>r>>k;
		for(int i=1;i<=idx;i++){
			if(f[i][r]-f[i][l-1]>=b[i]){
				res++;
			}
		}
		if(res<k){
			cout <<"0"<<endl;
			continue;
		}
		long long ans=1;
		for(int i=1;i<=k;i++){
			ans*=(res-i+1);
			ans/=i;
		}
		cout <<ans<<endl;
	}
	return 0;
}

括号序列

待更新……

谢谢