从江网站建设,河北省网络科技网站,贵阳网站建设方案维护,建设网站公牛客小白月赛66_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)冒着期末挂科的风险打了打#xff0c;缓解了一下网瘾#xff0c;感觉还行最近为了期末鸽了很多期的div3#xff0c;一学期末就手痒想训#xff0c;感觉再不打人要没了#xff0c;结果…牛客小白月赛66_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)冒着期末挂科的风险打了打缓解了一下网瘾感觉还行最近为了期末鸽了很多期的div3一学期末就手痒想训感觉再不打人要没了结果就是预习期末也预习不进去比赛也没打这几天不知道在干什么白白的浪费时间19号才全部考完还有8天才训练自由md心情非常不愉悦啊A-先交换小分类讨论题意思路分类讨论即可#include bits/stdc.h
#define int long long
const int mxn2e510;
const int mxe2e510;
using namespace std;int n;
int a[mxn];
void solve(){cinn;for(int i1;in;i) cina[i];int ok0;for(int i2;in;i){if(a[i]a[1]a[i]%21) ok1;}if(a[1]%21) cout0\n;else if(oka[1]%20) cout1\n;else cout-1\n;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __1;cin__;while(__--)solve();return 0;
}B-再交换构造小分类讨论题意思路构造题交换的两个数的位置一定是特殊的考虑ij的情况进行交换这样就是小分类讨论注意特判的情况当两个串串完全相同时不代表无解还可以交换别的数来满足条件在a数组找到第一个不是最小值的数在b数组找到最后一个最小值进行交换即可#include bits/stdc.h
#define int long long
const int mxn2e510;
const int mxe2e510;
using namespace std;int n;
string s,t;
void solve(){s.clear(),t.clear();cinn;cinst;s s;t t;int mi1e9;for(int i1;in;i){mimin(mi,s[i]-a1ll);if(s[i]t[i]) continue;else if(s[i]t[i]){if(in) cout1 1\n;else coutn n\n;return;}else{couti i\n;return;}}int ansi;for(int in;i1;i--){if(t[i]-a1mi){ansii;break;}}int p1;while(s[p]-a1mi) p;if(p!1) coutp p-1\n;else{cout1 ansi\n;}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __1;cin__;while(__--)solve();return 0;
}C-空洞骑士构造大小分类讨论思路首先这题是让我们构造位置那位置肯定是特殊的考虑一个0到1e9的数轴中间的金币是随机分配的我们只需要记录第一个金币和最后一个金币的位置然后去考虑起点s的位置三种情况s0s中间某个位置s1e9画个图就可以发现s为中间那个位置的贡献一定比另外两种小如果s在中间贡献差不多就是1.5个p_end-p_start但是如果s0或1e9贡献显然2*(p_end-p_start)所以第二种情况可以直接淘汰了那么讨论另外两种情况然后算一算贡献就行当s0时t取1e9或1两种情况算贡献取大的那个当s1e9t1e9-1或1两种情况算贡献取大的那个我自己在写的时候把中间的那种情况也算进去了但是不影响ac#include bits/stdc.h
#define int long long
const int mxn2e510;
const int mxe2e510;
const int end_p1000000000;
using namespace std;int m;
int p[mxn];
void solve(){cinm;int p_mx-1e9,p_mi1e9;for(int i1;im;i){cinp[i];p_mxmax(p_mx,p[i]);p_mimin(p_mi,p[i]);}sort(p1,p1m);int mx-1e9,ansi;for(int i1;im;i){if(mxmin(p_mx-p[i],p[i]-p_mi)){mxmin(p_mx-p[i],p[i]-p_mi);ansip[i];}}int a1max(p_mxp_mx-1ll,(long long)1e9);int a3((1e9-1)-p_mip_mi?(1e9-1)-p_mi:p_mi)1e9-p_mi;int a2min(p_mx-ansi,ansi-p_mi)p_mx-p_mi(p_mx-ansiansi-p_mi?p_mi:1e9-p_mx);int ans_amax(max(a1,a2),a3);//couta3\n;if(ans_aa1){if(p_mx-11e9-p_mx) cout0 1\n;else cout0 end_p\n;}else if(ans_aa2){if(p_mx-ansiansi-p_mi) coutansi 0\n;else coutansi end_p\n;}else{if(1e9-1-p_mip_mi) coutend_p end_p-1\n;else coutend_p 0\n;}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __1;//cin__;while(__--)solve();return 0;
}D-障碍枚举前缀和题意思路这道题只需要注意到x的取值范围那么就很好做了关键是比赛的时候还注意不到L最大取2e5那么x最大就是500如果超过500那么答案就会是负的遇到小数据我们考虑暴力枚举就好了去枚举拿掉多少个障碍然后去维护最大的答案值#include bits/stdc.h
#define int long long
const int mxn2e510;
const int mxe2e510;
using namespace std;int n,m,x;
int a[mxn];
void solve(){cinnm;for(int i1;im;i) cina[i];a[0]0,a[m1]n;int ans-1e9;for(int len0;len500;len){for(int l0;lm;l){int rllen1;ansmax(ans,a[r]-a[l]-len*len);}}coutans\n;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __1;//cin__;while(__--)solve();return 0;
}E生成树与路径图论构造题意思路关于图论的构造还没怎么写过这道题的构造条件是1.n个点m条边2.最小生成树的大小是最短路大小3.特殊条件是边是个排列对于第一个条件考虑构造1到n的一条链并边长是1-n-1这样就满足了第一个条件然后因为要m条边所以我们要继续连边但是在连边的过程中要保证第一个条件我们考虑这样连边#include bits/stdc.h
#define int long long
const int mxn2e510;
const int mxe2e510;
using namespace std;int n,m,u,v,idx0;
void solve(){idx0;cinnm;for(int len2;lenn;len){for(int l1;llen-1n;l){int rllen-1;coutl r idx\n;if(idxm) return;}}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __1;cin__;while(__--)solve();return 0;
}F-球球大作战贪心反证法(?)二分题意思路我们要求的是对于一个球是否存在一种方法使得这个球作为最终的胜利者首先是一个结论其他n-1个球自相残杀之后再和这个球去碰撞这样这个球是最大值证明反证法如果该球和其他任意一个球撞击若这个球比较小直接输掉若这个球比较大权值变成(a1a2)/2且a2a1所以权值不会变大证毕那么其他n-1个球该怎么去撞可以最小化这n-1个球碰撞后的值呢求出最好情况就可以看是否存在解法了另一个结论就是这n-1个球从小到大排好序之后最大值和次大值碰撞可以使n-1个值碰撞之后的值最小另外n-1个球是无序的所以可以考虑排序证明反证法考虑三个球直接去计算它们的贡献注意到a1的贡献除了2a2和a3的贡献除了4因此先撞大的球会使贡献变小证毕如果我们就这样去枚举球复杂度是O(n2)的肯定T但是对于两个球如果权值较小的那个球都有解的可能性那权值较大的一定有解因为权值较小的球其他n-1个球碰撞之后的权值一定比除了那个权值较大的球其他n-1个球碰撞之后的权值来的大所以满足了单调性直接去二分刚好有解的权值的下标就好了前提是数组排好序#include bits/stdc.h
#define int long long
const int mxn2e510;
const int mxe2e510;
using namespace std;int n,ans;
int a[mxn],b[mxn];
bool check(int x){int ansa[n];for(int in-1;i1;i--){if(ix) continue;ansa[i];ans/2;}return ansa[x];
}
void solve(){cinn;for(int i1;in;i) cina[i],b[i]a[i];sort(a1,a1n);int l1,rn;while(lr){int midlr1;if(check(mid)){ansmid;rmid-1;}else lmid1;}//coutans\n;int sa[ans];for(int i1;in;i){if(b[i]s) cout1;else cout0;}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __1;//cin__;while(__--)solve();return 0;
}
