当前位置: 代码迷 >> 综合 >> CF1559C Mocha and Hiking(图,思维,构造)
  详细解决方案

CF1559C Mocha and Hiking(图,思维,构造)

热度:120   发布时间:2023-10-13 23:53:41.0

原题链接

题意

输入一个数 nnn ,代表有 n+1n + 1n+1 个点,然后 1?(n?1)1 - (n - 1)1?(n?1),每个点都有一条边连向自己后面那条边。

然后对于点 1?n1 - n1?n,到点 n+1n + 1n+1, 有 nnn 个数

  • 如果 ai==0a_i == 0ai?==0 ,代表有一条边从 iii 连向 n+1n + 1n+1
  • 如果 ai==1a_i == 1ai?==1 ,代表有一条边从 n+1n + 1n+1 连向 iii

思路

  1. 第一种情况如果 a1==1a_1 == 1a1?==1,输出 n+1n + 1n+11?n1 - n1?n
  2. 第一种情况如果 an==0a_n == 0an?==0,输出 1?n1 - n1?nn+1n + 1n+1

CF1559C Mocha and Hiking(图,思维,构造)

  1. 第三种情况只要有 连续的 两个数 是 01,那么也肯定有解
    CF1559C Mocha and Hiking(图,思维,构造)

可以总结出:一定有解

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t; cin >> t;while (t -- ){
    int n; cin >> n;int a[n + 10];for (int i = 1; i <= n; i ++ ){
    cin >> a[i];}if (a[1] == 1){
    cout << n + 1 << " ";for (int i = 1; i <= n; i ++ ) {
    cout << i << " ";}cout << endl;continue;}if (a[n] == 0){
    for (int i = 1; i <= n; i ++ ) {
    cout << i << " ";}cout << n + 1 << " ";cout << endl;continue;}bool f = 0;for (int i = 1; i <= n; i ++ ){
    cout << i << " ";if (a[i] == 0 && a[i + 1] == 1 && f == 0){
    cout << n + 1 << " ";f = 1;}}cout << endl;}return 0;
}

总结

画画图就可以推出规律啦!