#include<bits/stdc++.h> #define LL long long using namespace std; const int M=1e5+7; int n,cnt; LL a[M]; map<LL,int> mp; LL check(LL x){ LL ret=(x&1)^0; for(LL bit=1;bit<=63;bit++){ LL u1=(x&(1ll<<(bit-1)))?1:0; LL u2=(ret&(1ll<<(bit-1)))?1:0; LL v1=(x&(1ll...

题目大意:                          参考代码: #include<bits/stdc++.h> #define LL long long using namespace std; const int M=1e6+7; int n,k,T; LL B[M],pre[M],A[M],c[40]; LL vis[40]; int main(){ scanf("%d",&T); while(T--){ int f=0; scanf("%d%d",&n,&k); pre[0]=0; for(int i=1;i<n;i++){ scanf...

题目大意: 给定一棵树，每个点选择黑、白有对应的代价。定义一棵树的收益为所有黑白点对间路径边权最大值的和 问如何选择每个点的颜色使得收益−-−代价最大？n≤3000n\le3000n≤3000 分析:因为要考虑路径中边的最大值，所以我们可以从小到大考虑每条边，建立KruskalKruskalKruskal重构树，将问题转换为树形DP,可以设dpi,jdp_{i,j}dpi,j​表示在iii子树内选了jjj个黑点的最大答案,记i的左儿子为lsonlsonlson,右儿子为rsonrsonrson,blackblackblack表示iii子树内黑点个数,枚举左子树的黑点数black1black1b...

题目大意: 给定一个长度为 nnn 的非负整数数组 aaa，保证 aaa 中元素至少有 n−1n−1n−1 个数字互不相同。 求 aaa 的长度为 kkk 的不同子序列的方案数，输出答案取模1e9+71e9+71e9+7的结果。 解题思路:关注什么时候的子序列会重复，会发现在下图中，影响的子序列是不包含下标333至555的数且选择了一个重复的数   推广:::设重复的数的下标为 pos1,pos2(pos1<pos2)pos1,pos2(pos1<pos2)pos1,pos2(pos1<pos2),总方案数易知为CnkC^k_nCnk​,重复的方案为只选择一个重复的数,且不再...

题目大意:：给定长度为nnn的数列a[]a[]a[]，定义f(l,r)=⊕i=lra[i]f(l,r)=\oplus^r_{i=l}a[i]f(l,r)=⊕i=lr​a[i],求下式: ∑1≤l1≤r1≤l2≤r2≤l3≤r3≤nf(l1,r1)∗f(l2,r2)∗f(l3,r3)\sum\limits_{1\le l1\le r1 \le l2 \le r2 \le l3 \le r3 \le n} f(l1,r1)*f(l2,r2)*f(l3,r3)1≤l1≤r1≤l2≤r2≤l3≤r3≤n∑​f(l1,r1)∗f(l2,r2)∗f(l3,r3) 其中1≤n≤2∗105,1≤m≤2∗105...

题目大意:在坐标轴的第一象限有个点,给定,和点的扩散速度(按圆形扩散，范围相交视为在同一连通块上)，给定个询问，询问时间为时连通块的数量 分析:不妨将每个点两两连边，边的权值为两点成为同一连通块的时间,可以发现此时问题便转化成求这张图的最小生成树类的问题，求出连通块数量减少时的时间。对于问题采用离线处理，易求出答案 参考代码: ">#define LL long long using namespace std; const int M=1005; int n,q; struct Edge{ int u,v; double w,tim; }e[M*M]; struct Node{ int v...

题目大意：构造一个长度为nnn的排列，使得满足mmm个约束条件： 区间逆序对个数是奇数或偶数。满足这些约束条 件的区间包含或不相交.(1≤n,m≤103)(1\le n,m\le 10^3)(1≤n,m≤103) 分析：关注其保证区间不相交，即：  所有的区间不相交或包含意味着这些区间可以构成一个树形结构。将区间视为一个点，可发现区间构成了一棵树。不妨建立一个000号区间作为根节点,范围111至nnn（即包含所有的区间),接下来，为了使代码更为简洁，可以建立nnn个长度为111的叶节点，再进行 DFSDFSDFS： 由于小区间的改变更为灵活，我们的换数字可从小区间开始(起始排列为111至nnn...

思路:首先考虑到sizei+1>sizeisize_{i+1}> size_isizei+1​>sizei​，所以当m>nm>nm>n时，只用保留最后nnn次即可。(前面的操作都取不到奶酪，可以去除 ) 接下来发现，每次操作一定是拿 走或破坏一个前缀的奶酪，所以如果我们知道了一个区间用大小为所少的包至多可以获得多少价值的奶 酪的话，可以写出 dpi,jdp_{i,j}dpi,j​表示当前已经拿走/破坏到了第i个奶酪，并且进行到了第j个操作，然后我们发现预处理可以使用区间转移:定义fi,j,kf_{i,j,k}fi,j,k​表示区间 i至j 背包容量为k时能获...

原题题面：https://ac.nowcoder.com/acm/contest/33195/K 题目大意：给定包含n(1≤n≤5000)n( 1 ≤ n ≤ 5000 )n(1≤n≤5000)个点的树T=(V,E)T=(V,E)T=(V,E),节点iii有权值aia_iai​,每条边也具有一定的边权值. 求子集S ⊆ V，满足最多有k(2≤k≤5)k(2\le k\le5)k(2≤k≤5)个点具有不同的权值，且最大化“生成边”的权值和。边eee是生成边，当且仅当存在u,v∈Su,v\in Su,v∈S,边eee在u,vu,vu,v的简单路径上。 输出最大的“生成边”的权值和。 分析： 此题的...

原题题面：https://ac.nowcoder.com/acm/contest/33195/H 题目大意： 你的血量为A(A>0)A(A>0)A(A>0),拥有最多7个随从，血量分别为a1,a2,a3…a7(ai>=0,若随从不存在则ai=0)a_1,a_2,a_3…a_7(a_i>=0,若随从不存在则a_i=0)a1​,a2​,a3​…a7​(ai​>=0,若随从不存在则ai​=0) 同样，你的对手的血量为B(B>0)B(B>0)B(B>0),拥有最多7个随从，血量分别为b1,b2…b7(bi>=0,若随从不存在则bi=0)b_1...

原题题面：https://ac.nowcoder.com/acm/contest/33195/F 题目大意： 给定可能有重边的无向图G=(V,E)G=(V,E)G=(V,E),和两个点s,t∈Vs,t\in Vs,t∈V，最初在s点有一个令牌，两个玩家Join Player.Cut Player轮流执行以下操作，Cut Player先手. :如果轮到Join Player,假如令牌在点uuu,则选择边(u,v)∈E(u,v)\in E(u,v)∈E,删除它并将令牌移动到vvv. :如果轮到Cut Player,假如令牌在点uuu,则选择边(u,v)∈E(u,v)\in E(u,v)∈E,删除它...