优化
- 再稍作分析，不难发现，如果一组内“初始时是关的”的灯为偶数个，那么我们可以 做到只把它们全部打开，也就是说打开了这一组所有的灯
- 如果一组内“初始时是关的” 的灯为奇数个，这个时候我们不能把所有的灯都打开，只好作出让步，选择放弃亮度最小的那盏灯。每一组都如此处理，最后加起来。
Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int manx=1e6+10;
const int mamx = 1e6 + 11;
const ll mod = 2123400401301379571;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar(); int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
int T ,a[manx] ,n ,k ,ans;
bool pd[manx];
inline int Check(int n ,int k ,bool pd[] ,int a[]){
int ret = 0;
for(int i = 1;i <= k;i ++){
int cnt = 0,minx = inf;
for(int j = i; j <= n; j+=k){
ret += a[j];
minx = min(minx ,a[j]);
if(pd[j] == 0) cnt++;//记录零的个数
}
if(cnt % 2 != 0) ret -= minx;
}
return ret;
}
int main(){
T = read();
while(T--){
ans = 0;
n = read(); k = read();
for(int i = 1;i <= n; i++) pd[i] = read();
for(int i = 1;i <= n; i++) a[i] = read();
if(k == 1){
for(int i =1;i <= n; i++) ans += a[i];
}else{
ans = Check(n ,k ,pd ,a);
/*
两种情况，第一个是不翻转1-k,得到的最小值，
第二个是翻转后得到的最小值，
（因为就两种情况前 1-k 翻与不翻）
*/
for(int i = 1;i <= k; i++) pd[i] ^= 1;//pd [i] ---> pd [k] 100 --> 0
ans = max(ans,Check(n ,k ,pd ,a));
}
cout<<ans<<'\n';
}
return 0;
}
T3 铁路网络 (network.cpp)
题面
- 给你一棵有根树，每条边有边权。
- 实现两种操作：
- \(a\). 给某一条路径上所 有边的权值加上一个数；
- \(b\). 询问某棵子树内所有点对的距离和。
思路
显然可以用树链剖分进行操作，和线段树进行维护，
路径修改，求子树间两点路径的总和（不是子树查询）
值得注意的是，点权变边权,操作路径修改是要注意 \(dfn[u]\) 的位置，避免多加，或少加
不妨设点 \(x\) 与它的父亲 \(fa[x]\) 相连的边的权值为 \(p[x]\)，
考虑 \(p[x]\) 会对那些点对产生贡献？
显然是经过 \(x——fa[x]\) 这条边的那些点对。记 \(size_[x]\) 为以 \(x\) 为根的子树的大小。
则经过 \(x——fa[x]\) 的点对有 \(size_[x]×(size_[i] – size_[x])\) 对
于是，子树 \(i\) 内的点 \(x\) 的贡献
\[p[x]\times size_[x]\times size_[i] - p[x] \times size_[x]^2
\]
\[\begin{alignedat}{3}
\sum_{i=1}p[x]\times size_[x]\times size_[i] - p[x] \times size_[x]^2\\
=size_[i]\times \sum_{i=1}(p[i]\times size_[i])-\sum_{i=1}(p[i]\times size_[i]^2)\\
\end{alignedat}
\]
Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
#define ll long long
const int manx = 1e6;
const int mod = 2123400401301379571;
const int inf = 0x3f3f3f3f;
inline int read(){
char c = getchar(); int x = 0, f = 1;
for( ;!isdigit(c);c = getchar()) if(c == '-') f = -1;
for( ;isdigit(c);c = getchar()) x = x*10 + (c^48);
return x * f;
}
struct node{
int v,nxt;
}e[manx];
int head[manx],cnt,n,m,dep[manx],fa[manx],size_[manx],val[manx],pre[manx],tp[manx],dfn[manx],hson[manx];
int js,sigma1,sigma2;
inline void add(int u,int v){
e[++cnt].nxt = head[u];
e[cnt].v = v;
head[u] = cnt;
}
namespace Tree{
#define ls i<<1
#define rs i<<1|1
struct tree{
int l;int r;
ll sum,lazy;
}tr[manx<<3];
inline void up(int i){
tr[i].sum = tr[ls].sum + tr[rs].sum ;
}
inline void down(int i){
if(tr[i].lazy){
ll x = tr[i].lazy ;
tr[ls].sum += (tr[ls].r - tr[ls].l +1)*x;
tr[rs].sum += (tr[rs].r - tr[rs].l +1)*x;
tr[ls].lazy += x;
tr[rs].lazy += x;
tr[i].lazy = 0;
}
}
inline void build(int i,int l,int r){
tr[i].l = l;tr[i].r = r;
if(l == r){
tr[i].sum = val[pre[l]];
return ;
}
int mid = (l + r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
up(i);
}
inline void add(int i,int l,int r,int w){
if(tr[i].l >= l && tr[i].r <= r){
tr[i].sum += (tr[i].r - tr[i].l +1)*w;
tr[i].lazy += w;
return;
}
down(i);
int mid=(tr[i].l +tr[i].r )>>1;
if(mid >= r)add(ls,l,r,w);
else if(mid < l)add(rs,l,r,w);
else add(ls,l,mid,w),add(rs,mid+1,r,w);
up(i);
}
inline ll only_query(int i,int u){
if(tr[i].l == tr[i].r ){
return tr[i].sum ;
}
down(i);
int mid=(tr[i].l +tr[i].r )>>1;
if(mid >= u) return only_query(ls,u);
else if(mid < u) return only_query(rs,u);
}
inline ll query(int i,int l,int r){
if(tr[i].l >= l && tr[i].r <= r){
return tr[i].sum ;
}
down(i);
int mid=(tr[i].l +tr[i].r )>>1;
if(mid >= r)return query(ls,l,r);
else if(mid < l)return query(rs,l,r);
return query(ls,l,mid)+query(rs,mid+1,r);
}
}
namespace Node{
inline void dfs1(int u,int pre,int d){
fa[u] = pre; dep[u] = d;size_[u] = 1;
for(int i = head[u]; i;i = e[i].nxt){
int v = e[i].v ;
if(v != pre){
dfs1(v,u,d+1);
size_[u] += size_[v];
if(!hson[u] || size_[hson[u]] < size_[v]){
hson[u] = v;
}
}
}
}
inline void dfs2(int u,int top){
tp[u] = top;
dfn[u] = ++js;
pre[js] = u;
if(!hson[u])return;
dfs2(hson[u],top);
for(int i = head[u];i;i = e[i].nxt ){
int v = e[i].v ;
if(v != fa[u] && v != hson[u]){
dfs2(v,v);
}
}
}
inline void add(int u,int v,int w){
while(tp[u] != tp[v]){
if(dep[tp[u]] < dep[tp[v]])swap(u,v);
Tree::add(1,dfn[tp[u]],dfn[u],w);
u = fa[tp[u]];
}
if(dep[u]>dep[v])swap(u,v);
Tree::add(1,dfn[u] + 1,dfn[v],w);
}
inline void query(int u){
for(int i = head[u]; i; i = e[i].nxt ){
int v = e[i].v ;
if(v != fa[u]){
Node::query(v);
int s = Tree::only_query(1,dfn[v]);
// cout<<s<<" "<<v<<endl;
sigma1 += (s * size_[v]);
sigma2 += (s * size_[v] * size_[v]);
}
}
return;
}
}
char a[9];
int main(){
//freopen("pp.in","r",stdin);
//freopen("network.out","w",stdout);
n = read();m = read();
for(int i = 1;i < n; i++){
int x = read(), y = read();
val[i+1] = y;
add(i+1,x);
add(x,i+1);
}
Node::dfs1(1,0,1),Node::dfs2(1,1),Tree::build(1,1,n);
for(int i = 1;i <= m; i++){
cin>>a;
ll ans = 0;
ll fan = 0;
int x,y,z;
if(a[0] == 'I'){
x = read(); y = read(); z = read();
Node::add(x,y,z);
}else{
x = read();
sigma1 = 0;
sigma2 = 0;
Node::query(x);
cout<<size_[x] * sigma1 - sigma2 <<endl;
}
}
return 0;
}
感谢观看
