P9741 「KDOI-06-J」翻转与反转题解

· · 题解

前言

打比赛的时侯手动模拟了一下，发现了一个能 AC 的规律，于是想发篇题解

前置芝士：list

list 是 c++ 的双向链表，使用如下。

list<int>my_list;//定义一个空list
bool e=my_list.empty()//返回list是否为空
int s=my_list.size()//返回list的长度
my_list.push_front(114514)//在链表前面插入114514
my_list.push_back(1919810)//在链表后面插入1919810
int f=my_list.front()//返回链表最前面的数
int b=my_list.back()//返回链表最后面的数
my_list.pop_front()//删除链表最前面的数
my_list.pop_back()//删除链表最后面的数

思路

看图：

我们可以发现如果 i \bmod 2 = n \bmod 2 那我们要把 \lnot a_i 插入到链表的前面；否则我们要把 a_i 插入到链表的后面。得出了结论就开始写代码吧。

code

#include<bits/stdc++.h>
using namespace std;
int n,a[2000001];
list<int>l;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(n%2==i%2)
            l.push_front(!a[i]);
        else
            l.push_back(a[i]);
    }
    while(!l.empty()){
        printf("%d ",l.front());
        l.pop_front();
    }
    return 0;
}