广州建站软件_有限责任公司的优缺点_互联网推广引流是做什么的_手机版百度一下

A. Sliding

Problem Statement

Red was ejected. They were not the imposter.

There are $n$ rows of $m$ people. Let the position in the $r$-th row and the $c$-th column be denoted by $(r,c)$. Number each person starting from $1$ in row-major order, i.e., the person numbered $(r-1)\cdot m+c$ is initially at $(r,c)$.

The person at $(r,c)$ decides to leave. To fill the gap, let the person who left be numbered $i$. Each person numbered $j>i$ will move to the position where the person numbered $j-1$ is initially at. The following diagram illustrates the case where $n=2$, $m=3$, $r=1$, and $c=2$.

Calculate the sum of the Manhattan distances of each person’s movement. If a person was initially at $(r_0,c_0)$ and then moved to $(r_1,c_1)$, the Manhattan distance is $|r_0-r_1|+|c_0-c_1|$.

Input

The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases.

The only line of each testcase contains $4$ integers $n$, $m$, $r$, and $c$ ($1\le r\le n\le 10^6$, $1\le c\le m\le 10^6$), where $n$ is the number of rows, $m$ is the number of columns, and $(r,c)$ is the position where the person who left is initially at.

Output

For each test case, output a single integer denoting the sum of the Manhattan distances.

Example

input
4
2 3 1 2
2 2 2 1
1 1 1 1
1000000 1000000 1 1

output
6
1
0
1999998000000

note

For the first test case, the person numbered $2$ leaves, and the distances of the movements of the person numbered $3$, $4$, $5$, and $6$ are $1$, $3$, $1$, and $1$, respectively. So the answer is $1+3+1+1=6$.

For the second test case, the person numbered $3$ leaves, and the person numbered $4$ moves. The answer is $1$.

Solution

具体见文后视频。

---

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long longusing namespace std;typedef pair<int, int> PII;
typedef long long LL;void solve() {int n, m, r, c;cin >> n >> m >> r >> c;int res = m - c;res += m * (n - r);res += (n - r) * (m - 1);cout << res << endl;
}signed main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int dt;cin >> dt;while (dt --)solve();return 0;
}

---

B. Everyone Loves Tres

Problem Statement

There are 3 heroes and 3 villains, so 6 people in total.

Given a positive integer $n$. Find the smallest integer whose decimal representation has length $n$ and consists only of $3$s and $6$s such that it is divisible by both $33$ and $66$. If no such integer exists, print $-1$.

Input

The first line contains a single integer $t$ ($1\le t\le 500$) — the number of test cases.

The only line of each test case contains a single integer $n$ ($1\le n\le 500$) — the length of the decimal representation.

Output

For each test case, output the smallest required integer if such an integer exists and $-1$ otherwise.

Example

input
6
1
2
3
4
5
7

output
-1
66
-1
3366
36366
3336366

note

For $n=1$, no such integer exists as neither $3$ nor $6$ is divisible by $33$.

For $n=2$, $66$ consists only of $6$s and it is divisible by both $33$ and $66$.

For $n=3$, no such integer exists. Only $363$ is divisible by $33$, but it is not divisible by $66$.

For $n=4$, $3366$ and $6666$ are divisible by both $33$ and $66$, and $3366$ is the smallest.

Solution

具体见文后视频。

---

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long longusing namespace std;typedef pair<int, int> PII;
typedef long long LL;void solve() {int n;cin >> n;if (n == 1 || n == 3) {cout << -1 << endl;return;}if (n % 2 == 0) {for (int i = 1; i <= n - 2; i ++)cout << 3;cout << 66 << endl;} else {for (int i = 1; i <= n - 5; i ++)cout << 3;cout << 36366 << endl;}
}signed main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int dt;cin >> dt;while (dt --)solve();return 0;
}

---

C. Alya and Permutation

Problem Statement

Alya has been given a hard problem. Unfortunately, she is too busy running for student council. Please solve this problem for her.

Given an integer $n$, construct a permutation $p$ of integers $1,2,\dots ,n$ that maximizes the value of $k$ (which is initially $0$) after the following process.

Perform $n$ operations, on the $i$-th operation ($i=1,2,\dots ,n$),

• If $i$ is odd, $k=k\&p_i$, where $\&$ denotes the bitwise AND operation.
• If $i$ is even, $k=k|p_i$, where $|$ denotes the bitwise OR operation.

Input

The first line contains a single integer $t$ ($1\le t\le 500$) — the number of test cases.

The only line of each test case contains a single integer $n$ ($5\le n\le 2\cdot 10^5$) — the length of the permutation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, output the maximum value of $k$ in the first line and output the permutation $p_1,p_2,\dots ,p_n$ in the second line.

If there are multiple such permutations, output any.

Example

input
6
5
6
7
8
9
10

output
5
2 1 3 4 5
7
1 2 4 6 5 3
7
2 4 5 1 3 6 7
15
2 4 5 1 3 6 7 8
9
2 4 5 6 7 1 3 8 9
15
1 2 3 4 5 6 8 10 9 7

note

For the first test case, the value of $k$ is determined as follows:

$k=0$ initially.

• On the $1$st operation, $1$ is odd, so Alya sets $k$ to be $k\&p_1=0\&2=0$.
• On the $2$nd operation, $2$ is even, so Alya sets $k$ to be $k|p_2=0|1=1$.
• On the $3$rd operation, $3$ is odd, so Alya sets $k$ to be $k\&p_3=1\&3=1$.
• On the $4$th operation, $4$ is even, so Alya sets $k$ to be $k|p_4=1|4=5$.
• On the $5$th operation, $5$ is odd, so Alya sets $k$ to be $k\&p_5=5\&5=5$.

The final value of $k$ is $5$. It can be shown that the final value of $k$ is at most $5$ for all permutations of length $5$. Another valid output is $[2,3,1,4,5]$.

For the second test case, the final value of $k$ is $7$. It can be shown that the final value of $k$ is at most $7$ for all permutations of length $6$. Other valid outputs include $[2,4,1,6,3,5]$ and $[5,2,6,1,3,4]$.

Solution

具体见文后视频。

---

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long longusing namespace std;typedef pair<int, int> PII;
typedef long long LL;void solve() {int n;cin >> n;std::vector<int> res;int lst = -1;if (n & 1) lst = n --;int sep = 1;while (sep * 2 <= n) sep *= 2;sep --;for (int i = 1; i <= n; i ++)if (i != 1 && i != 3 && i != sep - 1 && i != sep && i != n)res.push_back(i);std::vector<int> final = {1, 3, sep - 1, sep, n};if (sep == 3) final = {2, 1, 3, n};if (~lst) final.push_back(lst);for (auto v : final) res.push_back(v);if (~lst) cout << lst << endl;else cout << sep * 2 + 1 << endl;for (auto v : res)cout << v << " ";cout << endl;
}signed main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int dt;cin >> dt;while (dt --)solve();return 0;
}

---

D. Yet Another Real Number Problem

Problem Statement

Your task is to maximize the sum of the array after performing any number of such operations. Since it could be large, output this sum modulo 109+7
.Three r there are’s in strawberry.

You are given an array $b$ of length $m$. You can perform the following operation any number of times (possibly zero):

• Choose two distinct indices $i$ and $j$ where $1\le \mathbf{i}<\mathbf{j}\le \mathbf{m}$ and $b_i$ is even, divide $b_i$ by $2$ and multiply $b_j$ by $2$.

Your task is to maximize the sum of the array after performing any number of such operations. Since it could be large, output this sum modulo $10^9+7$.

Since this problem is too easy, you are given an array $a$ of length $n$ and need to solve the problem for each prefix of $a$.

In other words, denoting the maximum sum of $b$ after performing any number of such operations as $f(b)$, you need to output $f([a_1])$, $f([a_1,a_2])$, $\dots$, $f([a_1,a_2,\dots ,a_n])$ modulo $10^9+7$ respectively.

Input

The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1\le n\le 2\cdot 10^5$) — the length of $a$.

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9$) — the starting values of array $a$.

It is guaranteed that the sum of $n$ over all test cases will not exceed $2\cdot 10^5$.

Output

For each test case, output $n$ integers representing the answer for each prefix of $a$ modulo $10^9+7$.

Example

input
3
10
1 2 3 4 5 6 7 8 9 10
11
1 6 9 4 7 4 4 10 3 2 3
4
527792568 502211460 850237282 374773208

output
1 3 8 13 46 59 126 149 1174 1311
1 7 22 26 70 74 150 1303 1306 1308 1568
527792568 83665723 399119771 773892979

note

For each prefix in the first example, a possible array after operations is:

• $[1]$ and the sum is $1$;
• $[1,2]$ and the sum is $3$;
• $[1,1,6]$ and the sum is $8$;
• $[1,1,3,8]$ and the sum is $13$;
• $[1,1,3,1,40]$ and the sum is $46$;
• $[1,1,3,1,5,48]$ and the sum is $59$;
• $[1,1,3,1,5,3,112]$ and the sum is $126$;
• $[1,1,3,1,5,3,7,128]$ and the sum is $149$;
• $[1,1,3,1,5,3,7,1,1152]$ and the sum is $1174$;
• $[1,1,3,1,5,3,7,1,9,1280]$ and the sum is $1311$.

Solution

具体见文后视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long longusing namespace std;typedef pair<int, int> PII;
typedef long long LL;const int mod = 1E9 + 7;int ksm(int a, int b) {int res = 1;while (b) {if (b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;
}void solve() {int n;cin >> n;std::vector<int> a(n), b(n), c(n, 0), d(n, 0);for (int i = 0; i < n; i ++) {cin >> a[i], b[i] = a[i];while (b[i] % 2 == 0) c[i] ++, b[i] /= 2;d[i] = b[i];}for (int i = 1; i < n; i ++) c[i] += c[i - 1], (d[i] += d[i - 1]) %= mod;int sum = 0;stack<int> stk;for (int i = 0; i < n; i ++) {auto comp = [&](int a, int b, int c) -> int {// a </> b * 2^cif (c > 30) return 1;return a <= b * (1ll << c);};while (stk.size() && comp(b[stk.top()], b[i], c[i] - c[stk.top()])) {int lst = 0, pos = stk.top();stk.pop();if (stk.size()) lst = c[stk.top()];sum -= (b[pos] * ksm(2, c[pos] - lst) % mod - b[pos]);}// cout << sum << " ";if (stk.size()) sum += b[i] * ksm(2, c[i] - c[stk.top()]) % mod - b[i];else sum += b[i] * ksm(2, c[i]) % mod - b[i];// cout << sum << " ";stk.push(i);cout << ((sum % mod) + d[i] + mod) % mod << " ";}cout << endl;
}signed main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int dt;cin >> dt;while (dt --)solve();return 0;
}

---

E. Monster

Problem Statement

Man, this Genshin boss is so hard. Good thing they have a top-up of $6$ coins for only $ $4.99$ . I should be careful and spend no more than I need to, lest my mom catches me…

You are fighting a monster with $z$ health using a weapon with $d$ damage. Initially, $d=0$. You can perform the following operations.

• Increase $d$ — the damage of your weapon by $1$, costing $x$ coins.
• Attack the monster, dealing $d$ damage and costing $y$ coins.

You cannot perform the first operation for more than $k$ times in a row.

Find the minimum number of coins needed to defeat the monster by dealing at least $z$ damage.

Input

The first line contains a single integer $t$ ($1\le t\le 100$) — the number of test cases.

The only line of each test case contains 4 integers $x$, $y$, $z$, and $k$ ($1\le x,y,z,k\le 10^8$) — the first operation’s cost, the second operation’s cost, the monster’s health, and the limitation on the first operation.

Output

For each test case, output the minimum number of coins needed to defeat the monster.

Example

input
4
2 3 5 5
10 20 40 5
1 60 100 10
60 1 100 10

output
12
190
280
160

note

In the first test case, $x=2$, $y=3$, $z=5$, and $k=5$. Here’s a strategy that achieves the lowest possible cost of $12$ coins:

• Increase damage by $1$, costing $2$ coins.
• Increase damage by $1$, costing $2$ coins.
• Increase damage by $1$, costing $2$ coins.
• Attack the monster, dealing $3$ damage, costing $3$ coins.
• Attack the monster, dealing $3$ damage, costing $3$ coins.

You deal a total of $3+3=6$ damage, defeating the monster who has $5$ health. The total number of coins you use is $2+2+2+3+3=12$ coins.

In the second test case, $x=10$, $y=20$, $z=40$, and $k=5$. Here’s a strategy that achieves the lowest possible cost of $190$ coins:

• Increase damage by $5$, costing $5\cdot x$ = $50$ coins.
• Attack the monster once, dealing $5$ damage, costing $20$ coins.
• Increase damage by $2$, costing $2\cdot x$ = $20$ coins.
• Attack the monster $5$ times, dealing $5\cdot 7=35$ damage, costing $5\cdot y$ = $100$ coins.

You deal a total of $5+35=40$ damage, defeating the monster who has exactly $40$ health. The total number of coins you use is $50+20+20+100=190$ coins.

Solution

具体见文后视频。

---

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long longusing namespace std;typedef pair<int, int> PII;
typedef long long LL;void solve() {int x, y, z, k;cin >> x >> y >> z >> k;int res = 1E18;for (int a = 0; a <= 20000; a ++) {int A = z - (a + 1) * a * k / 2;if (A < 0) break;int en;for (int j = max(1ll, a * k); j <= min(A, a * k + k); j = en + 1) {if (j == A) en = A;else en = (A - 1) / ((A - 1) / j);// cout << a << " " << j - a * k << " " << (A + j - 1) / j << ":" << a * (k * x + y) + (j - a * k) * x + (A + j - 1) / j * y << endl;res = min(res, a * (k * x + y) + (j - a * k) * x + (A + j - 1) / j * y);}}cout << res << endl;
}signed main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int dt;cin >> dt;while (dt --)solve();return 0;
}

---

F. Tree Operations

Problem Statement

This really says a lot about our society.

One day, a turtle gives you a tree with $n$ nodes rooted at node $x$. Each node has an initial nonnegative value; the $i$-th node has starting value $a_i$.

You want to make the values of all nodes equal to $0$. To do so, you will perform a series of operations on the tree, where each operation will be performed on a certain node. Define an operation on node $u$ as choosing a single node in $u$’s subtree${}^{\text{∗}}$ and incrementing or decrementing its value by $1$. The order in which operations are performed on nodes is as follows:

• For $1\le i\le n$, the $i$-th operation will be performed on node $i$.
• For $i>n$, the $i$-th operation will be performed on the same node as operation $i-n$.

More formally, the $i$-th operation will be performed on the $(((i-1)\mathrm{mod}n)+1)$-th node.${}^{\text{†}}$

Note that you cannot skip over operations; that is, you cannot perform the $i$-th operation without first performing operations $1,2,\dots ,i-1$.

Find the minimum number of operations you must perform before you can make the values of all nodes equal to $0$, assuming you pick operations optimally. If it’s impossible to make the values of all nodes equal to $0$ after finite operations, output $-1$.

${}^{\text{∗}}$The subtree of a node $u$ is the set of nodes for which $u$ lies on the shortest path from this node to the root, including $u$ itself.

${}^{\text{†}}$Here, $a\mathrm{mod}b$ denotes the remainder from dividing $a$ by $b$.

Input

The first line contains a single integer $t$ ($1\le t\le 100$) — the number of test cases.

The first line of each test case contains two integers $n$ and $x$ ($1\le n\le 2000$, $1\le x\le n$) — the number of nodes and the root of the tree.

The second line of each test case contains $n$ integers $a_1,a_2,\dots ,a_n$ ($0\le a_i\le 10^9$) — the starting value of each node.

Each of the next $n-1$ lines of each test case contains two integers $u$ and $v$ ($1\le u,v\le n$, $u\ne v$) representing an undirected edge from $u$ to $v$. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$.

Output

For each test case, output a single integer denoting the minimum amount of operations needed to make all nodes $0$. If it’s impossible to make all nodes $0$, output $-1$.

Example

input
5
2 1
1 2
1 2
3 2
2 1 3
2 1
3 2
4 1
1 1 0 1
1 2
2 3
1 4
12 6
14 4 5 6 12 9 5 11 6 2 1 12
3 9
10 6
6 12
4 3
3 1
5 11
9 7
5 6
1 8
2 8
5 1
1 1
0

output
3
6
5
145
0

Solution

具体见文后视频。

---

Code

#include <bits/stdc++.h>
#define fi first
#define se secondusing namespace std;typedef pair<int, int> PII;
typedef long long LL;const int N = 2E3 + 10;int n, rt;
int a[N], ord[N], idx;
LL dp[N];
std::vector<int> g[N];void DFS(int u, int fa) {for (auto v : g[u]) {if (v == fa) continue;DFS(v, u);}ord[ ++ idx] = u;
}void solve() {cin >> n >> rt;for (int i = 1; i <= n; i ++)cin >> a[i];for (int i = 1; i < n; i ++) {int u, v;cin >> u >> v;g[u].push_back(v), g[v].push_back(u);}idx = 0, DFS(rt, -1);LL res = 1E18;for (int i = 0; i < 2 * n; i ++ ) {LL lo = 0, ro = 1E9, cnt = 1E18;while (lo <= ro) {LL mid = lo + ro >> 1, x = mid * 2 * n + i;for (int i = 1; i <= n; i ++) dp[i] = 0;for (int i = 1; i <= n; i ++) {int u = ord[i];for (auto v : g[u]) dp[u] += dp[v];dp[u] += a[u] - (x / n + (x % n >= u));if (dp[u] < 0) dp[u] = (-dp[u]) % 2;}if (dp[rt] == 0) ro = mid - 1, cnt = x;else lo = mid + 1;}res = min(res, cnt);}cout << res << endl;for (int i = 1; i <= n; i ++) g[i].clear();
}signed main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int dt;cin >> dt;while (dt --)solve();return 0;
}

---

视频讲解

---

最后祝大家早日