sol 7以下题目按照难度顺序给出M签到#includebits/stdc.h#define int long long#define pii pairint,int#define endl \n#define fi first#define se second#define dbg(x) cout#x xendl;#define dbg2(x,y) cout#x x #y yendl;#define dbg3(x,y,z) cout#x x #y y #z zendl;#define forn for(int i1;in;i)#pragma GCC optimize(2)using namespace std;void solve(){int n,m;cinnm;int kkn*(n-1)/2;if(mkk){cout0\n;return;}//最大就是n-1if(mn-1){int ans(1m-1)*(m-1)/2;coutans\n;return;}else{int ans(1n-2)*(n-2)/2;ans-(m-(n-1));coutans\n;return;}}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T1;cinT;while(T--){solve();}return 0;}N签到#includebits/stdc.husing namespace std;#define int long longvoid solve(){int n,k;cinnk;vectorinta(n1),pre(n5);int sum0;for(int i1;in;i)cina[i];sort(a.begin()1,a.end());for(int i1;in;i){suma[i];pre[i]pre[i-1]a[i];}if(k1){int hfk/2;int Max-1e18;for(int ihf1;in-hf;i){int numa[i];// coutnumendl;int dtk*num-pre[hf]-(pre[ihf]-pre[i-1]);Maxmax(Max,dt);}coutsumMax\n;return;}else{int hf(k)/2;int Max-1e18;for(int ihf;in-hf;i){double num1.0*(a[i]a[i1])/2.0;//coutnumendl;int dt1.0*k*num-pre[hf-1]-(pre[ihf]-pre[i-1]);//int Dt(int)dt;Maxmax(Max,dt);}coutsumMax\n;return;}}signed main(){int _t;cin_t;while(_t--){solve();}}B;线性基模板题注意到所有数的亦或和固定则对这个sumxor来说它是1的维度被拆分也是1 0对和没有影响而原来是0的维度我们则希望将它拆成 1 1对和的增量为拆出来的数*2ab(a^b)(ab)*2把所有数xor xorsum为1的位建立线性基从高位往低位贪心的取求最大值最后的贡献就是这个Max*2;#include bits/stdc.husing namespace std;using LL long long;#define endl \nLL mod998244353;LL ksm(LL a,LL n){LL res1;while(n){if(n1)resres*a%mod;n/2;aa*a%mod;}return res%mod;}void solve(){LL n;cinn;vectorLLa(n1);LL ans0;for(int i1;in;i){cina[i];ans^a[i];}vectorLLf(60);LL ans20;for(int i1;in;i){for(int j32;j0;j--){if((ansj)1){if((a[i]j)1){a[i]-(1llj);}//ans2|(1llj);}}for(int j32;j0;j--){if((a[i]j)1){if(f[j]){a[i]^f[j];}else{f[j]a[i];break;}}}}ans2ans;ans-ans2;LL ans10,x0;for(int i32;i0;i--){// if((xi)1)continue;if((x^f[i])x)x^f[i];}ans1(x^ans)x;cout2*xans2endl;}int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);LL T1;// build();cinT;while(T--){solve();}}L对于一组1≤ipj 则如果Api Ap j 则对打乱后逆序对变化的贡献是1 因为一开始是逆序对后来不是了否则对打乱后逆序对变化的贡献是 −1 。 所以只需考虑p的逆序对打乱前后逆序对的差的绝对值就是这些贡献 和的绝对值。因为这些贡献绝对值都是1能否让这些逆序对对结果的贡献都是同方 向的即都是1或−1让整体变动的绝对值最大化呢 答案是肯定的A[1,2,...,n] 正是这样的一个排列。 所以我们要求的就是对于p中所有的逆序对(i,j)(1≤iAj 的排列A的个数。 根据这些大小关系可以建立一个从小的数指向大的数的一个有向图 我们相当于要求其拓扑序个数。考虑一个还没确定拓扑序的子集S对应的答案是dp[S]我们可以任意 去除一个子集中对它没有入边的点u则我们可以将dp[S−{u}]转移 到dp[S] 中去。#include bits/stdc.husing namespace std;using LL long long;#define endl \nLL mod998244353;LL ksm(LL a,LL n){LL res1;while(n){if(n1)resres*a%mod;n/2;aa*a%mod;}return res%mod;}mt19937 rnd(time(0));void solve(){LL n;cinn;vectorLLp(n1),b(n1);for(int i1;in;i){cinp[i];}int f0;vectorvectorLLedag(n1);vectorLLdep(n1);for(int i1;in;i){for(int ji1;jn;j){if(p[i]p[j])edag[i-1].push_back(j-1),f1,dep[j-1];}}if(!f){LL ans1;for(int i1;in;i){ans*i;ans%mod;}coutansendl;return;}vectorLLdp(1LLn);dp[0]1;auto dfs[](autoself,int x)-LL{if(x0)return 1;vectorLLa;for(int in;i0;i--){if((xi)1){a.push_back(i);}}LL res0;for(int x1:a){if(dep[x1])continue;for(int y:edag[x1]){dep[y]--;//dep[y];}if(dp[(x^(1llx1))]0)resself(self,x^(1llx1));else resdp[(x^(1llx1))];res%mod;for(int y:edag[x1]){dep[y];}}dp[x]res;return dp[x]%mod;};LL ansdfs(dfs,(1lln)-1);cout2*ans%modendl;}int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);LL T1;// build();// cinT;while(T--){solve();}}G如果存在一个质数p在u,v之间则dis(u,v) 不超过 u→p的 边权加上p→v的边权因此答案不超过2。所以我们想到预处理1x)间存在的与n gcd 1 的数1.莫比乌斯反演 直接处理2.容斥定理某个区间含有因数p的数的个数是len/p,所有数-含单个因数的数含两个因数的数...(其实本质就是莫比乌斯反演但是考虑当区间被缩减到一个较小区间不一定存在这样一个质数所以我们考虑在临界开始dp求解暴力dp即可code:#includebits/stdc.husing namespace std;#define int long longvectorintins;int k;int n;int calc(int x){if(x0)return 0;int Mask(1k);int cnt0;for(int i0;iMask;i){int num1;int bits0;for(int j0;jk;j){if((ij)1){num*ins[j];bits;}}if(bits1)cnt-(x/num);else cnt(x/num);}return cnt;}void solve(){ins.clear();int l,r;cinlrn;int tmpn;for(int i2;i*itmp;i){if(tmp%i0){ins.push_back(i);while(tmp%i0)tmp/i;}}if(tmp1)ins.push_back(tmp);kins.size();int ans0;int nrmin(r,n-150-1);if(lnr){int lennr-l1;int xxcalc(nr)-calc(l-1);ans2*len-xx;}int stmax(l,n-150);if(str){int lenn-st1;vectorintdp(len);dp[n-st]0;for(int in-1;ist;i--){int Max__gcd(i,n);for(int ji1;jn;j){Maxmin(Max,__gcd(i,j)dp[j-st]);}dp[i-st]Max;}for(int ist;ir;i){ansdp[i-st];}}coutans\n;}signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);int _t;cin_t;while(_t--){solve();}}H0 ∼2n−1 中的数中二进制表示中有奇数个1的数有偶数个偶数个 1 的数也有偶数个。 而配对的两个数满足二进制表示中1的个数的奇偶性相同因此选取的 a, b 的二进制表示中1的个数的奇偶性也相同否则无法构造。 对于奇偶性相同的情况如何构造呢 有很多办法这里给出一个比较不需要动脑的。首先我可以将所有配 对的数都异或上一个a这不影响配对关系。同时我们可以将二进制 不同的位进行重新映射把所有b当前是1的位全部都挪到最低的位上 去。也就是可以将题目转化为删去0,22k−1的情况。 对于22k ∼2n−1 的数可以将每个数和它异或3的结果匹配。 k 1 的方案是显然的。 我们可以在删去0,22k−1 的对应方案的基础上构造删去0,22(k1)−1 的方案。 设V22k−1 则将(V,2V) 和(2V⊕3,4V) 匹配即可这样相当于拆 掉了原有的(2V,2V⊕3) 和 (4V,4V⊕3) 而重新构造了两对同时也让 没有匹配的数从V变成了4V3。 时间复杂度为O(2n) 。#include bits/stdc.husing namespace std;int main() {ios_base::sync_with_stdio(false);cin.tie(0);int t;cin t;while (t --) {int n, x, y, c 0;cin n x y;for (int i 0; i n; i ) c (x ^ y) i 1;if (c 1) cout No\n;else {cout Yes\n;int diff x ^ y, k c;vectorint pairing(1 n);for (int i 0; i (1 n); i ) {pairing[i] i ^ 3;}pairing[0] 0;pairing[3] 3;for (int i 2; i k; i 2) {int cur (1 i) - 1;pairing[cur] cur 1;pairing[cur 1] cur;pairing[(cur 1) ^ 3] cur 2;pairing[cur 2] (cur 1) ^ 3;pairing[(cur 2) ^ 3] (cur 2) ^ 3;}vectorint vals {0};for (int i 0; i n; i ) {if (diff i 1) {int cur_len vals.size();for (int j 0; j cur_len; j ) {vals.emplace_back(vals[j] ^ (1 i));}}}for (int i 0; i n; i ) {if (!(diff i 1)) {int cur_len vals.size();for (int j 0; j cur_len; j ) {vals.emplace_back(vals[j] ^ (1 i));}}}for (int i 0; i (1 n); i ) {if (pairing[i] i) {cout (vals[i] ^ x) (vals[pairing[i]] ^ x) \n;}}}}return 0;}F首先如果对于一棵树其最大边权为W则该树最大极差的最小值 不超过2W−1。证明直接对根节点赋值X接下来从根节点出发进行搜索每个新搜 索到的点一定能在[X−W,XW)区间内找到一个可行的权值。令dp[u][x]表示当前根为u当前节点取x情况下子树最大节点的最小值而因为所有节点的值可以同时平移所以节点的最小值一定为0则这个Min of Max 也可以表示子树最大极差对于叶子节点它取几这个最大节点的最小值就是几所以for(intj0;jMax;j)dp[u][j]j;考虑转移 对于一个节点的固定值x它的下级节点只能是x-w或者xw;所以intvainf;if(x-V.y00)vamin(va,dp[V.x0][x-V.y0]);if(xV.y0Max)vamin(va,dp[V.x0][xV.y0]);我们贪心的取最小dp[u][x]max(dp[u][x],va);取Max的原因是要求全部满足然后独立求解每颗子树即可for(intx0;xMax;x)ans[u]min(ans[u],dp[u][x]);#includebits/stdc.h#define int long long#define inf 0x3f3f3f3f3f3f3f#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define cnot coutNO\n#define cyes coutYES\n#define cans coutans\n#define pb push_back#define x0 first#define y0 second#define lc p1#define rc p1|1#define mem(a,b) memset(a,b,sizeof(a))#define sp(x) fixedsetprecision(x)#define all(v) v.begin(),v.end()#define fr(i,st,ed) for(int ist;ied;i)#define ffr(i,st,ed,dt) for(int ist;ied;idt)using namespace std;typedef pairint,stringPis;typedef pairint,intPii;typedef pairstring,stringPss;const int N1e55,mod998244353,M5000;int lowbit(int x){return x(-x);}vectorPiig[N];//int dp[N][M];int f[N],fv[N];void init(int n){fr(i,1,n){g[i].clear();f[i]0;fv[i]0;}//memset(dp,0,sizeof(dp));}void solve(){int n;cinn;init(n);int u,v,w;int Max0LL;fr(i,2,n){cinuvw;g[u].pb({v,w});g[v].pb({u,w});Maxmax(Max,w);}Max1;vectorvectorintdp(n1,vectorint(Max1));//dp[节点][当前节点值] 子树节点最大权值的最小值vectorintnode;queueintq;//node.pb(1);f[1]-1;fv[1]0;q.push(1);while(!q.empty()){int tq.front();q.pop();node.pb(t);for(Pii V:g[t]){if(V.x0f[t])continue;f[V.x0]t;fv[V.x0]V.y0;//node.pb(V.x0);q.push(V.x0);}}vectorintans(n1,0);for(int in-1;i0;i--){int unode[i];for(int j0;jMax;j)dp[u][j]j;for(Pii V:g[u]){if(f[V.x0]!u)continue;for(int x0;xMax;x){int vainf;if(x-V.y00)vamin(va,dp[V.x0][x-V.y0]);if(xV.y0Max)vamin(va,dp[V.x0][xV.y0]);dp[u][x]max(dp[u][x],va);//ans[u]min(ans[u],dp[u][x]);}}ans[u]inf;for(int x0;xMax;x)ans[u]min(ans[u],dp[u][x]);}for(int i1;in;i)coutans[i] ;cout\n;}signed main(){GG;int _t1;cin_t;while(_t--){solve();}}