图斯卡蓝瑟的小站 计算机个人学习记录

1001. AND Minimum Spanning Tree

solved at 00:39(+1)

有一张\(n\)个点的完全图，点编号是\(1\)到\(n\)，边权是点编号的bitwise and，求最小生成树，输出字典序最小的

1002. Blow up the city

upsloved

有一个DAG，出度为\(0\)的点是指挥中心，\(q\)次询问，每次给出两个点，这两个点存有关键物资，你可以炸掉一个点和它的邻接边，使得这两个点中任意一个点的物资不能到达指挥中心（有一个点不能到达任意一个指挥中心即可），求方案数，询问独立

目前为止打得最爽的一场多校

A. meeting

solved at 00:58(+1)

树上有\(k\)个关键点，让你选择一个树上的点，使得这些关键点到这个点的最大距离最小

A. Graph Games

upsolved

\(n\)个点，\(m\)条边的图\((1<=n<=1e5,1<=m,q<=2e5)\)，\(q\)次操作，操作有两种，一种是翻转区间内边的状态，第二种是询问两个点的邻接点集是否一致

太菜了，被学弟暴打

1002. Beauty of Unimodal Sequence

upsolved

要求输出字典序最小和最大的最长单峰子序列

有点自闭，本来应该昨天写的，拖到了今天

1001. Blank

upsolved

题意是在\(n\)个位置上填数，只能填\(0,1,2,3\)这四种，然后有\(m\)个限制条件，限制的是区间不同数的个数，求填数方案数\(1<=n,m<=100\)

##A. Eddy Walker

upsloved

有一个长为\(n\)的环，一开始位于\(0\)，每次随机向前或者向后走，求最后一个走到\(m\)的概率

D还没补，G看起来做不了

A Equivalent Prefixes

solved at 00:21

题意是有两个长为n的数组a，b，每个数组都是1到n的一个排列

询问一个最长的前缀p，使得对于任意的\(1 <= l <= r <= q\)，都有\(min\_element(a, l, r) = min\_element(b, l, r)\)（最小值的位置对应相等，而非值相等）

#牛客小白月赛16H　小阳的贝壳

题目链接

题意

维护一个数组，支持以下操作:

1: 区间加值

2: 询问区间相邻数差的绝对值的最大值

3: 询问区间gcd

Description:

Let's define the Eulerian traversal of a tree (a connected undirected graph without cycles) as follows: consider a depth-first search algorithm which traverses vertices of the tree and enumerates them in the order of visiting (only the first visit of each vertex counts). This function starts from the vertex number \(1\) and then recursively runs from all vertices which are connected with an edge with the current vertex and are not yet visited in increasing numbers order. Formally, you can describe this function using the following pseudocode: next_id = 1id = array of length n filled with -1visited = array of length n filled with falsefunction dfs(v): visited[v] = true id[v] = next_id next_id += 1 for to in neighbors of v in increasing order: if not visited[to]: dfs(to)You are given a weighted tree, the vertices of which were enumerated with integers from \(1\) to \(n\) using the algorithm described above. A leaf is a vertex of the tree which is connected with only one other vertex. In the tree given to you, the vertex \(1\) is not a leaf. The distance between two vertices in the tree is the sum of weights of the edges on the simple path between them. You have to answer \(q\) queries of the following type: given integers \(v\), \(l\) and \(r\), find the shortest distance from vertex \(v\) to one of the leaves with indices from \(l\) to \(r\) inclusive.