给定一个长度为n的数组。定义S[l, r]为[l,r]的区间和，求前w个S[l, r]为多少？
思路：赛时思路。类似于上场的D题，可以直接二分出第w大的值是多少，且所有权值为正值，二分check，对于每个位置i，满足单调性，同样可以使用双指针。得到第w大的值后，再以每一个位置i进行二分 > w的第一个位置，那么答案为此时以当前位置i为左端点，右端点为[l, n]的区间和。
#include题解解法更加巧妙。（关键还简单好写）
首先给定的数组都为非负值，那么第一大的区间和就为[1, n],那么此时第二大的区间和必在[1, n - 1], [2 , n]之间。假设第二大值为[2, n]，那么第三大的备选答案为[2, n - 1]，[3, n], [1, n - 1]。 依次类推，从备选答案中选可利用优先队列，且要注意判重区间。
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
typedef pair <int, int> PII;
ll a[maxn];
struct note{
int l;
int r;
ll sum;
bool operator < (const note &a) const{
return sum < a.sum;
}
};
map <PII, int> mp;
int main()
{
int n, w;
scanf("%d %d", &n, &w);
ll sum = 0;
for(int i = 1 ; i <= n ; i ++)
scanf("%lld", &a[i]), sum += a[i];
priority_queue <note> pq;
pq.push({1, n, sum});
while(w --)
{
note temp = pq.top();
pq.pop();
printf("%lld ", temp.sum);
if(temp.l <= temp.r - 1 && !mp.count({temp.l, temp.r - 1}))
{
mp[{temp.l, temp.r - 1}] ++;
pq.push({temp.l, temp.r - 1,temp.sum - a[temp.r]});
}
if(temp.l + 1 <= temp.r && !mp.count({temp.l + 1, temp.r}))
{
mp[{temp.l + 1, temp.r}] ++;
pq.push({temp.l + 1, temp.r, temp.sum - a[temp.l]});
}
}
return 0;
}
给定一棵树，求出以哪个点为根节点，所有点到当前点的贡献最小。
u–>v的贡献为
d
i
s
[
u
]
[
v
]
2
∗
c
[
u
]
dis[u][v] ^ 2 * c[u]
dis[u][v]2∗c[u]
非常明显的换根DP。
赛时因为式子推错了，写的超级复杂。。
树形DP，当前节点i的答案都是由儿子节点推出的。
考虑单点贡献公式是否由规律。（为简便，可直接假定为一条直链）
f[4] = 0
f[3] = c * c * c[4]
f[2] = (b + c) * (b + c) * c[4] + b * b * c[3]
f[1] = (c + b + a) * (c + b + a) * c[4] + (b + a) * (b + a) * c[3] + a * a * c[2]
因为为树形DP，直接考虑和儿子节点关系。
可以发现需要维护sumc[i]:以i点为根的子树中所有点权和（包含i号点）。
sum1[i]:以i号点为根的子树中一次项之和。
f[i]:以i号点为根的子树中的点对i号点的贡献
那么转移方程为:（sta为当前节点）
s
u
m
c
[
s
t
a
]
+
=
s
u
m
c
[
s
o
n
]
;
sumc[sta] += sumc[son];
sumc[sta]+=sumc[son];
s
u
m
1
[
s
t
a
]
+
=
s
u
m
1
[
s
o
n
]
+
w
[
i
]
∗
s
u
m
c
[
s
o
n
]
;
sum1[sta] += sum1[son] + w[i] * sumc[son];
sum1[sta]+=sum1[son]+w[i]∗sumc[son];
f
[
s
t
a
]
+
=
f
[
s
o
n
]
+
s
u
m
c
[
s
o
n
]
∗
w
[
i
]
∗
w
[
i
]
+
2
l
l
∗
w
[
i
]
∗
s
u
m
1
[
s
o
n
]
;
f[sta] += f[son] + sumc[son] * w[i] * w[i] + 2ll * w[i] * sum1[son];
f[sta]+=f[son]+sumc[son]∗w[i]∗w[i]+2ll∗w[i]∗sum1[son];
之后考虑换根。(换根DP一定要一步一步推！！！）
up[i]:除以i号点为根的子树中点对当前节点i的贡献
S
U
M
C
[
s
o
n
]
=
S
U
M
C
[
s
t
a
]
+
s
u
m
c
[
s
t
a
]
−
s
u
m
c
[
s
o
n
]
;
SUMC[son] = SUMC[sta] + sumc[sta] - sumc[son];
SUMC[son]=SUMC[sta]+sumc[sta]−sumc[son];
S
U
M
1
[
s
o
n
]
=
(
S
U
M
1
[
s
t
a
]
+
(
s
u
m
1
[
s
t
a
]
−
s
u
m
1
[
s
o
n
]
−
w
[
i
]
∗
s
u
m
c
[
s
o
n
]
)
)
+
w
[
i
]
∗
S
U
M
C
[
s
o
n
]
;
SUM1[son] = (SUM1[sta] + (sum1[sta] - sum1[son] - w[i] * sumc[son])) + w[i] * SUMC[son];
SUM1[son]=(SUM1[sta]+(sum1[sta]−sum1[son]−w[i]∗sumc[son]))+w[i]∗SUMC[son];
up[son]由两部分组成。
第一部分为除以sta点为根的子树对当前节点son的贡献
u
p
[
s
o
n
]
+
=
u
p
[
s
t
a
]
+
S
U
M
C
[
s
t
a
]
∗
w
[
i
]
∗
w
[
i
]
+
2
l
l
∗
w
[
i
]
∗
S
U
M
1
[
s
t
a
]
up[son] += up[sta] + SUMC[sta] * w[i] * w[i] + 2ll * w[i] * SUM1[sta]
up[son]+=up[sta]+SUMC[sta]∗w[i]∗w[i]+2ll∗w[i]∗SUM1[sta]
第二部分为以sta点为根的子树且除以son为根的子树对当前节点son的贡献
u
p
[
s
o
n
]
+
=
f
[
s
t
a
]
−
(
f
[
s
o
n
]
+
s
u
m
c
[
s
o
n
]
∗
w
[
i
]
∗
w
[
i
]
+
2
l
l
∗
w
[
i
]
∗
s
u
m
1
[
s
o
n
]
)
+
(
s
u
m
c
[
s
t
a
]
−
s
u
m
c
[
s
o
n
]
)
∗
w
[
i
]
∗
w
[
i
]
+
2
l
l
∗
w
[
i
]
∗
(
s
u
m
1
[
s
t
a
]
−
s
u
m
1
[
s
o
n
]
−
w
[
i
]
∗
s
u
m
c
[
s
o
n
]
)
up[son] += f[sta] - (f[son] + sumc[son] * w[i] * w[i] + 2ll * w[i] * sum1[son]) + (sumc[sta] - sumc[son]) * w[i] * w[i] + 2ll * w[i] * (sum1[sta] - sum1[son] - w[i] * sumc[son])
up[son]+=f[sta]−(f[son]+sumc[son]∗w[i]∗w[i]+2ll∗w[i]∗sum1[son])+(sumc[sta]−sumc[son])∗w[i]∗w[i]+2ll∗w[i]∗(sum1[sta]−sum1[son]−w[i]∗sumc[son])
const int maxn = 2e5 + 10;
typedef pair <int, int> PII;
int h[maxn], ne[maxn * 2], e[maxn * 2], idx;
ll w[maxn * 2], c[maxn], sumc[maxn], sum1[maxn], SUMC[maxn], SUM1[maxn], f[maxn], up[maxn];
void add(int u, int v, ll ww)
{
w[idx] = ww;
e[idx] = v;
ne[idx] = h[u];
h[u] = idx ++;
}
void dfs1(int sta, int fa)
{
sumc[sta] = c[sta];
for(int i = h[sta] ; i != -1 ; i = ne[i])
{
int son = e[i];
if(son == fa) continue;
dfs1(son, sta);
sumc[sta] += sumc[son];
sum1[sta] += sum1[son] + w[i] * sumc[son];
f[sta] += f[son] + sumc[son] * w[i] * w[i] + 2ll * w[i] * sum1[son];
}
}
void dfs2(int sta, int fa)
{
for(int i = h[sta] ; i != -1; i = ne[i])
{
int son = e[i];
if(son == fa) continue;
SUMC[son] = SUMC[sta] + sumc[sta] - sumc[son];
SUM1[son] = (SUM1[sta] + (sum1[sta] - sum1[son] - w[i] * sumc[son])) + w[i] * SUMC[son];
up[son] = up[sta] + SUMC[sta] * w[i] * w[i] + 2ll * w[i] * SUM1[sta] + f[sta] - (f[son] + sumc[son] * w[i] * w[i] + 2ll * w[i] * sum1[son]) +
(sumc[sta] - sumc[son]) * w[i] * w[i] + 2ll * w[i] * (sum1[sta] - sum1[son] - w[i] * sumc[son]);
dfs2(son, sta);
}
}
int main()
{
int n;
scanf("%d", &n);
memset(h, -1, sizeof(h)), idx = 0;
for(int i = 1 ; i <= n ; i ++)
scanf("%lld", &c[i]);
for(int i = 1 ; i < n ; i ++)
{
int u, v;
ll w;
scanf("%d %d %lld", &u, &v, &w);
add(u, v, w), add(v, u, w);
}
dfs1(1, -1), dfs2(1, -1);
ll res = 2e18;
for(int i = 1 ; i <= n ; i ++)
res = min(res, f[i] + up[i]);
printf("%lld\n",res);
return 0;
}
∑ i = 1 n ∑ j = 1 n ( a [ i ] x o r a [ j ] ) 2 \sum_{i = 1} ^ {n}\sum_{j = 1}^{n} (a[i] \; xor \;a[j]) ^ 2 ∑i=1n∑j=1n(a[i]xora[j])2
思路:考虑xor性质。且经典按位考虑。
先考虑 a [ i ] x o r a [ j ] a[i] \; xor \;a[j] a[i]xora[j]
a [ i ] x o r a [ j ] = ∑ i = 0 31 2 i ( a [ i ] > > i & 1 ≠ a [ j ] > > i & 1 ) a[i] \; xor \;a[j] = \sum_{i = 0} ^ {31}2^{i}\;(a[i] >> i \& 1 \neq a[j] >> i \&1) a[i]xora[j]=∑i=0312i(a[i]>>i&1=a[j]>>i&1)
那么 ( a [ i ] x o r a [ j ] ) ∗ ( a [ i ] x o r a [ j ] ) (a[i] \; xor \;a[j]) * (a[i] \; xor \;a[j]) (a[i]xora[j])∗(a[i]xora[j])为
∑ i = 0 31 2 i ( a [ i ] > > i & 1 ≠ a [ j ] > > i & 1 ) ∗ ∑ j = 0 31 2 j ( a [ i ] > > j & 1 ≠ a [ j ] > > j & 1 ) \sum_{i = 0} ^ {31}2^{i}\;(a[i] >> i \& 1 \neq a[j] >> i \&1) * \sum_{j = 0} ^ {31}2^{j}\;(a[i] >> j \& 1 \neq a[j] >> j \&1) ∑i=0312i(a[i]>>i&1=a[j]>>i&1)∗∑j=0312j(a[i]>>j&1=a[j]>>j&1)
∑ i = 0 31 ∑ j = 0 j = 31 2 i + j ( a [ i ] > > i & 1 ≠ a [ j ] > > i & 1 且 a [ i ] > > j & 1 ≠ a [ j ] > > j & 1 ) \sum_{i = 0} ^ {31}\sum_{j = 0}^{j = 31} 2^{i + j} (a[i] >> i \& 1 \neq a[j] >> i \&1 且 a[i] >> j \& 1 \neq a[j] >> j \&1) ∑i=031∑j=0j=312i+j(a[i]>>i&1=a[j]>>i&1且a[i]>>j&1=a[j]>>j&1)
可以发现且题目不考虑顺序。
那么只需要统计出任意两个数字第i位和第j位分别不相同即可。
对 2 i + j 2 ^ {i + j} 2i+j 取模，可以直接预处理。但可能比较懒，且时间复杂度也能过， 在这里直接计算了。
codell a[maxn], f[35][3][35][3];
const ll mod = 1e9 + 7;
ll get_mod1(ll a, ll b)
{
return (a % mod + b % mod) % mod;
}
ll get_mod2(ll a, ll b)
{
return (a % mod * (b % mod)) % mod;
}
ll ksm(ll base, ll power)
{
ll res = 1;
while(power)
{
if(power & 1)
res = get_mod2(res, base);
base = get_mod2(base, base);
power >>= 1;
}
return res;
}
int main()
{
int n;
scanf("%d", &n);
for(int i = 1 ; i <= n ; i ++)
scanf("%lld", &a[i]);
for(int i = 1 ; i <= n ; i ++)
{
for(int j = 0; j <= 31 ; j ++)
{
for(int k = 0; k <= 31 ; k ++)
{
f[j][a[i] >> j & 1][k][a[i] >> k & 1] ++;
}
}
}
ll res = 0;
for(int i = 0 ; i <= 31 ; i ++)
{
for(int j = 0; j <= 31 ; j ++)
{
for(int ii = 0; ii <= 1 ; ii ++)
{
for(int jj = 0; jj <= 1 ; jj ++)
{
res = get_mod1(res, get_mod2(ksm(2ll, (i + j) * 1ll), get_mod2(f[i][ii][j][jj],f[i][ii ^ 1][j][jj ^ 1])));
}
}
}
}
printf("%lld\n",res % mod);
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）