牛表 40point P≤500{P\le 500}P≤500，建边跑弗洛伊德算法，时间复杂度为O(n3)O(n^3)O(n3)。 意外的是评测机跑得非常快，导致暴力分超出预期。 100point 跑P−1{P-1}P−1次迪杰斯特拉算法，但是边数是满的，直接跑的复杂度是O(P3){O(P^3)}O(P3)。 考虑如何优化，通过打表可以观察到其实答案非常的小，我们可以假设答案不超过lim{lim}lim，那么用点u{u}u去更新的时候只需要转移到[max(1,u−lim),min(P−1,u+lim)][{max(1,u-lim),min(P-1,u+lim)]}[max(1,u−lim),m...

中位数 设是升序的，若，则，答案为。否则，无论如何第小的数都不会是最后得到的数组中第小的数，此时只需把所有操作都加到第个。时间复杂度。 #include<bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int N=2e5+5; void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);} int n,k; ll a[N]; int main() { int t;scanf("%d&q...

中位数 设是升序的，若，则，答案为。否则，无论如何第小的数都不会是最后得到的数组中第小的数，此时只需把所有操作都加到第个。时间复杂度。 #include<bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int N=2e5+5; void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);} int n,k; ll a[N]; int main() { int t;scanf("%d&q...

【题解】牛客挑战赛50@[toc]UPD: 非常抱歉，C题数据弱了，在回文树上暴力跳父亲的代码是不应该通过的，数据已增强。 致谢 感谢清楚姐姐、验题人和内测人员背后辛勤的付出和提供的意见！ A Red and Blue and Green 感谢兰子哥哥提供的暖心签到题！对于所有偶数位置，将它的颜色修改成和两边不同的颜色。 #include<bits/stdc++.h> #define inf 0x3f3f3f3f typedef unsigned long long ull; typedef long long ll; #define rep(i,l,r) for(int i=l;...

C：为啥你们的NTT跑这么快，我把输入改成快速，vector改成数组才能勉强卡过，主要时间消耗还是在NTT上

A：怪盗-1412 将序列排列成,这样可以得到最大化的子序列数量，答案为，时间复杂度。标程：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43780345 B：Dis2 与每个点距离为的点为这个点的度数。对于每个点，枚举和它有边相连的点，点对点的贡献为与点距离为的点的个数减去（减掉这个点），时间复杂度。标程：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43780359 C：序列卷积之和 设。设+。则预处理前缀和统计前缀和出现的...