前言

两道紫题（省选难度）QAQ，而且时限卡得很紧，享受爆零的快乐

T1 文具订购

题目传送门
根据题意，直接打暴力。枚举\(a,b\)，再根据订购原则更新答案（注意这里\(c\)就不用枚举了，可通过\(a,b\)计算）。
时间复杂度\(O(n^2)\)，对于\(0\leqslant n\leqslant 10^5\)的数据，开个氧气可以水过

//Author: stdout
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
inline int qaq(int x,int y,int z)  //三个数的最小值
{
	int ans=inf;
	if(x<ans) ans=x;
	if(y<ans) ans=y;
	if(z<ans) ans=z;
	return ans;
}
int main()
{
	//freopen("order.in","r",stdin);
	//freopen("order.out","w",stdout);
	int n,m=-1,s=-1,a=-1,b=-1,c=-1;  //s是最大物品总数，m是最大的a,b,c中的最小值
	cin>>n;
	for(int i=n/7;i>=0;--i)
		for(int j=n/4;j>=i;--j)
		{
			int k=n-7*i-4*j;  //计算c的总价
			if(k%3) continue;  //c的数量不是整数，下一个
			k/=3;int t=qaq(i,j,k);  //获取最小值和c的数量
			if(t>m)
				a=i,b=j,c=k,m=t,s=i+j+k;
			else if(t==m&&i+j+k>s)
				a=i,b=j,c=k,s=i+j+k;
		}
	if(a==-1&&b==-1&&c==-1) cout<<"-1";  //如果没有解
	else cout<<a<<" "<<b<<" "<<c; 
	return 0;
}

T2 跑步

题目传送门
声明:由于本蒟蒻水平菜,以下代码仅供娱乐,请大佬们自行跳过 会正解的大佬也可以教教我qwq
这题本蒟蒻开始用爆搜做,结果妥妥地T飞了(30分QAQ)
如果你输出前15个答案,你会发现答案似乎有些规律,

1,1,2,3,5,7,11,15,22,30,42,56,77,101,135

通过一个叫oeis的神奇网站(专门用来找数列规律)可以发现这是序列A000041
通过底下的PROG部分可以找到生成数列的代码(python): python大法好

def A000041(n):
    if n == 0: return 1
    S = 0; J = n-1; k = 2
    while 0 <= J:
        T = A000041(J)
        S = S+T if is_odd(k//2) else S-T
        J -= k if is_odd(k) else k//2
        k += 1
    return S 

python党直接cv就行了,而我们还需要转换一下

int solve(int x)
{
	if(!x) return 1;
	int s=0,j=x-1,k=2;
	while(j>=0)
	{
		int t=solve(j);
		if((k/2)&1) s+=t;
		else s-=t;
		if(k&1) j-=k;
		else j-=k/2;
		++k;
	}
	return s;
}

这样还是有递归,复杂度较高.我们还需要再优化一下,把递归变成dp(别忘了加模数),时间复杂度变为\(O(n)\).直接上AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int dp[N];
void solve(int n,int p)
{  //一通瞎改
	dp[0]=1;
	for(int i=1;i<=n;++i)
	{
		int j=i-1,k=2;
		while(j>=0)
		{
			if((k/2)&1) dp[i]=(dp[i]+dp[j])%p;
			else dp[i]=(dp[i]-dp[j]+p)%p;
			if(k&1) j-=k;
			else j-=k/2;
			++k;
		}
	}
}
int main()
{
	int n,p;
	//freopen("running.in","r",stdin);
	//freopen("running.out","w",stdout);
	cin>>n>>p;
	solve(n,p); 
	cout<<dp[n];
	return 0;
}

T3

咕咕咕