T1学习求余

正确思路

第1种情况 $k>n/2$ $a=k+q$

和相同,两个数越均匀乘积越大 当$k=a/2+1$ $q=a/2-1$是最大的

第2种情况 $k<n/2$ $a=b*k+q$

$k$会比$a/2+1$小,$q$也会比$a/2-1$要小

正确代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	freopen("mod.in", "r", stdin);
	freopen("mod.out", "w", stdout);
	long long n,maxx=0;
	cin>>n;
	if(n<=1000000) for(long long i=1;i<n;i++) maxx=max(maxx,n%i*i);
	else
	{
		long long k;
		k=n/2+1;
		maxx=n%k*k;
	}	
	cout<<maxx<<endl;
	return 0;
}

T2提取数字

错因

没全部开 $long long$

正确思路

用表达式求值的方法每次取出数字,+5后在求和

代码

#include<bits/stdc++.h>
using namespace std;
long long sum,i,n;
string s;
void qsz()
{
	long long ans=0;
	for(;i<s.size();i++)
	{
		if(s[i]>'9') break;
		ans=ans*10+int(s[i]-'0');
	}
	sum=sum+ans+5;
	return;
}
int main()
{
	freopen("number.in", "r", stdin);
	freopen("number.out", "w", stdout);
	cin>>n;
	cin>>s;
	for(i=0;i<s.size();i++)
	{
		if(s[i]>='0'&&s[i]<='9') qsz();
	}
	cout<<sum;
}

T3武器选择

错因

骗分的

正确思路

可以拿到最多的武器的数量是$\sqrt(n)$

可以只枚举能拿到的武器

现预处理一下 求个前缀和 f[i][j]表示武器i在前j个关卡中

出现了几次 这样就不需要遍历了

时间复杂度$O((m+n)*\sqrt(n))$

代码

#include<bits/stdc++.h>
using namespace std;
long long n,a[100050],m,ccnt[100050],b[1030],idx,flag[100050];
int f[510][100050];
int main()
{
	freopen("wq.in", "r", stdin);
	freopen("wq.out", "w", stdout);
	int l,r,k;
	cin>>n;
	for(int i=1;i<=n;i++) 
	{
		cin>>a[i];
		if(a[i]<=n) ccnt[a[i]]++;
	}
	for(int i=1;i<=n;i++)
	{
		if(a[i]>n) continue;
		else if(ccnt[a[i]]<a[i]) continue;
		else if(flag[a[i]]) continue;
		else
		{
			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;
	for(int i=1;i<=m;i++)
	{
		long long cnt=0;
		cin>>l>>r>>k;
		for(int j=1;j<=idx;j++)
		{
			if(f[j][r]-f[j][l-1]>=b[j]) cnt++;
		}
		if(cnt<k) cout<<0<<endl;
		else 
		{
			long long ans=1;
			for(long long j=1;j<=k;j++)
			{
				ans=ans*(cnt-j+1);
				ans/=j;
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}