牛客练习赛123（A,B,C,D）

牛客挑战赛，练习赛和小白月赛周赛不是一种东西。这玩意跟CF的div12差不多难度。而且找不到题解。所以决定不等题解补题了，直接写题解了。

比赛链接

光速签到下班，rk++。感觉E可能能补掉，看情况补吧。

B题感觉之前考了两次，结论和证明构造过程需要理解，赛时记得结论直接秒了。C题是不太裸的裸完全背包，思路不裸但是写法裸。D题需要加个优化，思路看的别人的，很妙。

A 炸鸡块哥哥的粉丝题

思路：

签到，截取前一半的子串即可。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int n;
string s;

int main(){
	cin>>n>>s;
	cout<<s.substr(0,(n+1)/2);
	return 0;
}

B 智乃想考一道鸽巢原理

思路：

看了评论区题解才发现，自己这么长时间理解的方法原来就是鸽巢原理。指路

我们想让某一种小球留下来，肯定先让其他小球先配对抵消掉，其他小球抵消剩下的再用这种小球来消。那么问题就变成了求其他小球抵消剩下的小球有几个，如果剩下的球比这种小球少，那就可以剩下这种小球，否则就剩不下。

我们把最多的那个小球看作是鸽巢，然后剩余的小球看作是鸽子，也就是鸽巢有 $mx$ 个，鸽子有 $rm=tot-a_i$ 个。

1. 当 $mx>\lfloor \frac{rm}{2}\rfloor$ 时：可以每个鸽巢放入一只鸽子，此时剩余的小球个数就是剩余的鸽巢个数，即 $mx-(rm-mx)=2\ast mx-rm$。
2. 当 $mx\le \lfloor \frac{rm}{2}\rfloor$ 时：可以用其他小球来充当鸽巢，使得鸽巢拓展到 $\lceil \frac{rm}{2}\rceil$ 个。然后其他小球依次放入鸽巢即可，可以保证存在一种方法使得小球不会放在同种颜色小球的鸽巢里（因为最少可以只有一种颜色又当鸽巢又放小球，其他颜色就不可能重复了。而每种颜色小球个数不会超过 $\lceil \frac{rm}{2}\rceil$ 个，所以这种颜色可以不重复）。此时会剩余 $rm\%2$ 个鸽巢。

所以我们枚举 $i$ 时，对每个 $i$ 只要知道剩余的小球的总个数和剩余最大个数的小球，就可以计算其他小球抵消最后会剩多少小球，也就知道能否剩下这种小球。我们可以设置一个变量记录所有小球个总个数，并处理出前缀最大值和后缀最大值，这样就可以快速查询了。

code：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;

int T,n;
int a[maxn],prem[maxn],sufm[maxn];
ll tot;

int main(){
	cin>>T;
	while(T--){
		cin>>n;
		tot=0;
		for(int i=1;i<=n+1;i++)prem[i]=sufm[i]=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			prem[i]=max(prem[i-1],a[i]);
			tot+=a[i];
		}
		for(int i=n;i>=1;i--)sufm[i]=max(sufm[i+1],a[i]);
		
		for(int i=1;i<=n;i++){
			ll mx=max(prem[i-1],sufm[i+1]),rm=tot-a[i],lst;
			if(mx>rm/2)lst=2*mx-rm;
			else lst=rm&1;
			cout<<"01"[a[i]>lst]<<" \n"[i==n];
		}
	}
	return 0;
}

C 智乃想考一道完全背包(Easy version)

思路：

如果位置 $k$ 上的物品本来就很好了，那么肯定选这个物品就行了。但是如果有个很好的物品远离位置 $k$，那么我们就需要选上从这个位置到 $k$ 上的所有物品，才能选上这一个物品，它就相当于和中间的物品进行捆绑销售了。

反正一定会捆绑销售，所以我们不如一开始就将 $l\sim k$ 或 $k\sim r$ 位置上的物品进行绑定，把它们变成一个物品，然后跑完全背包。

不过由于我们选了 $l\sim k$ 的物品的话，我们还能去拓展另一边到 $r$，并省下一个 $k$。所以另一边我们也需要绑定过来，也就是说需要把 $l\sim r$ 上的物品进行绑定。

如果我们以位置为横坐标，每个位置上物品选择的个数为纵坐标画直方图的话，它的形状就是一个金字塔型。我们绑定物品同时选取，其实就相当于绑定一行，每行都是整块选取。

时间复杂度看似是 $O(n^2\ast m)$ 的。但是由于背包容量最多 $m$，重量超过 $m$ 的物品我们根本更新不了答案，所以最多有 $m^2$ 级别个物品会更新 $dp$ 值，所以时间复杂度最多是 $O(n^2+m^3)$ 的。

code：

没必要开longlong

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=2005;
const int maxm=505;
typedef long long ll;
const ll linf=1e18;

int n,m,k;
ll dp[maxm];

ll tw[maxn],tv[maxn];

int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		cin>>tw[i]>>tv[i];
		tw[i]+=tw[i-1];
		tv[i]+=tv[i-1];
	}
	for(int l=1;l<=k;l++)
		for(int r=k;r<=n;r++){
			ll w=tw[r]-tw[l-1],v=tv[r]-tv[l-1];
			for(int j=w;j<=m;j++)
				dp[j]=max(dp[j],dp[j-w]+v);
		}
	
	for(int i=1;i<=m;i++){
		dp[i]=max(dp[i-1],dp[i]);
		cout<<dp[i]<<" ";
	}
	return 0;
}

D 智乃想考一道完全背包(Hard version)

思路：

朴素的想法是设 $dp[k][j]$ 表示位置 $k$ 为中心，容量为 $j$ 的最大价值。直接枚举 $k$ 的位置，对每个位置做法和上面相同，这样时间复杂度就会变成 $O(n\ast m^3)$，会 $T$ 掉 $\frac{1}{3}$ 的点。

考虑优化，发现对于选取了区间 $l\sim r$ 的整块物品，它可以去更新 $k\in [l,r]$ 的所有位置，而没有必要在选取不同 $k$ 的时候分别去更新每个 $dp[k][-]$。

原本我们先从小到大枚举 $l$，固定好 $l$ 后，然后枚举 $r$ 和 $k$，对一个位置 $k$，它应该用 $[l,r=k\sim n]$ 的物品来更新。这里为了实现上面说的优化，我们从大到小枚举 $r$，并且令 $k=r$，这样算出来的 $dp[r][-]$ 就考虑到了 $[l,r=k\sim n]$ 所有物品。$dp[r][-]$ 直接从 $dp[r+1][-]$ 转移过来或者从 $[l,r]$ 这件物品转移过来即可

这样优化后，由于不需要枚举 $k$ 的位置，时间复杂度被优化成了 $O(m^3)$。可以通过。

code：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=2005;
const int maxm=505;
typedef long long ll;
const ll linf=1e18;

int n,m;
ll dp[maxn][maxm];
//位置为k，背包容量为j 

ll tw[maxn],tv[maxn];
int ans[maxn],id[maxn];

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>tw[i]>>tv[i];
		tw[i]+=tw[i-1];
		tv[i]+=tv[i-1];
	}
	
	for(int l=1;l<=n;l++){
		ll w,v;
		for(int r=n;r>=l;r--){
			w=tw[r]-tw[l-1];
			v=tv[r]-tv[l-1];
			for(int j=w;j<=m;j++)
				dp[r][j]=max(dp[r][j],max(dp[r+1][j],dp[r][j-w]+v));
		}
	}

	
	for(int i=1;i<=m;i++){
		ll maxx=-linf,idx;
		for(int k=1;k<=n;k++){
			dp[k][i]=max(dp[k][i-1],dp[k][i]);
			if(dp[k][i]>maxx){
				maxx=dp[k][i];
				idx=k;
			}
		}
		ans[i]=maxx;
		id[i]=idx;
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<" \n"[i==m];
	for(int i=1;i<=m;i++)cout<<id[i]<<" \n"[i==m];
	return 0;
}