JZX102624的秘密基地

你按照x升序y降序排一遍序，按照x升序y升序再排一遍序，两遍一拼合，跑一个贪心就过了。 12345678910111213141516171819202122232425262728293031323334353637383940414243#include<bits/stdc++.h>using namespace std;int n;struct node{ int x,y; bool operator<(const node &r)const{ if(x!=r.x)return x<r.x; return y>r.y; }};bool cmp(node x,node y){ if(x.x!=y.x)return x.x<y.x; return x.y<y.y;}vector<node> v;bool buc[1000005];int main(){ ios::sync_with_stdio( ...

这个稍微难一点。 你先把三棵树建出来，然后随一坨序列进行乱搞。 具体地，你先随一个序列，然后用平面最远点对的方法去迭代直到不能再优化答案。 然后这道题卡时一定要松一点(取3.9s)，因为你迭代一次要花好长好长的时间的，所以如果你卡的比较紧(例如3.975s左右)在洛谷上会T。 代码写的可答辩了，没办法，毕竟这题太难了，正解的前置知识都不会。。。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include<bits/stdc++.h>using namespace std;#define ll long longconst int N=200005;int n,rt,a[N],v[N];ll d[N],ans;mt19937 rd((unsigned long long)new char);struct node{ int b[2*N],cnt;ll dep[ ...

分别按t和w升序和降序排序，然后贪心。 然后再随一些顺序贪心就过了。 1234567891011121314151617181920212223242526272829#include<bits/stdc++.h>using namespace std;#define ll long longll n,m,t[20],w[20],a[20],ans=1234567921234576792ll;mt19937 rd((unsigned ll)new char);inline bool cmp(int x,int y){return t[x]<t[y];}inline bool cmp2(int x,int y){return t[x]>t[y];}inline bool cmp3(int x,int y){return w[x]<w[y];}inline bool cmp4(int x,int y){return w[x]>w[y];}ll calc(){ ...

随一个序列然后贪心即可。 12345678910111213141516171819202122232425#include<bits/stdc++.h>using namespace std;int n,a[55],v[55][55],cnt[55],b[55];vector<int> ans;mt19937 rd((unsigned long long)new char);int main(){ cin>>n; for(int i=1;i<=n;++i)b[i]=i; int x,y; while(cin>>x>>y)v[x][y]=v[y][x]=1,++cnt[x],++cnt[y]; while(1.0*clock()/CLOCKS_PER_SEC<=0.985){ vector<int> g;g.push_back(b[1]); for(int i=2;i<=n;++i){ i ...

和上题类似，考虑随一个序列贪心。 因为没有多测，为保证正确性，考虑卡时。 然后就没什么难的了。 1234567891011121314151617181920#include<bits/stdc++.h>using namespace std;int n,a[25][25],b[1005],g[25][25],ans=2e9;mt19937 rd((unsigned long long)new char);int main(){ cin>>n; for(int i=1;i<=n;++i) for(int j=1;j<=3;++j){int x;cin>>x;a[i][x]=1;} for(int i=1;i<=n;++i)b[i]=i; while(1.0*clock()/CLOCKS_PER_SEC<=0.985){ shuffle(b+1,b+n+1,rd); int cnt=0; for(int i=1 ...

如果整个序列的GCD都不是1，直接输出不可以总司令就行了。 首先你发现一个很傻逼的性质是每个数只有最多2个有用，具体原因是因为一共两组，顶天一组一个。 所以你把那些出现次数多于2个的东西干成2个，然后随机一些序列跑贪心。 更具体地，你随一个序列，然后你贪心地选前面的数GCD起来直到它们的GCD是1，作为第一个序列；然后你去判断第二个序列的GCD是不是1就行了。 代码写的很答辩，轻喷。 12345678910111213141516171819202122232425262728293031323334353637383940#include<bits/stdc++.h>using namespace std;struct node{int x,id;bool operator<(const node &r)const{return x<r.x;}}a[100005],d[100005];int n,b[100005],c[100005],m,e[100005];mt19937 rd((unsigned long l ...

做法：先初始一个解，然后随机两个元素交换，看看能不能达到目标。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include<bits/stdc++.h>using namespace std;int bn[1000005],n,m,t,a[1000005],cur,sum;mt19937 rd(102624);int check(){ for(int i=1;i<=8000;++i){ int x=rd()%m+1,y=rd()%(n-m)+m+1; sum^=a[x];sum^=a[y]; swap(a[x],a[y]); if(sum==cur)return 1; } return 0;}int main(){ ios::sync_with_stdio(0);cin.tie(0); cin>>t; ...

题解我就是不交到洛谷上！ 交互题普遍难度虚高。 这种大便交互题一般有个特别逆天的常数，在这道题上是 $420$。 你考虑那个大常数咋用。 我们发现每次询问的本质是树上到 $u,v,w$ 距离的和最小的节点。 你考虑一个节点被作为答案回答的次数，发现如果这个点的三棵子树的大小为 $a,b,c$ （不足三棵子树的用 $0$ 补全），那么答案就是：$a\times b\times c$。 然后你发现一个很显然的事实，就是你发现出现次数最多的点，是根节点的两棵子树的根。 如果我们得到了那两个根（设为 $r_1,r_2$），那么就可以直接询问 $n-2$ 遍 $(r_1,r_2,i)$，当回答的是 $i$ 的时候，那个 $i$ 就是根，直接输出就行了，证明是显然的。 123456789101112131415161718192021222324252627#include<bits/stdc++.h>using namespace std;mt19937 rd((unsigned long long)new char);int n,h,cnt[1000005],cnt2[100000 ...

3401905d192fe19754b95d6ced40d27a0c7f256cc6b996ad451a253b773b878d45362df11bf6b49d9121b13e0ebb76bb8b5e4644d5bc37518ffebc227b15f64d53849dfea8301a10d602c8b60d3fbf9c5364bdf5c2a2e19f3320b2cb1a3c4186618c29f0b66a35854e638cb3b9f0399d49d54c8ba5494845d50cd51130287a6415e981bcfb4f68d477f3a7441f0e0b8160ab645d1b118b3c1440327359dbcde8d6e6b07c512fb8a2c92b4cf37f5da7670514742870c2e119c1906a8ab2db66cb7d2e0caa6bcc433ab8d19a6b4d4eb6d77632ad1af635a409c0c2ac1ff6e682bb7857e3a540ef26f9fe1dd6c839b50e7e21d029126a212371b ...

题解我就是不交到洛谷上！ 交互题普遍难度虚高。 没那么难，就是题目的trick比较新颖，不是很套路。 设当前询问出来的x在 $[l,r]$ 中，则下一次询问应该询问l个数。 考虑交互库给的结果，实际上是这样的：假如我们现在这次询问后还剩q次，则需要让我们把序列划分成一坨区间，这之中每个区间都能在q-1次询问后得出结果。 考虑dp。设f[i][j]为已知x最小可能是i，还剩j次询问时最大可以得出结果的[i,r]长度。用人话说就是最大可求解的r-i+1。转移就随便枚举区间长度转移。 预处理完dp数组之后，直接按照该数组询问即可。 记得用endl。记得用endl。记得用endl。记得用endl。记得用endl。记得用endl。 123456789101112131415161718192021222324252627282930313233343536#include<bits/stdc++.h>using namespace std;#define ll long longconst ll N=10000;ll f[N+5][6];inline void solve(ll i, ...