蓝桥杯2023年十四届省赛大学B组真题（共10道题)(AK)

2023年十四届省赛大学B组真题（共10道题)

算法涉及:

• 模拟: A B
• 基础算法: C(二分) G(前缀和)
• 图论: D F
• 树论: I J
• 动态规划: E
• 数据结构: H(堆+双链表)

(填) 试题 A: 日期统计

算法: 模拟 双指针

思路:

• 时间复杂度: O(365×N)
• 空间复杂度: O(N)

我们枚举(2023年中的)每一天, 然后去100个给定的字符中顺次查找, count记录, 只有count==8才是找其了的, ans++, 输出即可

填空题: cout<<"235";即可

#include <iostream>

using namespace std;
const int N=110;
int arr[N], month[]={0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int main() {
	for(int i=1;i<=100;i++) scanf("%d", &arr[i]); 	
	
	int ans=0;
	for(int m=1;m<=12;m++) {
		for(int d=1;d<=month[m];d++) {
			string s1=m<10?"0"+to_string(m):to_string(m);
			string s2=d<10?"0"+to_string(d):to_string(d);
			string s="2023"+s1+s2;
			
			int count=0, j=1;
			for(int i=0;i<s.size();i++) {
				for(;j<=100;j++) {
					if(s[i]-'0'==arr[j]) {count++; break;}
				}
				j++; // 注意++
			}
			if(count==8) ans++;
		}
	}
	printf("%d", ans); // 235
	return 0;
}

(填) 试题 B: 01串的熵

算法: 模拟

思路:

• 时间复杂度: O(1e8)
• 空间复杂度: O(1)

cpp中是有以2为底的对数的(log2(x))

填空题: cout<<"11027421";即可

#include <iostream>
#include <cmath> 

using namespace std;
const double eps=1e-3;

int cmp(double a, double b) {
	if(fabs(a-b)<eps) return 0;
	if(a>b) return -1;
	return 1;
}



int main() {
	int n=23333333;
	// i为0, j为1 (0比1少, 所以只用枚举到n/2) 
	for(int i=1;i<=n/2;i++) {
		int j=n-i;
		double t=(-1)*(((double)i*i/n)*log2(((double)i/n)) + ((double)j*j/n)*log2(((double)j/n)));
		if(!cmp(t, 11625907.5798)) {
			cout<<i<<endl;
		}
	}
	// 11027421
	return 0;
}

试题 C: 冶炼金属

算法: 二分

思路:

• **时间复杂度: O(NlogM) = 1e5 **
• 空间复杂度: O(N)

最小化二分模板

• Vmax: 按照A/B升序, Vmax=input[0]的A/B, 因为但凡再大1, input[0]都无法满足, 所以此时最大

• Vmin: 我们只知道Vmin∈[1, Vmax]之间, 但不知道Vmin为多少才能使得所有的input[i].A/Vmin都等于input[i].B

  因为整个满足单调减, 所以二分一定可以得到答案

#include <iostream>
#include <algorithm>
#define pii pair<int,int>

using namespace std;
const int N=10010;
pii input[N];
int n, maxn, minn;

bool check(int x) {
	for(int i=1;i<=n;i++) {
		if(input[i].first/x!=input[i].second) return false;
	}
	return true;
}

int Binary_search(void) {
	int l=0, r=maxn; 
	while(l+1!=r) {
		int mid=(l+r)/2;
		check(mid)?r=mid:l=mid;
	}
	return r;
}

int main() {
	scanf("%d", &n);
	for(int i=1;i<=n;i++) scanf("%d%d", &input[i].first, &input[i].second);
	sort(input+1, input+1+n, [](pii a, pii b) {
		return (double)a.first/a.second < (double)b.first/b.second;
	});
	maxn=input[1].first / input[1].second;
	minn=Binary_search();
	printf("%d %d",minn, maxn);
	return 0;
}

试题 D: 飞机降落

算法: DFS

思路:

• 时间复杂度: O(T×2^N×10⁵) =1e9 (2s正好) [比较迷, 因为time远远小于10⁵所以, 平均差不多1e8左右]
• 空间复杂度: O(N)

对什么进行DFS? 什么需要DFS? —> 当前最早空余时刻(time), 和当前各个飞机的降落状态(status)

因为只要我们知道time是多少, 我们就能对当前这个需要降落的飞机进行判断

• case1: 飞机降落时刻 >当前时刻(time) 往下传t+d(飞机一到就开始降落, 往下最早空余时间就是t+l
  

• case2: 当前飞机悬停l时间 > 当前时刻(time) 也可以降落, 往下传time+l, 飞机先悬着, 等到了最早空余时间, 就开始降落, 往下最早空余时间就是time+l
  

• 注意: 代码用的状态压缩(因为N<=10), 推荐用数组, 方便理解. 问我为什么用状态压缩? 嘻嘻, 因为懒得回溯,本人喜欢压行…回溯还得占两行

#include <iostream>

using namespace std;
const int N=11;
int T[N], D[N], L[N], n, flag=0;

// 当前飞机的状态(2), 当前 空余的最早时刻 
void DFS(int status, int time) {
	if(status==(1<<n)-1) { flag=1; return; } 
	else {
		for(int i=n-1;i>=0;i--) {
			if(!(status&(1<<i))) { // 这架飞机还没有起飞 
				int t=T[i], d=D[i], l=L[i];
				if(t>=time) DFS((status|(1<<i)), t+l); // case1: 飞机降落时刻 >当前时刻 
				else if(t+d>=time) DFS((status|(1<<i)), time+l); // case2: 当前飞机悬停l时间 > 当前时刻 也可以降落, 往下传time+l 
			}
		}
	}
}

int main() {
	int W; scanf("%d", &W);
	while(W--) {
		flag=0;
		scanf("%d", &n);
		for(int i=0;i<n;i++)  scanf("%d%d%d", &T[i], &D[i], &L[i]);
		DFS(0, 0);
		printf("%s\n", flag?"YES":"NO");
	}
	
	return 0;
}

试题 E: 接龙数列

算法: 动态规划-状态机DP

思路:

• 时间复杂度: O(N×11)
• 空间复杂度: O(N) 可以压缩为1维变成O(1)

状态机DP, 记录一下前一个是什么(状态), 再依据状态, 判断当前状态的转移方向

状态（11个) 前一个以0,1,2,…，9结尾 和 以11结尾(表示什么都可以选)

我们反着题意计算, 我们计算最多能保留多少数, 最后再用n去减去即可, 方便理解

注意: 这题必须有化为严格表机构, 记忆化搜索会爆!

• 递归:

// 当前在第i个数面前, 前一个数以status结尾, 返回最多能保留多少数 
int way1(int u, int status) {
	if(dp[u][status]) return dp[u][status];
	if(u==n+1) return 0;
	else {
		string s=to_string(arr[u]);
		int begin=s.front()-'0', end=s.back()-'0';
		int p1= way1(u+1, status); // 不要当前数
		int p2= begin==status||status==11 ? way1(u+1, end)+1: 0; // 要当前数 
		dp[u][status]=max(p1, p2);
		return dp[u][status];
	} 
}

// 在main中
cout<<n-way1(1, 11);

• 严格表依赖:

// 状态机DP,
// 状态(11个) 前一个以0,1,2,...,9结尾 和 以11结尾(表示什么都可以选)
#include <iostream>

using namespace std;
const int N=100010, INF=0x3f3f3f3f;
int arr[N], n, dp[N][15];

int main() {
	scanf("%d", &n);
	for(int i=1;i<=n;i++) scanf("%d", &arr[i]);
	
	for(int u=n;u>=1;u--) {
		for(int status=0;status<=11;status++) {
			string s=to_string(arr[u]);
			int begin=s.front()-'0', end=s.back()-'0';
			int p1= dp[u+1][status]; // 不要当前数
			int p2= begin==status||status==11 ?dp[u+1][end]+1: 0; // 要当前数 
			dp[u][status]=max(p1, p2);
		}
	}
	cout<<n-dp[1][11]<<endl;
	return 0;
}

试题 F: 岛屿个数

算法: BFS DFS

**思路: **

我们遍历海水, 只要不是子岛屿就一定能,在拓展海水的同时遇到, 一旦遇到(1)我们就DFS这座岛屿, 同时ans++

注意: 海水8方位拓展, 岛屿4方位拓展

/* 岛屿个数 (P1162 填涂颜色)
我们从最外圈开始(自己加一圈0海水), 八方位走BFS;
中途遇到岛屿就DFS,ans++; 最后BFS结束就是答案
*/

#include <iostream>
#include <cstring>
#define pii pair<int, int>

using namespace std;
const int N=55;
int m, n, arr[N][N], hh, tt, ans;
int b[]={1,0,-1,0,1,1,-1,-1}, bb[]={0,1,0,-1,1,-1,1,-1}, a[]={1,0,-1,0}, aa[]={0,-1,0,1};
bool st[N][N];
pii q[N*N];

void DFS(pii s) {
	st[s.first][s.second]=true;
	for(int i=0;i<4;i++) {
		int x=s.first+a[i], y=s.second+aa[i];
		if(x>=0&&x<=m+1&&y>=0&&y<=n+1&&!st[x][y]&&arr[x][y]) {
			DFS({x, y});
		}
		
	}
}
void FloodFill(pii s) {
	hh=0, tt=-1;
	q[++tt]=s;
	st[s.first][s.second]=1;
	while(hh<=tt) {
		pii u=q[hh++];
		for(int i=0;i<8;i++) {
			int x=u.first+b[i], y=u.second+bb[i];
			if(x>=0&&x<=m+1&&y>=0&&y<=n+1&&!st[x][y]) {
				if(arr[x][y]==1) DFS({x,y}), ans++; // 是岛屿 
				else st[x][y]=true, q[++tt]={x,y}; //是海水 
			}
		}
	}
}
int main() {
	int T; scanf("%d", &T); getchar();
	while(T--){
		scanf("%d%d",&m, &n); getchar();
		ans=0; memset(st, 0, N*N);
		for(int i=1;i<=m;i++) {
			for(int j=1;j<=n;j++) {
				char ch; scanf("%c",&ch);
				arr[i][j]= ch-'0';
			}getchar();
		}
		FloodFill({0,0});
		printf("%d\n", ans);
	}
	return 0;
} 

试题 G: 子串简写

算法: 前缀和

思路:

• 时间复杂度: O(N)
• 空间复杂度: O(N)

从双指针切入—> 前缀和实现

看到数据范围想到 要不O(NlogN), 要不O(N), 但前缀大多数是查找或排序, 用在字符串上比较少,而双指针用在字符串上比较多, 所以容易想到双指针

双指针切入: 我们用i记录a, 用j记录b, 都从1开始, 同时用两个数组记录ch1, 和ch2出现的位置( A[], B[] )(不浪费遍历过的数据), j往右走, 如果遍历到ch1, 就加入到A[]中, 反之加入到B[]中, 当j走到尽头, 那B[]中,>=i+(k-1)的b的位置就一定是一个子串, 从而想到前缀的思想:

前缀和具体实现:

1. 我们用A[]记录ch1出现的位置, 用S[]记录ch2个数的前缀和数组;
2. 然后我们遍历A[ ]数组, 对于每一个有ch1出现的位置i, 我们查看在i+(k-1)到len的区间上有几个ch2, 统计答案即可;

#include <iostream>
#include <cstring>
#define lli long long int

using namespace std;
const int N=500010;
int A[N], S[N], k, len; // S[]:为ch2个数的前缀和(B[]同理);  A[]:为ch1出现的位置 
char str[N], ch1[2], ch2[2];

int main() {
	scanf("%d", &k);
	scanf("%s %s %s", str+1, ch1, ch2);
	len=strlen(str+1);
	
	for(int i=1;i<=len;i++) {
		if(str[i]==ch1[0]) A[i]=1;
		if(str[i]==ch2[0]) S[i]=1;
	}
	for(int i=1;i<=len;i++) S[i]+=S[i-1];
	
	// for(int i=1;i<=len;i++) cout<<S[i]<<" "; puts("");
	
	lli ans=0;
	for(int i=1;i<=len;i++) {
	    if(A[i]) {
	        ans+=S[len]-S[min(len, i+(k-1)-1)];
	        // cout<<i<<": "<< S[len]-S[i+(k-1)-1]<<endl;
	    }
	}
	cout<<ans;
	return 0;
}

试题 H: 整数删除

算法: 优先队列 双向链表

思路:

算法1 (双向链表+优先队列) O(NlogN)[蓝桥杯和Acwing都能AC]

1. 因为涉及到删除数后, 还要找到其前后的值, 所以不难想到得用双链表
2. 我用优先队列pair<value, pos>维护最小值
3. 但同时我们需要一个st[]来记录当前值是否为真的值, 比如测样中, 我们把第一个1删了, 位于第二个位置的4就得+1, 如果!如果!一次pq.top()为第2个位置(值为4), 那这个值就是假的, 我们得把它的值+1(从pos=1来的那个1), 同时让st[2]=0;再把这个值塞会pq, 这不能算作一次操作(k不能–) 只有当pq弹出的是位置, 在st[]是0, 这个值才是真值(k–);
4. 时间复杂度分析: 有K次操作, 每次操作平均时间复杂度是O(logN) 优先队列出队嘛, 所以总的O(NlogN)

C++ 代码

/* 整数删除:    
* 我们用双向链表存数据 + 优先队列(pair<value, pos>) 
* 用map会TLE, 所以, map-->st[]  
*/

#include <iostream>
#include <queue>
#include <unordered_map>
#include <functional>
#define lli long long int
#define pii pair<lli,int>

using namespace std;

const int N=500010;
int bef[N], aft[N]; //双向链表
lli e[N]; 
int n, k;
//unordered_map<int, lli> rem; // pair<pos, addtion> 记录pos位置的数应该增加多少 
lli rem[N];
priority_queue<pii, vector<pii>, greater<pii> > pq; // pair<value, pos>

int main() {
	scanf("%d%d", &n, &k);
	for(int i=1;i<=n;i++){
		scanf("%ld", &e[i]);	
		bef[i]=i-1; aft[i]=i+1;
		pq.push({e[i], i});
	} 

	while(k) {
		lli value=pq.top().first;
		int pos=pq.top().second;
		pq.pop();
		if(!rem[pos]) { //为真值 
			rem[bef[pos]]+=value, rem[aft[pos]]+=value; //改值 
			aft[bef[pos]]=aft[pos]; //前一个的next为当前的next
			e[bef[pos]]+=value;
			bef[aft[pos]]=bef[pos]; //后一个的befor要等于当前的bef 
			e[aft[pos]]+=value;
			e[pos]=-1; 
			k--;
		}
		else { //当前为假值 
			lli addtion=rem[pos];
			value+=addtion;
			rem[pos]=0;
			pq.push({value, pos});
		}	
	}
	for(int i=1;i<=n;i++) if(e[i]!=-1) printf("%lld ", e[i]); puts("");
	return 0;
}

算法2 (线段树+双向链表) O(NlogN) [只有ACWing能AC]

1. 想到要频繁的改值, (在线操作), 也很容易想到线段树, 维护一个求区间最小值的线段树即可;
2. 时间复杂度分析: 有K次操作, 每次logN(线段树的modify和query都是logN的复杂度)所以总共 O(NlogN), 但常数很大, ACWing能过(给了3秒), 蓝桥杯那边只给了1s, 所以蓝桥杯过不了) 线段树+常数≈10e8(线段树的常数要×10), 很极限;

C++ 代码

// 怎么快速找到前后的点??? -----双向链表!!!!

#include <iostream>
#define lli long long int 
#define pii pair<lli,int>

using namespace std;
const int N=500010;
const lli INF=92233720368775807;
int n, k;
struct Element{
    int be, ne;
    lli value;
    int idx;// idx 为当前的位置
}arr[N];

struct Node{
    int l, r;
    pii minn={-1,-1}; // pair<value, pos> // 这里的pos指的是cnt的值, 其前一个值为e[be[cnt]]
}tr[4*N];



pii resmin(pii a, pii b) { return a.first<=b.first?a:b; }
void pushup(int u) { tr[u].minn=resmin(tr[u*2].minn,tr[u*2+1].minn); }

struct Node make_Node(int _l, int _r, lli _value, int _pos) {
    struct Node newnode;
    newnode.l=_l;
    newnode.r=_r; 
    newnode.minn.first=_value;
    newnode.minn.second=_pos;
    return newnode;
}

void build(int u, int l, int r) {
    if(l==r) tr[u]=make_Node(l,r,arr[l].value, arr[l].idx);
    else {
        tr[u]=make_Node(l,r,0,0);
        int mid=l+r>>1;
        build(u*2,l,mid);build(u*2+1,mid+1,r); //注意1
        pushup(u);
    }
}
void modify(int u, int poss, pii x) {
    if(tr[u].l==tr[u].r) tr[u].minn=x;
    else {
        int mid= tr[u].l+tr[u].r>>1;
        if(poss<=mid) modify(u*2,poss,x); //注意2
        else modify(u*2+1,poss,x);
        pushup(u);
    }
}
pii query(int u, int l, int r) {
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].minn; //注意3
    else {
        int mid= tr[u].l+tr[u].r>>1;
        pii res={0,INF};
        if(l<=mid) res=resmin(query(u*2, l, r), res);
        if(r>mid) res=resmin(query(u*2+1, l, r), res);
        return res;
    }
}

// for test
void printTR(void) {
    for(int i=1;i<=n;i++) printf("[%d,%d], value:%ld, pos:%d\n", tr[i].l, tr[i].r, tr[i].minn.first, tr[i].minn.second);
}

int main() {
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) {
        int t;scanf("%ld",&t);
        arr[i]={i-1,i+1, t, i};
    }
    // for(int i=1;i<=n;i++) cout<<arr[i].value<<" "; puts("");
    build(1,1,n);
    

    for(int i=1;i<=k;i++) {
        pii aim=query(1,1,n);
        //要找到真正的左位置, 和右位置
        int l=arr[aim.second].be;
        int r=arr[aim.second].ne;
        

        arr[aim.second].value=INF; // 将这个值删去
        modify(1,aim.second,{arr[aim.second].value, arr[aim.second].idx});
        arr[l].ne=arr[aim.second].ne;
        arr[r].be=arr[aim.second].be;
        if(l>=1) {
            arr[l].value+=aim.first;
            modify(1,l,{arr[l].value, arr[l].idx});// 左边+上这个值
        }
        if(r<=n) {
            arr[r].value+=aim.first;
            modify(1,r,{arr[r].value, arr[r].idx});// 右边+上这个值
        }
        // cout<<"value:"<<aim.first<<" pos:"<<aim.second<<endl;
        // printf("l: %d, r: %d\n", l, r);
        // for(int i=1;i<=n;i++) printf("%d ",arr[i].value); puts("");
        // printTR();
    }
    for(int i=1;i<=n;i++) if(arr[i].value!=INF) printf("%ld ",arr[i].value);
    
    return 0;   
}

关于在ACWing线段树快于优先队列, 个人猜测试测样的原因, 手写堆的话, 优先队列绝对更佳

试题 I: 景区导游

算法: BFS LCA

思路:

基本是一道LCA的裸题, 要求任意两个树上结点的最短路, 很容易想到是 $dist[a]+dist[b]-2*dist[LCA(a,b)];$ 其中dist是根节点到各个结点的距离, LCA(a,b) 是a和b的最近公共祖先.

再就是K个询问的处理要用前缀和思想, 不能暴力处理,

为什么N开1e5会爆, 最少要开4e5才AC…啧啧啧卡了好久还是不知道, 以后的LCA用DFS写, DFS没bug

#include <iostream>
#include <cstring>
#define lli long long int

using namespace std;
const int N=1000010, M=2*N;
int n, k, depth[N], fa[N][20], check[N];
int h[N], e[M], ne[M], t[M], idx;
lli dist[N];

void add(int a, int b, int w) { e[++idx]=b, t[idx]=w, ne[idx]=h[a], h[a]=idx; }
void BFS(int root) {
	memset(depth, 0x3f, N);
	depth[root]=1, depth[0]=0;
	int q[M], hh=0, tt=-1;
	q[++tt]=root;
	while(hh<=tt) {
		int u=q[hh++];
		for(int i=h[u];i;i=ne[i]) {
			int j=e[i];
			if(depth[j]>depth[u]+1) {
				q[++tt]=j;
				depth[j]=depth[u]+1;
				dist[j]=dist[u]+t[i]; // 获取从root到各个点的最短距离dist[]
				fa[j][0]=u;
				for(int k=1;k<=19;k++) fa[j][k]=fa[fa[j][k-1]][k-1];
			}
		}
	}
} 
int LCA(int a, int b) {
	if(depth[a]<depth[b]) swap(a, b);
	// 1. a跳到和b同一层
	for(int k=19;k>=0;k--) 
		if(depth[fa[a][k]]>=depth[b]) a=fa[a][k]; 
	if(a==b) return a;
	// 2. 一起跳
	for(int k=19;k>=0;k--) 
		if(fa[a][k]!=fa[b][k]) a=fa[a][k], b=fa[b][k];
	return fa[a][0];
}

// 返回a,b两点的最短距离 
lli query(int a, int b) {
	a=check[a], b=check[b];
	return (lli)1*dist[a]+dist[b]-2*dist[LCA(a,b)];
}
int main() {
    scanf("%d%d", &n, &k);
    for(int i=1;i<=n-1;i++) {
        int a, b, w; scanf("%d%d%d", &a, &b, &w);
        add(a, b, w); add(b, a, w);
    }
    
    // 1. 预处理LCA的 depth[]和fa[][] O(NlogN) 同时 获取从root到各个点的最短距离dist[] O(N) 
    BFS(1);
	
	// 2. 读入询问
	for(int i=1;i<=k;i++) scanf("%d", &check[i]);
	
	// 3. 处理询问 暴力处理要O(N^2logN), 可以采用全部加和, 求每段的时候-去即可 
	lli sum=0;
	for(int i=1;i+1<=k;i++) sum+=query(i, i+1); 
	
	for(int i=1;i<=k;i++) {
		if(i==1) cout<<sum-query(1,2)<<" ";
		else if(i==k) cout<<sum-query(k, k-1)<<" ";
		else cout<<sum-query(i, i-1)-query(i, i+1)+query(i-1, i+1)<<" ";
	}
    return 0;
}

试题 J: 砍树

算法: LCA 树上边差分

思路:

• 对m组询问, 对(ai, bi)之间的所有边都+1, 最后如果哪个边等于m, 说明m组询问都要经过这个边, 把它砍掉, 就能使得所有的ai, bi不连通, 如果没有等于m的就输出-1, 说明总会有另辟蹊径的两个点

• 时间复杂度: LCA: O(NlogN), m次询问: O(MlogN) DFS统计统计差分: O(N)

• 还有就是注意边的编号, 要开个 map<pii, int> 存从a到b的区间是第几个输入的

  蓝桥杯搞笑的, 这M=N¹⁰1s读都读不完 /笑死;

#include <iostream>
#include <map>
#define pii pair<int, int>

using namespace std;
const int N=100010, M=2*N;
int n, m, depth[N], fa[N][20], d[N], ans=0;
map<pii, int> num;
int h[N], e[M], ne[M], idx; 

void add(int a, int b) { e[++idx]=b, ne[idx]=h[a], h[a]=idx; }
void DFS(int u, int pre) {
	depth[u]=depth[pre]+1;
	fa[u][0]=pre;
	for(int k=1;k<=19;k++) fa[u][k]=fa[fa[u][k-1]][k-1];
	for(int i=h[u];i;i=ne[i]) if(e[i]!=pre) DFS(e[i], u);
}
int LCA(int a, int b) {
	if(depth[a]<depth[b]) swap(a, b);
	for(int k=19;k>=0;k--) if(depth[fa[a][k]]>=depth[b]) a=fa[a][k];
	if(a==b) return a;
	for(int k=19;k>=0;k--) if(fa[a][k]!=fa[b][k]) a=fa[a][k], b=fa[b][k];
	return fa[a][0];
}

void dfs(int u, int f) {
	for(int i=h[u];i;i=ne[i]) {
		int j=e[i];
		if(j==f) continue;
		dfs(j, u);
		d[u]+=d[j];
	}
	if(d[u]==m) ans=max(ans, num[{f, u}]);
}


int main() {
	scanf("%d%d", &n, &m);
	for(int i=1;i<=n-1;i++) {
		int a, b; scanf("%d%d", &a, &b);
		num[{a,b}]=num[{b,a}]=i;
		add(a, b); add(b, a);
	}
	DFS(1, 0);
	for(int i=1;i<=m;i++) {
		int a, b; scanf("%d%d", &a, &b);
		int lca=LCA(a, b);
		d[a]++, d[b]++, d[lca]-=2;
	}
	dfs(1, 0);
	printf("%d", ans==0?-1:ans);
	return 0;
}

总结&随笔:

很好, 一个寒假全在学DP, 寒假就写了两套真题;

限时的时候, FHIJ都没做出来, 这套总的来说比较难(模拟的题越少越难) 涉及的LCA和树上差分是全新的知识点, 虽然学完感觉不难, 但限时的时候不会=无从下手, I题刚开始写的暴力, 不知道什么是LCA, 暴力用的向上标记法, 蓝桥杯官网就对了1个测试点… 好了, 开学估计就要开考(4月初)咯, 在此之前还有天梯赛…啊, 好烦呀,前段时间写了套天梯赛的真题, 限时150, 全是图论+树论; 啧啧啧.

所谓突破, 无非是一次次接近极限的过程