NOIP2023 Simulation 4 Joint Test 25 B. Polygon
Article directory
- NOIP2023 Simulation 4 Joint Test 25 B. Polygon
-
- The general idea of the topic
- Ideas
- code
The main idea of the title
Give you a positive
n
n
n-sided polygon, each point has three colors, red, blue, and green. Now you want to connect
n
?
3
n-3
n? 3 diagonals, such that these diagonals divide the entire figure into
n
?
2
n-2
There are n?2 triangles, and the colors of the three vertices of each triangle are different.
Ensure that each color appears at least once and
n
n
Two adjacent points on an n-gon have different colors.
Output any edge-connected solution.
4
≤
n
≤
1
0
6
4\le n\le 10^6
4≤n≤106
Ideas
Obviously, the answer is no
I
m
p
o
s
s
s
i
b
l
e
!
Impossible!
Impossible!
If a color only appears once, just connect this point to all other points except adjacent points.
Otherwise, first find three adjacent points with different colors
Let these three points be
l
,
x
,
r
l , x , r
l,x,r,
l
l
The left side of l is
l
l
ll
ll,
r
r
The right side of r is
r
r
rr
rr
every operation.
if
l
l
=
=
r
r
ll == rr
ll==rr, connect the edges
(
l
,
r
)
(l , r)
(l,r) and exit.
if
s
[
l
l
]
=
=
s
[
x
]
s[ll] == s[x]
s[ll]==s[x] , even the edges
(
l
,
r
)
(l , r)
(l,r)
Otherwise if
s
[
r
r
]
=
=
s
[
x
]
s[rr] == s[x]
s[rr]==s[x] , even the edges
(
l
,
r
)
(l , r)
(l,r)
Otherwise connect the edges
(
l
l
,
x
)
,
(
x
,
r
r
)
(ll , x) , (x , rr)
(ll,x),(x,rr)
Then update the number and continue working on it
code
#include <bits/stdc + + .h>
#define fu(x , y , z) for(int x = y ; x <= z ; x + + )
using namespace std;
const int N = 1e6 + 5;
int n , ans1 , ans[N][5] , flg[5] , flg1[5];
char s[N];
int lst (int x) {<!-- --> return x == 1 ? n : x - 1; }
int nxt (int x) {<!-- --> return x == n ? 1 : x + 1; }
int main () {<!-- -->
freopen ("polygon.in" , "r" , stdin);
freopen ("polygon.out" , "w" , stdout);
scanf ("%d" , & amp;n);
scanf ("%s" , s + 1);
int x;
fu (i , 1 , n) {<!-- -->
if (s[i] == 'B') x = 1;
else if (s[i] == 'R') x = 2;
else x = 3;
flg[x] + + ;
flg1[x] = i;
}
fu (i , 1 , 3) {<!-- -->
if (flg[i] == 1) {<!-- -->
fu (j , 1 , n) {<!-- -->
if (flg1[i] == j || nxt(flg1[i]) == j || lst(flg1[i]) == j) continue;
printf ("%d %d\\
" , flg1[i] , j);
}
exit (0);
}
}
int l , r , ll , rr;
fu (i , 1 , n)
if (s[lst(i)] != s[nxt(i)] & amp; & amp; s[i] != s[lst(i)] & amp; & amp; s[i] != s [nxt(i)]) {<!-- -->
x = i;
break;
}
l = lst(x) , r = nxt(x);
while (1) {<!-- -->
ll = lst(l) , rr = nxt(r);
if (ll == rr) {<!-- -->
if (s[ll] == s[x]) {<!-- -->
ans[ + + ans1][1] = l;
ans[ans1][2] = r;
break;
}
else {<!-- -->
printf ("Impossible!");
exit(0);
}
}
if (lst(rr) == ll)
break;
if (s[ll] == s[x]) {<!-- -->
ans[ + + ans1][1] = l;
ans[ans1][2] = r;
x = l;
l = ll;
}
else if (s[rr] == s[x]) {<!-- -->
ans[ + + ans1][1] = l;
ans[ans1][2] = r;
x = r;
r = rr;
}
else {<!-- -->
ans[ + + ans1][1] = ll;
ans[ans1][2] = x;
ans[ + + ans1][1] = x;
ans[ans1][2] = rr;
l = ll;
r = rr;
}
}
fu (i , 1 , ans1) {<!-- -->
printf ("%d %d\\
" , ans[i][1] , ans[i][2]);
}
return 0;
}