跆拳道东莞网站建设,品牌网站建设解决,营销网站建设网站制作公司,php网站建设教程视频牛客挑战赛#xff0c;练习赛和小白月赛周赛不是一种东西。这玩意跟CF的div12差不多难度。而且找不到题解。所以决定不等题解补题了#xff0c;直接写题解了。
比赛链接
光速签到下班#xff0c;rk。感觉E可能能补掉#xff0c;看情况补吧。
B题感觉之前考了两次#x…牛客挑战赛练习赛和小白月赛周赛不是一种东西。这玩意跟CF的div12差不多难度。而且找不到题解。所以决定不等题解补题了直接写题解了。
比赛链接
光速签到下班rk。感觉E可能能补掉看情况补吧。
B题感觉之前考了两次结论和证明构造过程需要理解赛时记得结论直接秒了。C题是不太裸的裸完全背包思路不裸但是写法裸。D题需要加个优化思路看的别人的很妙。 A 炸鸡块哥哥的粉丝题
思路
签到截取前一半的子串即可。
code
#include iostream
#include cstdio
#include cstring
using namespace std;int n;
string s;int main(){cinns;couts.substr(0,(n1)/2);return 0;
}B 智乃想考一道鸽巢原理
思路
看了评论区题解才发现自己这么长时间理解的方法原来就是鸽巢原理。指路
我们想让某一种小球留下来肯定先让其他小球先配对抵消掉其他小球抵消剩下的再用这种小球来消。那么问题就变成了求其他小球抵消剩下的小球有几个如果剩下的球比这种小球少那就可以剩下这种小球否则就剩不下。
我们把最多的那个小球看作是鸽巢然后剩余的小球看作是鸽子也就是鸽巢有 m x mx mx 个鸽子有 r m t o t − a i rmtot-a_i rmtot−ai 个。
当 m x ⌊ r m 2 ⌋ mx\gt \left\lfloor\dfrac{rm}2\right\rfloor mx⌊2rm⌋ 时可以每个鸽巢放入一只鸽子此时剩余的小球个数就是剩余的鸽巢个数即 m x − ( r m − m x ) 2 ∗ m x − r m mx-(rm-mx)2*mx-rm mx−(rm−mx)2∗mx−rm。当 m x ≤ ⌊ r m 2 ⌋ mx\le \left\lfloor\dfrac{rm}2\right\rfloor mx≤⌊2rm⌋ 时可以用其他小球来充当鸽巢使得鸽巢拓展到 ⌈ r m 2 ⌉ \left\lceil\dfrac{rm}2\right\rceil ⌈2rm⌉ 个。然后其他小球依次放入鸽巢即可可以保证存在一种方法使得小球不会放在同种颜色小球的鸽巢里因为最少可以只有一种颜色又当鸽巢又放小球其他颜色就不可能重复了。而每种颜色小球个数不会超过 ⌈ r m 2 ⌉ \left\lceil\dfrac{rm}2\right\rceil ⌈2rm⌉ 个所以这种颜色可以不重复。此时会剩余 r m % 2 rm\%2 rm%2 个鸽巢。
所以我们枚举 i i i 时对每个 i i i 只要知道剩余的小球的总个数和剩余最大个数的小球就可以计算其他小球抵消最后会剩多少小球也就知道能否剩下这种小球。我们可以设置一个变量记录所有小球个总个数并处理出前缀最大值和后缀最大值这样就可以快速查询了。
code
#include iostream
#include cstdio
using namespace std;
typedef long long ll;
const int maxn1e65;int T,n;
int a[maxn],prem[maxn],sufm[maxn];
ll tot;int main(){cinT;while(T--){cinn;tot0;for(int i1;in1;i)prem[i]sufm[i]0;for(int i1;in;i){cina[i];prem[i]max(prem[i-1],a[i]);tota[i];}for(int in;i1;i--)sufm[i]max(sufm[i1],a[i]);for(int i1;in;i){ll mxmax(prem[i-1],sufm[i1]),rmtot-a[i],lst;if(mxrm/2)lst2*mx-rm;else lstrm1;cout01[a[i]lst] \n[in];}}return 0;
}C 智乃想考一道完全背包(Easy version)
思路
如果位置 k k k 上的物品本来就很好了那么肯定选这个物品就行了。但是如果有个很好的物品远离位置 k k k那么我们就需要选上从这个位置到 k k k 上的所有物品才能选上这一个物品它就相当于和中间的物品进行捆绑销售了。
反正一定会捆绑销售所以我们不如一开始就将 l ∼ k l\sim k l∼k 或 k ∼ r k\sim r k∼r 位置上的物品进行绑定把它们变成一个物品然后跑完全背包。
不过由于我们选了 l ∼ k l\sim k l∼k 的物品的话我们还能去拓展另一边到 r r r并省下一个 k k k。所以另一边我们也需要绑定过来也就是说需要把 l ∼ r l\sim r l∼r 上的物品进行绑定。
如果我们以位置为横坐标每个位置上物品选择的个数为纵坐标画直方图的话它的形状就是一个金字塔型。我们绑定物品同时选取其实就相当于绑定一行每行都是整块选取。
时间复杂度看似是 O ( n 2 ∗ m ) O(n^2*m) O(n2∗m) 的。但是由于背包容量最多 m m m重量超过 m m m 的物品我们根本更新不了答案所以最多有 m 2 m^2 m2 级别个物品会更新 d p dp dp 值所以时间复杂度最多是 O ( n 2 m 3 ) O(n^2m^3) O(n2m3) 的。
code
没必要开longlong
#include iostream
#include cstdio
using namespace std;
const int maxn2005;
const int maxm505;
typedef long long ll;
const ll linf1e18;int n,m,k;
ll dp[maxm];ll tw[maxn],tv[maxn];int main(){cinnmk;for(int i1;in;i){cintw[i]tv[i];tw[i]tw[i-1];tv[i]tv[i-1];}for(int l1;lk;l)for(int rk;rn;r){ll wtw[r]-tw[l-1],vtv[r]-tv[l-1];for(int jw;jm;j)dp[j]max(dp[j],dp[j-w]v);}for(int i1;im;i){dp[i]max(dp[i-1],dp[i]);coutdp[i] ;}return 0;
}D 智乃想考一道完全背包(Hard version)
思路
朴素的想法是设 d p [ k ] [ j ] dp[k][j] dp[k][j] 表示位置 k k k 为中心容量为 j j j 的最大价值。直接枚举 k k k 的位置对每个位置做法和上面相同这样时间复杂度就会变成 O ( n ∗ m 3 ) O(n*m^3) O(n∗m3)会 T T T 掉 1 3 \frac13 31 的点。
考虑优化发现对于选取了区间 l ∼ r l\sim r l∼r 的整块物品它可以去更新 k ∈ [ l , r ] k\in[l,r] k∈[l,r] 的所有位置而没有必要在选取不同 k k k 的时候分别去更新每个 d p [ k ] [ − ] dp[k][-] dp[k][−]。
原本我们先从小到大枚举 l l l固定好 l l l 后然后枚举 r r r 和 k k k对一个位置 k k k它应该用 [ l , r k ∼ n ] [l,rk\sim n] [l,rk∼n] 的物品来更新。这里为了实现上面说的优化我们从大到小枚举 r r r并且令 k r kr kr这样算出来的 d p [ r ] [ − ] dp[r][-] dp[r][−] 就考虑到了 [ l , r k ∼ n ] [l,rk\sim n] [l,rk∼n] 所有物品。 d p [ r ] [ − ] dp[r][-] dp[r][−] 直接从 d p [ r 1 ] [ − ] dp[r1][-] dp[r1][−] 转移过来或者从 [ l , r ] [l,r] [l,r] 这件物品转移过来即可
这样优化后由于不需要枚举 k k k 的位置时间复杂度被优化成了 O ( m 3 ) O(m^3) O(m3)。可以通过。
code
#include iostream
#include cstdio
using namespace std;
const int maxn2005;
const int maxm505;
typedef long long ll;
const ll linf1e18;int n,m;
ll dp[maxn][maxm];
//位置为k背包容量为j ll tw[maxn],tv[maxn];
int ans[maxn],id[maxn];int main(){cinnm;for(int i1;in;i){cintw[i]tv[i];tw[i]tw[i-1];tv[i]tv[i-1];}for(int l1;ln;l){ll w,v;for(int rn;rl;r--){wtw[r]-tw[l-1];vtv[r]-tv[l-1];for(int jw;jm;j)dp[r][j]max(dp[r][j],max(dp[r1][j],dp[r][j-w]v));}}for(int i1;im;i){ll maxx-linf,idx;for(int k1;kn;k){dp[k][i]max(dp[k][i-1],dp[k][i]);if(dp[k][i]maxx){maxxdp[k][i];idxk;}}ans[i]maxx;id[i]idx;}for(int i1;im;i)coutans[i] \n[im];for(int i1;im;i)coutid[i] \n[im];return 0;
}
