@[toc]
补题链接：https://ac.nowcoder.com/acm/contest/31454
A.So I'll Max Out My Constructive Algor…
链接：https://ac.nowcoder.com/acm/contest/31454/A
来源：牛客网
题目描述
BaoBao the Witch is stuck in a maze with nn rows and nn columns, where the height of the cell in the ii-th row and the jj-th column is h_{i,j}h
i,j
. To get out of the maze, BaoBao has to find a path which passes through each cell exactly once. Each time she can only move into the neighboring cell sharing a same edge with the current one. But as we know, BaoBao is super lazy, so every time when she climbs up (that is to say, moving from a cell with a smaller height to another with a larger height) her happiness value will decrease. As her helping hand, your task is to find a valid path so that when moving along the path, the number of times BaoBao climbs up will not be more than the number of times she climbs down.
More formally, you need to find a sequence (x_1, y_1), (x_2, y2), \cdots, (x{n^2}, y_{n^2})(x
1
,y
1
),(x
2
,y
2
),⋯,(x
n
2
,y
n
2
) such that:
For all 1 \le i \le n^21≤i≤n
2
, 1 \le x_i, y_i \le n1≤x
i
,y
i
≤n;
For all 1 \le i, j \le n^2, i \neq j1≤i,j≤n
2
,i
=j, (x_i, y_i) \neq (x_j, y_j)(x
i
,y
i
)
=(x
j
,y
j
);
For all 2 \le i \le n^22≤i≤n
2
, |xi - x{i-1}| + |yi - y{i-1}| = 1∣x
i
−x
i−1
∣+∣y
i
−y
i−1
∣=1;
\sum\limits{i=2}^{n^2}{[h{x{i-1}, y{i-1}} < h_{x_i, yi}]} \le \sum\limits{i=2}^{n^2}{[h{x{i-1}, y{i-1}} > h{x_i, y_i}]}
i=2
∑
n
2
[h
x
i−1
,y
i−1
<h
x
i
,y
i
]≤
i=2
∑
n
2
[h
x
i−1
,y
i−1
h
x
i
,y
i
], where [P][P] equals 11 when PP is true, and equals 00 when it is false.
Additionally, you discover that the heights in all cells are a permutation of n^2n
2
, so you just need to output the height of each cell in a valid path.
输入描述:
There are multiple test cases. The first line of the input contains an integer TT (1 \le T \le 1001≤T≤100) indicating the number of test cases. For each test case:
The first line contains an integer nn (2 \le n \le 642≤n≤64) indicating the size of the maze.
For the following nn lines, the ii-th line contains nn integers h{i, 1}, h{i, 2}, \cdots, h{i,n}h
i,1
,h
i,2
,⋯,h
i,n
(1 \le h{i, j} \le n^21≤h
i,j
≤n
2
) where h_{i,j}h
i,j
indicates the height of the cell in the ii-th row and the jj-th column. It's guaranteed that all integers in the input make up a permutation of n^2n
2
.
输出描述:
For each test case output one line containing n^2n
2
separated by a space indicating the heights of each cell in a valid path. If there are multiple valid answers you can output any of them. It's easy to prove that an answer always exists.
Please, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect!
示例1
输入
复制
1
2
4 3
2 1
输出
复制
4 3 1 2
题意：
- T<100, n<64，给出一个n*n的迷宫，每个点有一个高度。
- 选择一个点开始，遍历所有点，要求这条路径满足所有点仅且只能遍历一次，同时这条路径向上走（即从高度低的地方走到高度高的地方）的次数小于等于向下走的次数。
思路：
- 因为是个互逆的条件，所以对于任何一条遍历所有点的路径，如果不满足向上走<=向下走，那么这条路径的反向就必然满足这个条件。
- 随便找一条遍历所有点的路径，如果不满足就反向输出即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 100;
int a[N][N];
void solve(){
int n; cin>>n;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
cin>>a[i][j];
vector<int>p;
for(int i = 0; i < n; i++){
if(i%2){
for(int j = 0; j < n; j++)p.push_back(a[i][j]);
}else{
for(int j = n-1; j >= 0; j--)p.push_back(a[i][j]);
}
}
int cc = 0;
for(int i = 1; i < p.size(); i++){
if(p[i]>p[i-1])cc--;
else cc++;
}
if(cc < 0)reverse(p.begin(), p.end());
for(int i = 0; i < p.size(); i++){
cout<<p[i]<<" \n"[i==p.size()-1];
}
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T; cin>>T;
while(T--){
solve();
}
return 0;
}
K.Link-Cut Tree
链接：https://ac.nowcoder.com/acm/contest/31454/K
来源：牛客网
题目描述
BaoBao just learned how to use a data structure called link-cut tree to find cycles in a graph and decided to give it a try. BaoBao is given an undirected graph with nn vertices and mm edges, where the length of the ii-th edge equals 2^i2
i
. She needs to find a simple cycle with the smallest length.
A simple cycle is a subgraph of the original graph containing kk (3 \le k \le n3≤k≤n) vertices a_1, a_2, \cdots, a_ka
1
,a
2
,⋯,a
k
and kk edges such that for all 1 \le i \le k1≤i≤k there is an edge connecting vertices aia
i
and a{(i \mod k) + 1}a
(imodk)+1
in the subgraph. The length of a simple cycle is the total length of the edges in the cycle.
输入描述:
There are multiple test cases. The first line of the input contains an integer TT indicating the number of test cases. For each test case:
The first line contains two integers nn and mm (3 \le n \le 10^53≤n≤10
5
, 1 \le m \le 10^51≤m≤10
5
) indicating the number of vertices and edges in the original graph.
For the following mm lines, the ii-th line contains two integers u_iu
i
and v_iv
i
(1 \le u_i, v_i \le n1≤u
i
,v
i
≤n) indicating an edge connecting vertices u_iu
i
and v_iv
i
with length 2^i2
i
. There are no self loops nor multiple edges. Note that the graph is not necessarily connected.
It's guaranteed that neither the sum of nn nor the sum of mm of all test cases will exceed 10^610
6
.
输出描述:
For each test case output one line. If there are no simple cycles in the graph output "-1" (without quotes); Otherwise output kk integers separated by a space in increasing order indicating the indices of the edges in the simple cycle with the smallest length. It can be shown that there is at most one answer.
Please, DO NOT output extra spaces at the end of each line, or your solution may be considered incorrect!
示例1
输入
复制
2
6 8
1 2
2 3
5 6
3 4
2 5
5 4
5 1
4 2
4 2
1 2
4 3
输出
复制
2 4 5 6
-1
备注:
The first sample test case is shown below. The integers beside the edges are their indices (outside the parentheses) and lengths (inside the parentheses). The simple cycle with the smallest length consists of edges 22, 44, 55 and 66 with a length of 2^2 + 2^4 + 2^5 + 2^6 = 1162
2
+2
4
+2
5
+2
6
=116.
题意：
- 给出一个n个点m条边的无向图，第i条边的边长为2^i， 找到一个长度最小的环，从小到达输出构成这个环的边。
- n, m < 1e5
思路：
- 要环的长度最小，贪心的依次向图中加入边，当出现一个环的时候，这个环就是长度最小的那个。
- 每次加边前用并查集判断这条边的两个点是否联通，如果未联通就合并，联通了就dfs去找环输出。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int fa[N+10];
void init(int n){
for(int i = 0; i <= n; i++)fa[i]=i;}
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){
x=find(x);y=find(y);if(x!=y)fa[x]=y;}
vector<pair<int,int> >G[N];
vector<int>res;
void dfs(int u, int f, int me){
if(u == me){
sort(res.begin(), res.end());
for(int i = 0; i < res.size(); i++){
cout<<res[i]<<" \n"[i==res.size()-1];
}
}
for(auto t : G[u]){
int to = t.first, id = t.second;
if(to==f)continue;
res.push_back(id);
dfs(to, u, me);
res.pop_back();
}
}
void solve(){
int n, m; cin>>n>>m;
res.clear();
for(int i = 1; i <= n; i++){
G[i].clear(); fa[i] = i;}
int ok = 0;
for(int i = 1; i <= m; i++){
int x, y; cin>>x>>y;
if(ok==1)continue; //输入需要全部都输进来，不然直接return了会TLE
int xx = find(x), yy = find(y);
if(xx==yy){
res.push_back(i);
dfs(x, 0, y);
ok = 1;
}
merge(xx,yy);
G[x].push_back({
y, i});
G[y].push_back({
x, i});
}
if(ok==0)cout<<"-1\n";
return ;
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T; cin>>T;
while(T--){
solve();
}
return 0;
}
F.Sandpile on Clique
链接：https://ac.nowcoder.com/acm/contest/31454/F
来源：牛客网
题目描述
TheAbelian Sandpile Modelis a famous dynamical system displaying self-organized criticality. It has been studied for decades since it was introduced by Per Bak, Chao Tang and Kurt Wiesenfeld in a 1987 paper. The sandpile prediction is of wide interest in physics,
computer science, and mathematics, both for its beautiful algebraic structure and for its relevance to applications like load balancing and derandomization of models like internal diffusion-limited aggregation. The sandpile model is related to many other models and physical phenomena, like the rotor-routing model, avalanche models.
In the sandpile model, we are given an undirected graph GG whose vertices are indexed from 11 to nn. We're also given nn integers a_1, a_2, \cdots, a_na
1
,a
2
,⋯,a
n
where a_ia
i
indicates that there are a_ia
i
chips placed on vertex ii initially. Each turn we will pick an arbitrary vertex vv such that the number of chips on vv is not smaller than the number of edges connecting vv, denoted as d_vd
v
. For each neighbor of vv, it will receive one chip from vv. Therefore, vv will lost d_vd
v
chips. This process is called firing or toppling. Firing will keep happening until no vertex vv has at least d_vd
v
chips.
It can be proven that the order of firing doesn't affect the result. Meanwhile, it is also possible that the firing will never terminate. This instance is described as "recurrent". Now you are given a clique and the initial number of chips. Determine whether this instance is a recurrent one. If not, please output the final number of chips for each node respectively.
A clique (also called a complete graph) is a graph where every two vertices are connected with an edge.
输入描述:
There is only one test case in each test file.
The first line of the input contains an integer nn (2 \leq n \leq 5 \times 10^52≤n≤5×10
5
) indicating the size of the clique.
The second line contains nn integers a_1, a_2, \cdots, a_na
1
,a
2
,⋯,a
n
(0 \leq a_i \leq 10^90≤a
i
≤10
9
) where a_ia
i
indicates the initial number of chips placed on vertex ii.
输出描述:
Output one line. If the given sandpile instance will terminate, output nn integers separated by a space where the ii-th integer indicates the final number of chips on the ii-th vertex. Otherwise output "Recurrent" (without quotes) instead.
Please, DO NOT output extra spaces at the end of each line or your solution may be considered incorrect!
示例1
输入
复制
5
5 0 3 0 3
输出
复制
3 3 1 3 1
示例2
输入
复制
2
1 0
输出
复制
Recurrent
备注:
For the first sample test case:
We can only select vertex 11 at the beginning. The number of chips becomes {1, 1, 4, 1, 4}{1,1,4,1,4}.We can now select vertex 33 or 55 because both of them have at least 44 chips. We select vertex 33 and the number of chips becomes {2, 2, 0, 2, 5}{2,2,0,2,5}. Selecting vertex 55 will lead to the same result.We now select vertex 55. The number of chips becomes {3, 3, 1, 3, 1}{3,3,1,3,1}. There is no vertex with at least 44 chips so the firing terminates.
For the second sample test case, we can select vertex 11 and 22 repeatedly. The firing never terminates.
题意：
- 给出一个n个点的完全图，每个点上有一个权值。
- 当某个点权值大于与它相连的边时，它可以失去与边数相同的权值，然后给每一个连通的点分配 1 的权值。
- 问图上每个点的权值最后会不会趋于一个值不变，如果会，输出最后每一个点的权值，否则输出 "Recurrent"。
思路：
- 可以打个表找个规律，看看最后会趋向于什么情况。
- 如果能分配n次，那么第n次时，至少有1个点分到了n-1（最后一个点），1个点分到了n-2（倒数第2个点），1个点分到了n-3（倒数第3个点），，，1。 然后从n-1的点再向其他所有点分1次，就会诞生一个新的n-1的点，然后就会无限循环下去了。
- 大根堆模拟，每次用权值最大的点分配，看看轮数能不能达到n即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int a[N];
void solve(){
int n; cin>>n;
priority_queue<pair<int,int> >q;
for(int i = 1; i <= n; i++){
cin>>a[i]; q.push({
a[i], i});
}
for(int i = 1; i <= n; i++){
int x = q.top().first, id = q.top().second; q.pop();
if(x+i-1 >= n-1){
//第i轮获得i-1块饼干
a[id] = (x+i-1)-(n-1)-i; //先不算i
q.push({
a[id], id});
}else{
//不够分
for(int j = 1; j <= n; j++){
cout<<a[j]+(i-1)<<" \n"[j==n];
}
return ;
}
}
cout<<"Recurrent\n";
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T=1; //cin>>T;
while(T--){
solve();
}
return 0;
}
C.Laser Trap
链接：https://ac.nowcoder.com/acm/contest/31454/C
来源：牛客网
题目描述
BaoBao is playing the famous gameElden Ringthese days. It's an open-world game in which you can control your character to travel from places to places. However, your character could also enter a trap and you need to figure out how to escape. Right now, BaoBao's character is stuck in a 2-dimensional plane with deadly lasers. There are nn laser generators (each can be regarded as a point) shooting laser beams between every pair of them (so there are \frac{n(n-1)}{2}
2
n(n−1)
laser beams in total). The beams start and end at generator points and do not stretch to infinity.
Starting at point (0,0)(0,0), BaoBao wants to escape to point (10^{10^{10^{10^{10}}}}, 10^{10^{10^{10^{10}}}})(10
10
10
10
10
,10
10
10
10
10
) without touching any laser beam or generator. In order to do so, BaoBao can ask her friend DreamGrid to remove any number of laser generators, together with any laser beam that starts or ends at these generators. Output the minimum number of laser generators that need to be erased for the escape.
Note that BaoBao does not need to move in a specific direction to escape. Her escaping route can even be a curve if necessary.
输入描述:
There are multiple test cases. The first line of the input contains an integer TT indicating the number of test cases. For each test case:
The first line contains an integer nn (1 \le n \le 10^61≤n≤10
6
) indicating the number of laser generators.
For the following nn lines, the ii-th line contains two integers x_ix
i
and y_iy
i
(-10^9 \le x_i, y_i \le 10^9−10
9
≤x
i
,y
i
≤10
9
) indicating the location of the ii-th laser generator.
It is guaranteed that no two generators coincide, and no laser beam or generator will touch (0,0)(0,0).
It is also guaranteed that the sum of nn of all test cases will not exceed 10^610
6
.
输出描述:
For each test case output one line containing one integer indicating the minimum number of generators that need to be removed.
示例1
输入
复制
3
2
1 0
2 0
3
1 0
0 1
-1 -1
5
2 -1
1 2
-1 2
-2 -1
0 -2
输出
复制
0
1
2
备注:
The second and the third sample test cases are shown below. Solid dots and lines represent the remaining laser generators and beams, while hollow dots and dashed lines represent the removed laser generators and beams. The arrow is the escaping route.
题意：
- 在一个坐标系中已知 n 个点（1e6），任意两点间有一条线。
- 从（0，0）出发，想到（inf，inf）去，不能穿过任何线或者点（走间隙通过）。
- 问最少删除几个点才能到（inf，inf）。
思路：
- 想要逃出去，所有点都需要在从原点引出的贯穿原点的直线的同一侧， 所以我们需要将一个方向的半圆点都删除之后，才可以逃出去。
- 我们先极角排序（用atan2l计算long double的极角， 即按照点到原点的角度排序），
然后将n个点拓展为2n个点（绕原点转圈，第二圈的第一象限的角度比第一圈第四象限的大，第一圈的第一象限的角比第一圈的第四象限的小。我们把每个点，都生成一个位于第二圈的该点，使得这个点可以比后面的一些点大） - 然后双指针维护直线（半圆）一边的点的个数，最后取个min。
#include<bits/stdc++.h>
using namespace std;
typedef long double LD;
const LD pi = acosl(-1);
const int N = 2e6+10;
LD a[N];
void solve(){
int n; cin>>n;
for(int i = 1; i <= n; i++){
LD x, y; cin>>x>>y;
a[i] = atan2l(y,x);
}
sort(a+1, a+n+1);
for(int i = 1; i <= n; i++)a[i+n] = a[i]+2*pi;
int res = n;
for(int i = 1, j = 1; i <= n; i++){
while(j<=2*n && a[j]-a[i]<pi)j++;
res = min(res, j-i-1);
}
cout<<res<<"\n";
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T=1; cin>>T;
while(T--){
solve();
}
return 0;
}
