Theme NexT works best with JavaScript enabled

0xfaner's Blog

Just something trivial

A - meeting

题目描述

A new city has just been built. There’re $n$ interesting places numbered by positive numbers from $1$ to $n$ .

In order to save resources, only exactly $n-1$ roads are built to connect these $n$ interesting places. Each road connects two places and it takes 1 second to travel between the endpoints of any road.

There is one person in each of the places numbered $x_1,x_2 \ldots x_k$ and they’ve decided to meet at one place to have a meal. They wonder what’s the minimal time needed for them to meet in such a place. (The time required is the maximum time for each person to get to that place.)

输入描述

First line two positive integers $n,k$ - the number of places and persons.

For each the following $n-1$ lines, there’re two integers $a,b$ that stand for a road connecting place $a$ and $b$ . It’s guaranteed that these roads connected al $n$ places.

On the following line there’re $k$ different positive integers $x_1,x_2 \ldots x_k$ separated by spaces. These are the numbers of places the persons are at.

输出描述

A non-negative integer - the minimal time for persons to meet together.

示例1

说明

They can meet at place $1$ or $3$ .

备注

$1 \leq n \leq 105$

B - xor

题目描述

Your are given $n$ sets.Every set contains some integers.

We say a set can express an integer, only when there exists a subset of the set such that the bitwise-xor of the elements in the subset is equal to that integer.

Now you need to answer $m$ queries. Each query will give you three integers $l,r,x$ and you should answer if for every $i \in [l,r]$ ,the $i$ -th set can express $x$ .

输入描述

The first line contains two integers $n,m$ .

For each of the following $n$ lines, the first integer $sz$ stands for the size of this set and the following $sz$ integers stand for the elements in this set. The sets are described from number $1$ to $n$ .

For each of the following $m$ lines, there’re three integers $l,r,x$ that means a query.

输出描述

For each query, output a line.

If for every $i \in [l,r]$ ,the $i$ -th set can express $x$ , you need to print “YES”, and “NO” otherwise.

备注

$1 \le n,m \le 50000$ ， $1 \le sz \le 32$ ， $1 \le l \le r \le n$ ，the every integer in input $)\in [0,2^{32})$ 。

C - sequence

题目描述

Your are given two sequences $a_{1 \dots n}$ and $b_{1 \dots n}$ .You need to answer $\displaystyle \max_{1 \le l \le r \le n} \{min(a_{l \dots r}) \times sum(b_{l \dots r})\}$ 。
Where $min(a)$ means the minimal value of every element of sequence $a$ , $sum(a)$ means the sum of every element of sequence $a$ .

输入描述

The first line contains an integer $n$ .

The second line contains $n$ integers meaning $a_{1 \dots n}$ .

The third line contains n integers meaning $b_{1 \dots n}$ .

备注

For all test datas, $1 \leq n \leq 3 \times 10^6,-10^6 \leq a_i,b_i \leq 10^6$ .

D - triples I

题目描述

Doctor Elephant is testing his new program: output the bitwise or of the numbers inputed.

He has decided to input several multiples of $3$ and the output of the program should be his favorite umber $a$ .

Because he is lazy, he decided to input as few numbers as possible. He wants you to construct such an input for every $a$ he chose.

It’s guaranteed that for every aaa in the input there is such a solution. If there’re multiple solutions you can output any.

输入描述

There’re multiple test cases in a test file.

The first line contains a positive integer $T$ - the number of test cases.

In each of the following $T$ lines there is one positive integer $a$ .

输出描述

For each test case output a line. First you need to output the number of numbers in your input, and then you need to output these numbers, separating by spaces.

示例1

说明

$3=3, (3|6)=7$

备注

$1 \le T \le 10^5, 1 \leq a \leq 10^18$ .

E - triples II

题目描述

Doctor Elephant is testing his new program: output the bitwise or of the numbers inputed.

He has decided to input nnn multiples of $3$ and the output of the program should be his favorite number $a$ .

He wants to know how many possible sequences are there. Because the answer can be large, you only need to output the answer modulo $998244353$ .

输入描述

There’re multiple test cases in a test file.

The first line contains a positive integer $T$ - the number of test cases.

In each of the following $T$ lines there’re two non-negative integers $n$ and $a$ .

输出描述

For each test case output a line - the number of such sequences modulo $998244353$ .

备注

$1 \le T \le 500$ , $1 \leq n \leq 10^{18}$ , $0 \leq a \leq 10^{18}$ .

题解

解法

$S_{i,j}$ 表示分的集合包含 $i$ 个模 $3$ 为 $1$ ， $j$ 个模 $3$ 为 $2$ 的分法数量。

F - merge

题目描述

a is a permutation of $1 \dots N$ , the original values are given.

There are $M$ operations, each of them is of one of two types:

1 l m r, means replacing $a_{l \dots r}$ with $merge(a_{l \dots m},a_{m+1 \dots r})$ .

2 i, means that you need to answer the value $a_i$ .

Where $merge(a,b)$ means the following code：

输入描述

The first line contains two integer $N,M$ .

The second line contains $N$ integers $a_{1 \dots N}$ .

For the following $M$ lines, each line is of format 1 l m r or 2 i .

输出描述

For each operation of the second type, output a line containing the answer.

G - tree

题目描述

You are given a tree $A$ of $n$ nodes.

There are $m$ queries.

In each query, you are given a tree $B$ of $m$ nodes and you have to answer how many connected subgraphs of $A$ is isomorphic to $B$ .

Because the answer may be too large, you only need to output it modulo $10^9+7$ .

输入描述

The first line contains an integer $n$ .

The next $n-1$ lines,each line contains two integers - the endpoints of an edge of $A$ .

The next line, an integer $t$ - the number of queries.

For each query:

The first line contains an integer $m$ .

For each of the next $m-1$ lines, each line contains two integer - the endpoints of an edge of $B$ .

输出描述

For each query, output a line containing one integer that stands for the answer.

备注

For all test datas, $n \leq 2000$ , $t \leq 10000$ , $m \leq 12$ .

H - RNGs

题目描述

The relationship between Byteland and Bitland is on thin ice and a war is certained to start. The message of your agent shows that the communication in Bitland is encrypted. They’ve chosen three different RNGs (Random Number Generators) that can produce a sequence of 0s and 1s.

At the start of every day, they’ll randomly pick one RNG, pick one random seed and use that RNG to generate a binary sequence of length 2000. This sequence will act as an encryption key.

As an officer of Byteland, rather than decrypt the datas, you’ve decided to solve an easier problem first: for an encyption key generated, figure out which RNG is used to generate it.

The following is a sample code of these three RNGs written in the out-dated language, C++ (it’s recommend to copy-paste the following code to your favorite editor):

输入描述

The first line contains the number of test cases $T$ . In real data, $T=1000$ .

Each of the following $T$ lines contain a binary string of length $2000$ - an encryption key.

输出描述

Output $T$ lines, for the $i$ -th encryption key in the input, output $0$ if its generated using RNG0, $1$ if generated using RNG1 and $2$ if generated using RNG2.

示例1

说明

The sample is generated using RNG0 with $s=123$ . Please note that this test case is only a sample and won’t be included in the testing.

备注

Your program will be tested on one test data containing $1000$ test cases. Each test case is generated randomly: first randomly pick between (*rng[0],*rng[1],*rng[2]) , and randomly pick an integer s between $[0,109]$ , do srand(s), then call gen() $2000$ times and take the outputed sequence.

You must answer correctly for at least $990$ test cases. It’s worth noting that even if you’re unsure of the number of some certain test case, you still need to output $0,1 \ or\ 2$ , or you may get Wrong Answer verdict.

I - string

题目描述

We call $a,b$ non-equivalent if and only if $a \neq b$ and $a \neq rev(b),$ where $rev(s)$ refers to the string obtained by reversing characters of $s$ , for example $rev(abca)=acba$ .

There is a string $s$ consisted of lower-case letters. You need to find some substrings of $s$ so that any two of them are non-equivalent. Find out what’s the largest number of substrings you can choose.

输入描述

A line containing a string $s$ of lower-case letters.

输出描述

A positive integer - the largest possible number of substrings of $s$ that are non-equivalent.

示例1

说明

The set of following substrings is such a choice: $abac,b,a,ab,aba,bac,ac,c$ .

备注

$1≤∣s∣≤2×105$ , $s$ is consisted of lower-case letters.

J - free

题目描述

Your are given an undirect connected graph.Every edge has a cost to pass.You should choose a path from $S$ to $T$ and you need to pay for all the edges in your path. However, you can choose at most $k$ edges in the graph and change their costs to zero in the beginning. Please answer the minimal total cost you need to pay.

输入描述

The first line contains five integers $n,m,S,T,K$ .

For each of the following $m$ lines, there are three integers $a,b,l$ , meaning there is an edge that costs $l$ between $a$ and $b$ .

$n$ is the number of nodes and $m$ is the number of edges.

输出描述

An integer meaning the minimal total cost.

备注

$1 \le n,m \le 10^3,1 \le S,T,a,b \le n,0\le k\le m,1\le l\le10^6$ .
Multiple edges and self loops are allowed.

K - number

题目描述

300iq loves numbers who are multiple of $300$ .

One day he got a string consisted of numbers. He wants to know how many substrings in the string are multiples of $300$ when considered as decimal integers.

Note that leading and trailing zeros are allowed (both in original string and substrings you chose) and the same substring appearing in different places can be counted multiple times.

输入描述:

A single line consisting a string consisted of characters '0' to '9'.

输出描述:

The number of substrings that are multiples of $300$ when considered as decimal integers.

示例1

说明

'600', '0', '0', '00' are multiples of $300$ . (Note that '0' are counted twice because it appeared two times)

备注

let the string in the input be $s$ , $1 \leq |s| \leq 10^5$ .