# NK 0827 练习赛反思

NK 0827 练习赛反思

小小总结
期望得分 200 实际得分 210 还算可以的啦但还是要继续加油要稳住不要翻车的啊

A 异或

题面描述
何老板给你一个长度为(N)的整数数列。
请你帮他找出满足下列条件的数字对([l,r]) 的个数：
(a_l)^$a_{l+1}$(a_{l+2})...(a_r)=(a_l)+(a_{l+1})+(a_{l+2})...(a_r)
"(xor)"表示“异或”，对应c++中的符号是"^"
输入格式
第一行，一个整数
第二行，个空格间隔的整数
输出格式
一个整数，表示满足条件的数字对的个数

解：

双指针的裸题
首先异或被称为"不进位的加法"
那么区间就满足单调性
所以我们可以用双指针每次右指针扩展然后左边指针移动到合法位置中间的都行
code:

//
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll sum;
ll n;
#define maxnn 400000
ll a[maxnn];
ll tot=0;
int main() {
//	freopen("axor.in","r",stdin);
	//freopen("axor.out","w",stdout);
	scanf("%lld",&n);
	for(int i=1; i<=n; i++) {
		scanf("%lld",&a[i]);
	}
	sum=a[1];
	int now=1;
	for(int i=2; i<=n; i++) {
		if((sum^a[i])==sum+a[i]) tot+=i-now+1,sum+=a[i];
		else {
			while((sum^a[i])!=sum+a[i]) {
				sum^=a[now];
				now++;
			}
			sum+=a[i],tot+=i-now+1;
		}
	}
	printf("%lld",tot+1);
}

 2.二分+倍增的裸题

我们注意到区间具有单调性并且数据比较大所以可以考虑二分+倍增确定区间的起点然后跳到合法的最远的区间

code 已死

B 管辖

问题描述
何老板给你一棵树，树中共N个节点，编号1到N，1号点为根。
每个节点都有一个权值，其中第i个节点的权值为 (a_i)
树中共有(N-1)条边，每条边都有一定的长度，第i条边长度为 (w_i) 。
对于树中任意一点i,从i出发往根的路径中，距离i不超过(a_i)的点，都可以管辖i号点。
何老板想知道，每个点管辖的点有多少个(不包括自己)。他拜托你帮忙计算一下。

解：

倍增+树上差分的裸题
不过好像很多据老都写挂了.....
code:

//
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define  iuiu 200100
#define maxn  200100
#define ll long long
ll dis[iuiu][20];
int f[iuiu][20];
int n;
int w[maxn];
int las[maxn],en[maxn],tot,nex[maxn];
int  cnt[maxn],le[maxn];

void add(int a,int b,ll c) {
	en[++tot]=b;
	nex[tot]=las[a];
	las[a]=tot;
	le[tot]=c;
}
int go_up(int s,int v) {
	int u=ceil(log2(n));
	for(int k=u; k>=0; k--) {
		if(f[v][k]&&(s>=dis[v][k])) {
			s-=dis[v][k];
			v=f[v][k];
		}
	}
	return v;
}
void dfs(int v,int fa,int l) {
	f[v][0]=fa;
	dis[v][0]=l;
	int u=ceil(log2(n));
	for(int i=1; i<=u; i++) {
		f[v][i]=f[f[v][i-1]][i-1];
		dis[v][i]=dis[v][i-1]+dis[f[v][i-1]][i-1];
	}
	for(int i=las[v]; i; i=nex[i]) {
		int t=en[i];
		if(t!=fa) {
			dfs(t,v,le[i]);
			cnt[v]+=cnt[t];
		}
	}
	return ;
}
int main() {
	//freopen("brun.in","r",stdin);
	//freopen("brun.out","w",stdout);
	scanf("%d",&n);
	int x,y;
	for(int i=1; i<=n; i++) {
		scanf("%d",&w[i]);
	}
	for(int i=2; i<=n; i++) {
		scanf("%d%d",&x,&y);
		add(x,i,y);
	}
	dfs(1,0,0);
	for(int i=1; i<=n; i++) {
		int r=go_up(w[i],i);
		{
			cnt[f[i][0]]++;
			cnt[f[r][0]]--;
		}
	}
	dfs(1,0,0);
	for(int i=1; i<=n; i++) {
		printf("%d ",cnt[i]);
	}
}

2.搜索回溯+二分查找
注意到这是一条链对于每一个深度都是一个被争抢的资源
所以我们可以从根节点开始搜索然后二分查找
code:

//  
#include<stdio.h>  
#include<bits/stdc++.h>  
using namespace std;  
#define  iuiu 400100  
#define maxn  400100  
#define ll long long  
int n;  
ll f[maxn]; 
ll w[maxn];  
ll las[maxn],en[maxn],tot,nex[maxn];  
ll  cnt[maxn],le[maxn];  
ll ty[maxn],tx[maxn];
ll o=0;
void add(int a,int b,ll c) {  
    en[++tot]=b;  
    nex[tot]=las[a];  
    las[a]=tot;  
    le[tot]=c;  
}  
void dfs(int v,int fa,ll l) {  
    		f[v]=fa;
			ty[++o]=l; 
            tx[o]=v;  
			if(o)
            {  
                cnt[f[v]]++;  
                cnt[f[tx[lower_bound(ty+1,ty+1+o,l-w[v])-ty]]]--; 
            }   
			
    for(int i=las[v]; i; i=nex[i]) {  
        int t=en[i];  
        if(t!=fa) {  
            dfs(t,v,l+le[i]);  
        }  
    }   	
    		o--;
    return ;  
}  
void dfsD(int v,int fa) {  

    for(int i=las[v]; i; i=nex[i]) {  
        int t=en[i];  
        if(t!=fa) {  
            dfsD(t,v);  
            cnt[v]+=cnt[t]; 
        }  
    }  
    return ;  
}  
int main() {  
    //freopen("brun.txt","r",stdin);  
    //freopen("nnn.out","w",stdout);  
    scanf("%d",&n);  
    ll x,y;  
    for(int i=1; i<=n; i++) {  
        scanf("%lld",&w[i]);  
    }  
    for(int i=2; i<=n; i++) {  
        scanf("%lld%lld",&x,&y);  
        add(x,i,y);
		add(i,x,y); 
    }  
    dfs(1,0,0); 
    dfsD(1,0);  
    for(int i=1; i<=n; i++) {  
        printf("%lld ",cnt[i]);  
    }  
}

C 打分
问题描述
何老板给你一棵树，树中共(N)个节点，编号(1)到(N)，(1)号点为根。每个节点都有一个标记，要么为(0)，要么为(1)。
同时每个节点都有一个得分：
若i号节点的标记为(0)，则(i)的得分等于它的所有儿子节点中，得分最低的那一个的分值。
若i号节点的标记为(1)，则(i)的得分等于它的所有儿子节点中，得分最高的那一个的分值。
一开始叶子节点都没有分值，何老板需要给叶子打分。若这棵树总共有(M)个叶子节点，那么打分的分值是([1,M])区间中的整数，每个数字只能使用一次。
何老板想知道，怎样打分，才能使得根节点的得分尽可能大。请你计算出根节点可能的最大分值。

(Solution:)
排名问题的模板但我还是太ruo 现在我来复习一下
打分的区间是([1.M]) 有没有想到什么啊
wo 开始想的是贪心后来发现不行就设了一个估计函数混了10pts ...

注意到我们应该换个思路不只是纠结于贪心地首先给每个点打分那样你就掉坑里了
而应该关注子树的排名情况
对于(i)号节点定义 (size[i]) 是它子树内的叶子节点的个数 (s) 为(i)号点的儿子
(f[i])表示 i 能够得到的最佳排名
那么状态转移方程就很好写了

对于(i)号节点值为(1) 那么也就代表它能够取儿子排名内的最大但是儿子取得的最佳排名不一定是最后的
这取决于儿子能够获取的最佳排名在它子树内的情况
也就是说儿子的排名后面的都已经被填死了所以 i 最优能够得到的排名为 (f[i]-(size[s]-f[s]))
对于(i)号节点值为(0) 那么也就代表它只能够取儿子排名内的最小的但是儿子取得的最佳排名不一定是最靠前的但(f[i])的值要尽可能大
画个图可以发现因为最优排名之前的已经被填充了所以要让最小的最大答案就是被填充的总数+1 用数学式子表达为
(sum_s (f[s]-1)) +1

summary: 要加油鸭不要骄傲呢信竞的道路长且难但是你要稳住充满活力啊

刀剑映出了战士的心。而我的心，漆黑且残破

# NK 0827 练习赛 反思

NK 0827 练习赛 反思

# NK 0827 练习赛反思

NK 0827 练习赛反思