牛客周赛 Round 39（补题）

小红不想做完全背包 （hard）

题目描述

本题和easy版本的唯一区别是：ppp没有必须等于3的限制。

完全背包是一个经典问题，但小红完全不会完全背包，因此她不想做完全背包。

现在小红拿到了一个长的很像完全背包的题，她希望你帮她解决一下。
 

给定一个背包，有nnn种物品，每种物品的价值为aia_iai​，有无穷多个。小红有一个无穷大的背包，她希望往里面放若干个物品，使得最终所有物品的价值之和为ppp的倍数。小红想知道最终至少要放多少物品？

（注意：不能不放物品）

示例1

输入

复制4 3 1 2 3 4

4 3
1 2 3 4

输出

1

1

错误操作：

我的思路就正确，操作就是在我每次输入都没有存在一个数组中在进行处理。这导致有些没有遍历到或者其前面那个数据的最小值发生改变。导致答案错误。

思路：

我们用dp求最小到m值得操作数。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
#define N 2000
void solve()
{
   
 
	int i,j,k,n,m,t,a[N+50],f[N+50];
    cin>>n>>m;
    memset(f,1,sizeof(f));
    for(i=1;i<=n;i++){
        cin>>a[i]; a[i]%=m; f[a[i]]=1;
    }
    
	//cout << f[0] <<endl;
    for(i=1;i<=n;i++){
        for(j=0;j<m;j++){
            f[(j+a[i])%m]=min(f[(j+a[i])%m],f[j]+1);
        }
    }
    cout<<f[0];
   
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
//	cin>>t;0
	while(t--){
		solve();
	} 
	return 0;
} 

红不想做莫比乌斯反演杜教筛求因子和的前缀和

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

小红来到了一家蛋糕店，蛋糕店中售卖了若干种不同的长方体蛋糕，具体来讲，蛋糕店中售卖若干种形状为横向长度不大于nnn，纵向长度不大于mmm，高度不大于ppp个单位的蛋糕。每个蛋糕的表面要裹上奶油，也就是说，除了底面以外，其余5个面都需要裹奶油。我们不妨定义：奶油消耗量为暴露在空气中的5个面的面积之和。


我们定义两种蛋糕是不同的，当且仅当两个蛋糕的横向或者纵向长度或高度不同。即分别定义蛋糕横向的长度为iii，纵向的长度为jjj，高度为kkk，则可以用三元组(i,j,k)(i,j,k)(i,j,k)表示蛋糕种类的唯一性。

现在小红希望你求出，共有多少种不同的奶油消耗量为xxx的蛋糕？

输入

复制2 2 2 8

2 2 2 8

输出

复制2

2

思路：

直接以每个正方形来看即可，优化第 3层即可。判断1≤n,m,p≤3000 是否符合即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
void solve()
{
   
   	ll n,m,p,x,i,j,r = 0,k;
   	cin >> n >> m >> p >> x;
   	for(int i = 1;i <= n;i++)
   	{
   		for(int j = 1;j <= m;j++)
		{
			ll k = (x - i*j) /(2*(i+j));
			if(k >= 1 && k <= p && i*j + j*k*2 + i*k*2 == x){
				r++;
			}
		}	
	}
	cout << r<<endl;
   
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
//	cin>>t;
	while(t--){
		solve();
	} 
	return 0;
} 

小红不想做模拟题

思路：

题目意思是间A 区间 或B 区间全部变成 1 在 &

我们可以用 2 个 set  分别 记录 区间 A 的 0  和 区间 B 的 0 的 位置。

当将区间 A l r变成 1 就是 遍历 B 中区间 l r 那个位置 是否为 1 

set 的基础运用 

t.count(*it) 表示 *it 位置是否存在 

s.erase(it)表示 删掉这个位置 it会自动++；

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
void solve()
{
   
   	int n,q,i;
   	cin >> n;
   	string a,b;
   	cin>>a>>b;
	set<int>  s ={n},t = {n};
	int ans = 0;
	for(int i = 0;i < n;i++)
	{
		if(a[i] == '0') s.insert(i);
		if(b[i] == '0') t.insert(i); // B的 个数 
		if(a[i] == '1' && b[i] == '1') ++ans;
	}
	
	cin >> q;
	
	while(q--)
	{
		char ch;
		int l,r;
		cin >>ch>>l>>r;
		--l;--r;
		if(ch=='A'){
			auto it = s.lower_bound(l);
			//cout << *it << endl;
			while(*it <= r){
				if(!t.count(*it)) ++ans;
				//cout << *it<<endl;
				it = s.erase(it);
				//cout << *it  <<endl;
			}
		}else{
			auto it = t.lower_bound(l);
			while(*it <= r)
			{
				if(!s.count(*it)) ++ans;
				it = t.erase(it);
			}
		}
		cout <<ans<<'\n'; 
	}
   
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
//	cin>>t;
	while(t--){
		solve();
	} 
	return 0;
} 

解析：

求连续字段翻转一次或0次的升序序列。

我们用 lft 记录 其 升序的 序列长度。

用rgt 记录 其 从右到 左的降序序列长度。

在进行分类讨论：

单增、单减、先增后减、先减后增、先增后减再增。

用纸模拟一下。

我这 里的 x*y 是包含 a[i] ~ a[R] 这一段的

所以 len*(len -1)/2 - 1 的 -1 是减区 a[i]~ a[R]这一段的；

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,a[200010],lft[200010],rgt[200010];
void solve()
{
	ll ans = 0;
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> a[i];
	} 
	lft[0] = 0;
	rgt[n+1] = 0;
	a[0] = 0;
	a[n+1] = n+1;
	for(int i = 1;i <= n;i++)
	{
		if(a[i] > a[i-1])
		{
			lft[i] = lft[i-1] + 1;
		}
		else{
			lft[i] = 1;
		}
		ans += lft[i];// 一直递增 的  
	}
	
	for(int i = n ;i >= 1; i--)
	{
		if(a[i] < a[i+1])
		{
			rgt[i] = rgt[i+1] + 1;
		}
		else{
			rgt[i] =1;
		}
	}
	//cout << " ans  " << ans<<endl; 
	
	for(int i = 1;i <= n-1;i++)
	{
		if(a[i+1] < a[i]) //减de 
		{
			int R = i+1;
			while(R +1 <= n && a[R+1] < a[R])
			{
				++R;
			}
			int len = R - i + 1;
			//下降时的部分 
			ans+= 1ll*len*(len-1)/2-1;
			//cout <<" ： "<< 1ll*len*(len-1)/2-1 <<endl;
			
			//曲折的那部分  且包含 递减的那个区间  
			int x, y;
			if(a[R] > a[i-1])
			{
				x = lft[i-1]+1;	
			}else{
				x = 1;
			}
			
			if(a[i] < a[R+1])
			{
				y = rgt[R+1] + 1;
			}else{
				y = 1;
			}
			ans += 1ll*x*y;
			
			//小区间反转的部分 
			for(int j = i+1;j < R;j++)//降序 部分 
			{
				if(a[j] > a[i-1]) ans+= lft[i-1];
				if(a[j] < a[R+1]) ans+= rgt[R+1]; 
			}
			i = R;
		}
	}
	cout << ans<<'\n';
	
	
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	solve(); 
	return 0;
} 

时间复杂度为O（n);