Status of the team whose title has passed the code
A Array Click to view 388/4063
B Eezie and Pie Click to view 1042/2840
C Forest Click to view 38/144 failed
D Fourier and Theory for the Universe Click to view 11/61
E From AtCoder Click to view 6/47
F Hash Click to view 31/264
G Icon Design Click to view 1499/1873
H Jumping Steps Click to view 2/12
I Line Click to view 211/1576
J Number Game Click to view 1372/6243
K SolarPea and Inversion Click to view 3/13
L Stringing String Problem Click to view 0/37
M Z Name on grid Click to view 694/3648
G.Icon Design
Link: https://ac.nowcoder.com/acm/contest/33191/G
Source: Niuke.com
Title Description
What's the feeling of designing an icon for a school as a programmer? Now you have a chance doing it!
The icon of Nanjing Foreign Language School (NFLS for short) is not complicated, it can be represented as an ASCII art.
Since the icon might be used in different places, you need to print the icon in different size.
Given size nn, print the icon of size nn.
Detailed format is shown below, you can also look at the sample output to confirm it.
Like which is shown in the picture, '*' is used on the boundary, and '@' is used for the letters.
(n+1)(n+1) '.'s are used to seperate letters and the boundary horizontally, and nn '.'s are used vertically.
Each letter is (2n+3)(2n+3) characters wide and (2n+3)(2n+3) characters in height.
The icon's size is (4n+5) × (13n+19)(4n+5)×(13n+19).
Input description:
The first line contains a positive integer n(1\leq n\leq 5)n(1≤n≤5), representing the size of the icon.
Output description:
Print the icon of size nn.
Example 1
input
copy
1
output
copy
...
...@...@...@@@@@...@...@@@@@...
...@@...@...@...@...@...
...@.@.@...@@@@@...@...@@@@@...
...@...@@...@...@...@...
...@...@...@...@@@@@...@@@@@...
...
Example 2
input
copy
3
output
copy
...
...
...
...@...@...@@@@@@@@@...@...@@@@@@@@@...
...@@...@...@...@...@...
...@.@...@...@...@...@...
...@...@...@...@...@...@...
...@...@...@...@@@@@@@@@...@...@@@@@@@@@...
...@...@...@...@...@...@...
...@...@.@...@...@...@...
...@...@@...@...@...@...
...@...@...@...@@@@@@@@@...@@@@@@@@@...
...
...
...
meaning of the title
- Give a pattern of NFLS, simulate the pattern when n belongs to 1-5 according to the meaning rules, and output it.
Idea:
- You can print according to the meaning of the question. The code of the py method is relatively short, and cpp is also OK.
- And because the data is only 5, which is very small, you can also directly animate the pattern and save it in the array for output.
//C++
#include<bits/stdc++.h>
using namespace std;
int main(){
int n; cin>>n;
for(int i = 0; i < 4*n+5; i++){
for(int j=0; j < 13*n+19; j++){
if(i==0||j==0||i==4*n+4||j==13*n+18)printf("*");
else if((j==n+2||j==i+1||j==3*n+4||j==4*n+6||(j<=6*n+8&&j>4*n+6&&(i==n+1||i==2*n+2))||j==7*n+10||(j>7*n+10&&j<9*n+13&&(i==3*n+3))||((j==10*n+14)&&(i>=n+1&&i<=2*n+2||(i==3*n+3))||(j==12*n+16)&&(i>=2*n+2&&i<=3*n+3||(i==n+1)))||((j>10*n+14&&j<12*n+16)&&(i==n+1||i==2*n+2||i==3*n+3)))&&i>n&&i<3*n+4){
printf("@");
}else printf(".");
}
printf("\n");
}
return 0;
}
# python3
n=int(input())
print("*"*(13*n+19))
for i in range(n):
print("*"+"."*(13*n+17)+"*")
print("*"+"."*(n+1)+"@"+"."*(2*n+1)+"@"+"."*(n+1)+"@"*(2*n+3)+"."*(n+1)+"@"+"."*(3*n+3)+"@"*(2*n+3)+"."*(n+1)+"*")
for i in range(n):
print("*"+"."*(n+1)+"@"+'.'*i+"@"+"."*(2*n-i)+"@"+"."*(n+1)+("@"+"."*(3*n+3))*3+"*")
print("*"+"."*(n+1)+"@"+"."*n+"@"+"."*n+"@"+"."*(n+1)+"@"*(2*n+3)+"."*(n+1)+"@"+"."*(3*n+3)+"@"*(2*n+3)+"."*(n+1)+"*")
for i in range(n):
print("*"+"."*(n+1)+"@"+'.'*(i+n+1)+"@"+"."*(n-i-1)+"@"+"."*(n+1)+"@"+"."*(3*n+3)+"@"+"."*(5*n+5)+"@"+"."*(n+1)+"*")
print("*"+"."*(n+1)+"@"+"."*(2*n+1)+"@"+"."*(n+1)+"@"+"."*(3*n+3)+("@"*(2*n+3)+"."*(n+1))*2+"*")
for i in range(n):
print("*"+"."*(13*n+17)+"*")
print("*"*(13*n+19))
//charge by the meter
#include<bits/stdc++.h>
using namespace std;
int main(){
int n; cin>>n;
if(n==1){
cout<<"********************************"<<endl;
cout<<"*..............................*"<<endl;
cout<<"*..@...@..@@@@@..@......@@@@@..*"<<endl;
cout<<"*..@@..@..@......@......@......*"<<endl;
cout<<"*..@.@.@..@@@@@..@......@@@@@..*"<<endl;
cout<<"*..@..@@..@......@..........@..*"<<endl;
cout<<"*..@...@..@......@@@@@..@@@@@..*"<<endl;
cout<<"*..............................*"<<endl;
cout<<"********************************"<<endl;
}
if(n==2){
cout<<"*********************************************"<<endl;
cout<<"*...........................................*"<<endl;
cout<<"*...........................................*"<<endl;
cout<<"*...@.....@...@@@@@@@...@.........@@@@@@@...*"<<endl;
cout<<"*...@@....@...@.........@.........@.........*"<<endl;
cout<<"*...@.@...@...@.........@.........@.........*"<<endl;
cout<<"*...@..@..@...@@@@@@@...@.........@@@@@@@...*"<<endl;
cout<<"*...@...@.@...@.........@...............@...*"<<endl;
cout<<"*...@....@@...@.........@...............@...*"<<endl;
cout<<"*...@.....@...@.........@@@@@@@...@@@@@@@...*"<<endl;
cout<<"*...........................................*"<<endl;
cout<<"*...........................................*"<<endl;
cout<<"*********************************************"<<endl;
}
if(n==3){
cout<<"**********************************************************"<<endl;
cout<<"*........................................................*"<<endl;
cout<<"*........................................................*"<<endl;
cout<<"*........................................................*"<<endl;
cout<<"*....@.......@....@@@@@@@@@....@............@@@@@@@@@....*"<<endl;
cout<<"*....@@......@....@............@............@............*"<<endl;
cout<<"*....@.@.....@....@............@............@............*"<<endl;
cout<<"*....@..@....@....@............@............@............*"<<endl;
cout<<"*....@...@...@....@@@@@@@@@....@............@@@@@@@@@....*"<<endl;
cout<<"*....@....@..@....@............@....................@....*"<<endl;
cout<<"*....@.....@.@....@............@....................@....*"<<endl;
cout<<"*....@......@@....@............@....................@....*"<<endl;
cout<<"*....@.......@....@............@@@@@@@@@....@@@@@@@@@....*"<<endl;
cout<<"*........................................................*"<<endl;
cout<<"*........................................................*"<<endl;
cout<<"*........................................................*"<<endl;
cout<<"**********************************************************"<<endl;
}
if(n==4){
cout<<"***********************************************************************"<<endl;
cout<<"*.....................................................................*"<<endl;
cout<<"*.....................................................................*"<<endl;
cout<<"*.....................................................................*"<<endl;
cout<<"*.....................................................................*"<<endl;
cout<<"*.....@.........@.....@@@@@@@@@@@.....@...............@@@@@@@@@@@.....*"<<endl;
cout<<"*.....@@........@.....@...............@...............@...............*"<<endl;
cout<<"*.....@.@.......@.....@...............@...............@...............*"<<endl;
cout<<"*.....@..@......@.....@...............@...............@...............*"<<endl;
cout<<"*.....@...@.....@.....@...............@...............@...............*"<<endl;
cout<<"*.....@....@....@.....@@@@@@@@@@@.....@...............@@@@@@@@@@@.....*"<<endl;
cout<<"*.....@.....@...@.....@...............@.........................@.....*"<<endl;
cout<<"*.....@......@..@.....@...............@.........................@.....*"<<endl;
cout<<"*.....@.......@.@.....@...............@.........................@.....*"<<endl;
cout<<"*.....@........@@.....@...............@.........................@.....*"<<endl;
cout<<"*.....@.........@.....@...............@@@@@@@@@@@.....@@@@@@@@@@@.....*"<<endl;
cout<<"*.....................................................................*"<<endl;
cout<<"*.....................................................................*"<<endl;
cout<<"*.....................................................................*"<<endl;
cout<<"*.....................................................................*"<<endl;
cout<<"***********************************************************************"<<endl;
}
if(n==5){
cout<<"************************************************************************************"<<endl;
cout<<"*..................................................................................*"<<endl;
cout<<"*..................................................................................*"<<endl;
cout<<"*..................................................................................*"<<endl;
cout<<"*..................................................................................*"<<endl;
cout<<"*..................................................................................*"<<endl;
cout<<"*......@...........@......@@@@@@@@@@@@@......@..................@@@@@@@@@@@@@......*"<<endl;
cout<<"*......@@..........@......@..................@..................@..................*"<<endl;
cout<<"*......@.@.........@......@..................@..................@..................*"<<endl;
cout<<"*......@..@........@......@..................@..................@..................*"<<endl;
cout<<"*......@...@.......@......@..................@..................@..................*"<<endl;
cout<<"*......@....@......@......@..................@..................@..................*"<<endl;
cout<<"*......@.....@.....@......@@@@@@@@@@@@@......@..................@@@@@@@@@@@@@......*"<<endl;
cout<<"*......@......@....@......@..................@..............................@......*"<<endl;
cout<<"*......@.......@...@......@..................@..............................@......*"<<endl;
cout<<"*......@........@..@......@..................@..............................@......*"<<endl;
cout<<"*......@.........@.@......@..................@..............................@......*"<<endl;
cout<<"*......@..........@@......@..................@..............................@......*"<<endl;
cout<<"*......@...........@......@..................@@@@@@@@@@@@@......@@@@@@@@@@@@@......*"<<endl;
cout<<"*..................................................................................*"<<endl;
cout<<"*..................................................................................*"<<endl;
cout<<"*..................................................................................*"<<endl;
cout<<"*..................................................................................*"<<endl;
cout<<"*..................................................................................*"<<endl;
cout<<"************************************************************************************"<<endl;
}
return 0;
}
J.Number Game
Link: https://ac.nowcoder.com/acm/contest/33191/J
Source: Niuke.com
Title Description
There are three integers A, BA,B and CC written on the blackboard.
You can perform the following two operations as many times as you like:
- Change BB to A-BA−B.
- Change CC to B-CB−C.
Please note that each time you don't need to perform all two operations. You can choose one type of operation to perform.
You are given an integer xx. Answer whether you can change CC into xx using these operations.
You need to answer TT queries independently.
Input description:
The first line contains a positive integer T(1\leq T\leq 10 ^ 5)T(1≤T≤10
5
).
Each of the next TT lines contains four integers A, B, C, x(-10 ^ 8 \leq A, B, C, x \leq 10 ^ 8)A,B,C,x(−10
8
≤A,B,C,x≤10
8
).
Output description:
For each test case, output "Yes" if CC can become xx, and "No" otherwise (without quotes).
Example 1
input
copy
3
2 4 3 1
2 4 3 2
4 2 2 0
output
copy
Yes
No
Yes
explain
Please note that A, B, C, xA,B,C,x could be negative.
remarks:
Please note that A, B, C, xA,B,C,x could be negative.
Title:
- Given four numbers of ABCx, each operation can make B=A-B, or C=B-C.
- Both operations can be performed for any number of times to find whether there is a case where C=x.
Idea:
- It is found that doing twice 𝐵=119860𝐵 − 𝐵 equals not doing it, and doing twice 𝐶=𝐵 − 𝐶 equals not doing it, so the two operations will inevitably alternate.
b1 = a-b
c1 = b-c
c2 = b1-c1 = (a-b)-(b-c)=a-2b+c = c+(a-2b)
It can be seen that one a-2b will be added for each operation. A number of operations are k more. - If the two operations are used for the same number of times, 𝐶 can become a set 𝑆={𝑥 ｜𝑥=𝐶+𝑘 × (𝐴−2 × 𝐵)}, if the times are different, 𝑆={𝑥 ｜𝑥=𝐵 − 𝐶+𝑘 × (𝐴−2 × 𝐵)}
- Pay attention to special judgment 𝐴=2 × Situation of 𝐵
#include<bits/stdc++.h>
using namespace std;
int main(){
int T; cin>>T;
while(T--){
int a, b, c, x; cin>>a>>b>>c>>x;
if(a-2*b!=0){
if((x-c)%(a-2*b)==0 || (x-(b-c))%(a-2*b)==0){
cout<<"Yes\n";
}else{
cout<<"No\n";
}
}else{
if((x-c)==0 || (x-(b-c))==0){
cout<<"Yes\n";
}else{
cout<<"No\n";
}
}
}
return 0;
}
B.Eezie and Pie
Link: https://ac.nowcoder.com/acm/contest/33191/B
Source: Niuke.com
Title Description
Eezie, a pie maniac, would like to have some pies with her friends on a hot summer day. However, the weather is so hot that she can't go outdoors and has to call for the delivery service.
The city Eezie lives in can be represented by NN nodes connected by N - 1N−1 edges, and the city center is node 11. In other words, the city is a rooted tree, root of which is node 11. There are NN pie houses in the city, the ii-th on node ii. For some reason, a pie house on node ii can only deliver its pie to nodes on the simple path from node ii to node 11.
Eezie is a bit worried that a pie might lose its flavor during the deliver. After some careful calculation, she decided that a pie from the ii-th pie house can maintain its flavor if the distance it is delivered does not exceed its flavor-loss-distance d_id
i
. The distance between two nodes on the tree is the number of edges on the simple path between them.
Now, Eezie wants to order some pies for all her friends who live on different nodes of the tree. Therefore, she wants you to calculate for each node how many pie houses can deliver their pie to the node without flavor loss.
Input description:
The first line contains an integer N(1\le N \le 2\times 10^6)N(1≤N≤2×10
6
), representing the number of nodes of the city Eezie lives in.
Each of the next N - 1N−1 lines contains two integers u, v(1\le u,v \le N)u,v(1≤u,v≤N), representing an edge. It is guaranteed that the edges form a tree.
The last line contains NN integers d_1, d_2, \cdots, d_N(0\le d_i \le N)d
1
,d
2
,⋯,d
N
(0≤d
i
≤N), representing the maximum travel distances for pies from pie houses.
Output description:
Output NN integers in a line, the ii-th integer representing the answer for node ii.
Example 1
input
copy
10
1 2
2 3
2 4
3 5
4 6
4 7
1 8
8 9
8 10
0 0 1 2 2 5 3 1 0 2
output
copy
6 6 2 3 1 1 1 2 1 1
Title:
- Given a tree with n points, each point u has a weight value, that is, it can go up ai step (only through the path of root node 1). Now give each point on the path of each point network+1, and calculate the final value of each point.
Idea:
- If we can quickly find the 𝑘 level ancestors of each point, we can use the difference on the tree to find the final value.
- For k-level ancestors,
(1) Long chain partition can be used to calculate the 𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘119.
(2) You can also maintain the dfs stack during dfs. When you access the point, its ancestors must be down the current stack. Using this property, we can find all ancestors.
(3) You can also multiply the violence to find k-level ancestors. - For the difference on the tree, it should be noted that the difference of the tree is from the leaf node to the root node, from the bottom to the top (because there will be a part of the sum of prefixes from the top to the bottom that will be added more due to repeated statistics).
#include <bits/stdc++.h>
using namespace std;
#define RG register int
#define LL long long
const int maxn = 2e6+10;
//Quick read template
template<typename elemType>
inline void Read(elemType& T) {
elemType X = 0, w = 0; char ch = 0;
while (!isdigit(ch)) { w |= ch == '-';ch = getchar(); }
while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
T = (w ? -X : X);
}
//Save drawing template
struct Graph {
struct edge { int Next, to; };
edge G[maxn << 1];
int head[maxn];
int cnt;
Graph() :cnt(2) {}
void clear(int n) {
cnt = 2;fill(head, head + n + 2, 0);
}
void add_edge(int u, int v) {
G[cnt].to = v;
G[cnt].Next = head[u];
head[u] = cnt++;
}
};
Graph G;
int N, M;
//Long chain partition template
int Deep[maxn], Height[maxn], Anc[maxn][20], Top[maxn], Hson[maxn];
int highbit[maxn], MaxDeep[maxn];
vector<int> Up[maxn], Down[maxn], Path;
void DFS1(int u, int fa) {
Anc[u][0] = fa;
Height[u] = 1;
for (int i = 1;i < 20;++i)
Anc[u][i] = Anc[Anc[u][i - 1]][i - 1];
for (int i = G.head[u];i;i = G.G[i].Next) {
int v = G.G[i].to;
if (v == fa) continue;
Deep[v] = Deep[u] + 1;
DFS1(v, u);
Height[u] = max(Height[u], Height[v] + 1);
if (Height[Hson[u]] < Height[v]) Hson[u] = v;
}
return;
}
void DFS2(int u, int fa, int top) {
Path.push_back(u);
Top[u] = top;
MaxDeep[top] = max(MaxDeep[top], Deep[u]);
Down[top].push_back(u);
if (Hson[u]) DFS2(Hson[u], u, top);
for (int i = G.head[u];i;i = G.G[i].Next) {
int v = G.G[i].to;
if (v == fa || v == Hson[u]) continue;
DFS2(v, u, v);
}
if (u == top) {
int len = MaxDeep[top] - Deep[u] + 1;
for (int i = Path.size() - 1;i >= max((int)Path.size() - len - 1, 0);--i)
Up[top].push_back(Path[i]);
}
Path.pop_back();
}
int KthAnc(int u, int k) { //Finding k-order ancestors of u
if (k > Deep[u]) return 0;
if (k == 0) return u;
u = Anc[u][highbit[k]];
k -= (1 << highbit[k]);
if (Deep[u] - k == Deep[Top[u]]) return Top[u];
if (Deep[u] - k > Deep[Top[u]]) return Down[Top[u]][Deep[u] - k - Deep[Top[u]]];
return Up[Top[u]][Deep[Top[u]] - (Deep[u] - k)];
}
//Finding prefix sum for difference on tree
int v[maxn];
LL s[maxn], ans[maxn];
int dfs(int u, int f){
for (int i = G.head[u];i;i = G.G[i].Next) {
int v = G.G[i].to;
if (v == f) continue;
dfs(v,u);
ans[u] += ans[v];
}
ans[u] += s[u];
return ans[u];
}
int main() {
Read(N);
for (int i = 1;i <= N - 1;++i) {
int u, v;
Read(u);Read(v);
G.add_edge(u, v);
G.add_edge(v, u);
}
DFS1(1, 0);
DFS2(1, 0, 1);
int Max = 1;
for (int i = 1;i <= N;++i) {
if ((i >> Max) & 1) ++Max;
highbit[i] = Max - 1;
}
for(int i = 1; i <= N; i++){
ans[i] = 0; s[i] = 1; //Each point will be+1, so the direct initial value is+1
}
for(int i = 1; i <= N; i++){
cin>>v[i];
int lst = KthAnc(i,v[i]+1); //k+1 ancestor of the ith point
s[lst]--;
}
dfs(1,-1);
for(int i = 1; i <= N; i++){
cout<<ans[i]<<" ";
}
cout<<"\n";
return 0;
}
M.Z-Game on grid
Link: https://ac.nowcoder.com/acm/contest/33191/M
Source: Niuke.com
Title Description
Alice and Bob are playing a game on an n\times mn×m grid where each cell has either 'A', 'B' or '.' written on it. They take turns moving a chess piece on the grid and Alice moves first.
Initially the piece is on cell (1,1)(1,1). In each player's turn, he or she can move the piece one cell right or one cell down. That is, if the piece is on cell (x,y)(x,y) before the turn, the player can move it to (x+1,y)(x+1,y) or (x,y+1)(x,y+1), as long as it doesn't go beyond the grid.
At any time, if the piece is on a cell with 'A', Alice wins and the game ends. If the piece is on a cell with 'B', Bob wins and the game ends. If the piece reaches cell (n,m)(n,m) without the game ending, then it is a draw.
Since Alice cannot decide what acts Bob will take, she would like to know if she can be in control of the situation. Given the grid they're playing on, can you tell her if she can always find a way to win, draw or lose the game no matter what acts Bob takes?
Input description:
In the first line an integer T\space (1 \le T \le 50)T (1≤T≤50), representing the number of test cases.
For each test case, the first line contains two integers N,M\space (1\le N,M \le 500)N,M (1≤N,M≤500), representing the grid's size.
Each of the next NN lines for the case contains MM characters (either 'A', 'B' or '.'), describing the grid.
Output description:
For each test case, output three words 'yes' or 'no' in one line, representing if Alice can find a way to win, draw or lose the game respectively (without quotes).
Example 1
input
copy
2
3 3
...B
...B
BB.
1 3
...
output
copy
no no yes
no yes no
Title:
- Two people take turns to move a chess piece on the grid. The initial position of the chess piece is (1,1), and it can only move one space to the positive direction (right or below) of a certain dimension each time.
- There are some special points on the grid. Move to the point marked 'A' to win first, move to the point marked 'B' to lose first. If you do not move to the special point and can no longer move the pieces, it will be a draw. Ask if the first player has a strategy of winning, drawing and losing.
Idea:
- In a situation, only the position of the chess pieces and the current round will affect the final outcome. The chess pieces can only move right or down, so the state has no aftereffect. So we can consider dp
- It can be found that the three methods of winning and losing are similar. Here we take the first win as an example:
Use a Boolean number 𝑑 𝑝 [𝑗] [𝑗] to indicate whether the first move to (𝑗) will win. Because only one space can be moved at a time, A moves first, so you can know whether to move first or later when the position is determined. For the first hand and the second hand, separate transfer is required: - If manual operation is used first, then if one of (𝑗+1, 𝑗) and (𝑗+1) can make the first hand win, (𝑗) is the first hand win.
If the manual operation is later, then only (｜+1, 𝑗) and (｜, 𝑗+1) can make the first hand win, and (｜, 𝑗) can make the first hand win.
#include<bits/stdc++.h>
using namespace std;
const int maxn = 550;
char s[maxn][maxn];
int dp[maxn][maxn], n, m; //Move to (μ,𝑗𝑗𝑗𝑗𝑗𝑗𝑗𝑗𝑗𝑗𝑗𝑗𝑗𝑗119
int dfs(int x, int y){
if(dp[x][y]>=0)return dp[x][y]; //Memorization
if(s[x][y] == 'A')return 1; //Win (x,y win will interrupt x+1,y draw and so on, unable to come forward)
if(s[x][y] == 'B')return 4; //Losing
if(x==n&&y==m)return 2; //A tie
if(x==n)return dp[x][y]=dfs(x,y+1);
if(y==m)return dp[x][y]=dfs(x+1,y);
if((x+y)%2==0){ //It's the turn to move first, as long as one of the two can win/draw/lose
return dp[x][y]=dfs(x+1,y)|dfs(x,y+1);
}else{ //At present, it's the turn of the hind hand to move. You need both to win/draw/lose
return dp[x][y]=dfs(x+1,y)&dfs(x,y+1);
}
}
int main(){
int T; cin>>T;
while(T--){
cin>>n>>m;
for(int i = 1; i <= n; i++)scanf("%s",s[i]+1);
memset(dp,-1,sizeof(dp));
int ans = dfs(1,1);
if(ans&1)cout<<"yes ";else cout<<"no ";
if(ans&2)cout<<"yes ";else cout<<"no ";
if(ans&4)cout<<"yes\n";else cout<<"no\n";
}
return 0;
}
A.Array
Link: https://ac.nowcoder.com/acm/contest/33191/A
Source: Niuke.com
Title Description
Ranran has a sequence aa of nn integers a_1, a_2, \cdots, a_na
1
,a
2
,⋯,a
n
which satisfies \displaystyle \sum \dfrac 1 {a_i} \leq \dfrac 1 2∑
a
i
1
≤
2
1
and he is very proud of it, so he comes up with a problem for you.
You need to find out a sequence cc of mm integers c_0, c_1, \cdots, c_{m - 1}c
0
,c
1
,⋯,c
m−1
. With cc, you construct an infinite sequence bb, and b_ib
i
equals to c_{i\bmod m}c
imodm
. bb must satisfy the condition that in every consecutive a_ia
i
numbers of bb there exists a number equals to ii.
Please note that aa is 1-indexed and b, cb,c are 0-indexed. The value of mm is decided by you.
Can you solve the problem?
Input description:
The first line contains an integer n\ (1\leq n\leq 10 ^ 5)n (1≤n≤10
5
).
The second line contains nn integers a_1, a_2, \cdots, a_n\ (2\leq a_i \leq 2 \times 10 ^ 5, \sum \dfrac 1 {a_i} \leq \dfrac 1 2)a
1
,a
2
,⋯,a
n
(2≤a
i
≤2×10
5
,∑
a
i
1
≤
2
1
).
Output description:
The first line output an integer mm.
The second line output mm integers c_0, c_1, \cdots, c_{m - 1}c
0
,c
1
,⋯,c
m−1
.
You should guarantee that 1\leq m\leq 10 ^ 61≤m≤10
6
and 1\leq c_i\leq n1≤c
i
≤n.
Example 1
input
copy
1
2
output
copy
2
1 1
Title:
- Give an array whose length is n(1e5), each number ai (<2e5), and the sum of the reciprocal of all numbers<1/2.
- You need to construct a sequence with length m (<1e6). After satisfying the infinite copy of ci, i will appear once in each ai number.
- The title guarantees the existence of legal schemes.
Idea:
-
i appears once in each ai number. Obviously, the smaller the ai is, the more times (frequencies) it needs to appear. After sorting according to the ascending order of ai, it should be optimal to find the position that can be put up first each time.
-
Consider how to use conditional reciprocal sum less than or equal to 1/2.
Both sides of the equation are multiplied by 2, and each fraction on the left is multiplied by 2, which is equivalent to the denominator/2. That is, when each number ai is reduced to ai/2, the reciprocal sum is<1, and then ai is expanded. Obviously, the reciprocal sum is smaller, still less than 1.
Each_ ｜ Change it to a power smaller than his largest 2, and obviously the sum of reciprocal is less than or equal to 1.
Then, construct Huffman tree?, That is, the tree with the shortest weighted path length, and why m=1<<18 (,, -
But this problem is actually OK. The condition of less than or equal to 1/2 is not necessary, because the problem is guaranteed to have a solution(
Therefore, the greedy people from small to large can directly let m=the maximum value 1e6, and then violently find the first place in front or behind. If it is not enough, it will be added forward, and if it is more than enough, it will be moved backward until it can connect to the next cycle section to meet the requirements of<=a [i]. w.
//std
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
struct node{ int w, id;}a[maxn];
bool cmp(node x, node y){ return x.w < y.w; }
int b[maxn];
int main(){
ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
int n; cin>>n;
for(int i = 1; i <= n; i++){
cin>>a[i].w; a[i].id = i;
a[i].w = (1<<31-__builtin_clz(a[i].w));
}
sort(a+1,a+n+1,cmp); //Sort from small to large
int cur = 1, m = (1<<18);
for(int i = 1; i <= n; i++){
while(b[cur])cur++; //Find the first place to put it
for(int j = cur; j <= m; j += a[i].w){
b[j] = a[i].id;
}
}
cout<<m<<"\n";
for(int i = 1; i <= m; i++)cout<<max(1,b[i])<<" ";
return 0;
}
//greedy
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6+10;
struct node{ int w, id;}a[maxn];
bool cmp(node x, node y){ return x.w < y.w; }
int b[maxn];
int main(){
ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
int n; cin>>n;
for(int i = 1; i <= n; i++){
cin>>a[i].w; a[i].id = i;
}
sort(a+1,a+n+1,cmp); //Sort from small to large
int cur = 1, m = 1e6;
for(int i = 1; i <= n; i++){
while(b[cur])cur++; //Find the first place to put it
for(int j = cur; ; j += a[i].w){
while(b[j] || j>m)j--; //If it has been filled in or exceeded, it will be returned (guaranteed to have a solution)
b[j] = a[i].id;
if(m-j+cur<=a[i].w)break; //If you can connect the next cycle section, break
}
}
cout<<m<<"\n";
for(int i = 1; i <= m; i++)cout<<max(1,b[i])<<" ";
return 0;
}